基于近似凸壳的直线度误差评定方法

针对需要快速求解直线度误差的场合,提出了利用二维空间中测量点集近似凸壳评定直线度误差的近似算法,在此基础上构造真实凸壳求解直线度误差最小域值的精确算法.针对近似算法的原理误差进行误差分析,得到了近似算法的最大误差值.精确算法首先得到点集的近似凸壳,再插入近似凸壳外的点得到真实凸壳,然后查找该凸壳的对极元以求解直线度误差.通过仿真示例对提出的方法进行验证,结果显示算法是有效的,并且具有较强的鲁棒性和稳定性.     

车辆定位导航系统的新定位算法

依据大数定律及其相关的假设,用计算几何的若干知识,设计车辆定位导航系统的一种新定位算法.该算法通过计算凸壳、凸多边形三角剖分、凸多边形面积及直径等诸量获得车辆运行的近似路线.计算结果表明,用该算法可以提高车辆定位导航系统的定位精度,并优于基于卡尔曼滤波的GPS/INU/MM组合导航算法的结果.     

概率约束优化问题的一个光滑D.C.近似

概率约束优化问题通常是非凸且非光滑的,因而在数值计算上存在困难.基于Pinar-Zenios光滑和函数,建立了概率约束优化问题的一个光滑D.C.近似问题,提出了求解光滑D.C.近似问题的序列凸近似(SCA)算法,分析了初始解的选取方法,并讨论了算法的收敛性,收敛定理表明可以由SCA算法可以得到光滑D.C.近似问题的KKT点,并且在迭代过程中,确保了由SCA算法生成的解序列的极限点是近似问题的KKT点.     

基于凸壳技术的Delaunay三角网生成算法研究

TIN作为DEM的一种重要表达模型,其生成算法一直备受关注。首先对传统的生成算法原理进行总结,并针对其特点进行了分析,对利用凸壳建立TIN的原理和方法进行简单描述。由于许多计算几何学对点集进行限制以简化凸壳的建立过程,对凸壳的生成过程进行了改进。在点集的排序过程中剔除重复点,将点联入原凸壳过程中,排除共线这一特殊情况,建立新的凸壳,直至所有点都被包含在凸壳中。至此,三角网建立完毕。通过对三角形公共边进行LOP优化,使其满足Delau-nay三角网的特性。当所有三角形满足特性时,Delaunay三角网构建完毕。该算法的优势在于构网速度较快,并能够对重复点进行处理,同时在生成网的过程中对共线这种特殊情况进行处理。     

伪单调变分不等式近似点算法的收敛性

将近似点算法推广到具有伪单调映射的变分不等式.经典的近似点算法的子问题利用范数平方作为辅助函数.将一个可微强凸的函数作为辅助函数,在有限维空间和Hilbert空间上讨论伪单调算子近似点算法的收敛性.     

求解一类非凸变分不等式的近似点算法

介绍和考虑了一类新的非凸变分不等式,这类变分不等式包括了一些已知的和新的非凸变分不等式作为特例.利用一致r-近似正规集的概念,建立了这类变分不等式和不动点问题的等价关系.利用该等价关系,给出了一个求解此类非凸变分不等式的近似点算法,并证明了该算法在适当的条件下收敛.     

求解k(<10)-中心问题的快速算法

提出求解3-中心问题、4-中心问题、5-中心问题及k(<10)-中心问题的算法.设计该算法的依据是覆盖点集的凸壳必覆盖点集.算法首先判定点集凸壳的形状,然后确定k个圆的排列方式,最后以确定方式计算圆心位置.证明了算法的正确性并且分析了算法的复杂性.     

寻求多边形链顶点凸壳的算法

提出一种计算简单多边形链顶点凸壳的算法，基本思想是分段计算，在每段的计算中，先分4种不同情况计算出边链L1，然后利用一种技巧将L1上的部分顶点排列成顶点角递增序列，构成边链L2，最后对L2进行倒查，删去非凸壳顶点，剩下的点即凸壳顶点，该算法不仅易于实现，而且其时间复杂性是线性的。     

基于凸壳的支持向量机训练集选取算法研究

基于对支持向量机训练算法的研究与理解,针对支持向量的几何特点,结合凸壳的几何性质,对支持向量机训练算法的工作集选取进行了改进.在LIBSVM的环境下进行了对比分析.数值实验表明,改进的基于凸壳的训练数据选取算法缩短了训练时间并保持了良好的泛化能力,具有一定的参考价值.     

一类非凸规划的分支定界算法

针对一类非凸规划问题(NP)提出有效的分支定界算法.首先,利用目标函数的特性将其转化为等价的极小化问题(P),通过对其可行域的细分和求解一系列凸规划问题,不断更新(NP)全局最优值的上下界.为提高计算效率,一个问题的最优解作为下一个问题的初始解,并提出了新的删除技术.理论上证明该算法是收敛的,数值试验结果表明算法是有效可行的.     

金字塔凸壳算法的并行化处理

提出了在金字塔凸壳算法基础上的并行算法.在由多个PC机相互连接所构成的机群并行计算系统之上,采用消息传递方式执行该算法,经过与原串行金字塔算法进行对比,验证本并行处理算法的正确性、可行性和高效性.     

关于凸包及回收锥性质的研究

主要是应用凸分析中的凸集和回收锥的相关结论,对有限个凸函数集进行研究,由此得到了关于凸函数集{f1,…,fm}的凸包及回收锥的两个重要性质.     

一种基于凸包的Delaunay-TIN生成算法及优化

针对基于凸包的Delaunay三角网的生成,提出了环边增长比较判断法,并且采用区域分割、重心检测法、矩形区域检测法等方法进行了合理优化,最终在计算机上将其实现,提高了基于凸包的Delaunay三角网生成算法的效率.     

环状分布平面点集的凸包快速生成算法

针对栅格辅助法在处理环状分布平面点集时计算效率较低的问题,提出了一种格网2次处理算法.通过比较离散点所在网格的空间位置关系,经2次剔除点集中绝大部分不可能成为凸包顶点的内点,减少了参与Graham扫描的点数,提高了计算效率.实验结果表明,与栅格辅助法相比,格网2次处理算法能够明显提高处理环状分布平面点集的效率,而且对于其他空间分布较为均匀的平面点集的处理效率也有一定程度的提高.     

基于单调链法的凸壳三角剖分算法研究

在分析应用相关定义的基础上，该文提出了一种基于单调链法的凸壳三角剖分方法。这种算法的计算复杂度优于标准的Delaunay算法，有效性也比许多凸多边形算法要突出，是一种行之有效的快速算法。将它用于网格重新剖分处理，在矢量图形网格的简化、优化、压缩以及传输中都具有现实的应用意义。     

求凸壳顶点的一种算法

提出了一种求平面有限点集凸壳顶点的算法,并分析出该算法的时间复杂性是线性次乘法和O(nlogn)次两个数的比较。     

多元凸包函数Lip连续性

本文指出并纠正文献［１］中有关凸包函数一些引理证明中的疏漏．证明了在严格凸域中凸 包函数的连续性．用简明的方法证明了凸包函数的表现定理，并用几何方法证明凸包函数的Ｌｉｐ 连续性．     

基于凸包的棋盘格角点自动识别与定位方法

 采用Harris方法提取角点,应用对称算子剔除棋盘格外圈角点与伪角点,基于灰度梯度方法精确提取棋盘格亚像素角点。在此基础上,提出了基于凸包的棋盘格角点分层识别与自动定位方法,实现了棋盘格角点物像坐标的自动匹配,从而可实现摄像机自动精确标定。实验结果表明,该方法具有较高的精度与可靠性,适合于摄像机在线自标定。     

基于凸壳的点群目标空间方向关系研究

空间方向关系是GIS的重要理论问题,目前关于它的研究仍处于很不系统的阶段,本文主要结合凸壳的概念对点群目标间的空间方向关系进行分类,并给出了两点群间的空间关系算法,以实现对点群目标的空间关系理论的探索性研究.