共查询到18条相似文献,搜索用时 78 毫秒
1.
2.
平面点集凸包快速构建算法的研究 总被引:10,自引:0,他引:10
蒋红斐 《计算机工程与应用》2002,38(20):48-49,106
文章提出了一种提高构建凸包速度的新方法。该算法生成一个网格来管理离散点,在淘汰明显不位于凸包上的点时,将对离散点的取舍转换为对格的取舍,计算工作量只与离散点的范围及网格的密度有关,与离散点的数目无关;同时对点集也进行了初略的排序。在求取剩余点集的凸包时,采用了一种先分段求取凸包边界,最后将这些边界合并成凸包的方法,该方法充分利用了剩余点集所具有的有序性。 相似文献
3.
一种平面点集凸包与三角网格综合生成的算法 总被引:7,自引:0,他引:7
平面点集作为一种觉数学模型,其上常做的运算是求其凸包和三角网格,目前二者的研究是独立进行的,鉴于在很多情形下这两种处理结果均需要,提出了一种综合算法:在对离散点集进行delaunay剖分的过程中,增加对三角形边界的判别、管理功能,记录其中作为点集凸包边界的线段,使得在实现剖分的同时产生出点集的凸包,从而提高了算法效率,且当该算法实现单一的点集剖分或凸包功能或是用于简单多边形的凸包与剖分时效果也很好 相似文献
4.
5.
如何求平面上一组点的凸包 总被引:1,自引:0,他引:1
(一)问题 本刊擂台赛2001年第4期的问题是编程求解平面点集的凸包问题。 即给定平面上n个点的坐标(xi,yi),请求出一个包含所有点的最小凸多边形,该多边形称为这一组点的凸包。实际上它也形成了围绕所有点的最短路径。 相似文献
6.
确定平面点集凸包的一类最优算法 总被引:12,自引:2,他引:12
确定平面点集的凸包问题在计算机图形学、图象处理、VLSI设计与CAD/CAM等众多领域中有广泛的应用,多年来人们一直在寻找此问题的决策算法。 相似文献
7.
8.
平面点集凸包的最优实时算法 总被引:5,自引:1,他引:5
在星形多边形性质的基础之上,根据凸多边形是特殊的星形多边形,以星点为中心,以分别平行于x轴和y轴的直线作为相对坐标系的坐标轴,将平面区域划分为四个区,依据新的点与有向线段之间关系的判别式,从而简便快速地分离内部点和外部点,对外部点快速找到支撑点,提出了平面点集的最优实时算法,其时间复杂度为O(n).它同样适用于多边形并具有相同的时间复杂度.它还便于控制结果凸包的方向,只需调整初始三角形的方向即可,算法其它部分无需修改.算法具有高效、稳定等特点,从而在结合崔国华等的理论基础之上为找到一种线性的排序算法提供了实际的可能性.在文中的结论部分提供了本文算法和经典的Graham算法及堆式排序算法的执行时间的比较. 相似文献
9.
为解决实际工程应用中具有超大规模的平面点集的凸包计算问题,提出了一种基于点集所在区域正交化分割的新算法.利用点集几何结构的部分极点对平面点集进行正交化分割,以获取不相干的点集子集簇,再对所有点集子集分别计算其凸包极点,最后合并极点得到凸包点集.在不同层级的正交化分割过程中,根据已知极点的信息,逐层舍去对于凸包极点生成没有贡献的无效点,进而提高算法运行效率.在与目前常用凸包算法的对比实验中,该算法处理超大规模的平面点集时稳定性高且速度更快. 相似文献
10.
11.
12.
平面海量散乱点集凸壳算法 总被引:5,自引:0,他引:5
凸壳作为计算几何的一种基本的结构,对GIS的数据分析有着重要作用。在分析传统的凸壳算法的基础上,提出新的凸壳算法,即金字塔算法。同时采用3种快速算法提高执行效率。通过大量实验数据对比说明,算法对求平面海量散乱点集的凸壳非常有效,点集为10^7数量级的执行时间在主频为2.00GHz计算机上仅为3s~4s。 相似文献
13.
郝建强 《中国图象图形学报》2007,12(5):910-916
求平面点集的凸包是计算几何的一个基本算法。目前的算法较多,但这些算法均较复杂,为降低算法复杂性,首先从分析直线的正负划分性入手,利用其来对平面点集进行分类,以简化点到直线的距离计算;然后进一步详细地给出了一种改进的求平面任意散乱点集凸包的新算法。该算法在搜索凸包时,较目前流行的算法中所采用的前瞻回溯法既简单又速度快,该算法较传统的算法更是优越,尤其他不需要计算角度和欧氏距离。结果表明,利用该算法求任意平面散乱点集凸包不仅计算准确,而且计算过程中仅仅用到加、减、乘、比较运算。这样不仅使算法的每一步骤的时间复杂性大大降低,而且也使得整个算法的时间复杂性大大降低。经过分析,该算法也是一个最优的算法。 相似文献
14.
关于求平面点集凸包的一个O(n)时间算法的商榷 总被引:6,自引:0,他引:6
王志强等于1998年提出了一个计算平面点集凸包的新算法,并且声称该算法的最坏时间复杂度为O(n),从而为张性时间排序提供了可能性,该文对王志强等提出的求平面点集凸包算法的时间分析提出了不同观点,进一步明确了平面集凸包算法和排序算法的时间下界为Ω(nlogn). 相似文献
15.
16.
本文为构建离散点的凸包提出了一种改进的分治算法,它在查找每一个凸包顶点的同时,通过去除若干非凸包顶点来迅速减小问题的规模。本文对该算法的正确性给出了严格的证明。 相似文献
17.
确定平面点集的凸壳问题在计算机图形学、图像处理、CAD/CAM、模式识别等众多领域中有广泛的应用。本文根据凸多边形的性质构建了一种新的基于凸多边形的凸壳算法,该算法利用X、y坐标的极值将凸多边形分为几个段,应用凸壳顶点有序性,分段计算凸壳的顶点而得到凸壳。理论分析和实验结果表明,该算法运行速度快效率高,具有较强的实用性。 相似文献
18.
基于栅格划分构建平面点集凸壳的算法研究 总被引:4,自引:0,他引:4
提出了一个构建平面点集凸壳的新算法。该算法用栅格阵列将待处理点集划分成若干个子集,这样凸壳可以由部分位于点集边缘的子集确定;然后按逆时针顺序逐步处理这些子集,得到一个包含待处理点集的简单多边形,删除凹顶点后就得到待处理点集的凸壳。由于只对点集边缘的点进行局部处理,从而提高了构建凸壳的效率。在最坏情况下该算法的时间复杂度为O(NlogN)。 相似文献