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

为了提高凸包计算的效率,针对海岛正射点云的特点,提出了三级过滤措施,将平面点集抽稀至似边缘点集并排序,在此基础上改进了Graham算法,算法的时间复杂度为线性对数阶。通过对黄海开山岛等6个海岛点云进行计算,在普通、集中、扩散等3种类型情况下与多个经典算法进行对比,结果表明该算法平均运行效率为Quickhull算法的1.68倍、Andrew算法的8.93倍、Graham算法的20.65倍。因此,该算法可以被作为海岛、海岸、独立建筑物等正射点云凸包计算的关键算法。

简单快速的平面散乱点集凸包算法

凸包问题是计算几何的基本问题之一，在许多领域均有应用．传统点集凸包算法和简单多边形凸包算法平行发展，互不相干．文中将简单多边形凸包算法应用于散乱点集凸包问题中，提出了新的点集凸包算法．新算法不仅达到了Ｏ（ｎｌｏｇｎ）的理论时间复杂度下限，而且极其简单，易于实现．该算法已应用于工厂设计软件ＰＤＳＯＦＴ中。

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

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

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

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

海量平面点集Voronoi图的构造算法

进一步发展平面点集Voronoi图的增量式外置算法.在对"海量"点组成的平面点集进行Voronoi划分时,设计"硬盘数据文件——内存结构体数组"之间动态的数据交互方案,避开计算机内存的限制,有效实现了数十万Voronoi晶胞集合体的构造,存储Voronoi图几何信息的数据最后以文本文件的形式输出,方便Voronoi图在工程实际中的应用与二次开发.

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

凸包问题是计算几何的基本问题之一。为实时计算平面点集的凸包,近年来许多学者提出很多优秀的算法,但依然不能满足实际中的实时性需求。为此,本文提出一种简单但高效快速的凸包算法。由于凸包点必然位于平面点集边缘,本文算法能够快速地筛选出极少量的凸包点候选点集,这是本算法的核心优势。然后,使用本文另外提出的一种简单易于实现的改进的Graham扫描算法,或其他任何已有的凸包检测方法,即可快速而准确地计算出点集的凸包。经典的Graham扫描算法使用一个基点计算凸包,本文的改进算法则是根据凸包候选点的分布情况,将点集分成4个子块,也即使用4个基点分别在每块中进行凸包检测,最后将每个子块中的检测结果进行合并,得到最终的完整凸包。实验中,采用一组公开的动物骨骼点云数据作为一次测试集。在凸包计算完全正确的情况下,当点数约为3×1 0~5左右时,本算法的计算时间比其他算法减少2.22倍;当点数约为3×10~6时,本算法的计算时间比其他方法减少5.42倍。点数越多,所提出算法就表现出越明显的优势。

一个通用的快速三角化算法

提出了一个适用于任意平面多边形区域及散乱点集的通用三角化算法 .当算法应用于多边形区域时 ,首先对各个顶点和区域内部的散乱点按扫描方式排序 ,然后依次扫描各点 ,扩展生成新的三角形 ,从而获得局部已剖分区域 ,并最终完成整个区域的三角化 .将上述过程作适当改动后 ,可被用于平面散乱点集的三角网格化 .该通用算法除了具有快速三角化的特点之外 ,还采用局部区域的优化组合来体现最优化准则 。

平面点集凸壳的快速近似算法

提出并实现了平面点集凸壳的一种新的近似算法——多方向极值法。该算法首先根据用户输入的控制参数,顺序生成一系列极值方向,每个方向有对应的极值表达式;然后扫描平面点集中的点,依每个点的坐标更新各方向上的极值点信息;最后按照一定的顺序装配各极值点并去重,得到该平面点集的一个近似凸壳。实验表明,该算法执行效率高,不但可以单独应用在一些对时间要求比较苛刻而对精度要求不高的场合,而且可以作为快速凸壳算法的一个预处理过程。

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

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

新的高效平面点集凸壳构建算法

提出一种新的平面点集凸壳构建算法,算法基于角域处理的过程对点集分而治之计算凸壳,基于特征角计算的方法成对查找角域特征点,利用初始角域划分和角域更新的机制不断缩小问题规模,从而迅速逼近凸壳边。针对大规模数据点集,算法又引入迭代思想,利用算法本身对非凸壳点的快速删除能力进一步加速凸壳求解进程,使得算法性能进一步提升,算法时间复杂度和空间复杂度均为O(n)。实验结果表明,这是一个可行、高效而且稳定的算法,易于推广到三维,也容易改进成并行算法。

平面点集凸包快速构建算法的研究

文章提出了一种提高构建凸包速度的新方法。该算法生成一个网格来管理离散点,在淘汰明显不位于凸包上的点时,将对离散点的取舍转换为对格的取舍,计算工作量只与离散点的范围及网格的密度有关,与离散点的数目无关;同时对点集也进行了初略的排序。在求取剩余点集的凸包时,采用了一种先分段求取凸包边界,最后将这些边界合并成凸包的方法,该方法充分利用了剩余点集所具有的有序性。

利用正负划分性求平面点集凸包的最优算法

求平面点集的凸包是计算几何的一个基本算法。目前的算法较多,但这些算法均较复杂,为降低算法复杂性,首先从分析直线的正负划分性入手,利用其来对平面点集进行分类,以简化点到直线的距离计算;然后进一步详细地给出了一种改进的求平面任意散乱点集凸包的新算法。该算法在搜索凸包时,较目前流行的算法中所采用的前瞻回溯法既简单又速度快,该算法较传统的算法更是优越,尤其他不需要计算角度和欧氏距离。结果表明,利用该算法求任意平面散乱点集凸包不仅计算准确,而且计算过程中仅仅用到加、减、乘、比较运算。这样不仅使算法的每一步骤的时间复杂性大大降低,而且也使得整个算法的时间复杂性大大降低。经过分析,该算法也是一个最优的算法。

任意平面区域的自动三角剖分

提出平面区域内点集的新的自动生成法以及更加通用、健壮的任意平面区域的Delaunay三角剖分法 .前者同时保证新生成的点均位于域内 ,点的疏密程度连续变化和最终网格具有良好形态 ;后者在不添加辅助线 ,不改变原有点集和不增加编程难度的前提下 ,统一解决了任意平面区域 (多连通、多点共圆和非凸 )的自动三角剖分问题 ,并讨论了计算机数值精度问题 .

基于海量数据的二维凸包快速生成算法

凸包算法是计算机几何的基本问题之一,在很多领域应用广泛。传统的凸包生成算法在处理大容量数据时,表现出的时间复杂度相对较高而且凸包生成速率较低,已经不能满足实际海量数据的需求。为解决这一问题,提出了一种面对海量数据的快速凸包生成算法。该算法通过对散乱点集分区、一遍扫描排序,确定散乱点集边界,快速处理边界点集中处于共线的点等一系列预处理操作,快速排除凸包内部的点,缩小了问题规模,避免了对不在凸包上的点集的扫描处理,明显地缩短了凸包的求取时间,可保证最小凸包的快速生成。该算法极其简单,时间复杂度较低,理论上可达到o(nlogn),有利于凸包生成速度的提高。与传统算法进行了同步对比实验,结果表明,该算法运行有效性较好,且具有较好的应用前景。

平面散乱点集凸包的快速生成算法

凸包问题是计算几何的基本问题,在实际工程中得到了广泛的应用。传统的凸包生成算法一般需要两个步骤,首先将离散点按照某种特性排序,然后进行凸包生成。依据快速排序算法的思想,提出一种"一步法"构建平面点集凸包的算法,将构建平面点集的凸包问题与排序问题结合起来,在排序过程中快速生成点集凸包。整个过程达到时间复杂度下限O(nlogn)。该算法在"河北省蓄滞洪区信息管理系统"中得到了实际应用,效果理想。

基于有序点列的平面点集凸包的新算法

提出了一种基于有序简单多边形的平面点集凸包快速求取的改进算法,新的算法能够避免极值点重合的问题。本文算法不仅达到了O(nlnn)的理论时间复杂度下限,而且算法简单,易于实现。

长江口北槽水域的Delaunay三角剖分

为了进行长江口水动力过程等的有限元数值模拟 ,研究了任意平面区域的 Delaunay三角剖分和基于背景网格等值线点集的新的自动生成方法 :在局部三角形内得到等值线、进行自动加点 ;改进了任意平面区域的 Delaunay三角剖分法 ,与行波法结合 ,从区域边界向域内逐步三角化 .前者简化了自动加点算法 ,保证新生成点均位于域内、疏密连续变化和最终网格具有良好形态 ;后者则统一解决了多连通、4点共圆和非凸域的自动三角剖分问题 ,逐步减少人为给定边界的影响 ,从而减少了算法的运行时间 .据此开发的软件包可动态监控点、网格的生成过程 ,并经大量的测试、验证 ,应用于长江口北槽水域的自动加点和三角剖分 。

基于二分法判定点集是否在多边形内部的算法

提出一种基于二分法判定点集是否在多边形内部的算法 ,根据多边形 L的顶点和边分布的情况 ,分割平面为一组平面区域的有序集合 R,判定 R中每个区域是否在多边形 L内部 ;对于点集 S中的点 p,用二分法搜索 R,找到点 p所属的平面区域 ,从而判定出点 p是否在多边形内部 .该算法在最坏情况下的时间复杂性为 max(O(n log m) ,O(tm log m) ) ,其中 n为点集 S的点数 ,m为多边形 L的顶点数 ,t为多边形 L所有顶点的 X坐标的不同取值个数 .在一般情况下该算法比已有的算法效率更高 .

周培德三角剖分不是最小权三角剖分

平面点集的 (欧几里德 )最小权三角剖分问题是计算几何和算法领域的一个长期悬而未决的公开问题 .周培德于文献 [1]中提出了一个新的平面点集三角剖分算法 ,并称该算法能够获得最小权三角剖分 .文中通过给出反例 ,证明了该三角剖分不是最小权三角剖分 ,因此 ,最小权三角剖分问题仍有待于进一步研究 .

平面非规则曲线的一种快速识别与匹配算法

平面非规则曲线的识别与匹配主要用于图像识别、物体匹配等领域。在综合研究比较国内外的研究成果后,提出了一种新的快速提取特征进行筛选而后进行细节比对与匹配的方法。该方法首先通过提取构成平面非规则曲线的一系列离散点的关键特征进行快速筛选,而后逐步比对细节特征,分析其变化趋势,对平面非规则曲线的匹配有着较为满意的匹配效果。该方法相比现有的匹配方法,具有识别与匹配速度快,准确率高,适应性强等优点。