一种构建平面离散点集凸包的算法研究

本文提出一种矢量运算方法确定平面离散点集凸包，其原理是在构建凸包前，通过矢量计算判别出位于凸包多边形内部的点，预先将其删去，保留凸包多边形外部边缘的点，从而减少了构建凸包的离散点数目，提高运算速度。新算法达到O(n1ogn)时间复杂度下限，简单且易于实现。     

平面多边形简单性确定及其定向算法

给出了一个确定平面多边形为简单多边形的实用算法，同时，又给出了简单多边形为顺时针或逆时针走向的充要条件，利用这些条件，可较好地解决简单多边形走向判断的问题，且易于实现。     

可形变简单多边形重建算法

构造了一个多边形边的形变模型，利用格雷厄姆快速算法得到平面点集凸包，通过添加点的方法有选择地修正凸包的一些边界，使得经过形变后的多边形在形状上更加接近平面点集的外形轮廓，分析了形变过程中边界附近点集的疏密对插入新点的影响，提出了2种插入新点的方法，该算法与点集中的点次序独立并且能够在一定程度上控制多边形的精度，实验表明该算法结果良好。     

采矿计算机辅助设计中的多边形运算

从图形区域化描述及图素定向方面着手，引入特征值概念，对采矿计算机辅助设计中的多边形运算进行了全面研究．给出了简化多边形运算的计算公式，讨论了多边形算法构造的一般过程．最后给出了通用多边形运算算法，并用实例进行了验证．     

凸包算法的变形及应用

本文对计算几何中的基本算法之一：凸包问题的卷行李法,进行了变形,并利用新算法解决了求两个任意多边形的并、轮廓等问题．     

一种改进的局部多边形填充方法

本文提出了一种实现等值带彩色填充的改进算法。该算法不需要进行等值线的追踪,只需要进行离散数据网格化即可进行填充。同时在对多边形填充过程中使用了凸包算法,解决确定多边形顶点顺序问题。编程实现容易,计算速度跟网格密度相关而与绘图区域无关。文中给出了具体算法,同时展示了相关示例。     

坐标变换法求多边形的凸凹性

介绍一种求多边形凸凹性的亲手虎法。本算法通过标公式推导出计算多有任意顶点凸凹性的算子，算子的正负性决定了对应在顶点的凸凹性，进而可求多边形的凸凹性，一法也是求多边形最小凸包的有效方法。     

坐标变换法求多边形的凸凹性

介绍一种求多边形凸凹性的新算法.本算法通过坐标变换公式推导出计算多边形任意顶点凸凹性的算子,算子的正负性决定了对应顶点的凸凹性,进而可求多边形的凸凹性.同时,本法也是求多边形最小凸包的有效方法.     

一类六角系统的完美匹配

对于峰、谷点均位于其凸包的边界上的一类六角系统,本文给出了一个较简单的求完美匹配的算法。     

确定任意多边形顶点凸凹性的快速算法

给出了一种确定任意多边形顶点凸凹性的快速算法．该算法的时间复杂度是多边形顶点数目的线性函数     

近于凸函数的一些子类

文中给出了近于凸函数的一些子类，给出了这些子类的系数界。增长定理，导函数增长定理，导函数的幅角估计，一些形式的积分平均，给出了这些子类的闭凸包，导函数的闭凸包，给出了闭凸包的极端点及导函数闭凸包极端点的部分刻画，特别地推广了文献〔１〕中的结果。     

改进凸包的贝叶斯模型显著性检测算法

针对传统贝叶斯模型算法对图像显著区域检测精度需要进一步提高的问题,提出一种改进凸包的贝叶斯模型显著性检测算法。首先,利用流行排序算法对图像进行前景提取,提取的前景区域作为贝叶斯模型的先验概率;其次,利用颜色增强的Harris角点检测算法检测图像在RGB,HSV,CIELab 3个颜色空间中的特征点,分别构造RGB,HSV,CIELab空间的凸包,求取3个颜色空间下的凸包的交集;再次,通过贝叶斯模型根据先验概率、凸包与颜色直方图结合得到的观测似然概率计算获得显著性区域图;最后,将新算法在两大公开数据集MSRA和ECSSD中进行测试。结果表明,新算法能够有效抑制背景噪声,完整检出显著区域,F-measure值在MSRA和ECSSD数据库中的测试结果分别为0.87和0.71,准确率-召回率曲线在复杂图像数据库高于传统经典算法。新算法改进了传统经典算法的检测效果,进一步提高了显著图检测的准确性。     

关于某些几何覆盖问题的算法

提出了求覆盖平面点集最小圆的算法与平面点集中最大空圆的算法．其基本思想是，先把点集Ｓ分成若干层，然后逐层求不包围Ｓ中点的最大圆并保留之，最后找半径最大的圆．对于包围点集Ｓ的最小圆问题，本文提出的算法是，先求点集Ｓ的凸包，然后再求包围该凸包顶点的最小圆．     

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

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

多边形内点集的三角剖分算法

提出了一种多边形内点集的三角剖分算法，该算法采用逐层求凸壳，对不在凸壳边界上的多边形顶点给予特殊处理，然后逐层分割环域成三角形序列，最后优化各三角形的边长，改变分割方式，使之能得到最短长度或接近最短长度的三角剖分．     

基于自适应遗传算法的局部可重配置机床碰撞检验方法

为研究局部可重配置机床各模块间运动关系并防止模块间可能存在的碰撞干涉现象,针对局部可重配置机床部分模块需要更换或升级的特点,通过分析模块之间碰撞检验的拓扑结构,提取需要进行碰撞检验的模块的顶点坐标,运用构造凸包的方法,采用遗传算法计算凸包之间碰撞干涉情况,并使用自适应遗传算法对计算过程进行优化.结果表明该方法有效地提升了碰撞干涉计算效率和计算速度.     

支持向量机的最大间隔和对偶性

最初出现的支持向量机理论是基于2类线性可分问题的.针对线性可分情况,研究表明线性硬间隔分类机的对偶问题与凸壳问题(平分最近点法)是等价的,线性硬间隔分类机的最大间隔与凸壳问题的2个最近点的距离相等:针对非线性可分情况,研究表明线性软间隔分类机的对偶问题与缩小的凸壳问题(推广的平分最近点法)是等价的,线性软间隔分类机的最大间隔与缩小的凸壳问题的2个最近点的距离相等.对支持向量机分类问题给出了直观解释.     

寻求中国货郎担问题最短回路的多项式时间算法

研究求解中国货郎担问题最短回路的多项式时间算法。首先利用计算机几何凸壳与中轴的结构将集划分尤其中干个子点集,然后反复采用求子点集凸壳及划分科余子点集的方法,求得通过子点集的子路径,最后将各子路径连接成一条回路。中国货郎担问题存在多项时间算法求得最短回路。     

基于夹角的二维凸包改进算法

二维凸包问题是计算几何领域的经典问题之一,在地理信息系统中有广泛的应用.在凸包中,位于两凸点之间直线上点也在凸包上,但不是凸点,如何寻找凸点是凸包算法的关键.提出了基于夹角的平面点集凸包改进算法,以最大夹角,按顺时针的方向可得到所有的凸点,当满足最大夹角的点不唯一时,以离当前凸点最远的点为凸点.