欢迎访问我的网站,希望内容对您有用,感兴趣的可以加入我们的社群。

Python实现判定平面中的点是否在多边形的内部?

Python 迷途小书童 2年前 (2022-05-31) 1552次浏览 2个评论

环境

  • python 3.8

前言

在目标跟踪时,时常需要确定目标是否在某一区域内出现,这个问题的本质就是去判断,平面中的点是否在多边形的内部。

光线投射法

下面这张图来自维基百科,阐述了光线投射法(Ray-casting Algorithm)的基本原理

python

通常从待测试点出发画一条射线,可以是任意方向,然后计算直线与区域边界相交的次数,如果次数为奇数,则认为待测试点在区域内,如果是偶数,则认为待测试点在区域的外部。

代码实践

直接看代码吧

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))

参考资料

喜欢 (0)

您必须 登录 才能发表评论!

(2)个小伙伴在吐槽
  1. 应该是画一条射线
    匿名2022-07-20 17:46