多边形骨架线与形心自动搜寻算法研究

针对GIS中的应用，分析了传统的多边形骨架线与形心提取算法的不足之处，提出了一种基于约束Delaunay三角网结构的多边形主骨架线与形心的自动搜索算法，详细描述了该方法的基本思想，并在实验结果基础上分析了该算法的特点。     

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

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

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

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

顾及邻近五点的建筑物多边形化简方法

针对传统的建筑物化简算法无法准确保持建筑物局部细节几何特征,容易产生尖锐凸角等问题,提出了一种基于邻近五点的建筑物多边形化简方法。通过将多边形边界上的邻近五点定义为基本处理单元,实现对建筑物边界Z形平行、Z形不平行、U形平行、U形不平行的4类几何模式划分,进行渐进式化简,并针对化简过程中产生的尖角顾及角度约束对其削尖。对某地区部分1∶1万实际建筑物多边形数据进行试验,结果表明,所提算法在保持建筑物基本几何形态特征的基础上,能够尽可能地避免尖角的产生,化简结果更加符合人类的视觉认知。     

PDA环境下面状地物动态注记的研究与实现

提出了在PDA环境下,电子地图可视化过程中,面状地物动态注记的一种实现方法。其中,对在PDA环境下如何选择多边形裁剪算法和面状地物注记配置算法进行了简要分析,着重提出了面积加权计算多边形形心来配置注记的算法。     

地名注记的街区式居民地边界提取方法

针对基础地理信息数据中街区式居民地注记无对应边界范围信息的问题,该文提出了一种基于地名注记的街区式居民地边界提取方法。选取境界、道路、水系等矢量要素为约束条件,按位置提取了地名注记对应要素;根据要素提取结果计算聚合距离,以多边形聚合的方法进行制图综合,处理了可能出现的孤岛多边形及临近居民地未分割等异常情况,获得了较好的边界提取结果。实验结果表明,此方法保持了居民地的空间结构,为街区式居民地的边界提取提供了一种有效方法。     

网格模型的文物缺损面积计算

针对缺损文物的修复问题,本文提出通过计算三角网格模型中的三维孔洞面积来统计缺损文物面积的算法:建立三角网格中的点、边和面之间的拓扑关系,根据网格边界性质提取网格模型中的边界边,将提取出的孔洞边界边顺序连接组成孔洞多边形,并利用三角网格拓扑属性来识别孔洞边界和模型本身的外边界,通过坐标法计算三维孔洞多边形面积来统计文物缺损面积。应用实例表明,此方法用于孔洞边界的提取和缺损文物面积的计算是有效、可行的。     

煤矿地质成图中多边形快速生成算法

针对煤矿地质成图中左转算法生成多边形在复杂的二维图形条件下应用效率低的问题,该文提出了一种新的基于左转算法的多边形快速选取及自动生成算法,实现了2D图形环境中多边形的快速选取及自动生成。通过在进行多边形选取时的起始点,起始方向的选择和对悬挂点、线进行处理,解决了复杂图形下多边形选取及自动生成过程中存在的重复生成、效率低下和搜索回退问题。基于GeoMS3D实现该算法,实验结果表明:该算法逻辑简单、结构清晰,在实际的应用中表现出了较高的运算效率。     

一种基于边界搜索的栅格矢量化算法

栅格数据的矢量化是GIS领域重要的研究内容。针对栅格数据矢量化准确率低和效率低等问题,该文提出了一种基于边界搜索的矢量化算法,通过对栅格图像的一次遍历,提取结点和中间点,生成弧段,构建多边形;并在构建多边形中,提出了一种简单易行的最右侧方向判断方法,综合运用最小外接矩形和射线法判定逆时针多边形的归属。实验表明,该文提出的矢量化算法能够较准确矢量化复杂的栅格图像,具有较好的效率,可为多值栅格图像快速矢量化及相关研究提供借鉴。     

一种有效的复杂多边形裁剪算法

提出了一种基于扫描线思想和梯形分割技术的多边形裁剪算法,其主要步骤包括:计算主多边形(集)与窗口多边形(集)的交点,提取所有交点和多边形边界结点的纵坐标(y)并进行排序;以排序后的y作水平扫描线,分别对主多边形和窗口多边形进行梯形分割,获得两组梯形集合;对这两组梯形集合逐行执行梯形单元"交"运算,最后对结果交集进行边界追踪建立裁剪多边形。实验结果表明,该算法具有较好的计算效率,是一种比较实用的多边形裁剪算法。     

应用湖泊中心点作为控制点实现大区域遥感影像的配准

在进行北美阿拉斯加地区多期影像湖泊变化分析过程中,由于该区域长期被冰雪及湖泊覆盖,几乎没有较明显的地面标志点可作为影像配准控制点,给影像的配准工作带来困难。在分析长时相区域湖泊形状变化的基础上,认为湖泊中最稳定的点为湖泊的中心点,该点位置随湖泊面积的变化不大,可以作为影像配准的控制点。与多边形质心相比,多边形的最大内圆圆心始终位于多边形的内部,且以该点为圆心的内圆半径最大(对应的内圆即为最大内圆),其计算方法可以应用矢量多边形的Voronoi图来求得。本文在分析简单多边形Voronoi图性质及其计算方法的基础上,提出了一种面向复杂多边形的最大内圆圆心点查找方法,给出了其算法实现流程与算法的复杂度分析。通过北美阿拉斯加地区湖泊最大内圆圆心查找的测试实例,表明本文提出的方法能够较好地计算出各种复杂矢量多边形的最大内圆圆心点,并达到较高的计算效率,且以多边形最大内圆圆心点作为配准点实现的影像间配准效果也较好。     

割线中点距离的面要素匹配算法

针对面要素图幅接边中出现的由于端点距离计算量大导致程序效率低的问题,该文提出了一种基于割线中点距离匹配的边界匹配方法。该算法通过获取面要素与边界线重叠的各线段的中点,对各中点进行距离匹配,从而完成面要素各段割线的匹配与割线端点的匹配。通过对割线中点的匹配,减少面要素匹配中需要匹配的点,达到节省时间的目的。通过面要素匹配实验证明:该算法可以在确保匹配准确性的情况下有效缩短面要素边界匹配的时间。     

GPU友好的线状符号绘制算法

针对基于重复配置线型的地图线符号绘制方法的效率问题,本文提出了一种GPU(Graphic Processing U-nit)友好的绘制算法。对不跨越拐点的线型,采用基于平衡查找树的显示列表进行加速,并给出了适应显示列表的矢量线宽处理方法;对于拐点处需要变形的多边形图元,预先将其分解为凸多边形,并构造保凸的拐点变形算法来避免多边形实时凸剖分。算法较之于基于GDI(graphics device interface)的绘制,效率平均提高8倍以上。     

一种连续直线自动合并为多边形的算法

在地图矢量化或自动综合过程中经常需要处理连续直线融合为多边形的问题。在GIS程序开发的实践过程中提出了一种高效的自动合并算法。实验结果表明,该方法具有高效、准确的特点,可应用于矢量化、多边形自动综合等场合,具有一定的实践推广价值。     

基于约束点的无拓扑多边形数据压缩算法

分析了常规压缩算法(如Douglas-Peucker算法)压缩无拓扑多边形数据会产生公共边界不一致现象,认为出现此现象的原因是多边形公共边界的压缩起始点选择不一致,进而提出了一种新的基于约束点的无拓扑多边形数据压缩算法。算法原理包括:首先将多边形公共边界的两个端点作为约束点处理,使得多边形从约束点处逻辑上分成几段;然后利用常规压缩算法进行分段压缩,使每一多边形公共边界的压缩初始点一致,从而保证了无拓扑多边形数据的一致性压缩;最后大量试验验证了此算法的有效性。     

基于线要素综合的形状相似性评价模型

从面状要素形状描述模型中导出线状要素的相似性评价模型:将线状要素以首尾点的连线为对称轴作镜像处理构建其对偶面,以其对偶面的傅立叶形状描述子为其形状向量,以向量的欧氏距离来度量曲线的相似程度。为保证一定的评价精度,通过计算傅立叶第K项X、Y的增量值,来决定K值大小。最后对给定曲线运用不同的化简算法进行多层级的化简,通过本模型对形状的保真度进行分析。该模型具有数学严密性和实用性,能为选择曲线化简算法提供一种参考依据。     

5G基站的改进加权质心室内定位算法

针对现有基站室内定位算法参与定位基站选择及权重设置不合理导致定位精度低的问题,提出了5G环境下基于接收信号强度指示(RSSI)进行加权质心室内定位算法. 该算法通过RSSI测距得到5个已知基站到待定位点的距离,以已知基站位置为圆心作圆,针对相交所得的五边形区域,取任意3个顶点组成三角形,并根据不同的基站类型以及与待定位点的距离,设定合适权重计算三角形质心坐标,利用所得的10个三角形质心坐标做最大似然估计(MLE)得到最终定位点. 仿真结果表明:在基站稀疏和密集两种环境下,本算法较经典质心算法和加权质心算法,室内定位精度明显提高.      

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

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

离散目标群的边界搜索

搜索离散目标群的边界是地理信息系统(GIS)和地图学中一个重要问题,传统的算法是基于矢量数据的。本文提出了基于栅格数据搜索离散目标群的边界的新方法,并用两个点群算例介绍了用闭运算搜索边界的方法与流程,为数字高程模型生成、地图学等提供一种新的边界搜索方法。     

射线法判断点与包含简单曲线多边形关系的完善

点与多边形关系的判断问题一直是计算机图形学中的基本问题之一,目前判断点与多边形关系的射线法只考虑多边形边界全部由直线组成,而在实际应用中,多边形边界经常包含简单曲线。本文以圆弧为例,在分析已有射线法基础上,提出对射线法的完善算法,解决了点与包含圆弧的复杂多边形关系的正确判定。