Python:查找点是否位于多边形的边界上

Question

我有一个点 i，我想创建一个函数来知道这个点是否位于多边形的边界上。

使用:

def point_inside_polygon(x, y, poly):
    """Deciding if a point is inside (True, False otherwise) a polygon,
    where poly is a list of pairs (x,y) containing the coordinates
    of the polygon's vertices. The algorithm is called the 'Ray Casting Method'"""
    n = len(poly)
    inside = False
    p1x, p1y = poly[0]
    for i in range(n):
        p2x, p2y = poly[i % n]
        if y > min(p1y, p2y):
            if y <= max(p1y, p2y):
                if x <= max(p1x, p2x):
                    if p1y != p2y:
                        xinters = (y-p1y) * (p2x-p1x) / (p2y-p1y) + p1x
                    if p1x == p2x or x <= xinters:
                        inside = not inside
        p1x, p1y = p2x, p2y
    return inside

我只能知道这些点是否位于多边形内。

poly = [(0,0), (2,0), (2,2), (0,2)]
point_inside_polygon(1,1, poly)
True
point_inside_polygon(0,0, poly)
false
point_inside_polygon(2,0, poly)
False
point_inside_polygon(2,2, poly)
True
point_inside_polygon(0,2, poly)
True

我如何编写一个函数来查找某个点是否位于多边形的边界上？

Answer 1

将问题分解为三个步骤可能会有所帮助:

1. 编写一个可以确定if a point is on a line segment的函数.
2. 计算构成多边形边界的所有线段。
3. 如果该点位于任何一条线段上，则该点位于边界上。

这里有一些 python 代码，假设您已经为 isPointOnLineSegmentBetweenPoints 编写或找到合适的候选对象:

def pointOnPolygon(point, polygonVertices):
    n = len(polygonVertices)
    for i in range(n):
        p1 = polygonVertices[i]
        p2 = polygonVertices[-n+i+1]
        if isPointOnLineSegmentBetweenPoints(point, p1, p2):
            return true
    return false