基于结点逼近提取的平面点集Voronoi图构建算法.pdf

第36卷第4期 测绘学报 V01．36．No．4 2007年11月 ACTAGEODAETICAetCARTOGRAPHICASINICA Nov．．2007 文章编号：1001．1595(2007)04-0436—07 中图分类号：P208 文献标识码：A 基于结点逼近提取的平面点集Voronoi图构建算法 谢顺平1，王结臣1，冯学智1，邓敏2 (1南京大学地理与海洋科学学院，南京210093；2．中南=；：学测绘和国土信息T程系，k沙410083) for Voronoi of Points Planar AlgorithmConstructingDiagram Basedon and Vertices ApproximatingExtracting XIE Min2 Jie-chenl，IENGXue-zMl，DENG Shun—pin91，WANG t1．School《GeographicandOceangraphicSeienses，NanjingUniversity，N口嘶讯g and South Geo-i咖rmatics，Central University，‰础410083，China) Abstract：A for Voronoi of in set thetwo-dimensionalEu· topology—orientedconstructing point algorithm diagram dideanbasedon and Voronoiverticesaye inthis of 8p8ce approximatingextracting prOposedpaper．Theconcepts ale口,andits basic ofVoHJnoi invalvedinthere— dissection，the theorems searchingrectar。gle properties diagram。the Ladonof Voronoivertices，themechanmmof and verticesbased％ rectan出and disseethtgrectrLngleapproximating chained of the of theclosest basedonor— vertiees，the queue，thestrategyextracting algorithmsearching generator deredtableof the of relation and method are