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

时间:2025-07-10

第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字,全部文档内容请下载后查看。喜欢就下载吧 ……
一种生成Delaunay三角网的合成算法_武晓波(4).doc 将本文的Word文档下载到电脑

精彩图片

热门精选

大家正在看

× 游客快捷下载通道(下载后可以自由复制和排版)

限时特价:7 元/份 原价:20元

支付方式:

开通VIP包月会员 特价:29元/月

注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信:fanwen365 QQ:370150219