给定一个多边形和一个二维点，如何找到最接近该点的多边形的特征（顶点或边）？

一个天真的方法是找出多边形中每个边的最靠近给定点的边上的点，然后取最接近的点。有更快的算法吗？我的目标是实现一个2D超级马里奥银河风格的平台游戏。给定一个多边形和一个二维点，如何找到最接近该点的多边形的特征（顶点或边）？

显然，这可以与Voronoi区来完成，在这个视频：http://www.youtube.com/watch?v=Ldh2YKobuWo

但是，我无法找到与边缘以及点处理任何的Voronoi算法。想法？

2011-10-04 Jake

如果多边形是凸的，那么voronoi计算的开销远远超过朴素方法的开销。

如果这是多次运行，并且每次点稍有变化时，您只需要检查3段（考虑一下：当您四处移动时，假设进行多次检查，则最近的边将只会变为相邻边缘）

2011-10-04 20:59:46

最后一部分是不正确的。例如，如果您开始接近中间，可能会更改为多边形另一侧的线段。 –

@ Jean-FrançoisCorbett如果你在多边形的内部，那是真的。 –

幸运的是，对于我的应用程序来说，问题点永远不会在多边形内。万岁。 – Jake

计算每个边的point-line distance，然后选择最短的一个。没有捷径。 This site在各种语言中都有很好的解释和实现。

但是，找到“最接近给定点的边上的点”是一个计算上不必要的中间结果。

2011-10-04 21:00:25

回答