闭合轮廓的绕数算法

Question

假设我有一个由两个函数 x(p) 和 y(p) 定义的轮廓形状，其中 p 是距离沿着形状的周边移动，在 0 和 1 之间归一化。例如，关于原点的单位圆将定义为 x(p) = sin(2 * pi * p) 和 y(p) = cos(2 * pi * p) 。

确定一个点是否在该圆内的一个简单测试是计算该点与原点的距离，然后检测该距离是否小于或等于 1。

但是，如果我的形状有多个交叉点，并且比圆形复杂得多怎么办？

存在一个point in polygon测试由一组点定义的离散形状。这个算法很容易找到，因为它被用在很多地方。但是，如果我不想使用形状的离散定义，我可以使用什么算法来确定绕组数，假设形状是在编译时定义的？

Answer 1

推广多边形测试中的点，您可以找到y(p)=0 的所有解决方案，使得x(p)>0 并使用它们的奇偶校验数。

在圆的情况下，cos(2πp)=0 for p=(k+1/2)π，只有一个值[0,1) 范围内的 p 使 sin(2πp)>0。

到目前为止，如果您可以解析地求解 y 方程，那就太好了。否则，您将需要一个可靠的数值求解器，能够找出所有的根。另一种方法是使曲线变平(将其绘制为多段线，确保最大偏差容差)，然后应用多边形算法。

---

为了第二个例子，让我们用等式 r = 0.5 + cos Θ 和沿 X 的一些测试点来考虑 Pascal 的 limaçon。

y = (0.5 + cos Θ) sin Θ = 0

Θ=0、2π/3、π、4π/3。对应的横坐标为1.5、0、0.5和0。

您可以得出结论，X 轴上的内部点在 0.5 和 1.5 之间(也在 0 处，以退化的方式) .