| 海量平面点集凸壳的快速算法 |
| |
| 引用本文： | 樊广佺,张桂云,杨炳儒. 海量平面点集凸壳的快速算法[J]. 计算机工程, 2006, 32(21): 64-66 |
| |
| 作者姓名： | 樊广佺 张桂云 杨炳儒 |
| |
| 作者单位： | 北京科技大学信息工程学院,北京,100083 |
| |
| 摘 要： | 提出并证明了凸壳的城堡定理，设计并实现了城墙的快速搜索算法。该算法可以作为海量平面点集凸壳计算的数据预处理过程。在计算海量平面点集凸壳时，可以先用该算法从点集中筛选出一小部分点作为候选点集，再用其他凸壳算法就可以很快地计算出整个点集的凸壳。
|
| 关 键 词： | 城墙快速搜索算法 城堡定理 凸壳 计算几何 |
| 文章编号： | 1000-3428（2006）21-0064-03 |
| 收稿时间： | 2006-06-26 |
| 修稿时间： | 2006-06-26 |
Efficient Convex Hull Algorithm for Very Large Planar Point Set |
| |
| FAN Guangquan,ZHANG Guiyun,YANG Bingru. Efficient Convex Hull Algorithm for Very Large Planar Point Set[J]. Computer Engineering, 2006, 32(21): 64-66 |
| |
| Authors: | FAN Guangquan ZHANG Guiyun YANG Bingru |
| |
| Affiliation: | Information Engineering College, Beijing University of Science and Technology Beijing 100083 |
| |
| 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. |
| |
| Keywords: | Fast rampart search algorithm Castle theorem Convex hull Computational geometry |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载免费的PDF全文 |
