| 平面点集凸壳的一种快速算法 |
| |
| 引用本文： | 樊广佺,马丽平,杨炳儒.平面点集凸壳的一种快速算法[J].地理与地理信息科学,2006,22(6):38-41. |
| |
| 作者姓名： | 樊广佺 马丽平 杨炳儒 |
| |
| 作者单位： | 北京科技大学信息工程学院,北京,100083;河北经贸大学计算机中心,河北,石家庄,050061 |
| |
| 基金项目： | 国家科技成果重点推广项目(2003EC000001) |
| |
| 摘 要： | 提出一种计算平面点集凸壳的快速算法———八方向极值快速凸壳算法。该算法首先对平面点集进行一次扫描,从而快速查找到东、南、西、北、东南、西南、东北、西北8个方向上的极值点,构造出一个更接近凸壳的初始凸壳,从而在后续的点集扫描中可以排除更多的内点,使该算法计算效率更高。该算法的空间复杂度为O(N);其时间复杂度虽然无法突破最坏情况下O(NlogN)的理论下限,但其期望时间复杂度已达到线性水平,并且可以容易地扩展到三维和高维空间。
|
| 关 键 词： | 快速算法 JAVA 凸壳 计算几何 |
| 文章编号： | 1672-0504(2006)06-0038-04 |
| 收稿时间： | 2006-09-14 |
| 修稿时间： | 2006-11-02 |
An Efficient Algorithm for the Convex Hull of Planar Point Set |
| |
| FAN Guang-shuan,MA Li-ping,YANG Bing-ru.An Efficient Algorithm for the Convex Hull of Planar Point Set[J].Geography and Geo-Information Science,2006,22(6):38-41. |
| |
| Authors: | FAN Guang-shuan MA Li-ping YANG Bing-ru |
| |
| Institution: | 1 . Information Engineering College, Beijing University of Science and Technology, Beijing 100083 ; 2. Computer Center, Hebei University of Economics and Business, Shijiazhuang 050061 , China |
| |
| Abstract: | This paper presents and realizes an efficient algorithm for the convex hull of planer point set.It is Eight Direction Extreme Value Fast Convex Hull Algorithm.The extreme values on eight directions(east,west,south,north,east-south,west-south,east-north,west-north)are found fleetly after scanning the point set.Thus an initial convex hull that is closer to the real one is built.So more inner points can be excluded during the next scanning.During the second scanning,not only all the inner points of the initial convex hull are excluded,but also every outside point is associated with its unique initial convex hull edge.Thus,the searching of the farthest point is limited in its outside point set.In addition,when a point is judged as an outside point of a sub convex hull edge,the information of the farthest point of the sub convex hull edge is saved,so the distance calculating for searching the farthest point is avoided.All these make the algorithm more efficient.The space complexity of the algorithm is O(N).Although its time complexity can not break through the low limit of O(Nlog N)in the worst case,its expected time complexity is already linear.Additionally,the algorithm can be generalized to three or high dimension easily. |
| |
| Keywords: | efficient algorithm JAVA convex hull computational geometry |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
