surroundings
- python 3.8
foreword
During target tracking, it is often necessary to determine whether the target appears in a certain area. The essence of this problem is to determine whether the point in the plane is inside the polygon.
ray casting
The following picture is from Wikipedia and illustrates the basic principle of Ray-casting Algorithm
Usually, a straight line is drawn from the point to be tested, which can be in any direction, and then the number of times the line intersects the boundary of the area is calculated. If the number of times is an odd number, the point to be tested is considered to be in the area, and if it is an even number, the point to be tested is considered to be in the area. the exterior.
Code Practice
Just look at the code
def is_in_polygon(p, polygon): """ :param p: [x, y] :param polygon: [[], [], [], [], ...] :return: """ px, py = p is_in = False # 循环处理多边形的的每一条边，判断这条边是否和以待测试点向右画出的一条直线是否相交，如有相交，则结果反转一次for i, corner in enumerate(polygon): next_i = i + 1 if i + 1 < len(polygon) else 0 x1, y1 = corner x2, y2 = polygon[next_i] # 待测试点在多边形的顶点上，返回True if (x1 == px and y1 == py) or (x2 == px and y2 == py): is_in = True break if min(y1, y2) < py <= max(y1, y2): # 获取相交点的x 坐标x = x1 + (py - y1) * (x2 - x1) / (y2 - y1) # 在多边形的边上，返回True if x == px: is_in = True break # 待测试点在线的左侧，结果反转一次elif x > px: is_in = not is_in return is_in if __name__ == '__main__': point = [3, 3] polygon = [[0, 0], [7, 3], [8, 8], [5, 5]] print(is_in_polygon(point, polygon))
References
This article is reprinted from https://xugaoxiang.com/2022/05/31/python-point-is-inside-the-polygon/
This site is for inclusion only, and the copyright belongs to the original author.