A vector-based algorithm to generate and update multiplicatively weighted Voronoi diagrams for points, polylines, and polygons

详细信息	查看全文 | 推荐本文 |

• 作者：Yongxi Gong^a ; ^b ; Guicai Li^a ; Yuan Tian^b ; Yaoyu Lin^c ; Yu Liu^b ; ^{liuyu@urban.pku.edu.cn}
• 关键词：Multiplicatively weighted Voronoi diagrams ; Vector-based algorithm ; Boolean operations on conic polygons
• 刊名：Computers and Geosciences
• 出版年：2012
• 期刊代码：16_00983004
• 类别：ear
• 出版时间：May, 2012
• 卷：42
• 期：Complete
• 页码：118-125
• 文件大小：996 K

摘要

A Voronoi diagram is a basic data structure in geometry with many applications. Existing research studies have focused on ordinary Voronoi diagrams, and some vector-based algorithms have been developed to generate multiplicatively weighted Voronoi diagrams (MWVDs) for points. An algorithm to construct MWVDs for points, polylines, and polygons is raster-based and has drawbacks. We propose a vector-based algorithm to generate and update MWVDs for points, polylines, and polygons. The MWVDs of two sites characterize the geometric features of multiplicatively weighted Voronoi regions, and the algorithm for Boolean operations on conic polygons is the computational preliminary to the MWVDs of N sites. The proposed algorithm is vector-based and can deal with sites with mixed spatial extents and various weights. We implement the algorithm in C# and present several examples of generating and updating MWVDs.