【面】用射线法判断点是否在多边形区域内部

更新于
射线法是用被测点向任意方向（通常为了好算，使其射向右侧）做一条射线，判断射线与多边形的交点。如果交点的数量为奇数，则被测点在多边形内；如果交点的数量为偶数，则被测点在多边形以外。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class isPointinPolygon:
    def getPolygonBounds(self, polygon):
        # 求多边形的外包矩形
        lonlist = []
        latlist = []
        for i in range(len(polygon)-1):
            lonlist.append(polygon[i][0])
            latlist.append(polygon[i][1])
        maxlon = max(lonlist)
        minlon = min(lonlist)
        maxlat = max(latlist)
        minlat = min(latlist)
        return maxlon, minlon, maxlat, minlat

    def isPointInRect(self, point, rect):
        # 判断目标点是否在多边形的外包矩形内
        maxlon = rect[0]
        minlon = rect[1]
        maxlat = rect[2]
        minlat = rect[3]
        if (point[0] > maxlon or point[0] < minlon or point[1] > maxlat or point[1] < minlat):
            return False
        else:
            return True

    def main(self, point, polygon):
        rect = self.getPolygonBounds(polygon)
        if not self.isPointInRect(point, rect):
            return False
        else:
            count = 0
            point1 = polygon[0]
            for i in range(1, len(polygon)):
                point2 = polygon[i]
                # 点与多边形顶点重合
                if (point[0] == point1[0] and point[1] == point1[1]) or (point[0] == point2[0] and point[1] == point2[1]):
                    # print("在顶点上")
                    return False
                # 判断线段两端点是否在射线两侧 不在肯定不相交 射线(-∞,lat)(lon,lat)
                if (point1[1] < point[1] and point2[1] >= point[1]) or (point1[1] >= point[1] and point2[1] < point[1]):
                    # 求线段与射线交点 再和lat比较
                    point12lon = point2[0] - (point2[1] - point[1]) * (point2[0] - point1[0])/(point2[1] - point1[1])
                    # print(point12lon)
                    # 点在多边形边上
                    if (point12lon == point[0]):
                        # print("点在多边形边上")
                        return False
                    if (point12lon < point[0]):
                        count +=1
                point1 = point2
            # print(count)
            if count%2 == 0:
                return False
            else:
                return True
    
if __name__ == '__main__':
    func = isPointinPolygon()

    print(func.main([0.8,0.8], [[0,0],[1,1],[0,1],[0,0]]))
    print(func.main([0.8,0.8], [[0,0],[2,1],[0,1],[0,0]]))
0%