一种生成Delaunay三角网的合成算法_武晓波(4)

第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