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

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

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

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

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

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

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

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

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

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

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

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

一种基于单调多边形的三角剖分算法

提出了一种基于单调多边形三角化算法,被三角化的多边形可以含有任意个内孔。先根据边界y（x）方向的局部极值顶点作水平（垂直）分割线,将多边形划分成单连通y（x）单调多边形,然后再将各单调多边形三角化。算法考虑了各种几何奇异情况,因此比较稳定。     

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

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

基于扫描带的任意多边形窗口线裁剪算法

提出了一个基于扫描带的任意多边形窗口线裁剪算法。首先确定裁剪窗口所有顶点对于被裁剪直线段的位置关系,然后生成过顶点的扫描线,及时修改由相邻两条扫描线所构成的扫描带结构数据,增加每条扫描带中位于被裁剪直线段左侧的裁剪窗口的边界线数。最后,根据左侧边界线数的奇偶性,确定相应直线段的可见性,并最终实现任意多边形窗口的直线段裁剪过程。     

基于向量夹角的三角网格模型简化算法

提出以顶点向量夹角为剔除准则,运用顶点去除方法进行网格简化的算法。该算法首先计算每个网格顶点与其周围相邻顶点所形成的方向向量,然后根据方向向量的平均夹角来识别和简化网格中的平面区域,之后再以该顶点所处区域是否比较平坦为顶点去除限制条件,判断该顶点是否符合安全去除原则,这样可以保留特征顶点,进而保持物体的视觉特征。在顶点去除后,还需要对因此而形成的多边形进行三角形网格重建,以填补空洞。该算法在简化质量和简化速率方面取得了较好的平衡。     

B—SPLINE曲线顶点的反算

本文系统地探讨了B-Spline曲线特征多边形顶点反算的方法,特别是将Cholesky方法应用于闭曲线顶点的反算,使简化后的算法简捷、精确。     

一种多边形区域运算的改进算法

本文简述了利用两多边形的交点出入性质进行匹配运算的方法，重新定义了一区域中有向边与另一区域的进出关系，给出了两多边形区域存在部分顶点或边界重合时交点给出性质的判别原则，改进后的算法适于任何非凸多边形（含孔洞）的区域运算。     

与给定多边形相切的C 3连续B3样条曲线

描述了一种与给定多边形相切的B3样条曲线的算法。在算法中，所有的B3样条曲线的控制点可以通过对多边形的顶点简单计算产生，所构造的曲线对多边形具有保形性，曲线可以局部修改，最后给出了两个算例。     

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

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

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

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

复连通多边形的三角剖分

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

EB样条曲线曲面顶点的反算及特殊情形的讨论

本文给出了一种新的EB样条曲线、曲面在各种边界条件下的反算矩阵通式;并且讨论了特征多边形顶点共线和重顶点对两种较常用(即k=0和k=1/8时)的EB样条曲线形状变化的影响。其结果表明,适当迭取顶点共线和重顶点能使EB样条曲线、曲面满足实际应用中复杂外形设计对曲线、曲面的特殊要求。     

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

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

2D图形引擎中的平面多边形内外点判别

在2D图形引擎中,可见性判定是一个非常重要的问题.通过屏幕裁剪,可以进一步减少多边形数目,减轻引擎的负担.因此,在屏幕裁减阶段完成的屏幕顶点与多边形的内外关系判断就显得很重要了.文章结合2D图形引擎的特点和流行的内外点判别算法给出了在DirectX平台上使用VC++实现的平面多边形内外点判断算法,并将其应用于实际的2D图形引擎中.程序验证表明,该算法能有效判定屏幕顶点与多边形的内外关系,且算法效率较高、简单易行.     

点包容性检测

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