大规模等值线图的任意简单多边形窗口裁剪算法

针对大规模等值线图裁剪算法面临的两个主要问题,如何减少线段求交次数和判别保留部分的起止点,提出一种针对大规模等值线图的任意多边形裁剪算法.该算法首先使用等网格分割方法,在等值线线段与裁剪多边形边之间建立网格索引,减少线段求交次数;同时,在网格数据结构基础上,采用局部射线法,很好地解决了判断交点在裁剪多边形内外时间复杂度过大的问题,使得算法可以快速判断出需要保留(剔除)的等值线部分.本文算法的优点是能够在求出交点的基础上快速获得需要保留(剔除)部分的起止点;同时,算法中裁剪多边形可以是包含任意多个洞的任意简单多边形,克服传统算法中对裁剪多边形的特定约束条件.本文算法易于实现且高效.     

基于网格与R-树空间索引的矢量线图任意简单多边形窗口裁剪算法

针对大规模矢量线与大量裁剪窗口同时出现的线裁剪算法存在的三个主要问题,减少线段求交次数、简化交点出入属性计算以及无交点矢量线的取舍,本文提出了一种基于双空间索引的大规模线图任意多边形裁剪算法。算法根据裁剪多边形的边分别建立R-树索引和均匀Cell索引,应用两种索引各自的优点大幅减少被裁剪线段与裁剪多边形上线段的求交次数。在此基础上,基于均匀网格索引,提出局部射线法,简化交点出入属性计算和无交点矢量线的取舍。本文在传统算法基础上提出三点改进:首先提出基于两种空间索引模型进行线段求交计算,保证算法在理论上具有较低的时间复杂度;其次,在射线法和网格索引基础上提出局部射线法,使得判断每个交点出入属性的时间复杂度为O(1)～ O(n~(1/2)),与参考文献中的算法相比,此方法的优点是避免判断多边形上顶点的方向;最后,算法中裁剪多边形可以是包含任意多个洞的任意简单多边形,克服传统算法中对裁剪多边形的特定约束条件。     

基于编码与分类技术的任意多边形裁剪新算法

首次将编码与分类技术引入任意多边形的矩形窗口裁剪,通过编码分类技术根据多边形边与裁剪窗口的相对位置将边分为六类。采用一次编码技术获取一类窗内边,舍弃二类窗外边,得到必须求交的三类边;采用二次编码技术舍弃四类窗外边,得到需要求交的五、六类边;进一步提出裁剪窗口顶点相对于多边形的分类,利用窗口顶点分类和多边形边的编码特征快速处理三类、五类、六类窗口相交边。通过编码分类技术减少了多边形裁剪的运算量,并有效地维护了多边形的拓扑关系。实验结果表明算法稳定可靠,可实现对任意凹凸多边形的裁剪,在多边形与窗口的各种相对位置均具有较高的运算效率。     

介绍一种多边形裁剪算法

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

一种任意多边形窗口的直线裁剪算法

在多种裁剪算法的基础上进行分析和改进,提出了一种新的裁剪算法,算法通过计算任意多边形每条边所在直线与被裁剪线段所在直线求出真实的交点,并通过交点排序后的奇数校验法判断出交点所在位置,即是在任意多边形的内部还是外部,该裁剪算法通过实验证明了具有很高的算法效率.     

一种等值线图的任意复杂多边形窗口裁剪算法

给出了一种新的海量等值线图任意多边形窗口的快速裁剪算法。计算裁剪多边形的外包围盒并创建网格结构,利用网格结构对等值线进行快速预裁剪,通过链式结构对等值线进行细节裁剪得到最终裁剪结果。通过建立行链式结构可以实现以行扫描的方式快速判断点的内外属性,而且还能减少线段求交运算次数,基本能确定实际相交的线段时才进行求交运算。经过大量的实验,证明该算法非常高效且稳定。另外,新算法能有效地处理各种特殊裁剪多边形嵌套情况,克服了以往算法对裁剪多边形的约束条件。该算法程序实现简单且符合工程需求。     

大规模等值线图任意多边形裁剪算法

给出一种大规模等值线图任意多边形窗口的快速裁剪算法。首先进行传统算法的外包围盒裁剪,然后针对外包围盒创建一种约束网格结构,然后利用网格对等值线进行快速预裁剪,最后通过行扫描算法对等值线进行定位并进行局部细节裁剪得到最终裁剪结果。通过约束网格可以实现以行扫描的方式快速判断点的内外属性,而且基本能确定实际相交的线段时才进行求交运算,减少了大量的求交运算。另外,算法能有效地处理各种特殊裁剪多边形嵌套情况,克服了以往算法对裁剪多边形的约束条件。经过大量的实验,证明本文算法非常高效且稳定。     

基于交点参数的任意多边形窗口对圆裁剪

现有的任意多边形窗口的圆裁剪算法存在算法繁琐等问题, 且没有考虑多边形是带内环的情况, 本文提出了一种基于交点参数分析的多边形窗口的圆裁剪算法, 只需对多边形边与圆的交点在边所在直线的参数值进行比较, 即可判断出交点的进出点特性, 交点排序后, 通过进点$\Rightarrow $出点组合, 即可获得裁剪窗口内的圆弧, 完成裁剪. 编程实践的实例结果也证明本算法是切实可行的, 本文的方法既适用于仅有外环的一般多边形裁剪窗口, 也适用于带内环的任意多边形裁剪窗口的圆裁剪, 因此, 算法更具有通用性.     

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

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

适用于凹多边形的Cyrus-Beck改进算法

本文对目前常用的二维线段裁剪算法进行分析,提出了一种基于Cyrus-Beck算法的改进算法,使其能够扩展到对凹多边形的处理,通过对线段与裁剪窗口位置关系的严格判断将求交次数减到最少,并且通过对交点性质的判断来识别出线段的可见部分。理论分析和实验结果均表明该算法优于目前处理任意多边形裁剪框的算法。     

基于凸剖分的多边形窗口线裁剪算法

以不增加新点的方式将多边形剖分为一些凸多边形,并基于这些多边形的边建立二叉树进行管理.裁剪计算时,根据二叉树快速地找到与被裁剪线有相交的凸多边形,然后运用高效的凸多边形裁剪算法进行线裁剪.该方法能自适应地降低裁剪计算的复杂度,使其在O(logn)和O(n)之间变化,并在大多数情况下小于O(n),其中n是多边形边数.虽然该方法需要进行预处理,但在许多应用(如多边形窗口对多边形的裁剪)中,其总执行时间(包括预处理时间和裁剪时间)比已有的不需要预处理的裁剪算法少很多.     

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

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

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

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

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

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

基于VC的任意不自相交多边型新裁剪算法

计算机图形学的基础经典裁剪算法的改进是添加一些附加的判断条件以提高效率或只是适用于某种特殊条件环境的应用。对常用的线段裁剪算法和多边形之间的裁剪算法进行简单的原理描述与比较,提出一个新的任意不自相交多边形之间的裁剪算法,该算法以基本线段单元为控制对象,在线段求交中使用梁友栋-barskey算法,然后从裁剪之后的线段单元组中寻找多边形的线段单元组合。分带环多边形之间的裁剪和不带环多边形之间的裁剪来详细描述算法的实施步骤和算法流程;最后用C++语言实现该裁剪算法,结合工程应用解决了多边形裁剪实例,通过测试证明该算法对不自相交多边形之间的裁剪是很有效的,同时使用该算法解决了多边形与折线之间的裁剪问题,改善工程应用。     

基于圆形窗口的简单多边形填充算法

提出了一种新颖而实用的圆形窗口简单多边形填充算法，它具有快速裁剪与填充双重功能，也可完成单纯地裁剪功能，该算法将多边形的边视为有向线段，通过引入多边形顶点的入边和出边产我点的概念，深入研究了多这形被圆形窗口裁剪后区域的确定性填充问题，使截剪功能隐含于填充过程中，从而节省了填充之前的裁剪过程。     

Industrial strength polygon clipping: A novel algorithm with applications in VLSI CAD

We present an algorithm to compute the topology and geometry of an arbitrary number of polygon sets in the plane, also known as the map overlay. This algorithm can perform polygon clipping and related operations of interest in VLSI CAD. The algorithm requires no preconditions from input polygons and satisfies a strict set of post conditions suitable for immediate processing of output polygons by downstream tools. The algorithm uses sweepline to compute a Riemann–Stieltjes integral over polygon overlaps in O((n+s)log(n)) time given n polygon edges with s intersections. The algorithm is efficient and general, handling degenerate inputs implicitly. Particular care was taken in implementing the algorithm to ensure numerical robustness without sacrificing efficiency. We present performance comparisons with other polygon clipping algorithms and give examples of real world applications of our algorithm in an industrial software setting.     

A comparison of three shadow volume algorithms

This paper describes and compares three different approaches to computing shadows. Each is based on the idea of shadow volumes: basic algorithm, Shadow Volume BSP Tree algorithm, and Shadow Tiling, based on 2D space subdivision. Binary Space Partition trees are used to organise the polygons in the scene in a front-toback order from the point of view of the light source, and then shadows on a polygon are computed by clipping the polygon to the shadow volumes of polygons closer to the light source. The three algorithms differ in their approach to minimising the number of comparisons of a polygon with the shadow volumes of its predecessors, and one of the algorithms represents the total shadow volume itelf by a BSP tree. The algorithms are compared analytically and statistically.