随机形状多边形中的点？

Question

利用著名的光线投射算法，可以很容易地确定一个点是否在凸多边形中。在

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

但是如果多边形不是完全凸的呢？在

在给定边界点的情况下，如何确定一个点是否是一个随机形状的多边形？在

假设我有一个多边形的边界点

我该怎么做？在

最好用Python编写，但也欢迎任何通用的解决方案。在

Answer 1

实际上，如果使用 非零绕组数规则代替普通的奇偶规则。在

这是Adobe的Postscript语言参考中解释的方式（其中单词“path”表示定义多边形的多边形顶点列表）。在

The nonzero winding number rule determines whether a given point is inside a path by conceptually drawing a ray from that point to infinity in any direction and then examining the places where a segment of the path crosses the ray. Starting with a count of 0, the rule adds 1 each time a path segment crosses the ray from left to right and subtracts 1 each time a segment crosses from right to left. After counting all the crossings, if the result is 0 then the point is outside the path; otherwise it is inside.

Answer 2

投射一条光线，并计算光线穿过多边形的次数。（如果一条边正好位于光线上，这会很烦人，而且容易出错。）如果是奇数，则该点位于多边形中。否则，就不是了