光线投射点多边形线对齐边缘

我尝试使用下面的代码为Even-Odd Rule from Wikipedia 光线投射点多边形线对齐边缘

# x, y -- x and y coordinates of point 
# poly -- a list of tuples [(x, y), (x, y), ...] 
def isPointInPath(x, y, poly): 
     num = len(poly) 
     i = 0 
     j = num - 1 
     c = False 
     for i in range(num): 
       if ((poly[i][1] > y) != (poly[j][1] > y)) and \ 
         (x < (poly[j][0] - poly[i][0]) * (y - poly[i][1])/(poly[j][1] - poly[i][1]) + poly[i][0]): 
        c = not c 
       j = i 
     return c

Unfortuantely，它给我的简单直线多边形错误的结果时，我的测试点对齐水平边缘

 ----- 
    | | 
    | x ----| 
    x |--------|

治疗水平边缘作为边缘之一使得视为内两个点而忽略了水平边缘使得视为外

两个点210

那么我怎样才能使这种多边形的奇数规则工作？或建议替代算法？

来源

2017-01-06 Woofas

与不是轴对准的光线相交（例如，射线在45度。 – Ante

这是否意味着奇数规则（或任何光线投射算法）对于边缘与光线投射方向平行的多边形不起作用？这是一个主要限制，不是吗？ – Woofas

它可以更好地处理光线边缘重叠。如果光线与边缘重叠，则需要检查与边缘邻居（前一个和下一个边缘）的交集。类似的，将光线方向上的下一个边移动到前一个边，并检查光线是否与相连的边相交或仅触摸一个点。如果您绘制射线与相连的边相交。如果几何形状为U形（在右侧添加一个部件），则射线只会触及连接的边。 – Ante

从here采取以下规则似乎工作

沿交叉规则

向上的边缘包括它的起始端点，并排除其最终的终点;

下边缘排除其起始端点，并包括其最终端点;

水平边缘被排除

边缘射线相交点必须严格右侧的点P.

注意的是，上述的规则按照惯例

一个点左边或底边是内侧，右边或上边的点是外侧。这样，如果两个不同的多边形共享一个共同的边界线段，那么该线段上的一个点将位于一个多边形或另一个多边形中，但不是同时存在。

此外，作者指出，此方法仅适用于简单（非自相交）多边形。它还建议使用有效实现的卷绕号码，以更好地处理非简单多边形

来源

2017-01-09 03:13:59 Woofas

光线投射点多边形线对齐边缘

回答

相关问题