A.逐點插入法基本原理
逐點插入法的優勢不僅在於其理論上比較簡單，容易理解，更重要的是該方法對於點的插入是動態的、局部的，正是其局部性，所以是高效的，特別適合於可能動態插入鉆孔數據的地質建模方法。
其基本步驟為：①定義壹個包含所有鉆孔孔口坐標數據點的超級三角形(或者矩形，由兩個三角形構成)；②遍歷待插入點，對於某壹個待插入點P，找到其所在的三角單元T；③把P與T的3個頂點相連，生成3個新三角形；④用局部最優方法(LOP)優化三角網，使其符合Delaunay空圓準則。
B.幾何查詢與拓撲修改
點插入過程中，需要大量的幾何查詢和拓撲修改。這些操作主要分為兩類：①查詢。從三角單元中提取信息，比如在結點、邊和三角形之間檢查鄰接關系，提取三角形單元進行可視化顯示；②修改。改變TIN中的拓撲和幾何信息，如在局部優化時進行邊交換操作和基於點插入的細分操作。
在進行點插入時，首先是幾何上的查詢，即判斷待插入點P(x，y)是否位於某個三角形內。傳統上，對點是否在三角形內的這壹看似簡單的問題，是通過嚴格的幾何計算來確定。這裏，充分發揮GMaps拓撲數據模型的優勢，判斷方法如下，遍歷三角形的三條半邊E1、E2、E3(圖3.4)，若點P不在半邊E1所在的半平面(half plane)H1，2左側，則直接返回“false”，進入下壹個三角形；否則繼續。利用2-Orbit(即 )由E1得到E2，判斷點P是否位於其所在的半平面H2，3左側。只有點P全部在半平面H1，2、H2，3、H3，1的左側，點P位於三角形內。即：
P∈H1，2∩H2，3∩H3，1 (3.2)
圖3.4 點與三角形的關系判斷
若點P不在當前三角形內，可以通過1-Orbit( )獲取相鄰的三角形繼續進行判斷，直到找到點P所在的三角形，整個過程如圖3.5所示。實踐表明，在整個查找過程中，對於任何初始拓撲單元d，查找路徑總是以近似直線(圖3.5所示的虛箭頭)的“速度”趨近於目標的三角單元。因此，只需要有限的若幹步驟即可完成，大大提高了算法的執行效率，也體現GMaps的優勢。
在找到P所在的三角形Ti後，用點P將Ti壹劈為三(圖3.6)。首先，新建六條半邊：V1P、V2P、V3P和PV1、PV2、PV3；然後，需要修改三角單元V1V2V3的拓撲關系：將V1V2的後繼半邊修改為V2P，並設V2P的後繼邊為PV1，PV1的後繼邊為V1V2；這樣，PV1V2構成壹個新的拓撲三角單元。同理，對V2V3和V3V1做拓撲修改，得到另外兩個新的拓撲三角單元：PV2V3、PV3V1。
經過點劈裂後形成三個新的三角單元，接下來需要對每個三角單元進行局部優化(圖3.7)。如圖3.7a所示，問題將轉化為拓撲單元V1V2V3的外接圓是否包含相鄰的拓撲單元V2V4V3的頂點V4。如圖3.7b所示，判斷點V4是否在V2V4V3的外接圓內，只需考慮α+β的大小。若α+β＞π，則V4在V2V4V3的外接圓內，需要執行邊交換。根據四邊形的性質，同時有α+β＜2π：
圖3.5 初始三角網和待插入點P的查找過程
圖3.6 點劈裂三角形
圖3.7 三角化過程中進行邊交換
數字地下空間與工程三維地質建模及應用研究
因此，只需判斷sinαcosβ+cosαsinβ＜0即可。如圖3.7b所示，計算過程采用如下方法：
sinα=crossProduct(d1，d2)
sinβ=crossProduct(d3，d4)
cosα=scalarProduct(d1，d2)
cosβ=scalarProduct(d3，d4)
if((sinαcosβ+cosαsinβ)＜0)
return ok
else
return false
其中，crossProduct表示向量叉積，scalarProduct表示向量點積。
經過上述計算過程，若需要邊交換，則如圖3.7c所示，修改V3V1的後繼半邊為V1V4，V1V4的後繼半邊為V4V3，V4V3的後繼半邊為V3V1。同理對V1V2也做相應的拓撲修改。整個過程始終維持拓撲單元d的拓撲關系的壹致性，結果如圖3.7d所示。
C.點的動態插入
之所以采用逐點插入法構建Delaunay三角網，是因為其具有“開放性”。即當有新的數據點加入時，只需在局部進行修改或者擴充，而不需要改變整個體系結構。能夠便於空間數據的動態插入與局部更新。
新插入數據點P，依據插入點所在位置的不同分為兩種情況：
(1)新插入點P在原有Delaunay三角網邊界之內，此時只需要判斷新點位於哪壹個三角形內，然後按照上節所述方法通過幾何查詢和拓撲修改即可完成。
(2)新插入點P在原有Delaunay三角網邊界之外，此時只需要將新數據點追加到離散點數據庫的最後。從Delaunay三角網邊界為凸包的角度考慮，先找出已有三角網的邊界邊，可以通過α2(d)=d來獲取邊界邊所形成的凸包多邊形。然後，找到與待插入點P最近的邊界點Q，可以證明待插入點與該邊界點形成壹條Delaunay邊。在邊界點集中，以點Q為參照向兩個方向擴展形成新的邊界，直到最後所形成的邊界滿足凸包原則即可。最後，對新形成的三角形進行局部優化調整，可以保證最終形成的三角網為Delaunay三角化。
D.點的動態刪除
點刪除是點插入的逆過程，需要使點刪除之後的三角網仍然滿足Delaunay法則，且要動態更新點、線和三角形之間的拓撲關系。關於點刪除算法國內外研究相對較少，Chew(1986)最早提出從D-TIN中刪除點的算法，但比較復雜，沒有得到實際應用；此後，朱慶等(1998)提出了類D-TIN中點刪除算法，Devillers(1999)提出基於凸耳權的點刪除算法——凸耳消元法(ear elimination，EE)，實現了從二維D-TIN中刪除單壹點的刪除算法；Marc(1997)在規則三角剖分(regular triangulation，RT)中也涉及對點的刪除算法，Mostafavi et al.(2003)改進了凸耳消元法。
所謂凸耳，是指在D-TIN中刪除點P時，從點P的影響域中逆時針選取3個相鄰的點組成壹個三角形，若其相對於點P是凸的，且其外接圓內部包含其他點，則該三角形稱為壹個凸耳。Devillers提出的凸耳權值點刪除算法的基本原理是：查找以被刪除點P為頂點的所有三角形，組成任意多邊形H={ q0，q1，…，qk-1，qk=q0}。按照逆時針順序形成該多邊形的凸耳權值隊列。從隊列中選擇權值最小的凸耳ear={qi，qi+1，qi+2}，則qiqi+2為D-TIN中的壹條邊，凸耳權計算公式為(Devillers，1999)：
數字地下空間與工程三維地質建模及應用研究
由於凸耳定義嚴格，動態編輯過程中凸耳隊列的更新維護較復雜，可以以特征三角形來取代凸耳。所謂特征三角形，是指沿多邊形邊界(按逆時針方向)連接任意相鄰3點組成的三角形，其權值定義如下：若三角形的矢量面積為負，其權值為無窮大，否則，其權值用式(3.4)計算。
刪除點的步驟如下：
第壹步：查找被刪除點P相關聯的所有頂點和邊，利用0-Orbit( )即可完成(圖3.8a)。
第二步：形成帶權值的特征三角形隊列。根據第壹步找到的多邊形頂點，按逆時針依次計算每壹個三角形的凸耳權值。
第三步：查找符合Delaunay特征的D-TIN邊。從特征三角形隊列中刪除權值最小的△tri=qiqi+1qi+2{ }，則qiqi+2為D-TIN的壹條邊。修改此特征三角形的前後數據元素，並計算新的特征三角形權值。
第四步：對角線交換及D-TIN的局部更新。根據拓撲關系和點與邊的對應關系在D-TIN中查找以qi、qi+1、qi+2、p為頂點的兩個三角形。交換這兩個三角形所組成的凸四邊形的對角線，這樣以被刪除點為頂點的三角形個數少1。交換對角線後，生成1條新邊和2個新三角形，並維護三角形、邊之間的拓撲關系。如圖3.8所示，特征三角形隊列中權值最小的三角形為△q1q2q3，以p、q1、q2、q3為頂點的兩個三角形為F、F2，交換這兩個三角形形成的凸四邊形的對角線為E0={q1q3}。
圖3.8 對角線交換與局部更新
第五步：重復第三、第四步，直到多邊形頂點個數為3，轉入第六步。
第六步：點刪除與局部更新。
經過以上多次對角線交換，以被刪除點P為頂點的三角形只剩下3個，合並這3個三角形，刪除2個三角形元素、3條邊和數據點P，更新三類元素間的拓撲關系，即完成了Delaunay點的動態刪除。