点随机形状多边形？

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

投射光线，并计算光线穿过多边形的次数。 （如果边缘完全沿着光线，这会变得烦人和容易出错。）如果它是奇数，则该点位于多边形中。否则，它不是。

Answer 2

其实，如果你使用 非零匝数规则，而不是常见的奇偶规则的光线投射方法会奏效。

这就是它在Adobe的后记语言参考（其中“路径”一词表示定义多边形的多边形顶点列表）中的解释方式。

非零绕数规则确定一个给定的点是否是 路径内通过以任何方向概念性地描绘从该点的射线，以 无穷大，并且随后检查一 段的路径穿过射线的地点。从0开始计算， 规则每当路径段从左到右穿过 右侧时加1​​，每当段从右到左交叉时减1。 计算完所有交叉点后，如果结果为0，则该点在路径外部为 ;否则它在里面。