多边形算法中的点，当测试点位于多边形边上时返回true

我已经实现了基于http://alienryderflex.com/polygon/的点中多边形算法。多边形算法中的点，当测试点位于多边形边上时返回true

它工作正常，但是，因为它在文章中说：

如果测试点在多边形的边界，该算法将提供不可预知的结果

原来我当测试点位于多边形的边界/边（以及顶点）时，需要算法返回true。

有两种：

另一种算法，这将帮助我。或
一种方法来修改这个算法，得到我想要的东西（例如，通过运行算法之前扩大多边形一点点）

2016-03-04 James Bateson

该算法适用于浮点数，所以通常“边上”的概念比看起来更棘手。请参阅[每个计算机科学家应了解的浮点算术知识]（https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html）和[几何学中的健壮性问题的课堂示例计算]（https://people.mpi-inf.mpg.de/~mehlhorn/ftp/classroomExamplesNonrobustness.pdf）。 –

无论如何，您可以对您关心的情况进行预检。即如果点在多边形的边的ε内，则返回true。如果你的坐标是整数，那么你甚至可以用epsilon = 0来做到这一点。但即使对于多边形之外的距离为epsilon的点，该算法也可能返回true，因为它可能适用于浮点数 –

扩大多边形位是一个选项，但是这可能会非常棘手与凹多边形。

我的建议是将点转移到不同的方向（上/下/左/右）一小部分，然后对每个这些移动点进行计算。如果至少有一个移动点被确定为内部，那么将其计为内部。

另一种选择是让交叉点的计数行在不同的方向上运行，而不仅仅是水平方向。

但是这可能不值得，因为，正如您的链接文章所述： “这通常不是一个问题，因为无论如何多边形的边缘是无限薄的，并且点落在边缘上可以不管怎样都不会影响多边形的外观。“

来源

2016-03-04 19:48:05

多边形算法中的点，当测试点位于多边形边上时返回true

回答

相关问题