一种剖分平面多边形的通用算法执行

对一种用梯形来剖分非单调平面多边形的通用算法，在AMD雷鸟750MHZ CPU计算机上进行了计算，结果表明，本算法可以有效、经济地处理大量复杂的多边形，经优化处理后，可减少约34%的梯形个数。     

一个有效的多边形裁剪算法

多边形裁剪与线剪裁相比具有更广泛的实用意义,因此它是目前裁剪研究的主要课题.提出了一个多边形裁剪多边形的有效算法.其中的多边形都可以是一般多边形,既可以是凹多边形,也可以是有内孔的多边形.该算法不仅可以求多边形的"交"(多边形裁剪),而且可以求多边形的"并"和"差".它是以所提出的一系列新方法和新技术为基础而形成的.首先,该算法使用单线性链表数据结构,与其他使用双链表或树结构的算法相比,具有占用空间少及处理速度快的特点;其次,找到了两个多边形之间进、出点之间的关系.再通过合理的数据结构处理,减少了算法对多边形链表的遍历次数,而且允许多边形既可以按顺时针方向也可以按逆时针方向输入.最后,判断和计算交点是裁剪算法的主要工作.提出了一个具有最少计算量的交点判断和计算方法,进一步加快了算法的运行速度.与其他同类算法进行了比较,结果表明,新算法具有最简单的结构和最快的执行速度.     

基于顶点存储类型的多边形填充算法

提出了一种基于顶点存储类型的多边形填充算法。该算法将多边形顶点和新生成的交点划分为三种类型进行存储,然后由过顶点的扫描线将多边形分割成若干个梯形区域分别进行填充。此算法只涉及过顶点的扫描线,且多边行边上的像素点坐标可以直接从边的直线方程中获得,从而使得该算法大大降低了计算的复杂性。     

有向回路法和网格法:多边形内外点判别的新算法

该文把简单多边形视作一个有向回路,利用多边形的环绕方向和区域划分提出了两种判别内外点的新算法:有向回路法和网格法。有向回路法利用了多边形的方向性,在某些情况下可以不必遍历多边形的所有边。该算法程序简单,时间复杂度为O(n),平均性能优于复杂度为Θ(n)的射线法和标号法,但只能处理凸多边形。网格法是有向回路法的改进算法,利用了多边形的方向性和区域划分。网格法将n边形的包围盒划分为(n-1)×(n-1)个网格:如果待处理的点在某个网格内,则仅根据经过该网格的所有边就可以判断该点的内外性。网格法可以处理任意简单多边形,包括带孔的多边形;最坏情况下的时间复杂度为O(lgn),空间复杂度为Θ(n2)。     

Java手机多边形处理的研究

在LBS系统中手机终端地图的处理是LBS的核心问题之一，Java手机地图多边形分为无填充多边彤与填充多边形．针对Java手机无填充多边形按封闭折线处理，填充多边形利用二分法递归处理——填充多边彤P分割为两个与P不相交的内多边形P1与P2，再递归分割P1与P2，直到P1与P2为三角形为止．本文提出的多边形处理算法非常适用于资源受限设备，在LBS网络中测试，其运行良好高效，优于PNG地图．     

GIS环境中一种高效的多边形剪裁方法

在Weiler算法的基础上提出一种在GIS环境中计算非凸多边形之间的剪裁区域的新算法。该算法前提是多边形已根据梯形分解法被分解成若干个梯形,首先计算两个多边形之间的交叉点,并在计算的过程中按Weiler算法中的出点和入点来标示它们,然后逆序遍历所有的交叉点来确定剪裁区域。该算法通过减少交叉点的计算时间和遍历时间来提高Weiler算法的效率。在GIS这种具有频繁拓扑关系运算的环境中可以很好地提高运算效率,最后通过实验验证,即使在接近最坏的情况下,该算法也优于传统的Weiler算法。     

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

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

用VC++实现的任意多边形裁剪算法

提出了一个用VC++语言实现的凸多边形、凹多边形,也可以是带内环的多边形的裁剪算法,可以求上述多边形的"交"、"并"以及"差".首先,该算法使用VC++支持的CObList类和CArray类的对象存储数据,具有占用内存空间少及处理速度快的特点;再通过算法和数据结构的设计不仅使得多边形顶点可按顺时针方向或逆时针方向输入,而且减少了求解过程中对多边形顶点数据的遍历次数;基于判断和计算交点是裁剪算法的主要工作,文中引入了求交前的预处理,避免了大量不必要的求交,降低了算法的时间复杂度.最为重要的是该算法不需要对两多边形的边重合或两多边形在顶点处相交的情况作特殊处理.     

基于顶点与邻边相关性的多边形填充算法

为了加快多边形填充算法的运算速度，在深入挖掘顶点与相邻边关系对填充算法影响的基础上，提出了一种基于顶点与邻边相关性的多边形填充算法。该算法首先归纳了多边形顶点与邻边相关性的5种典型类型，然后依据顶点与邻边的相关性，对原有多边形进行了分割与重新组合，使其完全由简单的三角形和梯形这样的单元区域组成，这样就将复杂的多边形填充问题转化为这些单元区域的填充问题，并由此将扫描线与多边形边求交的乘除计算转化为加减运算。通过实验分析，新算法大大减少了运算的时间和复杂度，从而为多边形填充创造了一种有效的新途径。     

介绍一种多边形裁剪算法

本文详细地介绍了一种多边形裁剪新算法，窗口可以是任意凸多边形，被裁剪的多边形可以是任意凹或凸的多边形，     

带孔洞多边形的求交算法

为简化已有任意简单多边形求交算法并提高算法效率,首先将交点分类并排序,然后采用不同的遍历方法得到多边形的交集、并集和差集,在该算法的基础上设计带孔洞多边形的求交算法．所有算法均被实现,且复杂度较低,鲁棒性较好．     

复合多边形求差的高效矢量算法

从集合和几何的基本原理出发, 提出了复合多边形求差的一种矢量算法。算法首先区分多边形的拓扑相离、包含或相交关系。对于拓扑相离或包含的两个多边形, 其差容易计算; 对于相交的两个多边形, 应用平行线扫描算法来求解, 得到两个复合多边形的差。该算法的特点是可以解决嵌套了任意层次孔洞的两个多边形之间的求差运算, 这在计算机辅助设计、地理信息系统、地图数据处理等领域具有较广泛的应用前景。     

平面扩展简单多边形的布尔运算

Rivero等最近提出了一种用来计算任意平面简单多边形的交、并、差的新方法，在这一算法基础上进行扩展，使其可以应用到带圆锥曲线边的平面扩展简单多边形上，并给出了完整的数学模型。     

Linear-Time Algorithms for Hole-free Rectilinear Proportional Contact Graph Representations

In a proportional contact representation of a planar graph, each vertex is represented by a simple polygon with area proportional to a given weight, and edges are represented by adjacencies between the corresponding pairs of polygons. In this paper we first study proportional contact representations that use rectilinear polygons without wasted areas (white space). In this setting, the best known algorithm for proportional contact representation of a maximal planar graph uses 12-sided rectilinear polygons and takes O(nlogn) time. We describe a new algorithm that guarantees 10-sided rectilinear polygons and runs in O(n) time. We also describe a linear-time algorithm for proportional contact representation of planar 3-trees with 8-sided rectilinear polygons and show that this is optimal, as there exist planar 3-trees that require 8-sided polygons. We then show that a maximal outer-planar graph admits a proportional contact representation using rectilinear polygons with 6 sides when the outer-boundary is a rectangle and with 4 sides otherwise. Finally we study maximal series-parallel graphs. Here we show that O(1)-sided rectilinear polygons are not possible unless we allow holes, but 6-sided polygons can be achieved with arbitrarily small holes.     

Inclusion test for curved-edge polygons

In this work we present a new algorithm to study the inclusion of points into polygons whose edges are curve segments. It is valid for closed planar polygons whose edges can be straight line segments, conic arcs or cubic Bézier curves. Also it is valid for manifold and non-manifold closed planar polygons with and without holes. Our algorithm is robust and simple, firstly because it avoids the use of equations systems in the inclusion test, and secondly because it solves special cases effectively and homogeneously.     

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

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

格网划分的双策略跟踪多边形裁剪算法

论文提出了一种高效稳定的多边形裁剪算法,算法支持带内环的平面简单 多边形,同时也支持多边形的“并”和“差”等布尔运算。首先,设计了算法所需的数据结构; 其次,基于直线扫描转换Bresenham 算法原理提出了边网格划分的有效算法,并应用一个简 单的方法避免不同网格内边的重复求交;最后,将交点分类为普通交点和顶交点,并针对这 两类交点构造了不同的跟踪策略,在跟踪过程中交替、递归地应用这两个策略来确保算法处 理特殊情况时的稳定性。与其它同类算法的比较表明,新算法具有更高的效率。     

允许自由旋转的2个简单多边形匹配算法

为了解决二维不规则排料问题中的匹配问题,提出了一种允许自由旋转条件下,2个无孔洞的简单多边形之间的匹配算法.该算法基于2个多边形可以自由旋转的假设,对它们之间NFP为凹或凸的情况,选择适当的匹配方法,找出一种使得其匹配后空隙尽可能小,同时保证其整体的矩形的规整度也较高的匹配方案;并用匹配空隙的利用率、匹配后整体面积的利用率,以及匹配后整体的矩形规整度等多个指标来衡量匹配的效果.实验选择于ESICUP中的部分代表性的多边形样例与多个算法进行对比实验,结果表明,该算法在任意旋转精度的要求下,均具有运行速度快的特点,可以很好地应用于服装排料等实际问题.     

满足全局Delaunay特性的带特征约束的散乱数据最优三角剖分

本文给出了一种新的全局满足Ｄｅｌａｕｎａｙ特性的带特征约束散乱数据的优化三角剖分算法．统一的数据结构允许散乱数据带有外部边界或内部孔洞,并且约束特征可以是有向折线或封闭多边形．由于采用了“对半划分增量型附加特征点插入”算法,从而可以用较少的附加点来使全局Ｄｅｌａｕｎａｙ特性得到满足．