基于线段操作的多边形求交算法研究

根据多边形之间的相交状态求所有目标多边形线段与源多边形边界的交点;利用点与多边形关系判别法则判断出目标多边形与源多边形的公共线段;目标多边形与源多边形对调,再次判定出公共线段;最后将公共数据选择集中的公共线段首尾连接构成闭合多边形即为两个多边形求交结果。求交算法以线段操作为核心求解两多边形的交集,通过遍历公共线段来完成交集多边形边界的构建。该算法结构简单,易于编程实现,计算工作量小,求交效率高,已成功应用在土方计算软件开发中,在地图制图和地理信息空间分析等方面有广阔的应用前景。     

基于单调链和STR树的简单要素模型多边形叠置分析算法

针对简单要素类叠置分析的特点,利用STR(sort-tile-recursive)树索引改进算法能够将尽量多的多边形节点存储在STR树的叶节点中,减少在空间数据库中检索多边形时的磁盘读取次数。算法对多边形边界进行关于坐标轴的单调链分割,并在多边形求交过程中引入平面图的概念,利用平面图元素与各个多边形的拓扑关系来组织叠加后的多边形。该算法能有效减少求交点的时间,在线段求交中加入对连续出入点特殊数据的处理。同时该算法使用单调链减少多边形求交过程的比较次数,与其他使用双链表或单链表的算法相比具有占用空间少及处理速度快的特点。     

基于单调链的Red/Blue扫描线求交算法

提出了一种基于单调链的Red／Blue平面扫描线算法。该算法针对GIS中线段之间具有连接关系的特性，将平面连接线段集分解为一组单调链，通过对单调链的粗扫描过滤和对线段的精扫描求交，减少了扫描过程中的冗余计算，提高了线段集求交点的效率。实验证明，该算法对于处理具有连接关系的线段集的求交点问题具有很高的效率。     

以节点操作实现多边形求交的算法

根据多边形之间的交点状态确定与交点相关的节点信息,以节点操作为核心求解两多边形之间的交集。在此基础上,考虑重叠边、边边相交于边节点等情形,通过遍历交点来完成交集多边形边界的构建,从而提出一种多边形求交运算的改进算法。该算法结构简单,具有较快的计算速度和较高的效率,适合于地理信息系统中的空间叠置分析、缓冲区分析应用,对于地图制图中区域要素的截取操作也具有重要的参考价值。     

基于交比的单幅图像平面几何信息提取算法

提出并实现了基于交比这一射影变换不变量的单幅图像平面几何信息提取方法。该方法首先利用结构化场景中的平行、垂直等几何关系计算平面的灭点灭线;然后利用平面上已知长度的参考线段及灭点、灭线信息构建交比;最后依据待求线段与已知几何信息的位置关系计算待求线段的长度。对实验数据计算结果的精度分析验证了算法的正确性和可行性。     

平面拓扑模型的多边形矢量更新算法

为了提高土地利用变更图斑的更新效率,文章提出了一种平面拓扑图模型下的多边形矢量数据更新算法:采用平面拓扑图的数据结构,实现多边形几何对象间的线段求交计算,解决多边形间在重点和重边情况下的几何裁剪问题;通过对底图几何对象与变更几何对象之间拓扑关系的判别,不仅能够检测出矢量底图数据中发生变化的几何信息,而且可以减少几何运算的次数,提升矢量数据的更新效率。实验结果表明该算法具有良好的适用性及较高的更新效率。     

顾及几何形状相似性的简单多边形最近距离计算方法

提出简单多边形距离计算方法,在计算简单多边形最近距离的同时,可以求得多边形之间彼此面对的线段链.针对多边形之间不同位置关系,给出不同的最近距离和多边形之间彼此面对线段链的计算算法.     

关于优化n条线段求交算法的研究

首先分析了n条线段相交算法的不足，然后系统地阐述利用扫视法缩小求交线段的范围，利用点位判别法高效判断两线段是否相交的理论，从而提出了一套较为优化的n条线段求交算法。本文对其算法给出详细的分析和讨论，最后指出此算法的适用范围。     

空间对象精确网格索引的实现

针对使用传统算法创建网格索引存在遗漏网格的缺点,本文提出一种建立精确网格索引的新算法。该算法基于对线段与其所经过的网格对角线的关系的分析,实现了对线、多边形(包括复杂多边形)目标的精确网格索引。     

基于条带扫描思想的线目标缓冲区快速构建

空间目标缓冲区建立的传统算法是基于平行双线扩展思想,在基线复杂分布情形下,该算法对于岛屿和多边形外环的构建及空间关系的处理十分困难。将计算几何的旨在提高运算速度的“条带扫描”思想引入到缓冲区建立过程,对曲线分离出多个两点连接的线段集,生成每条线段的椭圆形基元缓冲区,通过条带扫描法对基元缓冲区叠置生成岛屿内环与多边形外环,判断其间的套合关系。该算法在严密的逻辑组合分析条件下能够对单条或多条基线的复杂情形生成正确的缓冲区多边形,同时运算速度得到改进,达到O(nlogn)。     

两个简单多边形求交的算法

采用了双向链表这种数据结构,对两简单多边形的顶点及交点进行存储,在对交点进行插入时,可直接插入链表中,避免了利用单向链表或数组进行存储时对点的重复查找。通过遍历两个顶点、交点混合表,可得到两多边形的交及多边形的顶点,从而得到两多边形的交集。相对其他类似的算法,该算法具有较快的计算速度和较高的效率。     

多边形间空间关系查询的异构多核架构并行算法

目前在空间关系查询中常用的Plane Sweep算法是一种串行算法,在处理海量空间数据时效率较低,而已有的并行计算方法对于普通的计算机并不适用。本文针对这个问题,提出了一种多边形间空间关系查询的异构多核架构并行算法,该算法先利用STR树索引过滤掉不相交的多边形,然后将过滤后的多边形数据集合分解为点集合和边集合,并对其构建四叉树索引;在保证数据浮点运算精度符合要求的情况下,利用GPU强大的批量运算能力快速处理边与边的相交情况并据此逐步计算得到环间的拓扑关系,再根据环间拓扑关系计算得到多边形间的维度扩展九交模型(DE-9IM)参数值;根据DE-9IM参数值与空间关系查询条件相比对,输出查询结果。最后通过试验验证了算法的准确性与高效性。     

Tile‐based polygon overlay of vector data in a virtual globe

The demand for analysis of large‐scale data has increased with increased access to spatial vector data. Polygon overlay of vector data in a virtual globe requires proprietary data structures and proprietary analysis algorithms. A vector data structure is designed for rapid polygon overlay in a virtual globe by recording the metadata of the triangles (TriMeta) that constitute polygons. A polygon overlay algorithm is proposed based on this data structure. The overlay of two complex GIS polygons is transformed into the intersection computation of their 3D triangular presentations. The intersection computation of two sets of triangles is reduced considerably by utilizing TriMeta to filter out the disjoint triangle pairs and rapidly identify the contained triangle. The new method improves the overlay efficiency in a virtual globe because the amount of computation required to calculate the intersections of two large polygons and drape the intersections onto a terrain surface is reduced.     

基于反向射线与顶点退化判断点在多边形内外的算法及应用

利用射线法判断点在多边形内外的方法简单易用,但是对于交点中含有顶点的情况,使用这种方法将产生奇异性,大大降低判断的准确性。鉴于这种情况,通过对已有的判断点在多边形内外算法的分析与研究,提出了基于反向射线和顶点退化处理相结合判断点在多边形内外的算法,并给出了具体的程序设计以及将该算法推广到了复杂多边形的情况。同时,将该算法应用于某市基础地理信息系统数据预编辑中,结果表明,判断准确率大大提高。     

基于GPU的任意多边形相交面积计算方法

一直以来,任意多边形相交面积的高效计算都是地理信息系统中空间分析算法研究的重点。文中提出了一种基于GPU的栅格化多边形相交面积算法GPURAS,在此基础上,分别采用蒙特卡罗方法和遮挡查询技术进一步提出GPURASMC算法和GPURASQ算法,并证明了上述算法的正确性。实验对简单多边形、任意复杂多边形及大数据量多边形进行了测试对比,结果表明:GPURAS算法精度高,通用性较好但效率受CPU与GPU通信延迟的影响;GPURASMC算法效率较高但牺牲了部分精度;GPURASQ算法精度高、效率高但局限于特定运行环境。与基于CPU的传统算法相比,文中所提3种算法效率更高,在处理包含大量顶点的多边形时,效率提升尤为明显。     

一种多边形交、并、差运算的有效算法

以周培德的Z5-4算法为参考，提出了一种简单多边形交、并、差运算算法——IBO算法。该算法能够处理二维现实世界中的各种情况，对于地理信息系统的空间分析有较好的应用价值。     

A general framework for error analysis in measurement-based GIS Part 3: Error analysis in intersections and overlays

This is the third of a four-part series on the development of a general framework for error analysis in measurement-based geographic information systems (MBGIS). In this paper, we study the characteristics of error structures in intersections and polygon overlays. When locations of the endpoints of two line segments are in error, we analyze errors of the intersection point and obtain its error covariance matrix through the propagation of the error covariance matrices of the endpoints. An approximate law of error propagation for the intersection point is formulated within the MBGIS framework. From simulation experiments, it appears that both the relative positioning of two line segments and the error characteristics of the endpoints can affect the error characteristics of the intersection. Nevertheless, the approximate law of error propagation captures nicely the error characteristics under various situations. Based on the derived results, error analysis in polygon-on-polygon overlay operation is also performed. The relationship between the error covariance matrices of the original polygons and the overlaid polygons is approximately established.This project was supported by the earmarked grant CUHK 4362/00H of the Hong Kong Research grants Council.     

基于二叉树思想的任意多边形三角剖分递归算法

提出了一种基于二叉树思想的任意多边形三角剖分递归算法。该算法采用二叉树思想，确定剖分三角形的二叉树状结构，并采用递归算法实现。这算法可适用于任意形状的凹或凸多边形，也适用于包含岛屿的多边形。此外，在考虑边界点高程的基础上，可充分顾及地形特征。该算法完全适用于长距离河流流域的三维面状表达。     

DGPS水下立体定位系统的解析求解算法

差分GPS水下立体定位系统通过测量目标到两个浮标的距离差来进行空间定位,由于这种双曲线定位模型在进行迭代计算时容易发散,所以本文根据空间浮标和目标的空间几何关系,提出了一种空间双曲线交会的直接算法,该方法能够直接求解目标点的空间坐标,且不存在定位结果的发散问题。