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

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

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