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

• 作者: 冯学智 王结臣 谢顺平 邓敏
• 来源期刊: 测绘学报
• 学科: 地球科学
• 关键词: Voronoi图 结点提取 四叉剖分 拓扑关系 搜索矩形域
• 年，卷（期）: 2007,（4）
• 所属期刊栏目: 学术论文
• 页码范围: 436-442
• 页数: 7页
• 分类号: P208
• 字数: 6333字
• 语种: 中文
• DOI: 10.3321/j.issn:1001-1595.2007.04.013

摘要

提出一种基于结点空间逼近、精确提取以及面向拓扑关系生成的2维平面点集的构建方法.主要给出了搜索矩形域及其剖分概念、Voronoi图的基本性质、矩形域与Voronoi图结点关系的定理及其证明、基于链队的矩形域剖分和结点逼近机制及结点提取策略、基于条带有序表的最近邻近发生元快速检索算法、矢量Voronoi图的拓扑关系建立算法等.经过算法分析和程序试验验证本文算法的时间复杂度为O(n log2 n),本方法可以扩展到平面任意发生元Voronoi图的构建,具有简洁、高精度、鲁棒性、高效、适合于海量数据等特点,并且具有较好的实用价值和应用前景.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	冯学智	南京大学地理与海洋科学学院	160	5398	41.0	67.0
2	谢顺平	南京大学地理与海洋科学学院	27	670	15.0	25.0
3	邓敏	中南大学测绘和国土信息工程系	160	1534	23.0	29.0
4	王结臣	南京大学地理与海洋科学学院	53	582	13.0	23.0