确定两个任意简单多边形交、并、差的算法

提出了把多边形的边分为奇偶边的新思想，根据输入多边形A，B之间边的拓扑关系，划分A，B边为内边、外边、重叠边3种，揭示A，B与它们的交、并、差之间边的本质联系，进而描述了确定任意两个简单多边形交、并、差算法．算法的时间复杂度为O((n m k)log(n m k))，其中n，m分别是A，B的顶点数，k是两多边形的交点数．算法建立在数学理论基础之上，很好地处理了布尔运算的奇异情形，比如重叠边，边与边相交于边的顶点等情形．本算法易于编程实现。     

确定两个任意简单多边形空间关系的算法

阐述了把简单多边形的边分为奇偶边的新思想,根据一多边形的边与另一多边形的拓朴关系,划分边为5种拓朴类型:内边、外边、重叠边、相交边、复杂边,进而给出了确定两个多边形空间关系的算法,算法的时间复杂度为O((n+m)log(n+m)),其中n、m分别是两输入多边形的顶点数。该算法建立在数学理论基础之上,没有奇异情况需要处理,易于编程实现。算法的主要思想对确定两个简单多面体空间关系亦有参考价值。     

基于圆形窗口的简单多边形裁剪算法

提出了一种新颖而实用的圆形窗口Ｖ对多边形Ｐ的裁剪算法。它将多边形Ｐ的边视为有向线段，通过引入多边形顶点的入边和出边交点的概念，深入研究了Ｐ被Ｖ裁剪后的区域确定问题，给出了作出Ｐ在Ｖ内部分的定理     

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

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

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

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

基于结点等效变化的缓冲区生成算法

目标缓冲区生成的算法一般都要经过两个阶段，即单个目标缓冲区多边形的独立生成过程和多个目标缓冲区多边形间的重叠合并过程。本文将要生成的缓冲区边界凹侧结点做等效变化成两个相等的点，且定义其连接关系为圆弧，从而取得了边连接的循环运算，便于处理和计算，消除了凸凹两侧缓冲边界数据链不一致性的表达，只寥寥几行代码实现了折线单目标缓冲区的生成，并且易于缓冲边界拓扑关系的建立。     

圆的等面积逼近和生成

本文描述用多边形等面积逼近和生成圆的算法，此算法是用一个与圆相交的多边形（而不是通常用的内接多边形）逼近一个圆，这个多边形的面积精确地等于圆的面积。因此，可以认为这种算法产生的多边形是对圆的一种等面积最佳逼近。     

任意多边形窗口的圆裁剪算法

针对任意多边形窗口内圆的裁剪问题,本文提出一种更加全面、有效的裁剪算法.该方法提出借助x-扫描线算法来判断圆和多边形窗口的位置关系,排除圆完全在窗口内或者窗口外的情况;针对多边形窗口和圆相交的情况,按照逆时针方向依次求出多边形各边与圆的交点;最终,通过判断两点间的关系,决定两点之间画线还是画弧,完成圆的裁剪.实验结果表明,该方法能够有效全面的完成多边形窗口的圆裁剪.     

一种自适应智能三边定位算法的设计与实现

为了有效抑制室内复杂环境对无线传感器网络节点定位精度的影响,以及降低室内定位系统对环境的依赖性,提出了一种自适应智能三边定位算法.该算法通过测量移动节点与各信标节点的距离值的波动情况,生成相应的自适应因子.该变化因子控制三边定位算法中距离半径的微调量,使3个定位圆的重叠部分的面积小于一定的数量级,然后在重叠区域中作最大内接圆,将圆心作为移动节点的位置.仿真结果表明该算法比加权三边定位算法具有更高的定位精度,鲁棒性好,能适应不同规模和类型的定位系统.     

多边形区域阴影线覆盖的Y-X算法

多边形区域阴影线覆盖问题是指用一组指定倾斜角的等间距的平行线覆盖以多边形为边界的区域.本文根据光栅图形显示中多边形扫描转换的 Y-X 算法的思想,给出了一个多边形区域阴影线覆盖的 Y-X 法.该算法既适用于单个多边形区域,亦适用于多个多边形区域.关于推广此算法,使之适用于边可以是圆弧的多边形区域的问题,本文亦作了讨论.本算法已应用于一个实际的CAD系统.     

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

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

基于R＋树的地图叠加分析双重循环算法

地图叠加是非常重要的 GIS空间分析功能之一 ,为此 ,提出了一种新的基于 R 树空间索引的矢量地图叠加分析双重循环算法 ,首先采用多边形穷举求交方法计算出线段相交点 ;然后运用引入、引出交点交替配对的叠加结果弧线段生成原则 ,进一步实现了面面叠加和线面叠加的双重循环算法 ;最后引入 R 树空间索引对空间数据的高效存取机制 ,对算法进行改进 ,进一步提高了计算速度 .实践结果表明 ,该算法快速、有效 ,具有较强的应用价值 .     

判定凸多边形可碰撞的最优算法

设P与Q是平面内任意二互不相交的凸多边形,d为任一给定方向,本文研究P沿d以平移方式运动可否与Q碰撞的判定问题.文中定义了凸多边形顶点集上的偏序关系,给出了判定可碰撞性的新的充分必要条件,据此采用四分搜索方法构造了判定可碰撞的算法.在最坏情况下算法的复杂度为O(logn),在不计常数因子的情况下,这是最优的.     

Efficient algorithm for polygon overlay for dense map image data sets

A map consists of a finite set of mutually disjoint polygons. A data structure and efficient algorithm for polygon overlay of dense map image data sets are discussed. The data structure, referred to as the ending-x structure, is a variant of the y-partition structure developed by Merrill which is still widely acclaimed as an optimum raster data structure. The modest refinement of the ending-x structure further reduces raster data volume. More importantly, it can significantly enhance the process of polygon overlay for multiple map image data sets. Considering the density of many map image data sets, and the significance of the polygon overlay problem to spatial data handling, these are significant advances. The paper describes the ending-x data structure and compares the algorithm for polygon overlay suggested by Merrill with one employing the ending-x structure.     

基于网格模板的栅格与矢量叠加统计算法

为了避免矢量栅格数据叠加统计分析中采用逐像元“扫描”判断法所导致的处理速度缓慢的问题,提出将矢量多边形底图切分成具有一定水平、垂直空间尺度的多行、多列网格模板,保存该模板文件,并在模板的基础上进行快速统计叠加的办法。实质是将矢量栅格数据叠加计算间接转换为计算简便的网格格点与栅格数据之间的叠合,从而提高了计算速度。由于底图格点大小及位置与栅格数据不能有效配准而导致“错位”,该文重点给出了解决此类问题在3种不同匹配方式下的处理算法。     

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.     

圆形窗口的凸多边形裁剪

已有的多边形裁剪算法都是针对矩形窗口或凸多边形窗口进行的。但是，在实际应用中，也常常使用圆形窗口对多边形区域进行裁剪和填充。因此，本文提出一个对干圆形窗口的凸多边形区域裁剪法，并且给出作出凸多边形Ｐ在窗口Ｖ之内部分的定理。     

CPN：一种基于小世界网络的P2P模型

利用群论理论中Cayley图方法,构建一种P2P动态覆盖网络模型CPN,并定义其DHT协议。CPN符合小世界网络的定义,具有较高聚集系数,稳定性好并支持显式分组。由于该覆盖网络是对称图,其上的路由算法相比经典的P2P覆盖网络更容易实现。仿真实验表明,该模型相比常见覆盖网络具有更优的性能。     

判定点集是否在多边形内部的算法

本文提出了判定ｎ个点的点集Ｓ是否落入多边形Ｌ内部的算法，该算法的复杂性为：ｍａｘ（Ｏ（ｍｎ），Ｏ（ｌｎ ｌｏｇ ｎ））比比较和Ｏ（ｌｎ）次乘法，其中ｍ是Ｌ的顶点数，ｌ为Ｓ的凸包层数。