A novel computation algorithm of Voronoi diagrams for multiply-connected planar areas

Bo Qian

doi:10.1117/12.830286

30 October 2009 A novel computation algorithm of Voronoi diagrams for multiply-connected planar areas

Bo Qian

Proceedings Volume 7498, MIPPR 2009: Remote Sensing and GIS Data Processing and Other Applications; 74983M (2009) https://doi.org/10.1117/12.830286
Event: Sixth International Symposium on Multispectral Image Processing and Pattern Recognition, 2009, Yichang, China

Abstract

This paper studies the practical generation of Voronoi diagrams of multiply-connected planar areas bounded by straight line segments. The key idea of the algorithm consists in calculating Voronoi polygon of every Voronoi object in planar areas independently. The main approach is divided into two steps. The first step is to calculate all relevant bisectors of the all Voronoi objects, and the second is to combine obtained bisectors into completed Voronoi polygons individually. The contents of steps are both very important and all codes are implemented in Visual C++ platform. The resulting codes are tested extensively on real-world data, and its practical running time seems to grow only linearly. Three statistical CPU-consumption charts have been drawn with the Voronoi diagrams computation data. The CPU-time consumptions records also gain the advantages over other published codes for computing Voronoi diagrams. The development of the algorithm is achieved by treating equidistant generation as a locus-tracing problem.

Citation Download Citation

Bo Qian "A novel computation algorithm of Voronoi diagrams for multiply-connected planar areas", Proc. SPIE 7498, MIPPR 2009: Remote Sensing and GIS Data Processing and Other Applications, 74983M (30 October 2009); https://doi.org/10.1117/12.830286

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available