在搜索多边形测试时,我发现了Dean Povey here所描述的测试。我喜欢这种方法,因为它很容易理解(沿x轴的光线投射),但是我遇到了与该方法的微小矛盾之处。在为实现编写单元测试时,我注意到以正方形作为“测试多边形”时,正方形左侧和底部边缘的点被识别为多边形的一部分,而多边形右侧和顶部的点则被识别为多边形的一部分。被识别为多边形外部。这是一张小图,显示了我的意思(+未被识别为内部,双倍线和x为):
+--------+
‖ |
‖ |
x========+
有谁知道我可以如何更改算法以显示边缘点的一致行为?边缘是否视为内部并不重要,只是行为是一致的。
最佳答案
要测试点P
是否位于边线QR
上,请考虑将Q
映射到原点并将R
映射到点(0, 1)
的转换。
使用复数,将此转换写为Z = (z - Q) / (R - Q)
并用P
转换(P - Q) / (R - Q)
。该数字必须是纯实数,并且其实数部分在[0, 1]
中。
您可以使用此测试来检测轮廓上的点。通过允许虚部很小,也可以允许公差。在这种情况下,建议对分母R - Q
进行归一化,以使虚部成为到该段的欧几里得距离。