首页 | 本学科首页   官方微博 | 高级检索  
     

基于平面点集的Voroni图的近似构造
引用本文:陈丽娜,马玉洁.基于平面点集的Voroni图的近似构造[J].微计算机信息,2007,23(27):263-264.
作者姓名:陈丽娜  马玉洁
作者单位:商丘师范学院计算机科学系,河南商丘,476000
摘    要:现有的平面上点的Voronoi图的构造方法一般很难扩展到一般平面图形的Voronoi图的构造上。以平面点集中的每个点作为生长核,以相同的速率向外扩张,直到彼此相遇为止而在平面上形成的图形即为平面点集的近似的Voronoi图。在VC 6.0的环境下实现了该算法,并将其与分治法所得的结果进行了比较。该算法直观、计算简单,通用性好。对于一般的平面图形,选取有代表性的边界点,再按照平面点集中Voronoi图的近似构造方法,就可以得到一般平面图形的近似的Voronoi图。

关 键 词:计算几何  Voronoi图  分治法
文章编号:1008-0570(2007)09-3-0263-02
修稿时间:2007-08-03

Construction of Voronoi Diagram Based on Planar Point Set
CHEN LINA,MA YUJIE.Construction of Voronoi Diagram Based on Planar Point Set[J].Control & Automation,2007,23(27):263-264.
Authors:CHEN LINA  MA YUJIE
Affiliation:The Department of Computer Science,Shangqiu Normal University,Shangqiu,China 476000
Abstract:Most of the algorithms of voronoi diagram based on planar point set are difficult to extend to the construction of voronoi diagram based on planar general figures. For each point in planar point set, expanded around at the same speed until they encoun-tered, thus the voronoi diagram based planar point set was approximately constructed .The algorithm was implemented under VC 6.0 and was compared with divide and conquer. The algorithm is simple, not calculation expensive and general. For general figures,we can choose some sample points, and construct their voronoi diagrams according to the construction of voronoi diagram based onplanar point set.
Keywords:computation geometry  voronoi diagram  divide and conquer
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号