一种基于Graham三角剖分生成Delaunay三角网的算法

目的提出一种基于Graham三角剖分生成Delaunay三角网的算法,加快Delaunay三角网的生成速度.方法首先按Graham扫描法对平面散乱点集进行排序,然后将排好序的点通过可见点的判断连接成Graham三角网,最后利用拓扑结构快速进行优化,使其成为Delaunay三角网.结果通过500至10000个点的测试,表明这种基于Graham三角剖分生成Delaunay三角网的生成速度快于传统基于凸包生成Delaunay三角网的生成速度.结论采用可见点表的数据结构以及利用点、边、三角形的有序性的特点构建Delaunay三角网,是提高建网速度的关键.     

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

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

曲面散乱点集的组合三角剖分法

曲面散乱点集的三角剖分广泛应用于三维重建领域.为了更加快速、准确的完成曲面重建,提出了一种组合三角剖分法.此方法将整个剖分过程分为三个步骤:首先借鉴分治算法的思想将整个点集进行区域划分,以降低其拓扑结构的复杂性;之后在各个小区域内依据异侧准则、法向量夹角最大准则、域值距离准则和最小内角最大准则进行直接三角剖分;最后根据三维Delaunay空球准则进行各区域边界的连接,从而完成剖分.实验结果表明,组合法可以准确、快速的实现曲面散乱点集的三角剖分.     

油藏任意约束平面域PEBI网格的生成算法

针对油藏任意约束平面多边形区域提出了一种实用的局部正交化网格（PEBI）生成算法。首先对边界顶点和区域内部散乱点按扫描方式排序，依次扫描各点生成新的三角形，再扫描新生成的三角形中不满足Delaunay准则的三角形，进而不断的处理这些不合理三角形最终完成整个区域的三角网格化，最后连接每个三角彤的外接圆圆心生成PEBI网格。剖分过程中采用了弹性平滑和对角线交换优化方法，很容易实现局部区域的最优化剖分。通过平面映射法就可以应用到油藏的三维PEBI网格剖分，因此本算法具有很好的可操作性和实用性。     

空间封闭点云的八象限三角剖分算法

提出了一种针对空间封闭点云的三角剖分算法.该算法首先根据空间封闭点云的分布特征,将其划分到三维坐标的八个象限中,使每部分点云的包角均小于180°;然后适当旋转各部分点云,使其对应投影平面面积最大化,再运用平面三角剖分方法对其进行三角剖分,从而得到各部分点云的剖分结果;最后将已处理的各部分用三角面片对其边界进行缝合,进而形成空间封闭点云的立体三角化.实验结果表明,该方法剖分速度快、形成的三角网格质量高,能够较好地再现原三维物体的表面特征.     

一种新的平面点集三角剖分算法

平面点集的三角剖分是计算机图形学中一个比较基本的算法,它的用途非常广泛．本文提出了一个平面点集的三角剖分算法,该方法是一种简单、实用、通用的三角剖分算法,并且给出了该算法在有限元网格中得到的剖分效果分析．     

5多边形高质量同构三角剖分的有效算法

为了使平面形状混合得到较好的结果,提出了一种新的构造2个多边形的高质量同构三角剖分的有效方法.通过加入一定数目的Steiner点生成其中一个多边形的质量较好的三角剖分,根据此三角网格中顶点之间的相对位置关系和邻接关系确定另一个多边形的三角剖分,然后利用面积均等方法和其他优化方法对同构的三角剖分同时进行优化.此算法将同构三角剖分的构造转化为一个稀疏线性方程组的求解,可以通过已有的程序库进行快速求解;同时通过约束一些对应特征点的位置,使生成的同构三角剖分具有较好的特征对应.此算法计算量小,运行效率高,对形状复杂的多边形仍然可以得到满意的结果,适合于morphing等实时性的应用要求.     

三维凸包的快速算法

很多情况下点集的凸包只是由其中一部分点的构成,在构造凸包时如能将其内部的点全部或大部分预先去掉,则可大大提高构造凸包的效率,通过地点集的最小包围盒进行剖分和利用凸集的凸性性质,给出了一个新的三维凸包快速算法,与传统方法相比,该方法具有计算简单,效率高的特点。     

三维稀疏散乱点集的直接三角剖分新方法

给出一种三维稀疏散乱点集在三维空间直接进行三角剖分的新方法——在形成初始三角形后对它周围的离散点循环三角化．通过在剖分过程中引入两相邻三角形的最小夹角、最优点搜索半径系数和最小张角这三个剖分参数,实现了任意三维稀疏散乱点集的完全剖分以及非封闭自由曲面边界的自动识别．针对某些特殊复杂曲面上稀疏散乱点集的剖分问题提出了“分部剖分”思想：根据曲面的特征在不同区域设置不同的剖分参数．实例表明,这种直接剖分方法能有效处理任意多连通封闭和非封闭自由曲面上的稀疏散乱点集的三角剖分问题．     

地图中面状要素标注算法的设计与改进

通过对现有的面状要素标注算法的深入研究,对面状要素标注算法采用分类处理.在求解多边形骨架的算法中,改进了求简单多边形的直径算法,提出了一种新的平面点集三角剖分算法,该算法直接以简化的多边形进行三角剖分,并将借用回溯法来解决面状要素标注所产生的冲突.理论分析和实验表明:与已有的标注算法相比,减少了骨架算法求解的步骤,有效的解决了面状要素标注所产生的问题.     

基于散乱点云的快速体积计算法

三维可视化体积计算基本上都是先由散乱点云构建出表面网格模型,然后基于网格模型计算体积,存在计算量大、速度慢的缺点.针对此问题提出一种快速体积计算法,首先使用改进的增量式Delaunay三角剖分对散乱点云进行四面体剖分;然后利用K近邻计算散乱点的拟合曲面和最小生成树,得到各点的法向量;由各点法向量剔除体外四面体;最后计算各四面体体积之和从而得到总体积.实验表明,该算法不仅保证了计算准确度,而且较传统算法大大提高了效率.     

改进的二维点集凸包快速求取方法

凸包问题是计算几何的基本问题，分为平面点集凸包和多边形凸包2类。对传统点集快速凸包算法进行改进．通过找到点集中8个方向的极值点来准确地确定凸包上的部分顶点，得到凸包的粗略逼近，接着在逼近结果上进行遍历，使用链表或栈这样的数据结构，找到逼近结果中连续2个顶点之间的漏检点，从而得到完整的凸包。整个过程达到复杂度下限，且在通常情况下接近线性时间。该方法已经有效地应用于基于控制点的图像配准中。     

求平面点集凸壳的一种新算法

提出了一个求平面点集凸壳的新算法.首先提取点集中的最小外接矩形,并对点集中的点进行分类,删除在最小外接矩形内的点,将剩余的点划分到不同的区间范围内,然后确定不同范围内的点与最小外接矩形顶点构成夹角的最大的点是凸壳的顶点,并以该点作为下次判断的顶点,循环往复,最后得到凸壳的顶点.将顶点顺序连接即为点集的凸壳.     

单域单向水平倾角最小化圈绕凸壳新算法

本文作者实现了对二维点集卷包裹凸壳算法的同构化改进与创新,并依据同构化凸壳构造基本定理,提出效率更高的单域单向水平倾角最小化圈绕凸壳新算法。本新算法的同构化特点是：1）找出给定二维点集的最低点,即Y轴座标值最小点（若有多个最小点,则只取最左的最小点）,并作为凸壳初始顶点（即最低顶点）;2）过最近新顶点,作平行X轴正方向的同向顶点射线,并找出当前点集内对该顶点射线倾角最小的点,以作为逐边圈绕的最新顶点;3）在当前点集分布域中,删除由初始顶点、次新顶点、最新顶点构成三角形所覆盖的全部点。并当所剩当前点集非空时才从“2）”继续作逐边圈绕。     

圆度误差评定中的一种新的删点技术

在圆度误差评定过程中，针对以往几种方法以采样点数据筛选过程中可能出现的误删和错删现象，本文提出一种新的删点技术，即采用凸壳理论实现对特征点的筛选，其实质是将寻找特征点的问题转化为求解壳顶点的问题，利用凸多边形的几何不变性来确保删点结果的准确性和唯一性，并大大简化运算过程中和提高运算速度，经过与实测结果的对比分析，证明了本文提出的删点技术正确可行。     

单叶函数一个新子族的极值点、支撑点及其应用

本文完全决定了G,S(G)的闭凸包与闭凸包的极值点、G的支撑点,且对S(G)的支撑点进行了研究。     

基于凸包算法的二维条码定位

在二维条码识别过程中,只有精确定位条码区域在原始图像中的位置,才能进一步做后续的矫正处理.文中以二维条码Data Matrix为例将计算几何中的凸包概念应用于条码定位,从像素点序列中筛选出凸包顶点以减少待处理像素点的数量.同时利用Data Matrix的定位图形特征设定筛选条件,最终得到用于定位条码区域的凸包顶点.凸包算法克服了传统直线检测算法因全局检测而需要大量存储空间的缺点.实验结果表明此算法能对扭曲或倾斜的二维条码区域进行有效的定位,并减少精确定位消耗的处理时间.     

一种确定高阶Delaunay三角网中可用k—OD边的算法

目的构建高阶Delaunay三角剖分方法的数字地形模型,有效地减少局部极值问题,使得地形模型能更好地反映原始地形的真实面貌．方法提出了一种确定高阶Delaunay三角网中可用k-OD边的方法,该方法首先在任意边uv的两侧分别确定两点,使每个点与uv边形成的三角形的外接圆不包含同侧的点,若这两三角形都为k—OD三角形,则uv边是可用k—OD边．结果用Visual C＋＋实现算法,通过实验验证了算法的有效性,对于具有n个点的点集P,在时间O（nk^2＋nklogn）内可以计算出所有的可用k—OD边．结论选择合适的可用k—OD边生成相应的高阶Delaunay三角网来模拟实际地形,可以有效地减少局部极小的数量,使地形模型更接近于实际地形．