Please wait a minute...
工程设计学报
Chinese Journal of Engineering Design  2004, Vol. 11 Issue (1): 6-10    DOI:
    
Approach to build Voronoi diagram for multiply-connected domains with free -form contour
 HU  Jun, WANG  Yu-Han, CAI  Jian-Guo
College of Mechanical Engineering, Shanghai Jiaotong University, Shanghai 200030, China
Download: HTML     PDF(352KB)
Export: BibTeX | EndNote (RIS)      

Abstract  The Voronoi diagram of connected domain is widely used. The generally adopted algorithms,such as divide-and-conquer method, are difficult to realize. A new method to establish free boundary connected domain Voronoi diagram is introduced based on the algorithm for determining the medial axis of an convex polygon. Through finding the bisectors of neighboring boundary elements, points of intersection of neighboring bisectors are obtained.Point of intersection with the minimum distance is used to realize the growing of Voronoi diagram. The entire simply-connected domain Voronoi diagram is established in this way. The Voronoi diagram merging algorithm for inner and outer boundary of multi-connected domain is also introduced.

Key words： connected domain      medial axis of polygon      bisector      Voronoi diagram     
Published: 28 February 2004
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
HU Jun
WANG Yu-Han
CAI Jian-Guo
Cite this article:

HU Jun, WANG Yu-Han, CAI Jian-Guo. Approach to build Voronoi diagram for multiply-connected domains with free -form contour. Chinese Journal of Engineering Design, 2004, 11(1): 6-10.

URL:

https://www.zjujournals.com/gcsjxb/     OR     https://www.zjujournals.com/gcsjxb/Y2004/V11/I1/6


自由边界平面连通域的Voronoi图生成方法研究

平面连通域的Vorono，图被广泛应用于许多领域，常用的分治法等算法实现较为复杂，影响了其应用范围在凸多边形中轴算法的基础上，提出一种建立自由边界平面连通域的Voronoi图的新方法.通过求解相邻边界元素的平分线，计算出相邻平分线的交点，由距离最小的平分线交点实现Voronoi图边的增长，最终建立完整的平面单连通域的Voronoi图.同时，还介绍了平面多连通域的内外边界的Voronoi图的合并算法.

关键词： 平面连通域,  多边形中轴,  平分线,  Voronoi图 
No related articles found!