我正在編寫一個程序，需要實施中軸抽取，其中Delaunay三角測量是一個步驟。外部中軸是不需要的，因此相應的外部三角形將被刪除。幸運的是，我用a page帶來了很多圖表，也提供了一種確定內部和外部Delaunay三角形（「基於虛線周長」）的方法，但這只是一個提示，沒有詳細解釋。任何人都知道算法？如何確定Delaunay三角形是內部還是外部？
編輯：我忘了提及初始點是從封閉多邊形的邊界採樣，我的意圖是確定每個Delaunay三角形是否在多邊形內。
該解決方案假定您有表示使用「虛擬無限德洛奈頂點」的方式CGAL做它（see details here）的Delaunay三角剖分的數據結構。
這個想法是找到邊界Delaunay邊：連接兩個連續採樣點的邊;然後通過Delaunay三角剖分「氾濫」，對Delaunay面孔進行分類。人們知道無限頂點是外部的，因此只要不跨越邊界邊界，就可以將它的鄰居（和鄰居的鄰居等）分類爲外部。如果到達邊界邊緣，可以簡單地將相鄰三角形標記爲內部並且繼續相似。
輸入：設定點的閉合的形狀的邊界，這甚至可以包含孔
輸出的密集採樣：在形狀的內部Voronoi圖（形狀的中軸的近似）
對於這樣
以下中軸近似的輸入，可以計算： 
這正是我想要的，謝謝。 – btw0 2009-06-24 09:23:56
也許我在這裏做了太多的假設，但它聽起來像是你有一個由一堆點組成的多邊形，並且你正在對這些點進行三角化。然後你想丟棄掉多邊形以外的所有三角形，對吧？
爲什麼不只是三角形多邊形（使用單調分解或類似的東西），以便您永遠不會創建任何外部三角形？我想這可能會增加運行時間（首先在O（nlogn）時間內進行三角測量，然後在O（n^2）時間內創建一個delaunay三角測量），但是可能會有更快的方法。
您是否考慮過使用不會創建外部三角形的不同形式的三角形？我曾經花了很多時間討論多邊形三角測量的理論方面。也許瀏覽課程網站會給你一些見解？ http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html#triangulation
編輯：其實，我只是想到別的。如果你已經有了想要三角化的多邊形，你可以使用格林定理。格林定理使用多邊形的周長來計算其面積！更重要的是，在這種情況下，您可以通過查看區域的符號來確定某個點是位於一條線的哪一側。在多邊形上，格林定理解決了一個簡單的減法問題。因此，請記住您知道的任何一點在多邊形內，並根據多邊形的每個邊計算面積。這告訴你每一行的哪一邊你的觀點需要成爲。現在簡單地在每個三角形內取一個點並做同樣的事情。如果任何標誌錯誤，那麼你有一個外部三角形。 （注意：根據你的多邊形的形狀，這可能實際上不起作用，它應該適用於凸多邊形，但凹面可能會引入其他併發症。）
它們呈現的算法看起來有點破碎，因爲他們在其中一個數字中顯示，這可能是Google Scholar中似乎沒有任何有用的引用的原因。
您的意思是這些點位於多邊形的邊界上，還是這些點是由多邊形限定的（但不一定是）？ 無論哪種方式，你現在不會碰到三角形可能與多邊形的邊界重疊的問題嗎（使其成爲內部和外部的邊界）？ 忽略這種情況（現在），假設我們已經對多邊形進行了梯形分解，我們可以使用點位置在O（t * nlogn）中查找完全內部和完全外部的三角形。 檢查重疊會導致初始方法的O（t * n）運行時間。 雖然可能有更好的方法。 – 2009-06-15 19:32:13