给定一个多边形和一个二维点，如何找到最接近该点的多边形的特征（顶点或边）？
一种简单的方法是，对于多边形中的每条边，找到该边上最接近给定点的点，然后选取最接近的点。有没有更快的算法？我的目标是实现一款 2D 《超级马里奥银河》风格的平台游戏。
显然，这可以通过 Voronoi 区域来完成，如本视频所示：http://www.youtube.com /watch?v=Ldh2YKobuWo
但是，我找不到任何处理边缘和点的 Voronoi 算法。有想法吗？
A naive approach is to find, for each edge in the polygon, the point on that edge closest to the given point, and then take the one that's closest. Is there a faster algorithm? My goal is to implement a 2D Super Mario Galaxy-style platformer.
Apparently this can be done with Voronoi regions, as in this video: http://www.youtube.com/watch?v=Ldh2YKobuWo
However, I can't find any Voronoi algorithms that deal with edges as well as points. Ideas?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
计算每条边的点线距离，然后选择最短的一条。没有捷径。 这个网站有很好的解释，甚至有多种语言的实现。
然而，找到“最接近给定点的边缘上的点”在计算上是不必要的中间结果。
Calculate the point-line distance for each of the edges, then pick the shortest one. There is no shortcut. This site has a good explanation and even implementations in various languages.
However, finding "the point on that edge closest to the given point" is a computationally unnecessary intermediate result.
如果多边形是凸的，那么 voronoi 计算的开销远远超过朴素方法的开销。
如果运行多次，并且每次点发生轻微变化，您只需要检查 3 个线段（想一想：当您四处移动时，假设多次检查，那么最近的边只会更改为相邻的边）
If the polygon is convex, then the overhead of the voronoi calculation far exceeds that of the naive approach.
If this is run many times, and each time the point changes slightly, you only need to check 3 segments (think about it: as you move around, assuming many checks, then the closest edge will only change to an adjacent edge)