线目标空间冲突自动检测方法研究

基于1:5万空间数据更新质量检查的实际应用需求,分析了空间冲突的自动检测问题;提出了基于平面扫描算法的空间冲突检测方法．该方法在平面扫描计算的同时利用四交模型计算线段间的拓扑关系;并根据线段间的拓扑关系推理线目标间详细的拓扑关系,将计算出的空间关系与规则比较进行空间冲突判断．该方法在国家1:5万空间数据库建库质量检查中应用,减轻了作业员的劳动强度,提高了数据质量检查的效率．

空间数据库中全局最近邻查询处理方法

空间数据库中基于层次化索引结构的全局最近邻(all-nearest-neighbor,All-NN)计算采用单节点展开策略的嵌套循环技术来降低计算开销.在同一数据集合的全局最近邻计算中,基于索引结构带来的对象空间位置临近性特点,抛弃传统理论距离裁剪规则和嵌套循环技术来减少计算和索引节点访问开销.提出了采用局部计算和完备计算两阶段的计算模型来获得全局最近邻结果.首先以叶节点为单位,采用扫描线算法获得节点内部所有对象的局部最近邻结果,然后根据计算结果得到启发式裁剪距离.在第2阶段采用层次化过滤的范围查询算法来获取外部的(可能的)最近邻对象.实验与分析表明该方法可以很好地支持不同种类、大小、分布的数据集合All-NN查询处理,具有良好的实用价值.

求解简单多边形间包含关系的扫描线算法

对于任意给定的一簇互不相交的简单多边形，本文提出一种旨在确定簇中多边形之间包含关系的扫描线法，并对其正确性和复杂性作出分析。

线段相交问题的平面扫描型改进算法

本文对计算平面上ｎ个线段所有交点的平面扫描算法及数据结构做了改进。若设这ｎ个线段的交点总数为ｋ，这ｎ个线段中与垂直扫描线相交的最多个数为ｍ，则改进后的算法的计算时间为Ｏ（ｎｌｏｇｍ＋ｋｌｏｇｍ），占用存储空间为Ｏ（ｍ）。

寻求平面上线段集凸壳的扫描算法

首先证明寻求平面上线段集凸壳问题的下界是O(nlogn),其方法是将平面上线段集凸壳问题与排序问题联系起来,由排序问题的下界推得平面上线段集凸壳问题的下界。然后提出一个算法,计算平面上线段集凸壳问题,其基本思想是将不交线段集中的线段按其端点的x,y坐标排序,并重排线段序。然后用平面扫描方法分段完成凸壳的构造。该算法的时间复杂性是O(nlogn)。

平面散乱点线集三角剖分的算法

利用平面扫描的思想 ,即利用从右到左移动的 y 轴扫描点线集 当扫描线达到某个给定点或给定线段端点时 ,将该点或端点与其上下相邻线段端点连接 新连线与已三角剖分的边只能在其端点处相交 该算法的时间复杂性为O(NlogN) 。

一种基于平面扫描的弧段分割与多边形自动构建算法

针对多边形自动生成的传统算法在自动化和时间效率方面的不足而导致的相应商用GIS软件数据处理和时空分析能力的欠缺,提出一种基于扫描思想的弧段分割和多边形自动生成算法。本算法具有以下特点:面向从求交开始至生成多边形结束的完整任务;充分利用求交过程中的有益信息,以较小的算法复杂度和极小的计算量,实现弧段分割和多边形自动构建;避免了传统方法中多边形嵌套关系的计算,并能有效地处理桥和悬边问题。实验结果表明,与传统算法相比,本算法在效率方面有明显的提升。

平面线段集三角剖分的算法

本文提出了计算平面线段集三角剖分的两种算法。第一个算法是利用平面扫描的思想,当扫描线达到事件点时,处理事件点,即将事件点与已被扫描的某些点连接,这样便将已扫描的区域三角剖分。当扫描线达到最左边的事件点时,处理该事件点,就完成了平面线段集的三角剖分。第二个算法基于逐层计算凸壳,并将凸壳改变为多边形,这样便形成嵌套的多边形层,这些多边形覆盖线段集凸壳内的区域,然后三角剖分每个多边形,即完成平面线段集的三角剖分。两个算法的时间复杂性分别为O(nlogn)、O(mnlogn),其中n为线段集中线段的数目,m为凸壳的层数。

平面最接近点对算法

描述了平面最接近点对问题,针对这一问题给出了3种算法,循环遍历算法、分治算法和平面扫描算法,并详细分析了3种算法的时间复杂度。

平面点线集三角剖分的扫描算法

提出计算平面点线集三角剖分的一种算法.该算法是利用平面扫描的思想,当扫描线达到事件点时,处理事件点,即将事件点与已被扫描的某些点连接,这样便将已扫描的区域三角剖分.当扫描线达到最左边的事件点时,处理该事件点,就完成了平面点线集的三角剖分.证明了算法的时间复杂性为O(NlbN),其中N是点线集中点的数目与线段端点数之和.

船体剖面剪流计算中闭室搜索算法

本文主要提出了船体剖面剪流计算中闭室单元的一种快速搜索算法。算法是以计算几何图形扫描法为基础,提出了基于行业特征的改进型快速算法。同时结合实际算例,给出了算法在剪流计算闭室搜索过程中的应用过程,并计算出算法的时间复杂度,总结了算法的实用性、快速性。为各大剖面计算软件提出了一种闭室单元搜索的解决方案。

一种有效支持空间分析的空间数据组织

Realms是一种用于描述空间平面的数学模型。它提出了一种所有空间对象共享一个共同的空间元素集合的思想以及一种空间元素的排序规则。这些特点使得二维空间能够线性化为一维有序的元素集合 ,将二维空间问题转化为一维线性问题 ,从而使得基于 Realms的空间数据组织能有效地支持平面扫描算法。通过对空间对象的简单扫描 ,能够实现多数空间分析算法。以Realms为基础实现空间数据管理系统能取得较高的效率 。

基于相似度匹配的场景深度估计方法

重建任意场景图像的深度图是多视立体中的一个基本问题。在视角间参数未知的情况下,基于立体匹配的深度估计方法因三维估计不准确、光度一致性较差而导致得到的深度图空洞较多、平滑性差,针对上述问题,提出了基于相似度匹配的场景深度估计方法,该方法通过使用SLAM估计两视图之间的参数,利用孪生神经网络实现图像间的相似度匹配,从而进行初始深度范围估计,有效的将深度估计控制在更接近实际的深度范围内,滤除了深度范围外的散焦点,使用平面扫描算法对深度范围分层进一步实现对场景深度的精确估计,从而获得纹理清晰、图像平滑性高的深度图。

改进的全局最近邻查询算法及其在空间数据库中的应用

针对基础数据集合和参考数据集合为相同数据集的情况,给出了一种新型的空间数据库全局最近邻查询算法,该算法能够利用数据最近邻结果的自身特点,避免较大的查询过程中的资源开销。实验结果表明,算法的效率要明显优于常用最近邻查询算法,并且对于不同的数据维数和数据元素数量,特别是对于高维的空间数据集合,算法具有较高的稳定性。

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

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

矩形集上的点定位

给出解决计算几何问题的两种算法， 其预处理部分分别基于对 Ｓ 的平面扫描和 Ｓ 在ｘ 轴的投影线段对应的线段树除描述算法的步骤外， 还进行算法的复杂性分析这两个算法可直接推广到等置矩形和ｄ