多边形测试中具有光线对齐边缘的多边形的射线投射点 [英] Ray casting point in polygon test for polygon with ray-aligned edges

问题描述

我尝试将以下代码用于维基百科的偶数规则

I tried using the following code for the 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, it's giving wrong results for my simple rectilinear polygon when my test point is aligned with one of the horizontal edges

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

将水平边缘作为边缘进行处理会将两个点都视为内部，而忽略水平边缘会将两个点都视为外部

Treating a horizontal edge as an edge makes both points regarded as within while ignoring the horizontal edge makes both points regarded as outside

那么如何使奇偶规则适用于这种多边形?还是建议其他算法?

So how can I make the even-odd rule work for such a polygon? Or suggest alternative algorithms?

推荐答案

以下规则摘自此处似乎有用

交叉规则

上升沿包括其起始端点，但不包括其最终端点；

an upward edge includes its starting endpoint, and excludes its final endpoint;

下降沿不包括其起始终点，而包括其最终终点；

a downward edge excludes its starting endpoint, and includes its final endpoint;

水平边缘被排除

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

the edge-ray intersection point must be strictly right of the point P.

请注意，以上规则遵循以下约定:

Note that the above rules follow the convention that

左侧或底部边缘上的点在内部，右侧或顶部边缘上的点在外部.这样，如果两个不同的多边形共享一个公共边界线段，则该线段上的一个点将位于一个或另一个多边形中，但不能同时位于两个多边形中.

a point on a left or bottom edge is inside, and a point on a right or top edge is outside. This way, if two distinct polygons share a common boundary segment, then a point on that segment will be in one polygon or the other, but not both at the same time.

作者还指出，该方法仅适用于简单的(非自相交)多边形. 它还建议使用有效的缠绕数实现代替，这样可以更好地处理非简单多边形

Also the author notes that this method only works for simple (non-self-intersecting) polygons. It also suggests using an efficient implementation of winding numbers instead which handles non-simple polygons better

这篇关于多边形测试中具有光线对齐边缘的多边形的射线投射点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！