一种任意简单多边形求差算法

提出一种基于线段操作的简单多边形求差算法。该算法的主要过程为:应用基于单调链的扫描线求交算法,求取交点,该过程减少了求交过程中的比较次数,从而提高了求交效率。基于线段操作的结果多边形连接算法,该过程利用基础的计算几何理论,寻找构成结果多边形的边,得到两个多边形的差。实验表明该算法思路简单,数据结构简单,易于编程实现,对于简单多边形求差问题具有普适性。     

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

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

空间关系中两相邻实体间最近距离算法研究

空间距离关系是最基本、最重要的一类空间关系。通过先考虑二维空间中两任意实体之间不同的相对位置关系,再利用构建Delaunay三角网寻找两者的邻近区域,从而计算出两者之间的最近距离。本文还提出了基于约束圆寻找并计算任意两个实体多边形之间的最近距离方法,并给出了约束圆的特征。这种方法适用于不用区分实体多边形的形状与位置的各种情况。     

城市地下管线缓冲区分析方法研究

缓冲区分析是地理信息系统中使用非常频繁的一种空间分析,基于地下管线系统缓冲区分析,可以通过计算绘制原始多边形外一定缓冲距离的缓冲区多边形,由缓冲区多边形查询受影响管线段信息。本文通过计算缓冲区多边形边界点坐标的方法,构造缓冲区多边形,利用缓冲区多边形与图上管线段的空间过滤关系,编程实现地下管线缓冲区管线段信息的获取。通过对作者开发的管线管理系统缓冲区分析模块进行测试,最终得到准确的管线段信息。     

伪形心多边形形心距离计算方法

针对多边形形心距离计算过程中存在的形心位于多边形外的问题,该文提出伪形心的概念,通过三角剖分的方式,计算多边形边界到多边形形心距离最小的点,将形心合理地平移到边界上,进而计算多边形形心距离。针对伪形心存在于邻接边的特殊情况,又提出将形心平移到多边形主骨架线上的改进算法。该文提出的算法简单,易于实现,适用性强,进一步扩展了多边形形心距离计算的思路。     

利用泰森多边形的点实体匹配算法

针对众源地理数据中的同名点实体之间存在距离、方向等非一致性偏差,导致匹配困难的问题,该文提出了基于泰森多边形的点实体匹配算法。利用相匹配的点实体数据集其对应的泰森多边形具有较高的对应关系这一特点,将不确定的点与点之间的匹配转化为匹配度更高的对应泰森多边形的匹配。首先统计出被彼此泰森多边形包含的点对,根据点对的距离概率分布,计算出距离阈值作为确认同名实体的条件之一;然后将泰森多边形的位置及形状相似性作为匹配条件二;最后将相似度最高的实体确认为同名实体。通过实验与现有的几种点实体匹配算法进行了比较,结果表明,该算法具有较高的查全率和查准率,且普适性强。     

曲边多边形中轴提取的新方法

针对现有多边形中轴提取方法在处理复杂图形和特殊图形上有较大困难的不足以及中轴连通性和位置准确性难以保证等问题,提出了一种曲边多边形中轴提取的新方法。首先在简单多边形的基础上进行拓展,提出曲边多边形的概念,并相应地定义了曲边多边形的中轴,然后在栅格距离变换的基础上引申出最近边缘点集距离均值变换,最后结合曲边多边形中轴点的特征和距离变换的原理制定出高效中轴点判定规则,利用种子点生长判别法提取曲边多边形的中轴,并给出具体实现步骤和流程。通过多组不同类型多边形及道路网与河网的实例验证,新方法不仅能适用于各类多边形,且能较好地抑制图形边界噪声的干扰,提取出具有良好的光滑性、准确性和连通性的多边形中轴,弥补了传统方法的不足。     

简单多边形间最大距离的求解算法

求解任意两个简单多边形间的最大距离,在几何图形计算中,一直是一个基本问题。在对多边形自身的特性以及两多边形间关系进行深入分析的基础上,提出了一个基于折线凸包的单调性的简单多边形间最大距离的求解算法。根据封闭折线内部所具有的特性,把封闭折线拆分成两个断开的折线,使一条折线在另一条折线左边。两个多边形分别被拆分成四条折线,两个分为一组。分别求出每组中两条折线的凸包,利用凸包的单调性可以快速地找出两个距离最远的顶点,其中较大的是两个简单多边形间的最大距离。算法的时间复杂度是线性的。     

地理信息系统中由线段数字化记录重建多边形的方法

本文研究由地图数字化线段记录重新形成多边形的方法。从结点、线段和多边形的拓扑关系出发,着重分析线段的连接、多边形组成线段的序列寻找、岛状多边形的处理、多边形属性编码等,为向量结构地理信息系统建立有关多边形的数据库记录提供算法基础。所述的方法无需规定线段数字化的方法与次序。     

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

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

邻接凸多边形方向关系计算及其推理

在对拓拟邻接凸多边形方向关系计算特殊性分析的基础上，提出了一个邻接凸多边形方向关系计算法和二维空间方向关系推理方法。与Voronoi图所表达的邻近拓扑关系相结合，该算法可以用于计算离散二维空间目标之间的方向关系。     

支持地图综合的面状目标约束Delaunay三角网剖分

针对多边形面状目标的综合问题,建立了二维空间中约束Ｄｅｌａｕｎａｙ三角网剖分结构,融入多边形的环、岛屿、边界、顶点的描述,通过形式化条件检索,在该结构上提取二维空间中各种感兴趣的由剖分三角形组成的区域,用于支持地图综合中邻近多边形的搜索、多边形弯曲部位的识别、冲突关系探测、多边形合并等操作。并对基于骨架线的图结构建立、分枝宽度计算等几何问题进行了详细讨论,指出了其在诸如双线河中轴化、街道中轴线网络模型建立、多边形合并中的邻近关系分析、面状目标注记自动定位领域的支持作用。     

制图综合中建筑物多边形的合并与化简

讨论了数字环境下顾及建筑物矩形几何特征的多边形自动综合算法,针对多边形之间的拓扑邻近与视觉邻近两种空间关系,提出了基于矢量和基于栅格的两种建筑物多边形合并方法。关于建筑物形状的化简,本文提出了矩形差分方法,并在此基础上建立了建筑物多边形化简的层次化途径。     

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

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

道路网络示意图的多边形生长算法

道路网络示意图是实体网络的抽象表示,因其更加符合人的认知习惯,在地图服务与地图制图领域已得到初步应用。以路径为单位的网络示意图自动生成算法只顾及节点与线段的局部布置,且较难以维护网络拓扑一致性。本文以闭合多边形(网眼)为基本单位,利用网眼的独立性与邻接性,提出了多边形生长算法,核心思想是将道路网络分类为闭合多边形与非闭合线段,以闭合多边形提取、映射、优化为主线,辅助组合非闭合线段。算例分析验证,本算法在网络均衡分布及拓扑一致性方面具有优势。     

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

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

RaPC:一种基于栅格化思想的多边形裁剪算法及其误差分析

传统的基于矢量计算的多边形裁剪算法的时间复杂度介于O(Nlog N)~O(N2)之间,且计算过程与特定的复杂数据结构耦合紧密,难以进行底层优化和细粒度并行化。在满足一定误差要求的前提下,采用栅格化处理思想可以实现多边形快速裁剪。本文在已有多边形裁剪算法特征的基础上,提出了一种基于栅格化处理思想的多边形裁剪算法——RaPC算法,并对其误差进行了分析和讨论。试验结果显示,RaPC算法的计算效率随网格单元增大呈幂函数规律降低;当网格大小恒定时,RaPC算法效率随多边形顶点数量呈线性增长,计算时间复杂度为O(N);在处理小数据集时Vatti算法表现出了较高效率,但是在处理包含大量顶点的多边形叠加时,RaPC算法更为高效;RaPC算法的面积误差与网格大小直接相关,提高网格空间分辨率可以有效地降低面积误差。RaPC算法在处理包含大量顶点的多边形叠加分析时比Vatti算法更为高效。     

改进的边标志栅格化算法

矢量多边形的栅格化算法是地理信息系统的基础算法之一。本文通过分析比较,认为边标志算法于众多栅格化算法中最为适合地理信息系统,并通过简化边界标志过程进行了改进,使得处理流程更为简单清晰,实现更为方便,算法更为精确有效。该改进算法使用统一的相加方法进行边界标志,无需对特殊顶点、尖锐多边形、带岛多边形等进行判断和边界转换,便可一次性正确标志,且无需顾及多边形边的存储顺序,更加适合地理信息系统矢量多边形的数据结构。