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

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

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

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

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

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

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

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

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

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

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

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

自动绘制室内平面图的点云向量追踪算法

根据建筑物室内墙壁的空间姿态特征,建立了一种自动绘制室内平面图的点云向量追踪算法。首先截取一定厚度的室内墙体点云并将其投影至水平面,在投影平面上建立正方形格网,对投影后的平面点进行分割管理,并通过八邻域算法对网格内点云进行聚类。然后采用网格重心法对聚类后的点云数据进行抽稀,并根据邻域内点间距与连线向量夹角大小对抽稀后的点进行追踪排序,建立追踪方向的向量序列,结合向量序列中相邻值夹角的突变情况完成不同墙面的点云分割。最后采用最小二乘算法对分割得到的相同墙面点云进行直线拟合,求取相邻墙体直线的交点,建立房屋墙体平面投影线段及其空间连接关系,依序输出墙体投影线段,完成房屋平面图的绘制并导出DXF格式数据交换文件。通过对某小区建筑物室内扫描数据的分析,对所提算法进行验证,结果表明所提算法可准确快速地对室内三维激光扫描点云进行分析处理,并完成室内建筑物平面图的绘制。     

单调链与二分法的Douglas-Peucker改进算法

针对Douglas-Peucker(D-P)算法对一些较复杂的曲线进行压缩时易产生自相交等错误,阻碍其在数据压缩方面的应用的问题,该文基于单调链与二分法,对D-P算法进行改进。该方法首先利用D-P算法对复杂曲线进行压缩,并将压缩后的曲线分成若干单调链;其次利用二分法对相交的单调链进行快速精确定位,并对相交的单调链进行处理,从而解决自相交问题。通过实验验证,在处理矢量数据压缩中自相交的问题时,改进的D-P算法在算法效率、压缩率和算法精度等方面都具有较好的效果。     

坐标排序的离散点凸包生成算法

针对传统的凸包生成方法在数据量较大情况下效率下降明显的问题,该文提出了一种基于平面离散点快速生成凸包算法。基于凸包边界单调性对平面点集分区域按X轴方向排序的方法,较好地减少了传统凸包生成算法的计算量,实现了凸包求取的高效性。实验结果表明:该算法不仅可以快速有效地生成凸包,还能够保证结果的准确性,且效率较高。     

一种道路网信息几何差异检测算法

道路网信息几何差异的检测在导航电子地图数据更新,数据压缩和质量检查中具有重要的现实意义。针对道路网信息和道路信息几何差异检测的实际应用特点,对传统的平面扫描线算法进行改进,提出一种新的计算道路网信息几何差异的高效算法。该方法的计算复杂度为O((n s)logn),n表示输入数据大小,s表示线段交点的个数;并且在实际地图生产中得到应用,结果表明该算法效率高,符合应用需求,可靠性好。     

鲁棒高效的矢量地图叠加分析算法

提出了一个鲁棒高效的内存矢量地图叠加分析算法,采用改进的平面扫描算法计算交点,解决了重叠边、交点位于端点等所有特殊情形。利用交点及其携带的信息来构造结果环,并且将没有产生交点的输入环忽略,或者增加到结果的外环(或内环)集合中去。所有结果环都带有标识码,增加该标识码信息可以简化后续的两个过程-内外环的匹配以及属性的继承。与一一循环方法相比,本文方法对任何叠加操作可以一次计算得到所有的交点。此外还实现了叠加分析操作,并且用一组真实地理数据的不同操作与ESRI的ArcGIS的叠加分析操作进行了比较,计算结果的要素数完全一致;计算时间耗费约为ArcGIS时间耗费的50%-60%。     

叠置分区辅助的相位编组直线提取算法

针对现有相位编组方法在区域分界线处产生边缘断裂及同一分区内直线拟合难题,提出了一种叠置分区辅助的相位编组直线提取算法。该算法通过两次分区生成交叠的八分区模式,二次分区中心线与一次分区分界线相重合。首先根据初始四分区,将梯度相位相同且相互连接的边缘点编组生成直线支持区,再对其进行边缘分裂,进而拟合出对应的直线。然后将不满足一次分区条件的边缘点再依据二次分区进行直线提取,以弥补一次分区在分界线附近产生的边缘断裂。本文算法原理简单,不需要参数调整。试验验证和对比分析表明,该算法不仅能有效、准确地提取影像上的直线特征,而且对于影像上的曲线特征也能通过直线拟合得到较好的提取结果。     

直升机电力巡检中电力线的自动提取

结合电力线在直升机航拍影像中的成像特性,提出了一种复杂自然背景中电力线的自动提取方法。首先,利用Ratio算子从复杂背景中检测出电力线边缘;然后把边缘转化成直线段,对出现断裂与欠连接的直线进行连接与合并;最后,从这些直线段中采样一些点集,利用随机一致性抽样算法(Ransac)从中选择尽可能少但足够的点来拟合成一根完整的电力线,并通过实验证明了该方法的有效性。     

路网环境下的混合数据最近邻查询算法

路网环境下的k最近邻查询方法在地理信息系统、智慧城市、数据挖掘、医疗营救和物流配送等领域都有着较为重要的作用,已有路网环境下的最近邻查询方法无法直接解决查询对象为点而数据对象为点和线段混合的复杂数据的近邻查询问题,为了弥补已有方法的不足,提出了路网环境下混合复杂数据的最近邻查询算法。将查询过程分为预处理、数据集约减和数据集精炼3个部分,并与3种对比算法进行对比实验,研究了测试数据对象的数量、路网规模的大小对中央处理器运行时间以及输入/输出代价的影响。结果表明,所提算法能有效地处理路网环境下混合数据的最近邻查询问题。     

采用斜拉式弯曲划分的曲线化简方法

线要素化简一直是自动制图综合中的重要研究内容。分析已有线化简算法在线弯曲形态保持和单调弧段划分时只考虑一侧等不足,提出线要素的斜拉式弯曲划分和化简新方法。该方法对线要素采用斜剖方式划分弧段,兼顾线要素两侧的弯曲形态;识别出每个划分的单调弧段是U型弧段还是V型弧段,是大弧段还是小弧段,从而分别对其进行不同的处理;在处理过程中,每化简完一个单调弧段,重新对线要素进行弧段划分,然后再次对每个单调弧段进行化简,以此类推,因此该算法是一种动态化简过程。实例显示,本算法在线要素特征点保持、u型弧段和V型弧段保持、大弯曲的保持、整体形态保持等方面非常有效,且化简率非常高,充分证明本算法的科学性和优越性。     

目标轮廓直线特征的高精度提取

针对小型物体高精度量测的要求,提出一种结合精确单点定位方法和基于分裂的最小距离误差线段逼近法的高精度轮廓直线特征提取算法.通过利用直线特征精确逼近目标的轮廓,搜索相邻直线段并计算交点,从而实现轮廓分割点的精确定位,进而为基于轮廓的三维量测与重建提供高精度的直线特征数据.与其他方法(如最小二乘模板匹配、抛物线拟合等)相比...     

Modelling Positional Uncertainty of Line Features by Accounting for Stochastic Deviations from Straight Line Segments

The assessment of positional uncertainty in line and area features is often based on uncertainty in the coordinates of their elementary vertices which are assumed to be connected by straight lines. Such an approach disregards uncertainty caused by sampling and approximation of a curvilinear feature by a sequence of straight line segments. In this article, a method is proposed that also allows for the latter type of uncertainty by modelling random rectangular deviations from the conventional straight line segments. Using the model on a dense network of sub‐vertices, the contribution of uncertainty due to approximation is emphasised; the sampling effect can be assessed by applying it on a small set of randomly inserted sub‐vertices. A case study demonstrates a feasible way of parameterisation based on assumptions of joint normal distributions for positional errors of the vertices and the rectangular deviations and a uniform distribution of missed sub‐vertices along line segments. Depending on the magnitudes of the different sources of uncertainty, not accounting for potential deviations from straight line segments may drastically underestimate the positional uncertainty of line features.     

利用线特征和SIFT点特征进行多源遥感影像配准

提出了一种基于线特征和SIFT点特征的多源遥感影像配准方法。该方法首先匹配待配准影像和参考影像中的线特征,利用匹配直线构建虚拟角点;其次,针对传统SIFT算法匹配多源遥感影像特征点存在的不足,采用线特征约束点特征的方法进行SIFT同名点对的提取;最后结合虚拟角点对及SIFT同名点对构建三角网进行小面元微分纠正。试验结果表明,本文方法能取得较高的配准精度。     

引入结点度的线/面拓扑关系细分方法与应用

针对线/面细分拓扑关系研究存在的不足,提出了一种基于结点度的线/面细分拓扑关系描述与计算方法。该方法在定义线/面单元交线并分析其特点的基础上,引入结点度来区分线/面单元交线细分类型。根据单元交线端点在线/面目标组成图形结构中结点度的不同,及线目标在度为3和4的交线端点处是否有相连线段、相连线段位于多边形的边界上、内部或外部4个谓词推导出了21种有意义的线/面交线细分拓扑关系类型。在此基础上分析比较了本文方法与现有方法的异同与优势,举例说明本文方法在复杂线/面细分拓扑关系描述中的应用。最后用Visual C#语言编程实现了该方法,并将其应用到线状道路/面状河流目标间的数据质量检查与修正中,验证可行性。