2016-06-30 60 views
1

將約束插入約束Delaunay三角剖分的步驟之一是通過去除與約束相交的三角形來重新調整空腔。在約束Delaunay三角剖分中約束插入

在下圖中,約束u(A-F)被插入到三角剖分中,並且它與三角形以藍色相交。所以藍色區域被重新調整。 Triangles in blue are to be removed from the triangulation

這意味着藍色的三角形將從三角形中移除,並且將添加新的三角形以填充刪除這些三角形時留下的孔。只有這些新的三角形將有邊緣AF(這是約束U) Triangles in green are the new triangles after inserting constraint u.

假設三角是插入約束U(除其他約束邊)之前德勞內,並在綠色的三角形是德勞內本身(不綠色多邊形的頂點在任何其他綠色三角形的圓內),是否需要在連接綠色三角形到紅色三角形的邊上檢查/執行邊緣翻轉?還是有某種保證不會發生邊緣翻轉的禮節?

換句話說,空腔外的頂點是否有可能成爲新三角形的一個圓? (請注意,此頂點以前不在其他任何圈內,因爲它之前是delaunay)。或者放在一個簡單的方法,是否需要檢查/執行重新調整後的邊緣翻轉腔邊緣?用於CDT

參考紙:https://infoscience.epfl.ch/record/100269/files/Kallmann_and_al_Geometric_Modeling_03

請注意,這些照片是用手工和GeoGebra不是實際的三角代碼所做的,這意味着在圖片中的三角形可以不看德勞內。此外,圖片只顯示了部分三角測量的視覺示例目的。

+0

關於您關於GeoGebra的筆記的評論。使用[ipe](http://ipe.otfried.org/)和CGAL-Ipelets(http://doc.cgal.org/latest/CGAL_ipelets/index.html#title3)可以讓您製作CDT圖片。 – sloriot

回答

0

我不這麼認爲。邊緣切割僅依賴於cw或ccw的排序點。

0

運行一些測試後,它看起來像三角測量可能會失去該操作後的delaunay正當性,所以邊緣需要翻轉。

我還沒有在任何文章中看過這篇文章,也沒有在任何代碼中看到過,所以我很懷疑我仍然可能是錯的。