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

对于每对相邻顶点 A,B：

1. 构造一个从 A 到 B 的向量，称之为 p

2. 现在构造一个从 A 到测试点 X 的向量，称之为 q

3. 一对向量的点积公式为 pq = |p||q|cosC，其中 C 是向量之间的角度。

4. 所以如果 pq/|p||q| == 1 则点 AX 和 AB 共线。在计算机上工作，您需要 1 - pq/|p||q| < some_small_value 取决于您想要的准确程度。

5. 还需要检查 |q| <|p| （即X比B更接近A）

如果 4 和 5 为真，则您的点位于边界上。

编辑

我认为我见过的另一种方法是采用测试点 X，并构建一条穿过 X 垂直于 A 和 B 之间的线的线。找到这条线与线 A->B 交叉的位置。计算出从 X 到该交叉点的距离，如果该距离足够小，则认为该点位于线上。

编辑——有趣的小练习！

由于我记错了一些数学，之前发布了一些错误的代码。在回家的火车上玩了一下 Pythonista，并想出了这个似乎基本上可行的方法。由于在 iPad 上编辑帖子非常痛苦，因此忽略了数学证明！

没有进行太多测试，没有对除零等进行测试，警告用户。

    # we determine the point of intersection X between
    # the line between A and B and a line through T
    # that is perpendicular to the line AB (can't draw perpendicular
    # in ascii, you'll have to imagine that angle between AB and XT is 90
    # degrees.
    #
    #       B
    #      /
    #.    X  
    #    / \
    #   /   T
    #  A
    # once we know X we can work out the closest the line AB
    # comes to T, if that distance is 0 (or small enough)
    # we can consider T to be on the line
    import math


    # work out where the line through test point t
    # that is perpendicular to ab crosses ab
    #
    # inputs must be 2-tuples or 2-element lists of floats (x,y)
    # returns (x,y) of point of intersection
    def intersection_of_perpendicular(a,b,t):

    if a[0] == b[0]:
            return (a[0],t[1])

    if a[1] == b[1]:
            return (t[0],a[1])

    m = (a[1] - b[1])/(a[0] - b[0]) #slope of ab

    x_inter = (t[1] - a[1] + m*a[0] + (1/m)*t[0])*m/(m**2 + 1)
    y_inter = m*(x_inter - a[0]) + a[1]
    y_inter2 = -(1/m)*(x_inter - t[0]) + t[1]

    #print '...computed ',m,(x_inter, y_inter), y_inter2
    return (x_inter, y_inter)

    # basic Pythagorean formula for distance between two points
    def distance(a,b):
        return math.sqrt( (a[0]-b[0])**2 + (a[1]-b[1])**2 )

    # check if a point is within the box defined by a,b at
    # diagonally opposite corners
    def point_in_box(a,b,t):
        xmin = min(a[0],b[0])
        xmax = max(a[0],b[0])
        ymin = min(a[1],b[1])
        ymax = max(a[1],b[1])

        x_in_bounds = True
        if xmax != xmin:
            x_in_bounds = xmin <= t[0] <= xmax
        y_in_bounds = True
        if ymax != ymin:
            y_in_bounds = ymin <= t[1] <= ymax
        return x_in_bounds and y_in_bounds

    # determine if point t is within 'tolerance' distance
    # of the line between a and b
    # returns Boolean
    def is_on_line_between(a,b,t,tolerance=0.01):
        intersect = intersection_of_perpendicular(a,b,t)
        dist = distance(intersect, t)
        in_bounds = point_in_box(a,b,t)
        return in_bounds and (dist < tolerance)


a = (0,0)
b = (2,2)
t = (0,2)

p = intersection_of_perpendicular(a,b,t)
bounded = point_in_box(a,b,t)
print 'd ',distance(p,t), ' p ',p, bounded

a = (0,2)
b = (2,2)
t = (1,3)

p = intersection_of_perpendicular(a,b,t)
bounded = point_in_box(a,b,t)
print 'd ',distance(p,t),' p ',p, bounded

a = (0.0,2.0)
b = (2.0,7.0)
t = (1.7,6.5)

p = intersection_of_perpendicular(a,b,t)
bounded = point_in_box(a,b,t)
on = is_on_line_between(a,b,t,0.2)
print 'd ',distance(p,t),' p ',p, bounded,on