Abstract: 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.

Key words: Fast rampart search algorithm, Castle theorem, Convex hull, Computational geometry

摘要： 提出并证明了凸壳的城堡定理，设计并实现了城墙的快速搜索算法。该算法可以作为海量平面点集凸壳计算的数据预处理过程。在计算海量平面点集凸壳时，可以先用该算法从点集中筛选出一小部分点作为候选点集，再用其他凸壳算法就可以很快地计算出整个点集的凸壳。

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

CLC Number: 

• TP312