基于顶点间距离性质的凸多边形直径算法

平面点集的直径问题在计算机图形学、模式识别、图像处理、cAD,CAM等众多领域中均有广泛应用,该问题可转化为求凸多边形直径问题.研究得出了凸多边形顶点间距离关系的4条性质,利用这些性质提出一种基于顶点间距离性质的凸多边形直径算法.理论分析和实验结果表明,该算法计算速度快、存储效率高,实用性较强.     

基于夹角符号序列的凸多边形直径算法

对一个凸多边形直径算法———夹角序列法,进行了较为深入的分析和研究,并在此基础上提出了夹角符号序列算法。算法分别讨论了利用求夹角正切值符号序列和余弦值符号序列来求解凸多边形直径的两种途径,并给出了各自的算法实现,最后对算法进行了验证,实验结果证明夹角符号序列算法效率高、可靠性好。     

求凸多边形直径的改进算法

求凸多边形直径是计算几何中的一个基本问题,在Preparata-Shamos算法的基础上,提出了采用动态规划和二分查找的算法,不需要对凸多边形进行预处理,使整个算法的时间复杂度降低到O(n)级别。对算法实现的理论分析结果进行了验证,实验结果表明算法具有较高效率。     

一种求凸多边形宽度的优化算法

提出了一种优化的线性时间算法计算凸多边形的宽度。首先证明了凸多边形的宽度只可能介于“点边式”跨度之间,缩小了宽度的计算范围。其次提出了一种距离比较算法,降低了凸多边形跨度的计算量。最后,在“点边式”基本算法和距离比较算法的基础上,提出了计算宽度的优化算法。仿真分析表明,提出的优化算法提高了计算凸多边形宽度的效率,算法的时间复杂性降为O(n)。     

一种改进的求凸多边形直径的最优算法

求凸多边形的直径是计算几何中的一个基本问题。该文对Preparata-Shamos提出的最优算法进行了改进,使距离比较中的运算的次数从44n次减少到14n次,并减少了平行边的处理时间。实验结果表明,算法的运行时间减少到原来的53%。     

基于夹边边对的凸多边形间快速相交检测算法

本文在对现有的相交检测算法进行研究的基础上，提出了基于夹边边对的空间平面凸多边形快速相交检测算法，为平面凸多边形间判交问题提供了一致的计算方法，并将算法的应用对象扩展到任意空间平面凸多边形。该算法分为两步：第一步，确定所要检测的两个凸多边形是否都存在相对于另一凸多边形所在平面的夹边边对，如果至少一个凸多多边形中不存在相对于另一凸多边形所在平面的夹边边对，那么立即返回两个多边形不相交；第二步，根据前面计算得到的两个凸多边形中的夹边边对，计算两组边对间对应夹边的符号距离判断两个多边形是否相交     

基于直线斜率的凸多边形线裁剪算法

凸多边形的线裁剪算法在计算机图形学中占据着很重要的地位,现在的许多领域均有很重要的应用。本文提出了一种非常有效的基于直线斜率的凸多边形线裁剪算法,并与Cyrus—Berk算法进行了比较。结果表明：本算法更加简单、高效。     

基于向量的多边形扫描转换方法

提出了一种基于向量的多边形扫描转换方法,给出了相关的转换算法,并与一般计算机图形学原理教材中的常用几种多边形的扫描转换算法进行了相关比较分析.结论是在凸多边形的扫描转换上文中所提算法明显优于其他算法;对凹多边形也只需在凸多边形计算的基础上增加对凹边的判断与处理,但效率仍然高过其他算法.     

平面散乱点集约束Delaunay三角形剖分切割算法

文章提出了一种基于切割的平面散乱点集约束Delaunay三角剖分算法。该算法的基本思路是首先对平面散乱点集作约束最大空圆凸多边形剖分,然后对多边形的内部再作约束Delaunay三角形剖分。文章还证明了平面散乱点集的约束最大空圆凸多边形剖分是唯一的以及约束Delaunay三角剖分的不唯一性仅仅体现在约束最大空圆凸多边形的内部。使用约束最大空圆凸多边形的概念消除了由于“退化”现象（三个以上的点共圆）带来的算法上的潜在错误。     

二维Voronoi图和中轴的特征区分

对多边形Voronoi图和中轴两个概念进行了重新定义以适应更广泛的工程应用.分析对比了含直线段、圆弧和自由曲线的区域轮廓边界Voronoi图和中轴的各自的特征,给出了二者在凸多边形、简单多边形等不同情况下的相互关系及证明.     

圆形窗口的凸多边形裁剪

已有的多边形裁剪算法都是针对矩形窗口或凸多边形窗口进行的。但是，在实际应用中，也常常使用圆形窗口对多边形区域进行裁剪和填充。因此，本文提出一个对干圆形窗口的凸多边形区域裁剪法，并且给出作出凸多边形Ｐ在窗口Ｖ之内部分的定理。     

求解简单多边形和平面点集凸包的新算法

沿一定方向遍历凸多边形的边，其内部在边的同一侧。本文依据凸多边形的这一特性，提出求解简单多边形凸包的新算法，进而扩展得到求解平面点集凸包的新算法。新点集凸包算法先找到点集的极值点，得到极值点间的候选点子集，再求得相邻极值点间的有序凸包点列，最后顺序连接极值点间的有序凸包点列，得到凸包。新算法达到目前平面点集凸包问题的渐进最好算法的时间复杂度O（n log h），其中，n为平面点集的点数，h为平面点集凸包的顶点数。相比相同复杂度的凸包算法，新算法简单、易于实现。又由于是顺序求得凸包上的点，新算法还具有更易于实现基于其上的有效空间算法的优点。     

A straightforward algorithm for computing the medial axis of a simple polygon

A new algorithm for computing the medial axis of a simple polygon is presented. Although the algorithm runs in O(kN) time where k is the hierarchy of the Voronoi diagram of the polygon ranging from O(N) to O(logN) it is simple to implement and it does not require the complex data-structures required for the faster methods. This is an important factor in many applications of the medial axis.     

平面点集凸壳的快速算法

提出一种计算平面点集凸壳的快速算法。利用极值点划分出四个矩形,它们包含了所有凸壳顶点,通过对矩形中的点进行扫描,排除明显不是凸壳顶点的点,剩余的点构成一个简单多边形。再利用极点顺序法判断多边形顶点的凹凸性并删除所出现的凹顶点,最终得到一个凸多边形即为点集的凸壳。整个算法简洁明了,避免了乘法运算（除最坏情况外）,从而节省计算时间。     

一种基于几何关系编码的高效凸多边形线裁剪算法

提出了基于直线与凸多边形几何位置关系编码的一种新的凸多边形线裁剪算法,用凸n边形窗口对m条直线进行裁剪.实验结果表明,当n较大时,该算法所用的时间大约是著名的Cyrus-Beck算法所用时间的1/3左右.如果m的数值也较大时,该算法的速度还将大大提高.所以在实际应用中,新算法提高了裁剪效率并具有很好的稳定性.     

基于最大基线倾角智能逼近的凸壳新算法

本文评述了有代表性的折半分治递归凸壳算法，并利用同构化凸壳基本定理提出效率更高的最大倾角智能逼近凸壳新算法。本新算法的同构化特点是：1）找出给定二维点集最外点（指最左、最右、最高、最低点），即其X轴、Y轴坐标值最大、最小的四个初始极点；2）用该初始极点，把原二维点集分布域划分为四个子分布域；3）分别在这四个子分布域中，各基于自身最新所得极点依次动态构造其基线倾角最大的当前极点，并用这些极点作凸边，来逐步智能逼近和最终生成该给定二维点集的凸壳。     

基于凸剖分的多边形窗口线裁剪算法

以不增加新点的方式将多边形剖分为一些凸多边形,并基于这些多边形的边建立二叉树进行管理.裁剪计算时,根据二叉树快速地找到与被裁剪线有相交的凸多边形,然后运用高效的凸多边形裁剪算法进行线裁剪.该方法能自适应地降低裁剪计算的复杂度,使其在O(logn)和O(n)之间变化,并在大多数情况下小于O(n),其中n是多边形边数.虽然该方法需要进行预处理,但在许多应用(如多边形窗口对多边形的裁剪)中,其总执行时间(包括预处理时间和裁剪时间)比已有的不需要预处理的裁剪算法少很多.     

简单多边形分解成凸多边形差组合的算法

本文说明一种把简单多边形分斛成凸多边形的差形式的组合的算法。该算法在求一简单多边形凸包的同时求出凸包和原多边形的差(把差称为内多边形),再对内多边形递归地作同样计算便可得到最终结果。最后证明了运算法的时间复杂性为O(N~2),其中N为原多边形的边数。     

基于凸片段分解的多边形窗口线裁剪算法

将多边形窗口的边顺序地分割成一些片段,使得每个片段都能局部地形成一个凸多边形,称为凸片段,并建立一个二叉树来管理这些凸片段．在裁剪计算时,先根据二叉树快速地找到与被裁剪线段相交的凸片段,再利用高效的凸多边形线裁剪算法对这些凸片段进行裁剪操作．文中算法能有效地降低裁剪计算的时间复杂度,使其在O（logN）～O（N）之间自适应地变化,且大部分情况下时间复杂度小于O（N）．