最快的孔洞三角測量算法？

我正在尋找RTS遊戲的路徑，我正在從遊戲的網格構建導航網格。最快的孔洞三角測量算法？

我已經寫了一個類似於前進方塊的算法，它可以創建並簡化地圖的可行走區域和不可行區域之間的邊界。現在我有一個只包含邊的「網格」。我需要對這個網格進行三角剖分，以便最終的三角剖分包含最初的邊緣，然後我可以移除不可走區域以在導航網格中創建孔。例如，我需要這樣做......

enter image description here

三角形表示地圖的可行走區域。這些洞代表不可行走的地區，如山脈或建築物。網格可以被認爲是2D，因爲高度是不相關的。這顯然是一個非常簡單的情況。遊戲中的導航網格將包含數千個頂點和多個孔，但我可以將其分解爲更小的塊以進行動態更新。

我已經看過約束Delaunay三角剖分算法，首先創建一個Delaunay三角網點，然後刪除相交約束邊緣的任何三角形，然後重新進行三角測量所移除的三角形。

這對於我的目的似乎有點多餘。我的網格不需要是Delaunay，它完全由受約束的邊組成，所以如果可能的話，我想跳過額外的三角網。有更好的算法嗎？我看了看，只能找到約束Delaunay算法。或者，也許我錯了，有約束的Delaunay算法會是最好的？

我已經完成了從頭開始的導航網格路徑查找，但從未必須自己生成導航網格。三角測量算法對我來說是新的。任何見解？

來源

2013-12-08 Janz Dott

由於您對三角形沒有特殊要求，所以像[多邊形三角網]（http://en.wikipedia.org/wiki/Polygon_triangulation）這樣的簡單方法比使用Delaunay更好。 – Ante

我看了一下Ear-Clipping方法，它似乎比Delaunay三角測量稍慢，但需要我按循環順序排序頂點，對不對？ –

現在我意識到你只有邊緣。在每一種情況下，您都需要連接和定位邊緣，找到某個零件位於其他零件的內部（要知道它是否爲孔），然後對具有孔的多邊形進行三角化。可以通過從孔添加2個相同的邊到多邊形邊界或其他孔來移除孔。耳廓修剪是一種簡單的方法，通過空間分割（BSP樹，四叉樹...），它比O（n^2）更快。 – Ante

Fernandez et al 2008在分解複雜域的問題上似乎接近最先進的技術。如果您正在尋找（可能更簡單）的替代方案，作者在p370的第二段列出了其他可能的算法。

來源

2013-12-09 16:50:20

最快的孔洞三角測量算法？

回答

相關問題