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

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

有共线边的多边形窗口的线裁剪算法

采用参考坐标系B、顶点类型、重合段、处理单位Unit等概念，有效地处理了交点的计算以及裁剪线通过顶点或边的情况．由于利用了多边形窗口结构上的有序性和完整性的特点，文中算法不仅适用于凹多边形窗口，而且适用于相邻边共线等特殊情况的多边形窗口。     

判断点与多边形拓扑关系的改进算法

为了解决射线法不能有效地判断点在复杂多边形内或外的问题,根据射线与多边形边界相交的特性,分析射线所经过的多边形的不同类型顶点,提出了对顶点数加1、加2和加3的运算方法。通过判断交点个数的奇偶性,改进了射线法,并给出了计算模型和算法的详细步骤,简单有效的将现有的射线法扩展到更复杂的多边形中,能准确的判断点与多边形的位置关系。4种不同算法对比分析结果表明,该算法能解决其它3种算法存在的问题,并且在简单多边形和复杂多边形中都是有效的。     

加强局部简便计算的点在多边形内的高效判定

点在多边形内的检测是计算几何中的一个基本问题,有着广泛的应用需求。已提 出许多方法减少要测试的多边形的边以加速。其中,均匀网格法具有很好的作用,因为各网格 中的边很少,而测试点可迅即定位于一个网格。我们曾提出一种均匀网格法,预计算各网格中 心点位于多边形内/外的属性,然后将测试点与所在网格的中心点连线,检测该连线与多边形的 边的相交情况即可。其预处理和检测的复杂度分别为 O(N)和 O( N ),N 为多边形的边数。本 文在此基础上进一步改进,预计算网格交点位于多边形内/外的属性,然后将测试点与其邻近网 格交点的连线,转换为与坐标轴平行的两条相连直线段,以提高与多边形边求交计算的便捷性。 实验结果表明,可将检测速度提高 2 倍多。     

多边形链求交的改进算法

多边形链求交是CAD&CG及相关领域研究中的一个基本问题 利用多边形链的凸凹性、单调性等特性 ,结合包围盒技术 ,在扫描线算法基础上 ,提出一种多边形链求交的改进算法 该算法特别适用于包含大量直线段且交点数相对于顶点数少得多的多边形链求交的情况     

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

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

判断点与简单多边形位置关系的新算法

基于射线法提出了一种新的判断点与简单多边形位置关系的算法。该算法是通过查找简单多边形所有顶点在确定区域内中斜率最小点,以此点确定一条射线,使得这条射线不穿过简单多边形的顶点。此算法不但保持了原来射线法相对其它方法有容易理解、计算简单等优势,并在此基础上排除了射线法中特殊的射线与简单多边形的顶点相交或射线过简单多边形边的特殊情况,大大地降低了算法的时间复杂度,提高了检测速度。     

借助梯形分割的点面包含分析

在诸多研究领域中,判断点是否在多边形内是一个非常基本的问题。在分析了解决这一问题的传统方法基础上,提出了一种基于梯形分割的点面包含算法。该算法将多边形分割成若干个梯形网格单元,将判断点是否位于多边形内的问题转化为判断点是否位于梯形网格单元中这一问题。算法已用于GIS平台软件相应的包含分析模块,试验结果证明该算法稳定可靠、适用于任意复杂多边形而无需对奇异情况进行单独处理。     

圆与多边形重叠区域的判定算法

本文提出了一种实用的圆与多边形重叠区域的判定算法，它集判断与确定功能于一体。该算法将多边形的边视为有向线段，通过引入多边形顶点的入边，出边交点的概念，研究了圆与多边形重叠区域的确定问题，并给出了作出其重叠区域的定理。     

一种高效的一般多边形线段裁剪算法

直线段的裁剪是图形绘制中的基本问题,针对当前主流的直线段裁剪算法,或者不能适应一般多边形窗口的裁剪,或者在复杂裁剪情况下裁剪效率低下的问题,提出了一种高效的一般多边形线段裁剪算法.该算法排除掉明显不在裁剪窗口内的直线段,以及相交于伪交点的情况,再利用改进的交点计数法确定位于窗口内的区间.实验结果表明,该算法不仅具有高效性,还能适应于复杂的裁剪情况.     

基于网格中心点的点在多边形内的高效判定

提出一种基于均匀网格的点在多边形内的高效判定算法.它首先建立均匀网格,并从左至右依次计算每个网格单元中心点的位置属性.每个单元中心点的位置属性直接依据其左侧邻接单元已知位置属性的中心点快速获得.在判定点的位置时,确定被测点所在单元,并依据该单元中心点的位置属性判定被测点的位置属性.由于预处理和判定时均利用邻近点的已知位置属性来确定未知点位置属性,可以很好地进行局部化的计算.因此,新方法比现有方法快很多,并且其预处理时间复杂度也由同类网格算法的O(N3/2)下降为O(N).同时,新方法可以统一处理含有自相交及重叠边的非流形多边形.实验结果表明,相比于其他基于均匀网格的方法,新方法可将预处理的速度提高几倍,将判断计算的速度提高十几到几十倍.其速度甚至优于具有该问题最低判定计算时间复杂度O(logN)的基于凸剖分的判定算法.     

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

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

基于拓扑映射的点集在凸多边形内外判断算法

通过拓扑映射 ,点在凸多边形内外的判别可以转化为映射点在射影直线上的位置关系问题 .首先通过设置中心点 ,获取凸多边形各顶点的拓扑映射点 ,对于每个检测点 ,根据其映射点与顶点拓扑映射点的相对位置关系 ,即可确定检测点位于多边形哪条边的范围内 ;然后将检测点与该边进行包围盒测试 ,对于点在边包围盒外的情况 ,只需根据比较判别即可得到结果 ,对于点在边包围盒边界上或内部的情况 ,则需通过叉积运算进行判别 .该方法几何意义清晰 ,实验结果表明 ,该算法运行可靠 ,对于单个点或多点组成的点集均有较高的检测速度 .     

基于有序简单多边形的平面点集凸包快速求取算法

凸包问题是计算几何的基本问题之一，在许多领域均有应用。传统平面点集凸包算法和简单多边形凸包算法平行发展，互不相干。本文将改进的简单多边形凸包算法应用于平面点集凸包问题中，提出了新的点集凸包算法。该算法首先淘汰掉明显不位于凸包上的点，然后对剩余点集排序，再将点集按照一定顺序串联成有序简单多边形，最后利用前瞻回溯方法搜索多边形凸包，从而得到点集的凸包。本文算法不仅达到了Ｏ的理论时间复杂度下限，而且算法     

基于单调链的判断点是否在多边形内的方法

提出了一种判断点是否在多边形内的新方法，该方法由两部分组成：(1)预处理，即先求出多边形的所有极点；(2)检测，即采用折半查找找到相关点和相关边，根据被检测线穿过的相关边数来判断检测点是否在多边形内。该方法解决了射线法无法解决的奇异情况，且在检测过程中不必处理多边形的所有边。实验结果证明，该方法简单、易实现、快速。     

基于凸片段分解的多边形窗口线裁剪算法

将多边形窗口的边顺序地分割成一些片段,使得每个片段都能局部地形成一个凸多边形,称为凸片段,并建立一个二叉树来管理这些凸片段．在裁剪计算时,先根据二叉树快速地找到与被裁剪线段相交的凸片段,再利用高效的凸多边形线裁剪算法对这些凸片段进行裁剪操作．文中算法能有效地降低裁剪计算的时间复杂度,使其在O（logN）～O（N）之间自适应地变化,且大部分情况下时间复杂度小于O（N）．     

一种基于离散点的透明折射算法

传统真实感图形绘制所采用的造型都是基于多边形的表示方法 ,由于该方法存在着一些不足之处 ,为此提出了一种基于离散点的表示方法 ,该方法首先求出场景中 ,曲面上的某些离散点 ,然后将这些离散点排列成若干序列并存储 .同时也提出 ,并实现了一种基于离散点的透明折射算法 ,该算法的关键就是如何确定检测线段 ,由于只有该检测线段上的像素对应序列中的点才有可能在折射线上 ,这样就抛弃了大量的不需要参与运算的点 ,因此可减小计算量 .试验结果表明 ,该表示方法及透明折射算法可以较准确、真实地反映实际场景中的透明现象 .     

多边形的简单性、方向及内外点的判别算法

本文用三维空间来解决二维平面问题，从而得出一个简单的点与有向线段之间关系的判别式，并在此基础上根据凸凹点的性质及有向多边形的性质提出了不用解任何方程组也不用于计算三角函数的判定平面多边形的简单性，方向及内外点的简单，强健而高效的算法。     

基于线段与线段求交的矩形窗口裁剪算法

我们首先对线段是否完全可见进行判定 ,然后对被裁剪线段与矩形窗口四边所在的线段是否相交进行判定并求交。若交点存在则用替换法替换相应的点 ,最后连接被替换后的点得到被裁剪后的线段 ;若交点不存在则线段完全不可见 ,线段将被完全裁剪掉。