java - 简单的多边形点测试，边缘行为一致

Question

在搜索多边形点测试时，我在这里找到了 Dean Povey 所描述的测试。我喜欢这种方法，因为它很容易理解（沿 x 轴的光线投射），但我遇到了与该方法的小不一致。在为我的实现编写单元测试时，我注意到当将正方形作为“测试多边形”时，正方形左侧和底部边缘的点被识别为多边形的一部分，而多边形右侧和顶部的点被识别为多边形之外。这是一张小图，显示了我的意思（+ 不被识别为内部，双线和 x 是）：

+--------+
‖        |
‖        |
x========+

有谁知道我如何更改算法以显示边缘点的一致行为？边缘是否被认为是内部并不重要，只是行为是一致的。

标签： javaandroidgeometrycomputational-geometry

Answer 1

要测试点是否P位于边上QR，请考虑映射Q到原点和R点的变换(0, 1)。

使用复数，将此转换写为Z = (z - Q) / (R - Q)并转换P为(P - Q) / (R - Q)。这个数字必须是纯实数，它的实部在[0, 1].

您可以使用此测试来检测轮廓上的点。也可以通过允许虚部为小数来允许公差。在这种情况下，建议对分母进行归一化R - Q，使虚部变为到线段的欧几里得距离。