Bowyer-Watson算法：如何用超三角形頂點去除三角形來填充「孔」

Question

我正在實現如Wikipedia所示的Bowyer-Watson算法。在我的實現，一切都按我所期望的，直到僞代碼的最後一部分：

for each triangle in triangulation // done inserting points, now clean up 
    if triangle contains a vertex from original super-triangle 
     remove triangle from triangulation 

如果我按照這裏的僞代碼從字面上看，我可以在我的Delaunay三角失蹤三角形結束。

舉一個例子，請考慮下面的圖片。我正在進行三角測量的網站呈現爲藍色圓圈。三角形以黑色線條（不包括圖像邊框）和連接網站或邊界/超級三角形頂點呈現。外接圓呈灰色，中心呈紅圈。 Voronoi單元每個都塗上不同的顏色（希望）會使問題更加明顯。

該圖顯示了在執行上面僞代碼中列出的步驟之前的三角測量的狀態。請注意，超三角形的兩個頂點超出了圖像的右側和底部。

此圖像顯示去除包含超級三角形頂點不經任何進一步的考慮任何三角形之後的步驟：

頂部三個頂點應該有一個外心在一個新的三角形綠色/褐色細胞相遇的地方。問題在於，「之前」圖像中顯示的角點在該外接圓內，因此算法的常規處理從未生成該三角形。

如何以僞代碼表示此邊緣案例，以便我可以檢查並解決它？我想避免一些可怕的「嘗試每個組合的網站共享一個三角形的超級三角形頂點有效circumcircle」循環。

幾年前，我讀了Bowyer和Watson的論文，如果有必要，我會再次閱讀他們的答案。我希望（1）其他人可能有答案，並且（2）如果我再次遇到這個問題，我可以使用Stack Overflow來查找答案。

---

編輯

所以我已經找到了相對便宜，但不完美的變通。我的超級三角形以編程方式確定爲圍繞網站的邊框而不與其兩側相交。這個想法是由Java的各種令人沮喪的問題引起的，這些問題考慮了我的一些計算的外心座標或座標之間的距離是無限的。這種謹慎讓我的超級三角形變得如此之小，以至於它的頂點有時會落在有效的三角形的外心中。增加超三角形的大小使問題似乎消失。但是，凸包上的三角形可能非常鈍，以致其中一個頂點仍然可能落入有效的外接圓內。

我認爲這意味着我最初的問題在面對浮點數限制時仍然有效。有沒有廉價的方法來保證Bowyer-Watson算法生成有效的三角剖分？

Answer 1

看來你有解決你的問題的方法，但是也可以檢查三角形的外接中心是否在超級角之外。您可以使用多邊形測試。也許它可以保證沒有缺失的三角形。

Answer 2

我在實現這裏描述的Bowyer-Watson算法時遇到了同樣的問題：http://paulbourke.net/papers/triangulate/。我在互聯網上找不到任何有用的東西，甚至在我的大學裏詢問，但沒有結果。過了一段時間，我想出了一個解決方案。 我從發現問題消失開始，邊界三角形的頂點應該理想地位於無窮遠處，這是不實際的。那麼如果三角形在無窮遠處有一個或兩個頂點，那麼三角形外接圓的外觀是什麼？這只是通過其他要點。因此，如果點位於三角形的外接環上，則測試點位於左邊還是右邊。

算法則是這樣的：

1. 檢查是否有三角形的頂點位於在無窮遠處。換句話說：檢查三角形是否與邊界三角形共享某些頂點。

2. 如果它共享所有三個頂點：平凡。

3. 如果它共享零頂點：經典方法 - 檢查點與外部中心的距離是否短於環形半徑。

4. 如果它共享一個頂點：檢查點是否位於由其他兩個頂點定義的線的左側/右側。 one vertex in infinity

5. 如果它共享兩個頂點：檢查點是否位於由這兩個頂點定義的線的左側/右側，但是移動到第三個點。換句話說，您只需從這些共享頂點之間的線上獲取斜率矢量，並對其進行移位，以使該線穿過第三個點。 two vertices in infinity

測試點位於線的左側還是右側取決於三角形的纏繞順序。