资源描述：
《delaunay 三角形构网的分治扫描线算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第36卷第3期测绘学报Vol.36,No.32007年8月ACTAGEODAETICAetCARTOGRAPHICASINICAAug,2007文章编号:1001-1595(2007)03-0358-05中图分类号:P208文献标识码:ADelaunay三角形构网的分治扫描线算法芮一康,王结臣(南京大学地理信息科学系,江苏南京210093)ANewStudyofCompoundAlgorithmBasedonSweeplineandDivide-and-conquerAlgorithmsforConstr
2、uctingDelaunayTriangulationRUIYi-kang,WANGJie-chen(DepartmentofGeographicInformationScience,NanjingUniversity,Nanjing210093,China)Abstract:AsoneofthemostimportantDTMmodel,Delaunaytriangulationiswidelyappliedinmanifoldfields.Awidevarietyofalgorithmshavebee
3、nproposedtoconstructDelaunaytriangulation,suchasdivide-and-conquer,in-crementalinsertion,trangulationgrowth,andsoon.ThecompoundalgorithmisalsoresearchedtoconstructDelau-naytriangulation,andprevalentlyitismainlybasedondivide-and-conquerandincrementalinsert
4、ionalgorithms.Thispapersimplyreviewsandassessessweeplineanddivide-and-conqueralgorithms,basedonwhichanewcom-poundalgorithmisprovidedafterstudyingthesweeplinealgorithmseriously.Tostartwith,thisnewcompoundal-gorithmdividesasetofpointsintoseveralgridtileswit
5、hdifferentdividingmethodsbydivide-and-conqueralgo-rithm,andthenconstructssubnetineachgridtilebysweeplinealgorithm.FinallythesesubnetsarerecursivelymergedintoawholeDelaunaytriangulationwithasimplifiedefficientLOPalgorithm.Fortopologicalstructureisim-portan
6、ttotemporalandspatialefficiencyofthisalgorithm,weonlystoredataaboutvertexandtriangle,thusedgeisimpliedlyexpressedbytwoadjacenttriangles.Inordertofittwosubnetsmergingbetter,weoptimizesomedatastructureofsweeplinealgorithm.Forinstance,frontlineandbaselineoft
7、riangulationarecombinedtooneline,andfourpointerspointtowheremaximumandminimumofxaxisandyaxisareinthisoutline.Thetestshowsthatthisnewcompoundalgorithmhasbetterefficiency,stabilityandrobustnessthandivide-and-conquerandsweeplinealgo-rithms.Especiallyifwefind
8、therightdividingmethodreplytodifferentcircumstance,itssuperiorityisremarkable.Keywords:Delaunaytriangulation;compoundalgorithm;sweeplinealgorithm;divide-and-conqueralgorithm摘要:Delaunay三角网作为一种主要的DTM表示法,具有极其广泛的用途。基于分治
