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

该文提出了计算两凸多边形交集面积的新的计算机算法。算法设计的思路简单,易于实现,实际应用中具有鲁棒性（ｒｏｂｕｓｔｎｅｓｓ）。     

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基于交点符号法的凸多边形窗口的线裁剪算法

凸多边形窗口的线形裁剪算法是计算机图形学的基本问题之一，在许多领域均有应用。Cyrus-Beck算法是现有凸多边形窗口的线裁剪算法中最经典的，它采用不的是参数化方法。本文提出一种新的算法，采用基于交点符号的判别方法，裁剪过程在直角坐标系下进行。实验结果表明，本算法比Cyrus-Beck算法简单、直观。     

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

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

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

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

关于“判定凸多边形可碰撞的最优算法”一文的商榷

本通讯对题中所引一文的算法的时间分析提出了不同看法。     

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

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

一个加权剖分简单多边形为凸多边形的算法

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

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

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

基于无迹变换的协方差交集算法研究

针对分布式数据观测系统中数据融合存在数据线性化过程误差较大、滤波过程中的错误无法修正的问题,提出了一种基于无迹变换的协方差交集算法。该算法首先对系统数据进行无迹变换,然后对数据采用协方差交集算法滤波,可得到较好的滤波性能。实验结果表明,该算法弥补了协方差交集算法的不足,能够修正数据线性化误差及滤波产生的错误,是一种有效的数据融合算法。     

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

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