逐點(diǎn)插入算法

為了檢測(cè)逐點(diǎn)插入算法的實(shí)現(xiàn)效果，用DEM數(shù)據(jù)進(jìn)行了D-TIN剖分實(shí)驗(yàn)。試驗(yàn)的主要目的是觀察用逐點(diǎn)插入算法進(jìn)行三角剖分所構(gòu)成的TIN模型是否能夠很好地反映地形特征。⑴數(shù)據(jù)來(lái)源：撫仙湖流域DEM數(shù)據(jù)，采樣點(diǎn)正方形規(guī)則分布，采樣點(diǎn)個(gè)數(shù)為10848x4507。⑵軟、硬件配置：Intel?Core2Quad2.4GHzCPU,2G內(nèi)存，NVIDIAGeForce9600顯卡，WindowsXP操作系統(tǒng)，編程工具為VC++6.0,渲染引擎為OpenGL。⑶實(shí)驗(yàn)方法步驟：該算法主要步驟為：首先利用數(shù)據(jù)點(diǎn)的坐標(biāo)極值形成初始矩形包容盒以便進(jìn)行剖分初始化(圖2.14)，找到待插入采樣點(diǎn)所在位置，然后開(kāi)始逐點(diǎn)插入進(jìn)行三角剖分并局部?jī)?yōu)化，最終完成構(gòu)TIN。具體的實(shí)現(xiàn)步驟及部分代碼如下：構(gòu)造矩形包圍盒進(jìn)行初始三角剖分圖2.14包圍盒初始剖分圖2.14包圍盒初始剖分{pCal->getScope(amCurPt,minPt,maxPt);get4Ori();}//初始化三角網(wǎng)，生成兩個(gè)初始三角形voidCTiNPrc::initTicell(){//包圍盒的4個(gè)邊界點(diǎn)amCurPt[0]=oriP0;amCurPt[1]=oriP1;amCurPt[2]=oriP2;amCurPt[3]=oriP3;CTICelltiCell;//初始三角形1tiCell.iId=iGlbCellId++;tiCell.iPtId[0]=0;tiCell.iPtId[1]=1;tiCell.iPtId[2]=2;tiCell.iTpId[1]=1;amCurCell.Add(tiCell);//初始三角形2tiCell.iId=iGlbCellId++;tiCell.iPtId[0]=2;tiCell.iPtId[1]=3;tiCell.iPtId[2]=0;tiCell.iTpId[1]=0;amCurCell.Add(tiCell);}判斷待插入點(diǎn)與三角形的關(guān)系//判斷點(diǎn)在哪個(gè)三角形內(nèi)CTiNPrc::jgPtInWhCell(CPt3d&pt,int&CellId){CTICellFirstCell;FirstCell=amCurCell[amCurCell.GetSize()-1];CPt3dp1,p2,p3;p1=amCurPt[(FirstCell.iPtId[0])];p2=amCurPt[(FirstCell.iPtId[1])];p3=amCurPt[(FirstCell.iPtId[2])];intity,tt;ity=pCal->jg(pt,p1,p2,p3);switch(ity){?第一種情況：點(diǎn)在三角形內(nèi)部case0:CellId=FirstCell.iId;return0;break;?第二種情況：點(diǎn)在三角形邊上

case-1:case-2:case-3:case-23://點(diǎn)在p1對(duì)面的邊上case-31://點(diǎn)在p2對(duì)面的邊上case-12://點(diǎn)在p3對(duì)面的邊上CellId=FirstCell.iId;returnity;break;}}插入點(diǎn)構(gòu)TIN并進(jìn)行局部?jī)?yōu)化?點(diǎn)在三角形內(nèi)部的剖分和優(yōu)化當(dāng)插入點(diǎn)在三角形的內(nèi)部時(shí)，連接插入點(diǎn)和原來(lái)三角形的3個(gè)頂點(diǎn)，生成三個(gè)新的小三角形和3條新邊，并維護(hù)點(diǎn)、線(xiàn)和三角形之間的拓?fù)潢P(guān)系，完成點(diǎn)在三角形內(nèi)部的插入和三角網(wǎng)的局部?jī)?yōu)化，剖分情況如圖2.15所示。圖2.15插入點(diǎn)在三角形內(nèi)部的剖分情況圖2.15插入點(diǎn)在三角形內(nèi)部的剖分情況具體的實(shí)現(xiàn)代碼如下：voidCTiNPrc::quick_spltCell(CPt3dpt,CTICell&surCell,CTICellAry&arTICell){intiConId=surCell.iId;CTICelltiCell[3];//剖分后3個(gè)三角形頂點(diǎn)賦值tiCell[0].iPtId[0]=surCell.iPtId[0];tiCell[0].iPtId[1]=surCell.iPtId[1];tiCell[0].iPtId[2]=pt.iIdx;〃第1個(gè)三角形tiCell[1].iPtId[0]=surCell.iPtId[1];tiCell[1].iPtId[1]=surCell.iPtId[2];tiCell[1].iPtId[2]=pt.iIdx;//第2個(gè)三角形tiCell[2].iPtId[0]=surCell.iPtId[2];tiCell[2].iPtId[1]=surCell.iPtId[0];tiCell[2].iPtId[2]=pt.iIdx;//第3個(gè)三角形//剖分后3個(gè)三角形編號(hào)；tiCell[0].iId=iGlbCellId++;tiCell[1].iId=iGlbCellId++;tiCell[2].iId=iConId;//剖分后3個(gè)三角形拓?fù)涞慕iCell[0].iTpId[0]=tiCell[1].iId;tiCell[0].iTpId[1]=tiCell[2].iId;tiCell[0].iTpId[2]=surCell.iTpId[2];tiCell[1].iTpId[0]=tiCell[2].iId;tiCell[1].iTpId[1]=tiCell[0].iId;tiCell[1].iTpId[2]=surCell.iTpId[0];tiCell[2].iId=iConId;tiCell[2].iTpId[0]=tiCell[0].iId;tiCell[2].iTpId[1]=tiCell[1].iId;tiCell[2].iTpId[2]=surCell.iTpId[1];〃三角形的ID號(hào)和在三角形數(shù)組中的存儲(chǔ)位置一致arTICell.SetAt(tiCell[0].iId,tiCell[0]);nCurCellId++;arTICell.SetAt(tiCell[1].iId,tiCell[1]);nCurCellId++;arTICell.SetAt(tiCell[2].iId,tiCell[2]);//剖分后相鄰三角形拓?fù)浣or(inti=0;i<3;i++){

rebirthsjwTp(iConId,tiCell[i],arTICell);}CTICell*pnCell=NULL,*psCell=NULL;//進(jìn)行局部?jī)?yōu)化；for(i=0;i<3;i++){if(i<2)pnCell=&(arTICell[iGlbCellId-2+i]);elsepnCell=&(arTICell[iConId]);{rebirthTinTp(pnCell->iId,amCurPt[pnCell->iPtId[2]],arTICell);}}}?插入點(diǎn)在三角形的邊上的剖分和優(yōu)化如果插入點(diǎn)在三角形的邊上，則要分為兩種情況考慮。第一種情況：插入點(diǎn)所在的邊只屬于一個(gè)三角形，則連接插入點(diǎn)與其所在邊相對(duì)的頂點(diǎn)，形成2個(gè)新的三角形和一條新邊；第二種情況：插入點(diǎn)所在的邊是兩個(gè)三角形的公共邊，則連接插入點(diǎn)與其所在邊的左右三角形內(nèi)相對(duì)的兩個(gè)頂點(diǎn)，形成新的小三角形和新的邊，并維護(hù)點(diǎn)、線(xiàn)和三角形之間的拓?fù)潢P(guān)系，完成點(diǎn)在三角形內(nèi)部的插入和三角網(wǎng)的局部?jī)?yōu)化。剖分情況分別如圖2.16、2.17所示。圖2.16插入點(diǎn)所在邊只屬于一個(gè)三角形的剖分情況圖2.17插入點(diǎn)所在邊屬于兩個(gè)三角形的剖分情況兩種剖分情況的具體實(shí)現(xiàn)步驟及部分實(shí)現(xiàn)代碼如下：voidCTiNPrc::quick_splitCellPtOE(CPt3dpt,CTICell&surCell,CTICellAry&arTICell){intiConId1,iConId=surCell.iId;?插入點(diǎn)所在邊只屬于一個(gè)三角形的情況CTICellsurCell2;if(surCell.iTpId[0]==-1){CTICelltiCell1[2];//剖分后2個(gè)三角形頂點(diǎn)賦值tiCell1[0].iPtId[0]=surCell.iPtId[0];tiCell1[0].iPtId[1]=surCell.iPtId[1];tiCell1[0].iPtId[2]=pt.iIdx;tiCell1[1].iPtId[0]=surCell.iPtId[2];tiCell1[1].iPtId[1]=surCell.iPtId[0];tiCell1[1].iPtId[2]=pt.iIdx;//剖分后2個(gè)三角形編號(hào)tiCell1[0].iId=iGlbCellId++;tiCell1[1].iId=iConId;//剖分后2個(gè)三角形拓?fù)涞慕iCell1[0].iTpId[0]=-1;tiCell1[0].iTpId[1]=surCell.iId;tiCell1[0].iTpId[2]=surCell.iTpId[2];tiCell1[1].iTpId[0]=tiCell1[0].iId;tiCell1[1].iTpId[1]=-1;tiCell1[1].iTpId[2]=surCell.iTpId[1];//三角形的ID號(hào)和在三角形數(shù)組中的存儲(chǔ)位置一致arTICell.SetAt(tiCell1[0].iId,tiCell1[0]);nCurCellId++;arTICell.SetAt(tiCell1[1].iId,tiCell1[1]);//剖分后相鄰三角形拓?fù)浣ebirthsjwTp(iConId,tiCell1[0],arTICell);//生成的2個(gè)三角形的局部?jī)?yōu)化CTICell*pnCell1=NULL;pnCelll=&(arTICell[iConId]);〃第1個(gè)三角形if(pnCell1->iTpId[2]>=0)rebirthTinTp(pnCell1->iId,amCurPt[pnCell1->iPtId[2]],arTICell);pnCell1=&(arTICell[iGlbCellId-1]);//第2個(gè)三角形if(pnCell1->iTpId[2]>=0)rebirthTinTp(pnCell1->iId,amCurPt[pnCell1->iPtId[2]],arTICell);return;}?插入點(diǎn)所在邊屬于兩個(gè)三角形的情況surCell2=arTICell[surCell.iTpId[0]];iConId1=surCell2.iId;intiPtMark;boolb;b=findTpId(&surCell2,surCell.iId,iPtMark);if(!b)return;CTICelltiCell[4];//剖分后4個(gè)三角形頂點(diǎn)賦值tiCell[0].iPtId[0]=surCell.iPtId[0];tiCell[0].iPtId[1]=surCell.iPtId[1];tiCell[0].iPtId[2]=pt.iIdx;tiCell[1].iPtId[0]=surCell2.iPtId[(iPtMark+2)%3];tiCell[1].iPtId[1]=surCell2.iPtId[iPtMark];tiCell[1].iPtId[2]=pt.iIdx;tiCell[2].iPtId[0]=surCell2.iPtId[iPtMark];tiCell[2].iPtId[1]=surCell2.iPtId[(iPtMark+1)%3];tiCell[2].iPtId[2]=pt.iIdx;tiCell[3].iPtId[0]=surCell.iPtId[2];tiCell[3].iPtId[1]=surCell.iPtId[0];tiCell[3].iPtId[2]=pt.iIdx;//剖分后4個(gè)三角形編號(hào)tiCell[0].iId=iGlbCellId++;tiCell[1].iId=iGlbCellId++;tiCell[2].iId=iConId1;tiCell[3].iId=iConId;//剖分后4個(gè)三角形拓?fù)涞慕iCell[0].iTpId[0]=tiCell[1].iId;tiCell[0].iTpId[1]=tiCell[3].iId;tiCell[0].iTpId[2]=surCell.iTpId[2];tiCell[1].iTpId[0]=tiCell[2].iId;tiCell[1].iTpId[1]=tiCell[0].iId;tiCell[1].iTpId[2]=surCell2.iTpId[(iPtMark+1)%3];tiCell[2].iId=iConId1;tiCell[2].iTpId[0]=surCell.iId;tiCell[2].iTpId[1]=tiCell[1].iId;tiCell[2].iTpId[2]=surCell2.iTpId[(iPtMark+2)%3];tiCell[3].iId=iConId;tiCell[3].iTpId[0]=tiCell[0].iId;tiCell[3].iTpId[1]=tiCell[2].iId;tiCell[3].iTpId[2]=surCell.iTpId[1];〃三角形的ID號(hào)和在三角形數(shù)組中的存儲(chǔ)位置一致arTICell.SetAt(tiCell[0].iId,tiCell[0]);nCurCellId++;arTICell.SetAt(tiCell[1].iId,tiCell[1]);nCurCellId++;arTICell.SetAt(tiCell[2].iId,tiCell[2]);arTICell.SetAt(tiCell[3].iId,tiCell[3]);//剖分后相鄰三角形拓?fù)浣ebirthsjwTp(iConId,tiCell[0],arTICell);rebirthsjwTp(iConId1,tiCell[1],arTICell);//生成的4個(gè)三角形的局部?jī)?yōu)化CTICell*pnCell=NULL;pnCell=&(arTICell[iCo