| 一种构建平面离散点集凸包的算法研究 |
| |
| 引用本文： | 俞梅.一种构建平面离散点集凸包的算法研究[J].上海应用技术学院学报,2003,3(2):118-120. |
| |
| 作者姓名： | 俞梅 |
| |
| 作者单位： | 上海应用技术学院机械与自动化工程学院 上海，200235 |
| |
| 摘 要： | 本文提出一种矢量运算方法确定平面离散点集凸包，其原理是在构建凸包前，通过矢量计算判别出位于凸包多边形内部的点，预先将其删去，保留凸包多边形外部边缘的点，从而减少了构建凸包的离散点数目，提高运算速度。新算法达到O(n1ogn)时间复杂度下限，简单且易于实现。
|
| 关 键 词： | 多边形 凸包 矢量算法 离散点数目 |
| 文章编号： | 1671-7333(2003)02-0118-03 |
| 修稿时间： | 2002年4月9日 |
A Vector Algorithm Research on the Construction of the Convex Hull of a Set of Planar Point |
| |
| YU Mei.A Vector Algorithm Research on the Construction of the Convex Hull of a Set of Planar Point[J].Journal of Shanghai Institute of Technology: Natural Science,2003,3(2):118-120. |
| |
| Authors: | YU Mei |
| |
| Abstract: | This paper presents a vector algorithm for constructing the convex hull of a set of planar discrete points.The computing method is to remove all or most points lying in the interior of the hull and reserve the possible vertices of the exterior boundary of the hull before the convex hull is constructed.Therefore,the number of the points for constructing the convex hull is greatly reduced.The computing rate is improved and the constructed efficiency is enhanced. |
| |
| Keywords: | polygon convex hull vector algorithm |
| 本文献已被 CNKI 维普 等数据库收录！ |
