平面点集凸壳的一种近似算法

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (12): 40-41.

平面点集凸壳的一种近似算法

樊广佺王小牛杨炳儒

北京科技大学河北经贸大学北京科技大学河北经贸大学北京科技大学信息工程学院

收稿日期:2006-09-05 修回日期:1900-01-01 出版日期:2007-04-20 发布日期:2007-04-20
通讯作者: 樊广佺

An Approximate Algorithm for Convex Hull of Planar Point Set

FAN Guangquan1, WANG Xiaoniu2, YANG Bingru1

(1. Information Engineering College, Beijing University of Science and Technology, Beijing 100083;
2. School of the Geosciences and Resources, China University of Geosciences, Beijing 100083)

Received:2006-09-05 Revised:1900-01-01 Online:2007-04-20 Published:2007-04-20
Contact: GuangQuan Fan

摘要/Abstract

摘要： 提出了一种计算海量平面点集凸壳的快速近似算法——点集坐标旋转法（PSCR）。该算法采用点集不断旋转并求X（Y）坐标极值的方法得到平面点集的近似凸壳。它充分利用了成熟的数据库技术，能够在比较短的时间内计算出海量平面点集的近似凸壳。它不需要空间索引的支持，并能获得比较理想的近似效果。

关键词: 近似算法, 凸壳, 计算几何

Abstract: The paper presents an efficient approximate algorithm for Convex Hull of very large planar point set. That is Point Set Coordinate Rotation Algorithm (PSCR). It rotates the point set and calculates the extremum of X(Y) coordinate, and finally gets the Convex Hull of the point set. Using well-developed database technology, the algorithm can calculate out the approximate Convex Hull of very large planar point set. It does not need the support of spatial index, and achieves a better approximation effect.

Key words: Approximate Algorithm, Convex Hull, Computational Geometry

樊广佺王小牛杨炳儒. 平面点集凸壳的一种近似算法[J]. 计算机工程与应用, 2007, 43(12): 40-41.

FAN Guangquan1, WANG Xiaoniu2, YANG Bingru1

. An Approximate Algorithm for Convex Hull of Planar Point Set[J]. Computer Engineering and Applications, 2007, 43(12): 40-41.

[1]	曾维新1，赵翔1，2，冯滔1，唐九阳1，2. 面向领域的命名实体消歧方法改进研究[J]. 计算机工程与应用, 2018, 54(17): 126-134.
[2]	蒋小娟1，张安1，陈永1，陈光亭2. 内部节点受限的最小生成树问题算法研究[J]. 计算机工程与应用, 2017, 53(10): 35-37.
[3]	许孝盛1，靳萍2，郑稳2. 室内座椅线框图识别[J]. 计算机工程与应用, 2016, 52(23): 196-202.
[4]	聂文艳1，王仲根2. 应用ACA算法快速分析导体目标电磁散射特性[J]. 计算机工程与应用, 2015, 51(4): 232-234.
[5]	刘鹏程1，2，揭毅1，2，杨文博1，2. 临近特征点类型匹配的多边形渐变表达模型[J]. 计算机工程与应用, 2015, 51(22): 42-47.
[6]	傅天裕1，2，罗永龙1，2，郭良敏1，2，孙玲玲1，2. 保护私有信息的两多边形相交面积计算[J]. 计算机工程与应用, 2014, 50(9): 37-40.
[7]	吴芬1，仲红1，2，石润华1，2. 隐私保护的费马问题极值计算协议[J]. 计算机工程与应用, 2014, 50(4): 77-80.
[8]	赵建芳1，钱雪忠1，贾志伟2. 基于凸壳的约束信息扩展方法[J]. 计算机工程与应用, 2014, 50(4): 173-176.
[9]	周雪梅1，黎应飞2. 基于Bowyer-Watson三角网生成算法的研究[J]. 计算机工程与应用, 2013, 49(6): 198-200.
[10]	王继强. 集合覆盖问题的模型与算法[J]. 计算机工程与应用, 2013, 49(17): 15-17.
[11]	纪鹏宇1，谢红1，赵蕴龙2. 一种中继节点上的网络-信道编码联合设计方案[J]. 计算机工程与应用, 2012, 48(34): 102-106.
[12]	戴海鹏，唐厚君. 求凸多边形直径的改进算法[J]. 计算机工程与应用, 2011, 47(3): 44-46.
[13]	王继强. 基于TSP的图的路包装问题的算法研究[J]. 计算机工程与应用, 2011, 47(21): 220-222.
[14]	赵军¹，高满屯²，王三民². 求平面多边形集凸壳的方法[J]. 计算机工程与应用, 2011, 47(1): 205-207.
[15]	何晓琼，陈冲，李荣珩. 工厂地址集中的k-种产品选址问题的近似算法[J]. 计算机工程与应用, 2010, 46(8): 238-241.