基于有序简单多边形的平面点集凸包快速求取算法

凸包问题是计算几何的基本问题之一，在许多领域均有应用。传统平面点集凸包算法和简单多边形凸包算法平行发展，互不相干。本文将改进的简单多边形凸包算法应用于平面点集凸包问题中，提出了新的点集凸包算法。该算法首先淘汰掉明显不位于凸包上的点，然后对剩余点集排序，再将点集按照一定顺序串联成有序简单多边形，最后利用前瞻回溯方法搜索多边形凸包，从而得到点集的凸包。本文算法不仅达到了Ｏ的理论时间复杂度下限，而且算法     

一种高效的平面点集凸包递归算法

凸包是计算几何的基本结构, 在许多图形图像相关领域得到了广泛应用. 本文提出了一种简单快速的平面点集凸包算法, 使用了主成分分析法(Principle component analysis, PCA)对点集进行预处理, 并研究了适用的排序规则和凸包边缘点判定原则. 该算法已成功应用于一光栅投影三维形貌快速测量系统,对相位干涉图中密集残留点所形成的最小凸包进行提取. 系统将提取的凸包区域进行掩码标记, 从而避免密集残留点造成相位展开错误, 保证了三维形貌重构的准确性. 实验结果表明, 该算法准确可靠, 并且运行效率较高.     

平面点集凸包的并行算法研究

提出了在基于有序简单多边形的平面点集凸包快速求取算法基础上改进的并行算法，该算法的时间复杂度达到了O（n）。在PC机互连构成的机群（COW）并行计算系统上以消息传递方式执行该算法，通过与原串行算法对比验证了该算法的可行性、正确性和高效性。     

确定平面点集凸包的一类最优算法

确定平面点集的凸包问题在计算机图形学、图象处理、ＶＬＳＩ设计与ＣＡＤ／ＣＡＭ等众多领域中有广泛的应用，多年来人们一直在寻找此问题的决策算法。     

平面点集凸包的最优实时算法

在星形多边形性质的基础之上,根据凸多边形是特殊的星形多边形,以星点为中心,以分别平行于x轴和y轴的直线作为相对坐标系的坐标轴,将平面区域划分为四个区,依据新的点与有向线段之间关系的判别式,从而简便快速地分离内部点和外部点,对外部点快速找到支撑点,提出了平面点集的最优实时算法,其时间复杂度为O(n).它同样适用于多边形并具有相同的时间复杂度.它还便于控制结果凸包的方向,只需调整初始三角形的方向即可,算法其它部分无需修改.算法具有高效、稳定等特点,从而在结合崔国华等的理论基础之上为找到一种线性的排序算法提供了实际的可能性.在文中的结论部分提供了本文算法和经典的Graham算法及堆式排序算法的执行时间的比较.     

如何求平面上一组点的凸包

(一)问题 本刊擂台赛2001年第4期的问题是编程求解平面点集的凸包问题。 即给定平面上n个点的坐标(xi,yi),请求出一个包含所有点的最小凸多边形,该多边形称为这一组点的凸包。实际上它也形成了围绕所有点的最短路径。     

一种平面点集凸包与三角网格综合生成的算法

平面点集作为一种觉数学模型,其上常做的运算是求其凸包和三角网格,目前二者的研究是独立进行的,鉴于在很多情形下这两种处理结果均需要,提出了一种综合算法：在对离散点集进行ｄｅｌａｕｎａｙ剖分的过程中,增加对三角形边界的判别、管理功能,记录其中作为点集凸包边界的线段,使得在实现剖分的同时产生出点集的凸包,从而提高了算法效率,且当该算法实现单一的点集剖分或凸包功能或是用于简单多边形的凸包与剖分时效果也很好     

基于平面的均匀分布和正态分布点集的凸包加速算法研究

研究怎样对于平面散乱点集进行的凸包算法的加速,主要的思想是计算一个点集的边界,摒弃边界范围内的点集,并且对于均匀分布和正态分布分别计算了最适合的加速因子,得到了平均意义上的O(n)的凸包算法.     

基于区域正交化分割的平面点集凸包算法EI北大核心CSCD

为解决实际工程应用中具有超大规模的平面点集的凸包计算问题,提出了一种基于点集所在区域正交化分割的新算法.利用点集几何结构的部分极点对平面点集进行正交化分割,以获取不相干的点集子集簇,再对所有点集子集分别计算其凸包极点,最后合并极点得到凸包点集.在不同层级的正交化分割过程中,根据已知极点的信息,逐层舍去对于凸包极点生成没有贡献的无效点,进而提高算法运行效率.在与目前常用凸包算法的对比实验中,该算法处理超大规模的平面点集时稳定性高且速度更快.     

海量平面点集凸壳的快速算法

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

平面海量散乱点集凸壳算法

凸壳作为计算几何的一种基本的结构,对GIS的数据分析有着重要作用。在分析传统的凸壳算法的基础上,提出新的凸壳算法,即金字塔算法。同时采用3种快速算法提高执行效率。通过大量实验数据对比说明,算法对求平面海量散乱点集的凸壳非常有效,点集为10^7数量级的执行时间在主频为2．00GHz计算机上仅为3s～4s。     

关于求平面点集凸包的一个O(n)时间算法的商榷

王志强等于1998年提出了一个计算平面点集凸包的新算法，并且声称该算法的最坏时间复杂度为O(n)，从而为张性时间排序提供了可能性，该文对王志强等提出的求平面点集凸包算法的时间分析提出了不同观点，进一步明确了平面集凸包算法和排序算法的时间下界为Ω(nlogn).     

一个改进的简单多边形凸包算法

凸包问题是计算几何的基本问题之一，在许多领域均有应用。该文通过给出反例，证明文献[4]提出的简单多边形凸包的双动线检测算法不能正确求出任意多边形的凸包，并分析了其缺点，提出了一个改进的算法。改进的算法解决了线性算法所不能解决的自交问题，且实现简单。     

求解简单多边形和平面点集凸包的新算法

沿一定方向遍历凸多边形的边,其内部在边的同一侧。本文依据凸多边形的这一特性,提出求解简单多边形凸包的新算法,进而扩展得到求解平面点集凸包的新算法。新点集凸包算法先找到点集的极值点,得到极值点间的候选点子集,再求得相邻极值点间的有序凸包点列,最后顺序连接极值点间的有序凸包点列,得到凸包。新算法达到目前平面点集凸包问题的渐进最好算法的时间复杂度O（n log h）,其中,n为平面点集的点数,h为平面点集凸包的顶点数。相比相同复杂度的凸包算法,新算法简单、易于实现。又由于是顺序求得凸包上的点,新算法还具有更易于实现基于其上的有效空间算法的优点。     

A Total Order Heuristic-Based Convex Hull Algorithm for Points in the Plane

Computing the convex hull of a set of points is a fundamental operation in many research fields, including geometric computing, computer graphics, computer vision, robotics, and so forth. This problem is particularly challenging when the number of points goes beyond some millions. In this article, we describe a very fast algorithm that copes with millions of points in a short period of time without using any kind of parallel computing. This has been made possible because the algorithm reduces to a sorting problem of the input point set, what dramatically minimizes the geometric computations (e.g., angles, distances, and so forth) that are typical in other algorithms. When compared with popular convex hull algorithms (namely, Graham’s scan, Andrew’s monotone chain, Jarvis’ gift wrapping, Chan’s, and Quickhull), our algorithm is capable of generating the convex hull of a point set in the plane much faster than those five algorithms without penalties in memory space.     

基于凸多边形的凸壳算法

确定平面点集的凸壳问题在计算机图形学、图像处理、CAD／CAM、模式识别等众多领域中有广泛的应用。本文根据凸多边形的性质构建了一种新的基于凸多边形的凸壳算法，该算法利用X、y坐标的极值将凸多边形分为几个段，应用凸壳顶点有序性，分段计算凸壳的顶点而得到凸壳。理论分析和实验结果表明，该算法运行速度快效率高，具有较强的实用性。     

基于栅格划分构建平面点集凸壳的算法研究

提出了一个构建平面点集凸壳的新算法。该算法用栅格阵列将待处理点集划分成若干个子集,这样凸壳可以由部分位于点集边缘的子集确定;然后按逆时针顺序逐步处理这些子集,得到一个包含待处理点集的简单多边形,删除凹顶点后就得到待处理点集的凸壳。由于只对点集边缘的点进行局部处理,从而提高了构建凸壳的效率。在最坏情况下该算法的时间复杂度为O(NlogN)。     

一种平面点集凸壳的快速算法

文章提出了一种对平面离散点集凸壳的快速算法,该算法首先对离散点进行扫描线方式排序,构造初始凸壳,然后把剩下的离散点加入到已有的凸壳中生成新的凸壳.实验表明该算法具有很好的效率.