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

Approximate algorithm for convex hull of planar point set

作　　者：樊广佺[1] 王小牛[2] 杨炳儒[1] 

机构地区：[1]北京科技大学信息工程学院,北京100083 [2]中国地质大学地球科学与资源学院,北京100083

出　　处：《计算机工程与应用》2007年第12期40-41,76,共3页Computer Engineering and Applications

基　　金：国家科技成果重点推广项目(No.2003EC000001)。

摘　　要：提出了一种计算海量平面点集凸壳的快速近似算法——点集坐标旋转法(PSCR)。该算法采用点集不断旋转并求X(Y)坐标极值的方法得到平面点集的近似凸壳。它充分利用了成熟的数据库技术,能够在比较短的时间内计算出海量平面点集的近似凸壳。它不需要空间索引的支持,并能获得比较理想的近似效果。The paper presents an efficient approximate algorithm for Convex Hull of very large planar point set.That is Point Set Coordinate Rotation Algorithm（PSCR）.h 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.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]