給定一個多邊形和一個二維點，如何找到最接近該點的多邊形的特徵（頂點或邊）？

一個天真的方法是找出多邊形中每個邊的最靠近給定點的邊上的點，然後取最接近的點。有更快的算法嗎？我的目標是實現一個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

回答