摘要
提出了一种计算海量平面点集凸壳的快速近似算法——点集坐标旋转法(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.
出处
《计算机工程与应用》
CSCD
北大核心
2007年第12期40-41,76,共3页
Computer Engineering and Applications
基金
国家科技成果重点推广项目(No.2003EC000001)。
关键词
近似算法
凸壳
计算几何
approximate algorithm
Convex Hull
computational geometry
