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

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

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

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

基于凸多边形顶点检测的肝脏CT灌注图像肋骨和脊椎骨分割方法研究

在参考肋骨和脊椎骨解剖学位置特征基础上,设计了高效的基于凸多边形顶点检测的肋骨和脊椎骨检测和分割方法.该方法首先针对肝脏CT灌注图像的基本特点,采用高斯滤波和最大相关准则法进行二值化;然后基于凸多边形检测的方法,对肋骨和脊椎骨二值化区域进行分割.实验结果表明,该算法有效地实现了肝脏CT灌注图像中肋骨和脊椎骨的分割.因计...     

点集在凸多边形内外判断算法的拓扑映射方法

提出了基于拓扑映射的点集在凸多边形内外判断的新算法。首先做凸多边形各顶点的拓扑映射点,然后将每个检测点的映射点与其插值,从而只需判断该点和凸多边形其中一条边的关系就可得出其与凸多边形的位置关系。     

任意多边形三角剖分的算法

提出了将任意多边形三角剖分的算法．其方法是，首先确定多边形各顶点的凸凹性，然后不断切割多边形的不规则部分，使其成为凸多边形，最后对凸多边形进行三角剖分．证明了算法的正确性，并对该算法的复杂性进行了分析．     

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

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

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

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

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

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

基于凸剖分的点在多边形内的高效判定

提出一种点在多边形内的快速判定算法.与这方面已知的最快算法相比,新方法在预处理时间、空间需求和判定计算等方面,均达到了相同的复杂度,且没有奇异情况,能运算更快,甚至快一倍多.其步骤是:将一个多边形剖分成一些凸多边形,并进行二叉树的组织管理;然后,判断一个点是否在该多边形内时,先根据二叉树找到最可能包含该点的凸多边形,再判断该点是否位于该凸多边形内,就可完成判定计算.     

基于简单凹多面体的凸剖分算法

本文依据凹多边形的特征,把其分为梳状多边形和普通凹多边形,并采取不同的剖分策略。对于梳状多边形,依据其特征采用角平分线划分,能够得到最少数目的凸多边形;而对于普通多边形以对角线划分为主,角平分线划分为辅,每次能够划分出包含顶点个数尽可能多的凸多边形,最终能够得到次最少数目的凸多边形。从而减少计算Minkowski子和的数目,提高了整个Minkowski和求和算法的速度。     

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

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

避障问题最短路径的两级动态规划算法

研究了任意点对的平面避障问题.用凸多边形表示障碍物,凸多边形的集合构成障碍环境.在此基础上,提出了一种新的路径规划思路:对图结构进行扩展,用传统的Floyed算法进行一级规划;对传统Floyed算法扩展后进行二级规划,很好地解决了任意点对的平面避障问题.利用矢量间夹角的关系来判断障碍环境中点对的连线是否交叉于多边形.经理论证明和算例验证,该算法方便简洁,容易实现,表明了算法的正确性.     

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

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

确定任意多边形中轴的算法

提出确定凸多边形中轴和任意简单多边形中轴两个算法,其基本思想是利用与多边形两条边或三条边等距离的点的轨迹。算法的时间复杂性均为线性的,优于Ｌｅｅ算法（１９８２年）和Ａｇｇａｒｗａｌ算法（１９８９年）。与Ｃｈｉｎ等人提出的算法（１９９９年）具有相同的时间复杂性的阶,但思想方法完全不同,并且产生的结果也不相同,该算法获得直线段树,更有利于应用。     

一个简单多边形凸单元剖分的算法

通过分析剖分得到的凸多边形的结构特点，发现了剖分线的特征性质，并引入可视链及可视度的概念加以描述。在此基础上，给出了一个利用剖分线的特征性质剖分简单多边形为凸多边形的剖分算法，算法消除了剖分后存在部分凸多边形可以合并的现象，既能使剖分得到的凸多边形数目较少，又能使得到的剖分有较好的形态质量。实例表明算法具有较高的运行效率，因此有很好的实用性。     

改进的加权部分简单多边形为凸多边形的算法

对加权剖分简单多边形为凸多边形算法的权函数做了改进,新的权函数容易计算,可以反映在点对间加入部分线时获得剖分在形态质量方面的性质,因此可以用来引导剖分。给出了一个利用这种权函数加权剖分简单多边形为凸多边形的算法实现步骤,讨论了所建立算法的性质。结果表明算法既能够使剖分得到的凸多边形数目较少,又能够使得到的剖分具有较好的形态质量,因此有很好的实用性。     

判定凸多边形可移动性算法的推广

文［１］研究了两个凸多边形可移动性问题的最优判定算法，讨论了简单多边形Ｐ和凸多边形Ｑ的可移动性问题。提出了一种与［１］具有相同时间复杂度的最优算法。