一种生成Delaunay三角网的合成算法_武晓波(4)
时间:2025-07-11
时间:2025-07-11
第1期武晓波等:一种生成Delaunay三角网的合成算法 35
WeatherReview,1911,39:1082—1084.
[2] V.J.D.Tsai.DelaunaytriangulationsinTINcreation:anoverview
andalinear-timealgorithm[J].Int.J.ofGIS,1993,7(6):501—524.
[3] M.I.Shamos,D.Hoey.Closest-pointproblems[C].Proceedings
ofthe16thAnnualSymposiumontheFoundationsofComputerSci-ence.1975,151—162.
[4] B.A.Lewis,J.S.Robinson.Triangulationofplanarregionswith
applications[J].TheComputerJournal,1978,21(4):324—332.[5] wson.SoftwareofC'surfaceinterpolation,Mathematical
SoftewareIII.J.Rice[M].AcademicPress,NewYork,1977.[6] D.T.Lee,B.J.Schachter.TwoalgorithmsforconstructingaDe-launaytriangulation[J].Int.J.ofComputerandInformationSci-ences,1980,9(3).
[7] putingDirichlettesselations[J].ComputerJournal,
1981,24:162—166.
[8] S.W.Sloan.AfastalgorithmforConstructingDelaunaytriangula-tionsintheplane[J].AndvancedEngineeringSoftware,1987,9:34—55.
[9] G.Macedonio,M.T.Pareschi.AnAlgorithmforthetriangulation
ofarbitrarilydistributedpoints:applicationstovolumeestimateandterrainfitting[J].Computers&Geosciences,1991,17:859—874.
[10] K.E.Brassel,D.Reif.ProceduretogenerateThiessenpolygons
[J].GeophysicalAnalysis,1979,11:289—303.
[11] M.T.McCaullagh,C.G.Ross.Delaunaytriangulationofarandom
datasetforirarithmicmapping[J].TheCartographicJournal,1980,17:93—99.
[12] rkin.AnANSICprogramtodetermineinexpectedlinear
timetheverticesoftheconvexhullofasetofplanarpoints[J].Computers&Geosciences,1991,17(3):431—443.
[13] Sedgewick,R.Algorithms[M].Addison-Wesley,NewYork,1988.
致谢
阎守邕研究员全面指导了这项研究,对本文的
段落安排及文字运用等方面提出了许多珍贵建议并作了修改。在此谨向他表示诚挚的敬意和感谢。赵健、崔景年、田青、周艺、王涛等同仁在研究过程中给予了大力帮助,在此也向他们表示衷心感谢。
AHybridizedMethodforBuildingDelaunayTriangulation
WUXiao-bo, WANGShi-xin, XIAOChun-sheng
(InstituteofRemoteSensingApplications,ChineseAcademyofSciences, Beijing 100101,China)
Abstract: Awidevarietyofalgorithmshavebeenproposedtoconstructtriangulation.Theyfallintothreebroadcate-gories:divide-and-conquer,incrementalinsertionandtriangulationgrowth.Thefirsttwogroupsofthemethodshavebeenextensivelyappliedtomanydisciplinesbecauseoftheireasinessinimplementation.Theyare,however,constrainedei-therbytheircomputationalinefficiencyorbytheirstringentdemandoncomputermemory.Inthispaperahybridized
methodisproposedtotakeadvantageofbothalgorithms'strengthssothattheselimitationscouldbeovercome.Inatestof2533points,thecomputationefficiencyofthehybridizedmethodismuchhigherthanthatofincrementalinsertionmethodinallcases,andisalsohigherthanthatofdivide-and-conquermethodinmostcases.Thebestefficiencyisachievedwhenthedatapointsarepartitionedintoone-tenthoftheoriginalsize.Key words: hybridizedmethod;delaunaytriangulation;divide-and-conquer;incrementalinsertion
…… 此处隐藏:636字,全部文档内容请下载后查看。喜欢就下载吧 ……