摘要
提出并证明了凸壳的城堡定理,设计并实现了城墙的快速搜索算法。该算法可以作为海量平面点集凸壳计算的数据预处理过程。在计算海量平面点集凸壳时,可以先用该算法从点集中筛选出一小部分点作为候选点集,再用其他凸壳算法就可以很快地计算出整个点集的凸壳。
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.
出处
《计算机工程》
EI
CAS
CSCD
北大核心
2006年第21期64-66,共3页
Computer Engineering
关键词
城墙快速搜索算法
城堡定理
凸壳
计算几何
Fast rampart search algorithm
Castle theorem
Convex hull
Computational geometry
