|
|||||
|
|
| 平面点集凸壳的一个性质 | |
| 引用本文： | 樊广佺,曲文龙,杨炳儒.平面点集凸壳的一个性质[J].地理与地理信息科学,2008,24(1):46-48. |
| 作者姓名： | 樊广佺 曲文龙 杨炳儒 |
| 作者单位： | 1. 河北经贸大学信息技术学院,河北,石家庄,050061;北京科技大学信息工程学院,北京,100083 2. 石家庄经济学院信息工程学院,河北,石家庄,050031 3. 北京科技大学信息工程学院,北京,100083 |
| 摘 要： | 该文揭示了平面点集凸壳的一个性质,即如果一个子凸壳包含东、西、南、北4个方向上的极值点,则其任一条子凸壳边的外点必在该边所确定的外直角三角形中,并对该性质进行了数学证明。在此基础上,利用该性质对快速凸壳算法进行了改进,达到了良好的加速效果。 |
| 关 键 词： | 矩形区域过滤 快速算法 凸壳 计算几何 |
| 文章编号： | 1672-0504（2008）01-0046-03 |
| 收稿时间： | 2007-01-12 |
| 修稿时间： | 2007-06-18 |
A Property of the Convex Hull of Planar Point Set |
|
| FAN Guang-quan,QU Wen-long,YANG Bing-ru.A Property of the Convex Hull of Planar Point Set[J].Geography and Geo-Information Science,2008,24(1):46-48. | |
| Authors: | FAN Guang-quan QU Wen-long YANG Bing-ru |
| Abstract: | Convex hull is one of the basic problems in computational geometry.For its importance,people are searching for the faster algorithms all the time.Convex hull has many characteristics.It is also a powerful tool to construct other geometry structures.This paper reveals a property of the convex hull of planar point set.If the sub convex hull includes four extreme value points(the north,the south,the east and the west),the outside points to an edge of the sub convex hull will be inside of the outside right-angled triangle decided by the edge.It is strictly proved in the paper.According to the content of the property,the fast convex hull algorithm by using the rectangle-area filtering technique is improved,and a good accelerating effect is achieved during the experiments.The rectangle-area filtering technique can also be used in the case of three-dimension. |
| Keywords: | rectangle region filtration efficient algorithm convex hull computational geometry |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |