利用极点顺序的多边形顶点凹凸性判别算法

提出一种根据多边形各个极点在顶点序列中的先后顺序确定多边形方向的算法.对于多边形顶点凹凸性的判别,提出通过确定某个顶点与其相邻两顶点构成三角形的方向,进而利用多边形方向与该三角形方向是否相同而确定该顶点凹凸性的方法.该算法包括了点包含的判别.试验表明,该算法不含乘法运算,使运算高效稳定.     

计算两凸多边形的并集多边形及其面积的计算机算法与实现

提出计算两平面凸多边形的并集(多边形)及其面积的计算机算法，并对算法实现给出详细的计算过程。程序实现中，文中将算法分为判定点是否在多边形内部、求两多边形交点、求并集多边形及其面积三部分。引入利用向量叉积符号判定三角形的方向，进而判别平面上一点是否在凸多边形内的方法，简化了计算。还进一步提出了运用“区间分割”求两相交线段交点的新颖方法。     

多边形裁剪通用算法

本文根据计算机图形学中多边形裁剪的特点，提出改进内点判断法，线段参数方程求交法和特殊交点等算法，具有通用性较强，算法简单的优点，可用于任意多边形之间的裁剪。     

复连通多边形的三角剖分

文章简要回顾了多边形的三角剖分 ;基于将复连通多边形假定看作简单多边形的思想 ,着重讨论了复连通多边形的三角剖分 ;通过对具体实例的分析 ,将判断多边形顶点的凹凸性与判断某点在三角形的外部或内部的问题合二为一 ,简化算法函数     

连接不相交线段成简单多边形(链)的算法

提出一个实际问题，即如何连接平面上h条线段成一简单多边形或者简单多边形链，并证明了连接平面上线段集S成一简单多边形链的一个充分条件，S中有一条线段连接凸壳CH（S）中不相邻顶点，另外还提出了连接平面上线段集S成一简单多边形或者简单多边形链的算法，其基本思想是首先逐层计算线段集S的凸壳，并将这些凸壳改变多边形；然后计算各多边形之间的交点，进而删去这些交点。最后合并若干个简单多边形为一个简单多边形，当S中线段数目n较大时，用分治思想可以设计分治算法，较好地求解了这个问题，利用计算机求解这个问题上有实际应用价值。     

点包容性检测

介绍了一个易于实现的点包容性检测算法--倾斜射线法,其特点是射线不会与多边形的顶点或边重合,无须作特殊情况的处理,需计算的区域小,因而计算量小.判断倾斜射线与多边形的交点数,如果交点数为奇数,则点在多边形内,否则,点在多边形外.验证表明,此算法简单有效、稳定可靠,对自相交多边形及带孔多边形等情况同样适用.     

基于边向量斜率比较的简单多边形顶点凸凹性快速判别算法

对于给定的平面简单多边形顶点序列,判别多边形方向和顶点凸凹性的传统方法为:先计算多边形相邻边向量的叉积或相邻3个顶点所确定三角形的有向面积,再由叉积或有向面积的符号来确定顶点的凸凹性,使得处理一个顶点需要2次以上的乘法运算。笔者通过边向量斜率的计算和比较,将多边形顶点的凸凹性与边向量的斜率联系起来,并采用“假设-检验”方法,提出了一种快速判别简单多边形方向与顶点凸凹性的新算法,其时间复杂度为)(nO,判别多边形任一顶点凸凹性所需的乘法运算平均不超过1次。该算法原理直观简单,实现容易。实际运行结果表明,该算法速度快捷、运行稳定。     

简单多边形方向及顶点凹凸性的快速判定

基于简单多边形方向与顶点凹凸性的内在联系，采用极值点性质判定多边形方向，通过多边形顶点坐标判定其拓扑映射点之间的位置关系，结合以上两方面对顶点的凹凸性作出判断。对基于拓扑映射的多边形顶点凹凸判别算法作出有效的改进，避免了原算法申大量的重复计算。实践证明，有效的减少计算次数，提高了效率。     

生成三维多边形平面域的双直线算法

提出了一种生成三维多边形平面域的新算法,该算法由主投影的扫描转换与主投影方向坐标的离散计算两部分构成。算法的两个部分相互独立,因而在第一部分可采用任意一种已有的多边形扫描转换算法来实现。主投影方向坐标的离散计算可通过两个整型数组（代表双直线）快速获得。算法可保证在理论上共面的两个多边形面域的公共部分在离散后完全重叠。     

确定任意多边形的核的算法

本文提出确定任意简单多边形Ｌ的核的算法，该算法的时间复杂性是Ｏ（ｌｎ）次乘法，其中ｎ是多边形的Ｌ的顶点数，ｌ是多边形Ｌ中凹点的数目。