python三角網(wǎng)格代碼-三角剖分算法（delaunay）

python三??格代碼_三?剖分算法（delaunay）開篇在做?個LowPoly的課題，?這種低多邊形的成像效果在現(xiàn)在設(shè)計中越來越被喜歡，其中的低多邊形都是由三?形組成的。?如何?動?成這些看起來很特殊的三?形，就是本章要討論的內(nèi)容。選擇其是最先是由很多離散的點組成，基于這個確定的點集，將點集連接成?定??的三?形，且分配要相對合理，才能呈現(xiàn)出漂亮的三?化。這時則要求使?三?剖分算法(Delaunay)，引于【定義】三?剖分：假設(shè)V是?維實數(shù)域上的有限點集，邊e是由點集中的點作為端點構(gòu)成的封閉線段,E為e的集合。那么該點集V的?個三?剖分T=(V,E)是?個平圖G，該平圖滿?條件：1.除了端點，平圖中的邊不包含點集中的任何點。2.沒有相交邊。3.平圖中所有的?都是三??，且所有三??的合集是散點集V的凸包。在實際中運?的最多的三?剖分是Delaunay三?剖分，它是?種特殊的三?剖分。先從Delaunay邊說起：【定義】Delaunay邊：假設(shè)E中的?條邊e(兩個端點為a,b)，e若滿?下列條件，則稱之為Delaunay邊：存在?個圓經(jīng)過a,b兩點，圓內(nèi)(注意是圓內(nèi)，圓上最多三點共圓)不含點集V中任何其他的點，這?特性?稱空圓特性。【定義】Delaunay三?剖分：如果點集V的?個三?剖分T只包含Delaunay邊，那么該三?剖分稱為Delaunay三?剖分?！径x】假設(shè)T為V的任?三?剖分，則T是V的?個Delaunay三?剖分，當前僅當T中的每個三?形的外接圓的內(nèi)部不包含V中任何的點。如圖，將離散點聯(lián)結(jié)成Delaunay三?形算法關(guān)于Delaunay三?形的算法，有翻邊算法、逐點插?算法、分割合并算法、Bowyer-Watson算法等。?在這?種算法中，逐點插?算法?較簡單、易懂，在本?中只針對該算法進?討論，該算法也是?前使?最為?泛的Delaunay算法。在該算法中，主要應(yīng)?Delaunay三?形【定義4】，理解下來就是每?個三?形的外接圓圓內(nèi)不能存在點集內(nèi)的其它任何?點，?有時候會出現(xiàn)點在外接圓上的情況，這種情況被稱為“退化”。在?章?對該?法進?了分析，并提出了偽代碼思路：subroutinetriangulateinput:vertexlistoutput:trianglelistinitializethetrianglelistdeterminethesupertriangleaddsupertriangleverticestotheendofthevertexlistaddthesupertriangletothetrianglelistforeachsamplepointinthevertexlistinitializetheedgebufferforeachtrianglecurrentlyinthetrianglelistcalculatethetrianglecircumcirclecenterandradiusifthepointliesinthetrianglecircumcirclethenaddthethreetriangleedgestotheedgebufferremovethetrianglefromthetrianglelistendifendfordeletealldoublyspecifiededgesfromtheedgebufferthisleavestheedgesoftheenclosingpolygononlyaddtothetrianglelistalltrianglesformedbetweenthepointandtheedgesoftheenclosingpolygonendforremoveanytrianglesfromthetrianglelistthatusethesupertriangleverticesremovethesupertriangleverticesfromthevertexlistend其?法雖然可實現(xiàn)三?化，但是效率還是不太?在看過優(yōu)化后的偽代碼為：input:頂點列表(vertices)//vertices為外部?成的隨機或亂序頂點列表output:已確定的三?形列表(triangles)初始化頂點列表創(chuàng)建索引列表(indices=newArray(vertices.length))//indices數(shù)組中的值為0,1,2,3,......,vertices.length-1基于vertices中的頂點x坐標對indices進?sort//sort后的indices值順序為頂點坐標x從?到?排序(也可對y坐標，本例中針對x坐標)確定超級三?形將超級三?形保存?未確定三?形列表(temptriangles)將超級三?形push到triangles列表遍歷基于indices順序的vertices中每?個點//基于indices后，則頂點則是由x從?到?出現(xiàn)初始化邊緩存數(shù)組(edgebuffer)遍歷temptriangles中的每?個三?形計算該三?形的圓?和半徑如果該點在外接圓的右側(cè)則該三?形為Delaunay三?形，保存到triangles并在temp?去除掉跳過如果該點在外接圓外(即也不是外接圓右側(cè))則該三?形為不確定//后?會在問題中討論跳過如果該點在外接圓內(nèi)則該三?形不為Delaunay三?形將三邊保存?edgebuffer在temp中去除掉該三?形對edgebuffer進?去重

將edgebuffer中的邊與當前的點進?組合成若?三?形并保存?temptriangles中將triangles與temptriangles進?合并除去與超級三?形有關(guān)的三?形end?多數(shù)同學(xué)看過偽代碼后還是?頭霧?，所以?圖來解釋這個過程，我們先?三點來做實例：如圖，隨機的三個點根據(jù)離散點的最?分布來求得隨機?個超級三?形(超級三?形意味著該三?形包含了點集中所有的點)我的?法是根據(jù)相似三?形定理求得與矩形?半的?矩形的對?三?形，擴??倍后則擴?后的直?三?形斜邊經(jīng)過點(Xmax,Ymin)但是為了將所有的點包含在超級三?形內(nèi)，在右下?對該三?形的頂點進?了橫和?的擴展，并要保證這個擴展三?形底?于?，才能實現(xiàn)包含這樣求得的超級三?形不會特別?使得計算復(fù)雜，?且過程也簡單，并將超級三?形放?temptriangles中接下來就像是偽代碼中描述的那樣，對temptriangle中的的三?形遍歷畫外接圓，這時先對左邊的第?個點進?判斷，其在圓內(nèi)所以該三?形不為Delaunay三?形，將其三邊保存?edgebuffer中，temptriangle中刪除該三?形將該點與edgebuffer中的每?個邊相連，組成三個三?形，加?到temptriangles中再將重復(fù)對temptriangles的遍歷并畫外接圓，這時使?的是第?個點來進?判斷該點在三?形1外接圓右側(cè)，則表?左側(cè)三?形為Delaunay三?形，將該三?形保存?triangles中該點在三?形2外接圓外側(cè)，為不確定三?形，所以跳過(后?會講到為什么要跳過該三?形)，但并不在temptriangles中刪除該點在三?形3外接圓內(nèi)側(cè)，則這時向清空后的edgebuffer加?該三?形的三條邊，并?該點寫edgebuffer中的三?邊進?組合，組合成了三個三?形并加?到temptriangles中再次對temptriangles進?遍歷，這?該數(shù)組?則含有四個三?形，?個是上次檢查跳過的含有第?個點的三?形和新根據(jù)第?個點?成的三個三?形該點在三?形1外接圓右側(cè)，則該三?形為Delaunay三?形，保存?triangles中，并在temptriangles中刪除該點在三?形2外接圓外側(cè)，跳過該點在三?形3外接圓內(nèi)側(cè)，將該三邊保存?tempbuffer中，并在temptriangles中刪除該點在三?形4外接圓內(nèi)側(cè)，將該三邊保存?tempbuffer中，并在temptriangles中刪除這時，tempbuffer中有六條邊，triangles中有兩個三?形，temptriangles中有1個三?形對tempbuffer中的六條邊進?去重，得到五條邊，將該點與這五條邊組合成五個三?形并加?到temptriagnles中，這時temptriangles中有6個三?形由于三個點已經(jīng)遍歷結(jié)束，到了不會再對第三個點形成的三?形做外接圓，這時則將triangles與temptrianlges合并，合并后的數(shù)組表?包含已經(jīng)確定的Delaunay三?形和剩下的三?形這時除去合并后數(shù)組中的和超級三?形三個點有關(guān)的所有三?形，即進?數(shù)組坐標的限定，則得到了最后的結(jié)果：這是?最少的三個點來做講解，點數(shù)越多的話計算量會越?，但是都是在上?步驟下進?的。問題在?點對三?形外接圓位置關(guān)系進?判斷的時候，為什么點在外接圓的右側(cè)的話可以確定該三?形是Delaunay三?形?當點外接圓的外側(cè)且?右側(cè)時，為什么要路過三?形，不把該三?形確定為Delaunay三?形呢？?先，我們在開始的時候?qū)υ?法進?優(yōu)化時，我們增加了?個indices數(shù)組來操作vertices，并對indices依據(jù)vertices的x坐標進?了從?到?的排序則我們在后?遍歷點時是從點集的最左側(cè)開始的，如圖：當遍歷下?個點時，該點在外接圓的右側(cè)，則表?以后所有的點都在該外接圓的右側(cè)，則保證了Delaunay三?形的空圓特性?當點在外接圓外，并?外接圓右側(cè)時，如圖：在該三?形的外切圓中，當遍歷到點1時，符合在外側(cè)的條件，但是不能確定后?所有的點都保持在外接圓外側(cè)如果說該三?形就為Delaunay三?形的話，如圖中的點2及后?可能出現(xiàn)