algorithm - 编程竞赛中的多边形算法中的点

Question

在编程竞赛中解决多边形中的点的最佳算法是什么？

score 1 · Accepted Answer

从该点射出一条射线（在任意方向上）并检查它穿过多边形边缘的次数，如果它是偶数则该点在多边形之外，否则该点在多边形内。

如果您需要对大量查询点执行此操作，则可以对多边形进行三角剖分（实际上是对多边形内部和包含它的凸面之间的区域进行三角剖分），以便您可以在 O(log n) 中进行射线拍摄

score -1 · Accepted Answer

-1

如果你有一个凸多边形，你可以使用这个：

于 2012-04-08T06:11:45.390 回答

2 回答 2