海量平面点集凸壳的快速算法  

Efficient Convex Hull Algorithm for Very Large Planar Point Set

作　　者：樊广佺[1] 张桂云[1] 杨炳儒[1] 

机构地区：[1]北京科技大学信息工程学院,北京100083

出　　处：《计算机工程》2006年第21期64-66,共3页Computer Engineering

摘　　要：提出并证明了凸壳的城堡定理,设计并实现了城墙的快速搜索算法。该算法可以作为海量平面点集凸壳计算的数据预处理过程。在计算海量平面点集凸壳时,可以先用该算法从点集中筛选出一小部分点作为候选点集,再用其他凸壳算法就可以很快地计算出整个点集的凸壳。The paper presents and proves castle theorem of convex hull. Then it designs and realizes the fast rampart search algorithm. This algorithm can be treated as the preprocess of convex hull.calculation of very large planar point set. When calculating convex HULL of very large planar point set, a very small part data is selected out as candidate point set, and the convex hull of whole planar point set can be retrieved from the candidate point set.

关 键 词：城墙快速搜索算法 城堡定理 凸壳 计算几何 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]