计算机仿真
計算機倣真
계산궤방진
Computer Simulation
2015年
8期
306-310
,共5页
苏天赟%王雯%吴蔚%李新放
囌天赟%王雯%吳蔚%李新放
소천빈%왕문%오위%리신방
三角网%逐点插入法%点定位算法%三角形重心
三角網%逐點插入法%點定位算法%三角形重心
삼각망%축점삽입법%점정위산법%삼각형중심
Delaunay triangulation%Incremental insertion algorithm%Point positioning algorithm%Triangle barycenter
逐点插入法是构建Delaunay三角网的主要方法之一,而在众多三角形中能否快速找到插入点所在三角形是影响整个逐点插入法构网速度的重要因素.在分析现有点定位算法的基础上,结合三角形重心的几何性质,提出了一种新的点定位算法,简化了待插点位于三角形两条边外侧时的寻找下一三角形的计算步骤,避免了求三角形重心坐标和相交边的过程,并将新算法应用到点云数据地形建模中.实验结果表明,上述算法较目前其它点定位算法能够有效的缩短搜索路径,避免了目前已有算法存在的搜索路径长、搜索路径求解计算量大等问题,较其它算法能提高Delaunay三角网构网过程中点定位的效率,并减少点云数据地形建模时间.
逐點插入法是構建Delaunay三角網的主要方法之一,而在衆多三角形中能否快速找到插入點所在三角形是影響整箇逐點插入法構網速度的重要因素.在分析現有點定位算法的基礎上,結閤三角形重心的幾何性質,提齣瞭一種新的點定位算法,簡化瞭待插點位于三角形兩條邊外側時的尋找下一三角形的計算步驟,避免瞭求三角形重心坐標和相交邊的過程,併將新算法應用到點雲數據地形建模中.實驗結果錶明,上述算法較目前其它點定位算法能夠有效的縮短搜索路徑,避免瞭目前已有算法存在的搜索路徑長、搜索路徑求解計算量大等問題,較其它算法能提高Delaunay三角網構網過程中點定位的效率,併減少點雲數據地形建模時間.
축점삽입법시구건Delaunay삼각망적주요방법지일,이재음다삼각형중능부쾌속조도삽입점소재삼각형시영향정개축점삽입법구망속도적중요인소.재분석현유점정위산법적기출상,결합삼각형중심적궤하성질,제출료일충신적점정위산법,간화료대삽점위우삼각형량조변외측시적심조하일삼각형적계산보취,피면료구삼각형중심좌표화상교변적과정,병장신산법응용도점운수거지형건모중.실험결과표명,상술산법교목전기타점정위산법능구유효적축단수색로경,피면료목전이유산법존재적수색로경장、수색로경구해계산량대등문제,교기타산법능제고Delaunay삼각망구망과정중점정위적효솔,병감소점운수거지형건모시간.
