奇偶算法如何计算多边形边数？

Question

我想知道奇偶算法如何识别复杂多边形中的点。

我现在知道的是，它会从最左边到该点进行水平搜索，并计算触摸的边缘数量。

但是，如果接触的边位于 2 条边的交集中，会发生什么情况？它是怎么算的？

多边形示例：

Answer 1

我喜欢的方法（适用于整数和浮点坐标）是：

• 对于非水平线段，每个线段包括其最底部的点，但不包括其最顶部的点。

• 根本不将水平线段包含在奇偶计数中。

这确保了多边形内部和外部的每个点的偶数和奇数计数都是正确的，但对于边界上的点并不完全一致。 如果这对您很重要，您可能需要添加一条规则，即实际位于线段上的任何点都包含在多边形中。

Answer 2

有很多方法可以解决这个问题，但我所知道的最安全的方法是

稍微改变光线方向

这在数字上是安全的，但实施起来并不像听起来那么容易。要么更改整个光线并从头开始计算，要么在有问题的命中之前更改某处。

您需要确保不会形成闭合环路，例如通过之字形图案（因此您可以在原始方向的某个圆锥体内交替旋转 CW 和 CCW）。

如果光线完全平行于并接触多边形的边缘，请忽略该边缘或计算两次或再次更改光线方向。

改变光线方向总是安全的，因为它可以避免奇点和数值不稳定。

顺便说一句。您使用的这种内部多边形算法的名称是众所周知的 Hit test

Answer 3

我们必须查看在该顶点相交的多边形的两条线段的另一端点。如果这些点位于构造线的同一侧（图片上的第一个选项），则交点算作偶数个交点。但是，如果它们位于构造线的另一侧（图片上有 2 个选项。），则交点算作单个交点。