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

• 学术探讨 • 上一篇    下一篇

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

樊广佺 王小牛 杨炳儒   

  1. 北京科技大学 河北经贸大学 北京科技大学 河北经贸大学 北京科技大学信息工程学院
  • 收稿日期: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. (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

摘要: 提出了一种计算海量平面点集凸壳的快速近似算法——点集坐标旋转法(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