求凸壳顶点的一种算法

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

GENOCOP算法的初始种群的确定

针对遗传算法求解具有凸可行域优化问题使用随机法产生初始种群容易造成早熟收敛,提出用凸可行域的部分顶点作初始种群,将新方法应用于具有线性约束的数值优化问题,计算示例结果表明该方法是一种可行而且有效的优化算法.     

一种判定简单多边形可视顶点的算法

简单多边形可视顶点的判断是计算几何的一个基本问题,广泛应用于许多领域。尤其是在凹多边形凸分解问题中。而作为其基础的判断顶点可视性的算法却极少,既有算法本身过于复杂,不利于实际应用。本文参考有关判断点在多边形内外的算法,提出了解决判定简单多边形可视顶点对的新算法,应用于软件CSforecast,实践证明该算法具有简洁,可靠、运行速度快等特点。     

Delaunay三角剖分的递进构造算法

提出一个计算有限点集Ｓ的Ｄｅｌａｕｎａｙ三角剖分的递进算法，本算法通过对点集Ｓ进行预处理，使得每次插入的点落在已处理点集的凸壳外，从而减少了查找第一个删除顶点的时间，并且能够在最优时间内维持凸壳，克服了Ｂｏｗｙｅｒ算法的缺陷。     

基于超顶点交流策略的并行蚁群算法

通过分析影响并行蚁群算法性能的诸多因素，以提高算法效率减少通信量为主旨，提出了1种基于超顶点交流策略的并行蚁群算法．在该算法中，处理机之间交流的内容不再是最优解或信息素矩阵，而是由若干个顶点组合成的超顶点，从而改变了计算粒度；其次，又提出了1种更忠实于真实蚁群信息系统的基于信息素递减的信息素更新方法，减少了最优解对蚂蚁后选择路径上信息素的影响．通过对TSP进行的实验表明，与其他交流策略的并行蚁群算法相比，该算法有较强的全局收敛性和更快的寻优速度．     

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

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

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

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

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

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

应用思维进化计算求解顶点着色问题

应用思维进化计算求解顶点着色问题,给出求解给定图的色数、最小着色的算法。介绍了顶点着色问题的编码与解码方法、特征、信息矩阵的概念,从而应用思维进化计算的趋同和异化求解该问题。实验结果表明该算法是求解顶点着色问题的一种新的有效算法。     

一种Douglas—Peucker加速算法

本文分析了Douglas—Peucker（DP）算法的复杂度,表明在最坏情况下为O（n^2）其中n为矢量压缩前的顶点数。接着,提出了一种基于路径凸壳的算法,在最坏情况下的复杂度仍为O（nlog2）,与常规DP算法在最优情况下的复杂度相同。     

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

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

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

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

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

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

求解货郎担问题的几何算法

提出了求解货郎担问题的一种几何算法，它的时间复性为：Ｏ（ｎ＾３／ｍ）次比较，Ｏ（ｎ＾２）次求距离运算与Ｏ（ｎ＾３／ｍ＾３）次加法运算，其中ｎ，ｍ分别为点集的点数和凸包顶点数。     

求解简单多边形核的新算法

利用凹顶点间的位置信息,提出一种自动选择凹顶点来裁剪多边形的新求核算法.在选定凹顶点进行裁剪的同时,未选定的凹顶点集被分离成为待继续分离的凹顶点集和待裁剪包含核的凸多边形的凹顶点集.通过逐步对核的存在性进行判定,可较快对多边形的核为空集的情况加以报告.在多边形有核的情况下,裁剪过程不断更新包含核的多边形,快速求解得到包含核的凸多边形,从而可以采用凸多边形的线裁剪算法来加速求核计算.新的求核算法在快速判断出空核和提高求核速度方面都有较大改进.     

基于足底压力的人体重心轨迹包络面积算法

为了评估人体平衡功能,需要计算人体重心轨迹包络曲线的面积,提出了一种包络曲线的计算方法。首先,通过足底压力采集系统获取足底压力数据,计算得到人体重心点;然后,提出了一种基于斜率逐步比较的重心轨迹包络凸多边形构造法,通过斜率比较筛选出包络凸多边形的顶点;最后,根据斜率大小对凸点进行排序,通过三角形面积累加得到包络凸多边形的面积。计算实例证明,提出的算法与经典的快包法相比提高了人体重心轨迹包络曲线面积的计算速度,算法具有良好的稳定性,稳定性差值在±0.01 s之内,算法的时间复杂度为O(nlgn),可有效应用于人体重心轨迹包络面积的计算。     

GIS中散乱点集凸包的快速算法及编程

在地理信息系统(GIS)中,不规则三角网(TIN)的生成及数字地面模型(DTM)的建立都会用到点集凸包的计算.通过研究了传统凸包算法,并对其进行改进,提出简单快速的点集凸包改进算法.经过验证,新算法可准确快速地求出点集凸包.     

在MIMD－CREW模型上确定凸多边形可碰撞区域的并行算法

设Ｐ和Ｑ是平面内任意两个互不相交的凸多边形，目前确定Ｐ与Ｑ的可碰撞区域的最佳串行算法时间复杂度为Ｏ（ｎ＋ｍ），其中ｎ和ｍ分别为凸多边形Ｐ和Ｑ的顶点个数．在该算法的基础上构造了一个易于并行化的求支撑点的串行算法，进而给出了在ＭＩＭＤ－ＣＲＥＷ模型上确定可碰撞区域的并行算法，其时间复杂度为Ｏ（（Ｓ＋ｌｏｇ＿２（ｎ＋ｍ））ｌｏｇ＿２（ｎ＋ｍ）／ｌｏｇ＿２Ｓ），其中Ｓ为处理机个数     

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

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

旅行推销员问题凸包方法的性能比分析

在欧几里德平面上证明了旅行推销员问题的凸包方法的性能比上界为n／2,同时给出了凸包随意插入算法的性能比可以接近n／2的例子。另外,对凸包增量最小插入法、凸包最近插入法及凸包最近加入法给出了性能比不超过3的证明。