如何确定点位于多边形上?

How to determine a point lies on a polygon?

我正在解决一个问题,该问题需要查明一个点是否严格位于多边形内

嗯,我知道 java awt 包,所以我可以使用这个

polygon.contains(pointToCheck)

但问题是根据官方文档 definition of insideness 给出的是

A point is considered to lie inside a Shape if and only if:

  • it lies completely inside theShape boundary or
  • it lies exactly on the Shape boundary and the space immediately adjacent to the point in the increasing X direction is entirely inside the boundary or
  • it lies exactly on a horizontal boundary segment and the space immediately adjacent to the point in the increasing Y direction is inside the boundary

那么如何删除多边形上的点数?

如果有人可以建议一个更好的算法来检查一个点是否严格位于多边形内,它也会有所帮助。

一个简单的解决方法是检查您的观点是否在轮廓上。一种方法是依次获取所有边,将其中一个端点移动到原点并旋转以将另一个点带到 X 轴上,比如 (0, L)。如果 Y = 00 ≤ X ≤ L.

那么你的观点就在边缘

那么您可以将此测试与内部测试结合起来。


注意:根据您的应用程序和坐标的数字表示方式,"on an edge" 的定义可以有不同的定义。

多边形点的 Hao 算法包括检查点是否位于边界上。 paper includes fairly understand psuedo-code if you want to write it yourself. I have written a javascript implementation here.

在 java 世界中,另一种选择可能是查看 Java Topological Suite. The PointLocator method 可能会满足您的要求。