改进的三维点集凸包求取算法

为提高三维点集凸包的求取效率,提出充分利用凸包极值点和性质改进的三维点集凸包求取算法.首先,求出三维点集中的极值点,并由它们形成初步凸包;其次,根据初步凸包与点的位置关系,排除其内部点;最后,依次考察其外部点,求出符合要求的点集、棱边集和面集,并对凸包进行扩展,得到凸包的点集、棱边集和面集.与普通算法进行时间的复杂度分析比较及实验表明,该算法效率较高.     

点集模型的直接可见性测试与基于视点的绘制

点集模型作为一种新兴的三维几何形体表示形式,近年来备受关注.本文运用点集法向计算与凸包构建等技术,对原始点集模型进行直接可视性计算,并利用可见性计算的结果对点集模型进行基于视点的绘制.算法首先对原始模型进行基于视点的精简,剔除大部分不可见点;再对精简后的模型进行球面对称变换,并构建变换后点集的凸包,进而提取出可见点集;最后运用真实感图形绘制技术实现可见点集的快速绘制.实验证明,本文算法能够快速地计算点集模型中采样点的可见性.该算法可应用于点集模型基于视点的绘制与曲面重建,以及点集模型的阴影绘制等领域.     

基于改进LMedS算法和贪心估计的相位立体匹配

为了改善基于相位测量轮廓术的测量系统测量效率低、系统稳定性差等缺陷,提出一种基于改进LMedS算法和贪心估计策略的快速相位立体匹配方法.首先在LMedS算法中引入平差函数模型,通过及时剔除错误样本减少计算成本函数的累加次数,不仅保持了LMedS算法的良好鲁棒性,而且有效地减少了算法的计算量;用贪心估计策略对改进的LMedS算法获得的初始内点集进行优化,剔除相对匹配程度较差的内点,并用优化的内点集求解基本矩阵,进一步提高算法的估计精度和鲁棒性;最后结合相位立体匹配原理对实物进行了三维重建,分析比较了传统的基于摄像机标定结果的相位立体匹配方法与改进方法的性能.实验结果表明,该方法满足三维形貌测量对实时性、鲁棒性和精度的要求,测量数据完整、可靠.     

基于二维凸包的TSP算法

二维凸包是指包含平面点集的最小简单多边形,广泛应用于GIS.将二维凸包与TSP相结合,提出了基于二维凸包的TSP算法,首先快速凸包算法构造城市点集的凸包,该凸包是经过部分城市点且其余点都在其内部的回路.其次将其余的城市点依次插入回路形成新回路,使新回路的长度增量最小,直至所有的城市点都在回路上.在TSPLIB中的典型实例上的实验结果表明,该算法比简单遗传算法更快得到问题的近似解.     

基于分层学习的三维模型兴趣点提取算法

针对基于学习的三维模型兴趣点提取问题,提出一种兴趣点分层学习的全监督算法.提取三维模型表面所有顶点的特征向量后,将人工标注的兴趣点分为稀疏点和密集点,对于稀疏点使用整个三维模型进行神经网络训练,对于密集点则找出兴趣点分布密集的区域进行单独的神经网络训练;然后对2个神经网络进行特征匹配,得到一个用于三维模型兴趣点提取预测的分类器.测试时,提取新输入的三维模型上所有顶点的特征向量,将其输入到训练好的分类器中进行预测,应用改进的密度峰值聚类算法提取兴趣点.算法采用分层学习的策略,解决了传统算法在模型细节处难以准确提取密集兴趣点的问题.在SHREC’11数据集上的实验结果表明,与传统算法相比,该算法提取兴趣点的准确率更高,出现的遗漏点和错误点更少,对解决越来越精细的三维模型的兴趣点提取问题有较大帮助.     

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

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

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

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

基于凸包改进的流行排序显著性检测

针对传统的基于图的流行排序显著性检测算法仅仅依赖边界背景先验显著图来提取前景种子,影响最后的排序结果,使得显著性检测结果较差的问题,提出结合凸包提取更精确的前景种子进行流行排序的算法.首先提取图像边界结点作为背景种子进行流行排序得到背景估计显著图,并将该显著图二值化得到粗略的前景区域;然后通过颜色增强的Harris角点检测算法获得图像角点,并用其构造粗略包含显著目标的凸包;最后将凸包和前景区域相结合提取更精确的前景种子进行流行排序得到最后的显著图.在3个公开的图像数据集上,与其他经典算法相比,该算法在PR曲线、MAE值和F-measure上均获得了提升.     

基于凸包和网格索引技术的快速TIN生成算法及应用

在原有凸包推进算法的基础上,提出了一种针对散乱点集的快速生成TIN的算法.通过在三角形外接圆的最小网格覆盖中查找点扩展三角形,使得每次查找的点的个数与且只与散乱点的分布有关,而与散乱点集的大小无关;同时利用有向凸包和动态修正前沿圈等技术避免生成重复三角形,从而大大提高了建网的速度.实践证明,该算法具有可操作性和较强的实用性.该算法实现了两类基于不规则三角网数字地面模型的分析应用.     

Two parallel algorithms for the convex hull problem in a two dimensional space

Two parallel algorithms for determining the convex hull of a set of data points in two dimensional space are presented. Both are suitable for MIMD parallel systems. The first is based on the strategy of divide-and-conquer, in which some simplest convex-hulls are generated first and then the final convex hull of all points is achieved by the processes of merging 2 sub-convex hulls. The second algorithm is by the process of picking up the points that are necessarily in the convex hull and discarding the points that are definitely not in the convex hull. Experimental results on a MIMD parallel system of 4 processors are analysed and presented.     

人体重心动摇轨迹包络面积的快速算法

传统的人体重心动摇轨迹包络面积计算方法是先确定包络所有点的凸包形状,再计算凸包的面积,其最优时间复杂度接近O(nlbn)。针对上述问题给出一种近似凸包计算方法,通过计算点集在不同旋转角度下的坐标,查找X轴和Y轴的最大最小极值点,快速标定构成凸包点,确定凸包形状。算法的时间复杂度接近于O(n)。实际应用证明,该算法能满足精度要求,提高人体重心动摇轨迹包络面积计算速度。     

基于凸多边形的凸壳算法

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

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

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

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

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

基于最优凸壳技术的Delaunay三角剖分算法

提出了一种基于最优凸壳技术的Delaunay三角剖分算法。该算法对离散点进行扫描线方式排序，利用最优凸壳技术进行凸壳的生成和三角网联结，最后利用有向边的拓扑结构进行三角网优化。该算法不但避免了所有的交点测试，而且使得新加入点与凸壳边的平均比较次数不大于4，从而实现了高效的三角剖分。     

一种改进的构建凸包的分治算法

本文为构建离散点的凸包提出了一种改进的分治算法，它在查找每一个凸包顶点的同时，通过去除若干非凸包顶点来迅速减小问题的规模。本文对该算法的正确性给出了严格的证明。