一种两维三角剖分的新算法

提出一种两维三角剖分的新算法,算法首先应用求两维点集凸包的Graham扫描法,求出两维点集的凸包,然后将凸包包含的点从原有点集中去掉,求出剩余点集的凸包.如此递归应用Graham扫描法求出一系列凸包,并将原始区域划分为多个独立的子区域,然后利用本文中提出的方法对2个凸包之间的子区域进行三角剖分,从而实现对整个原始区域的三角剖分.     

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

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

线性拓扑空间的一种广义内点

给定两个线性拓扑空间X和以及Y的一个含原点的凸尖锥C，对X的子集定义一种与连续线性算子空间L（X，Y）和C相关的广义内点，引入L（X，Y）中算子与X的子集垂直的概念，刻画的集的广义内点与算子垂直该集的某种等阶性，给出广义内点的性质及与通常拓扑内点、代数内点和集的仿射包与凸包等之间的关系，证明了凸集的广义内部仍是凸集和Banach空间的非空可分闭凸集的广义内部非空等结果，并举例说明了广义内点与代数内点和拓扑内点的相异性和宽泛性。     

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

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

改进核空间对称稀疏表达用于高光谱波段选择

提出改进核空间对称稀疏表达(IKSSR)降维方法来解决高光谱影像(HSI)的波段选择问题.该方法利用核函数方法和稀疏系数的二值约束条件改进对称稀疏表达模型,在映射得到的核空间构建包含所有波段向量对应的数据点的凸包,通过寻找最小凸包的原型点实现波段子集的优化选择.改进核空间对称稀疏表达方法采用矢量量化策略初始化波段子集,利用块坐标下降方法将非凸问题转换为凸目标函数优化问题,实现目标波段子集选取.基于两个公开高光谱数据集,对该方法和4种主流的波段选择方法进行实验比较研究.实验结果表明,利用改进核空间的对称稀疏表达方法得到的总体分类精度优于对称稀疏表达模型和其他3种方法.     

平面散乱点集凸包并行算法

提出一种构造平面散乱点集凸包的线性算法,它所需的乘法次数不超过Ｏ（ｌｏｇ＾３ｎ）,从而使该问题的计算复杂度在数量级上达到最优。     

基于凸集投影轮廓的透视文本灭点探测

提出了一种基于凸集投影轮廓的透视文本灭点探测方法.通过构建d邻域连接成分的凸集,并对这些凸集进行投影轮廓分析,可以快速确定水平灭点.在探测到水平灭点的基础上,对文本全部前景像素凸集的投影轮廓分析,可以快速探测到垂直灭点.试验结果表明该方法是有效的.     

非凸区域上SPH计算结果后处理方法研究

系统考察了利用Delaunay三角化实现SPH(smoothed particle hydrodynamics)算法后处理的途径.针对非凸物质域上SPH粒子点集的最小凸包的Delaunay三角化,会得到一些并不属于物质域的空白单元,提出一种"单元称重"算法,通过SPH求和近似获得单元的加权质量,利用不属于物质域中的空白...     

平面有限点集最小凸包集的计算方法

给出了平面上有限点集ｐ１,ｐ２,···,Pｎ最小凸包问题的计算方法．     

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

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

一种简单多边形剖分的算法及实现

多边形剖分在计算几何、计算机图象、图形处理中的是一个经典问题。本提出一种新的算法，它把简单多边形剖分为凸多边形且使产生的凸多边形数目最少。     

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

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

超立方体计算机上的平面凸壳算法

给出了在超立方体结构的计算机上，求平面点集的凸壳的一个算法，并分析了算法的正确性和时间复杂性。     

基于凸包切割的不规则三角网及其邻接关系的生成算法

不规则三角网(TIN)是一种重要的数字高程模型,它一般是基于离散采样点来构建的;构建TIN的算法可归结为由二维平面内的离散点生成Delaunay三角网.目前有很多Delaunay三角网生成算法,但不足之处是已有的算法对三角形之间邻接关系的维护缺乏具体的论述和明确的约定.作者按照凸包切割的思想提出了一种完整的算法,并对三角网的生成和三角形邻接关系维护的具体步骤和约定做了详细论述.编程实验表明:本算法能够正确地将凸包剖分为三角形,且能够保证三角形之间具有正确的邻接关系;当将剩余的非凸包顶点的离散点插入已有的三角形时,仍能保持三角形之间的正确邻接关系.     

简单多边形凸包的算法

给出了一种求任意简单多边形凸包的算法.算法中采用了逐次删除凹顶点排除非凸包上的点直至没有凹顶点,从而求得凸包的思想.其几何意义明显,易于编程实现.该算法的时间复杂度为顶点个数的线性次乘法、线性次减法及顶点个数与其对数乘积次比较.给出了准确的时间复杂度的上界.     

用优化凸包法作B—Spline曲线的求交运算

本文在分析B-Spline曲线所具有的几何特性的基础上,提出了用优化凸包方法,作B-Spline曲线的求交运算,内容包括B-Spline曲线与直线求交、B-Spline曲线与圆弧求交及B-Spline曲线与B-Spline曲线求交。 本算法主要从工程应用的实用性出发,首先将B-Spline曲线作离散处理,然后为了提高求交速度,依据其理论,对B样条曲线的凸包多边形进行了优化处理,使得凸包多边形的包括范围大为减小,在判断该优化凸包是否与直线、圆弧或另一样条曲线段的优化凸包相交的前提下,作求交运算。求交精度随B-Spline曲线离散精度的提高而提高。     

网格计算机上的平面凸壳算法

给出了二维网格结构的计算机上求平面点集的凸壳的一个算法，并分析了算法的时间复杂度。