测绘科学
測繪科學
측회과학
SCIENCE OF SURVEYING AND MAPPING
2008年
1期
141-143
,共3页
夏兰芳%胡鹏%白轶多%黄梦龙
夏蘭芳%鬍鵬%白軼多%黃夢龍
하란방%호붕%백질다%황몽룡
最小生成树%距离变换%Voronoi图%Delaunay三角网
最小生成樹%距離變換%Voronoi圖%Delaunay三角網
최소생성수%거리변환%Voronoi도%Delaunay삼각망
本文介绍了最小生成树及其常见的算法,对比栅格算法分析了基于矢量的最小生成树算法的缺点,介绍了地图代数的距离变换和基于地图代数的距离变换图生成Voronoi图、Delaunay三角网,然后根据最小生成树MST是Delaunay三角剖分的一个子集,逐次删掉Delaunay三角网中每个三角形的最长边,从而得到最小生成树,该方法不仅适用于欧氏非障碍空间,同样也适用于障碍空间的情况,解决了以往最小生成树在障碍空间下(尤其是当障碍空间中的障碍是全形态的条件下)难以求解的问题,具有一定的理论意义.
本文介紹瞭最小生成樹及其常見的算法,對比柵格算法分析瞭基于矢量的最小生成樹算法的缺點,介紹瞭地圖代數的距離變換和基于地圖代數的距離變換圖生成Voronoi圖、Delaunay三角網,然後根據最小生成樹MST是Delaunay三角剖分的一箇子集,逐次刪掉Delaunay三角網中每箇三角形的最長邊,從而得到最小生成樹,該方法不僅適用于歐氏非障礙空間,同樣也適用于障礙空間的情況,解決瞭以往最小生成樹在障礙空間下(尤其是噹障礙空間中的障礙是全形態的條件下)難以求解的問題,具有一定的理論意義.
본문개소료최소생성수급기상견적산법,대비책격산법분석료기우시량적최소생성수산법적결점,개소료지도대수적거리변환화기우지도대수적거리변환도생성Voronoi도、Delaunay삼각망,연후근거최소생성수MST시Delaunay삼각부분적일개자집,축차산도Delaunay삼각망중매개삼각형적최장변,종이득도최소생성수,해방법불부괄용우구씨비장애공간,동양야괄용우장애공간적정황,해결료이왕최소생성수재장애공간하(우기시당장애공간중적장애시전형태적조건하)난이구해적문제,구유일정적이론의의.
