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

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

基于凹凸顶点判定的简单多边形区域的三角剖分

本文先介绍了基于凹凸顶点判定的简单多边形的三角剖分算法 ,然后提出了一种新的算法 ,将简单多边形区域转化为简单多边形 ,进而实现简单多边形区域的三角剖分     

简单多边形顶点凸凹性的快速确定算法

本文深入剖析了平面简单多边形方向（逆时针或顺时针）与顶点凸凹性的内在本质联系，提出了确定顶点凸凹性的快速算法，并解决了根据凸点确定多边形方向的基本问题。本文方法已应用于工厂设计软件ＰＤＳＯＦＴ的工厂模型消隐和平剖图消隐中，实践证明效果很好。     

求简单多边形可见点的一种新算法

提出一种求简单多边形可见点的新算法,通过对多边形作预处理,可预先剔除其中部分不可见点,并消除了判断可见点过程中的螺旋状态.将多边形剩余顶点序列分割为四段,每段分别按文中给出的方法找出可见点.算法中对点与线段的位置关系,用点与线段围成的三角形的方向表示.三角形的方向通过极点顺序法确定,避免了使用耗时的叉积法.试验表明,算法准确、高效和稳定.     

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

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

简单多边形集凸包的快速算法

提出了一个简单多边形集凸包的快速算法.先求出每个简单多边形的(子)凸包,根据凸包的切线性质,从有关的子凸包中抽取一段严格单调的折线.应用归并排序方法把位于一条直线右侧的一组严格单调的折线合并成一条折线,把合并后的折线和子凸包集的外接矩形上的边连结成一条封闭折线,即一个简单多边形,使其能够把所有子凸包包围起来,最后求出这个简单多边形的凸包.算法的时间复杂度为线性O(n),并且给出一个例子进行了验证.     

点在多边形内测试的新算法

判断点在多边形内是诸多领域的一个基本问题。分析了解决这一问题的一些传统算法,改进了射线交叉法。避免了射线与多边形的一条边重合、射线经过多边形顶点这两种临界情况的处理和求交点运算。算法的时间复杂度为4n次减法,3n次乘法,6n次比较（n为多边形顶点数）。程序简单易行,计算量较小。     

基于形心与顶点连线表示的多边形变形

研究了平面多边形变形问题。从几何角度出发,采用形心和形心与各顶点的连线来描述多边形。根据两多边形的形心—顶点连线长度及相邻连线之间的夹角给出匹配度函数,并以此来建立两多边形顶点之间的对应。线性插值对应连线的长度和相邻两连线之间的夹角,得到中间融合多边形相应的几何信息,然后按照给定方法顺时针依次生成中间多边形各顶点。实现了一般平面多边形的自然变形。     

简单Hamilton系统的能控性

对于简单Hamilton系统,通过引入本原Poisson括号,讨论了简单Hamilton系统的能达性分布,从而提出了该系统的位形能控性,给出了简单Hamilton系统位形能控的条件,最后证明了简单Hamilton系统的能控性与位形能控性是等价的。     

基于扫描区间表示的不规则多边形快速定位算法及应用

不规则多边形定位算法是排料算法的重要组成部分,其效率对排料算法的性能有重要影响。基于扫描区间表示的不规则多边形定位算法因能适应任意复杂多边形而被广泛采用,但它存在计算量大的不足。通过深入研究基于扫描区间表示的多边形定位算法,该文从两个方面对其方法进行改进：首先提出候选平移位置矩阵的概念,进而实现定位扫描算法;然后通过最大跨度比较法快速排除一些不可能的行,从而通过减少定位扫描算法的调用次数进一步加速。该算法已应用于自主开发服装排料软件,多个实际衣片数据的测试结果证明了该文算法的有效性和高效性。     

点包容性检测

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

一种简单多边形凸包的新线性算法

给出了一个计算简单多边形凸包的新算法，其搜索策略为：对简单多边 形上的点进行分类，排除不可能为凸包上的点，缩小搜索范围，从而降低算法的时间复杂度，该算法具有线性时间复杂度和空间复杂度，同时，具体量化了该算法的复杂度，给出了该算法的时间复杂度和空间复杂度的确定的上界，即，时间复杂度为不超过4(n-4）次乘法，6（n-4）次减法和17n-12次比较运算，空间复杂度为不超过2n个存储单元（n是该简单多边形顶点的个数）。     

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

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

一个求解多边形最小面积外接矩形的算法

多边形最小面积外接矩形是地理信息系统和图形学领域一个极其有用的工具,但是其精确求解过程比较困难.首先证明了一个多边形的最小面积外接矩形必定过该多边形凸包的一条边,然后基于该思想提出了一个计算多边形最小面积外接矩形的算法,并对算法的效率进行了分析.最后给出了算法的实验算例,进一步说明了算法的可行性与可靠性.     

基于端点与交点编码的矩形窗口多边形裁剪新算法

从矩形窗口裁剪任意多边形的本质特征出发,提出多边形各边端点编码技术。通过对多边形各边端点的一次及二次编码,可快速得到所有窗内边并舍弃绝大部分窗外边,还可快速判断该端点是内点还是外点。在已获取的窗内边、相交边的交点以及交点编码的基础上,可以得到正确的裁剪结果。同时考虑了矩形窗口与多边形相互包容的特殊情形。实验结果表明,新算法稳定可靠,实现了对任意凹凸多边形的裁剪,具有通用性强、算法简捷、裁剪效率较高的优点。     

视点相关的复杂模型的简化算法

为克服Hoppe边折叠算法存在计算量很大,运行速度很慢的缺点,在Garland边折叠算法基础上,将边折叠算法与视点相关因子相结合,对复杂模型进行了简化,并使用改进的多边形模型的数据结构,实时动态地生成了多层次的LOD模型。实验结果表明,该算法能够在保留模型重要的几何特征的前提下,实现模型较大幅度的简化。     

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

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