计算两凸多边形交集面积的计算和算法

该文提出了计算两多边形交集面积的新的计算机算法，算法设计的思路简单，易于实现，实际应用中具有鲁棒性（robustness)。     

计算多边形交集、并集面积的算法

平面多边形交集与并集面积的计算机算法可以利用多边形裁剪算法来实现。本文提出的算法思想是利用Weiler-Atherton多边形裁剪算法中的多边形链表,在遍历链表时遇到交点就改变跟踪方向,这样可以求出并集顶点表,求交集时只要从入点开始跟踪遇到交点再改变跟踪方向;最后,通过交集和并集表求出它们的面积。多边形可以是凸的或凹的、甚至是带孔的。     

如何编程求两凸多边形的公共面积

一、问题 2001年第7期擂台赛给出了这样一个问题:给定两凸多边形,则两凸多边形的相交部分也一定是一个凸多边形,请编程求出它们公共相交的凸多边形的面积。 (二)预备讨论 首先介绍后面要用到的几个子问题的解法。 第一,如何判断一个点是否在一个凸多边形内部?     

求两凸多边形间的距离的快速算法

本文提出了一个求两互不相交的凸多边形间的距离的快速算法，两个凸多边形间的距离指的是这两凸多边形沿着连心线方向以平移方式相互接近直至相交时所经过的路径长度。     

求平面内两互不相交的凸多边形的内公切线的最优算法

设P与Q为平面内两个互不相交的分别具有m与n个顶点的凸多边形,它们的顶点用直角坐标描述并且沿其边界按顺时针方向依次列出.本文给出求P与Q的内公切线(或称斜支撑线)的时间复杂度为O(logm+logn)的最优算法,从而突破了李辉关于解决同一问题的时间复杂度为O(m+n)的算法是最优的论断.     

判定凸多边形可碰撞的最优算法

设P与Q是平面内任意二互不相交的凸多边形,d为任一给定方向,本文研究P沿d以平移方式运动可否与Q碰撞的判定问题.文中定义了凸多边形顶点集上的偏序关系,给出了判定可碰撞性的新的充分必要条件,据此采用四分搜索方法构造了判定可碰撞的算法.在最坏情况下算法的复杂度为O(logn),在不计常数因子的情况下,这是最优的.     

关于凸多边形的修剪算法研究

该文研究并提出了一种凸多边形的裁剪算法，它不同于传统的多边形剪算法，仅需对视口在点所关联的边检查与视口的相一。裁剪速度快，简单易行。     

一种凸多边形的修剪与填充算法

本文给出了一种凸多边形的填图算法,它集修剪与填充功能于一体,也可单纯完成对凸多边形的修剪任务。     

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

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

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

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

圆形窗口的凸多边形填充算法

给出了一种基于圆形窗口的凸多边形填充算法，它集裁剪与填充功能于一体，也可完成单纯地裁剪功能。     

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

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

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

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

图像目标外接多边形及凸壳的一种构造方法

对二值图像进行Hough变换后,在(ρ,θ)空间中选取了一组边界对应点,通过计算与这些边界对应点对应的图像空间中直线的交点,构造了图像目标的外接多边形;通过比较相距π/2 rad的投影区间长度是否相等,或区间长度的乘积是否为最小,得到了形状外接正方形和外接最小面积矩形;利用构造形状外接多边形的方法并通过增加边的数目,构造了形状的近似凸壳.实验和理论分析表明,文中算法具有好的抗噪性能和广泛的适用范围.     

Computing the Maximum Overlap of Two Convex Polygons under Translations

Finding a vast array of applications, the list-ranking problem has emerged as one of the fundamental techniques in parallel algorithm design. Surprisingly, the best previously known algorithm to rank a list of n items on a reconfigurable mesh of size was running in O(log n ) time. It was open for more than 8 years to obtain a faster algorithm for this important problem. Our main contribution is to provide the first breakthrough: we propose a deterministic list-ranking algorithm that runs in O(log^* n ) time as well as a randomized one running in O(1) expected time, both on a reconfigurable mesh of size . Our results open the door to a large number of efficient list-ranking-based algorithms on reconfigurable meshes. Received February 1997, and in final form February 1998.     

用凸多边形微量增长法求解TSP

采用凸多边形微量增长方法，给出了一个求解TSP问题算法。该算法首先找出边界点，生成凸多边形，然后反复从剩余结点中，选取最小增量的点，插入到多边形中，最后得到TSP的路径。算法实现容易、运行速度快。采用该算法生成的CTSP路径接近其最优解。