改进的边标志栅格化算法

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

实现栅格图形和图像数据矢量化提取的游程轮廓追踪法

提出一种直接利用栅格图形游程编码进行图斑边界多边形矢量化提取的有效方法。对遥感图像专题信息和栅格型地理空间分析结果的矢量化提取是GIS的重要手段 ,栅格数据结构可简化解决叠置分析等一类空间分析问题 ,其中需要高效矢量化技术的支撑。本方法充分利用栅格游程编码所具有的可操作性强、检索和转换便捷、隐含横向差异信息、可处理高精度和大规格图形和图像等特征 ,定义了“上邻游程”和“下邻游程” ,并采用相应有效查找算法和基于游程轮廓追踪的矢量化技术 ,使得计算机处理栅格数据矢量化的规模、精度和效率明显提高 ,可广泛应用于栅格型地理空间分析和遥感图像处理等方面。     

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

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

多边形拓扑关系构建的栅格算法

矢量数据拓扑关系的自动建立是GIS软件的核心模块之一，也是技术难点之一。简要分析传统算法的优缺点，在此基础上，借鉴基栅格的种子点填充算法和矢量数据求交的栅格探测法的思想，提出建立图幅多边形与弧段所属关系的栅格算法，给出算法的各主要步骤和实现方法。分析与试验表明，新算法在特殊情况处理、多边形内点自动建立、处理效率、简化编程等方面有一定优势。     

一种抗切割处理的栅格地理数据水印算法

本文提出了一种基于精度特征的栅格地理数据盲水印算法。首先,分析了栅格地理数据切割处理的特征及其对常规水印算法产生的影响,在此基础上,结合栅格地理数据精度特点,依据栅格地理数据的有效位平面生成水印信息位,而后,采用量化思想将水印信息嵌入对应的可变位平面。实验表明,所提出的水印算法在保证栅格地理数据精度的基础上,对于任意尺寸的数据都有较好的适用性,同时,对于任意强度的切割处理,该算法都体现了良好的鲁棒性。     

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

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

矢量数据栅格化的一种有效方法——环绕数法

矢量数据栅格化是GIS数据处理的一项重要任务。目前,已存在多种栅格化方法,但是每种方法都有各自的局限性。本文首次提出了环绕数法,它基于计算几何转角理论,通过计算跨越数来确定环绕数,是一种简单、高效、易于实现的栅格化方法。应用环绕数法,不但可以完成简单多边形的栅格化,而且可以完成自交多边形的栅格化。     

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

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

面积误差最小约束下矢量数据向栅格数据转换的优化算法

在总结现有的矢量数据向栅格数据转换算法的基础上,提出一种面积误差最小约束下的优化算法。该算法保证了多边形矢量数据在栅格化后的面积误差尽可能最小,从而提高所得栅格数据在面积分析相关领域中应用的可信度。     

2DRE四叉树—栅格结构的变换算法

本文提出并分析了2DRE四叉树到栅格结构的变换算法。这一算法可看作栅格—2DRE四叉树变换算法的逆变换,但不是它的“反演”,而是采用了较为简洁的求交集运算以及栅格—2DRE四叉树变换算法中的编码转换方法,使得这一算法的实现更加有效,且避免了在图像较大而内存较小的情况下可能发生的“溢出”等矛盾。     

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

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

一种基于条件极值的建筑多边形直角化的方法

在地图综合中,许多建筑多边形化简的方法都是针对于直角多边形的,建筑多边形的直角化也是地图数据在进入GIS之前对数据完整性检验的必经过程.本文介绍了一种利用条件极值来计算直角地物中各点坐标改正数的方法.该方法成功用于大比例综合缩编软件GenTool,并获得了满意的效果.     

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

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

基于本质矩阵的无人机影像精确匹配

无人机影像以其低成本、获取容易、信息量大等优点得到了广泛的应用。影像匹配是影像数据处理的重要环节，常用影像匹配的方法存在误匹配多或剔除大量正确匹配的问题。LMedS算法比其他稳健方法更严格，"5点算法"得到的本质矩阵可用于匹配点对共面的场景。本文使用LMedS算法结合"5点算法"求解本质矩阵作为剔除误差的模型，同时利用ORB算法提取速度快的特点，构建了一种精准同时兼顾了效率的匹配方法。本文对该算法开展了试验研究，并与其他常规算法进行比较。试验结果表明，本文算法保留的匹配点数数量多，分布较均匀，适用于多种场景，是一种有效、快速精准的影像匹配算法。     

地图印前计算机辅助设计软件系统研究与实践

介绍地图印前系统在我国产业部门应用概况及计算机图形辅助设计软件用于地图印前系统的三个共性问题。以计算机图形辅助设计软件MicroStation95为例,详细探讨该软件用于地图印前制作所涉及的技术要点。并以《南京市教育地图》为例,对用该软件进行彩色地图编制与出版的优点与局限性进行了探讨。     

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

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

A topology-preserving polygon rasterization algorithm

Conventional algorithms for polygon rasterization are typically designed to maintain non-topological characteristics. Consequently, topological relationships, such as the adjacency between polygons, may also be lost or altered, creating topological errors. This paper proposes a topology-preserving polygon rasterization algorithm to avoid topological errors. Four types of topological error may occur during polygon rasterization. The algorithm starts from an initial polygon rasterization and uses a set of preserving strategies to increase topological accuracy. The count of the four types of error measures the topological errors of the conversion. Topological accuracy is summarized as 1 minus the ratio of actual topological errors to the total number of possible error cases. When applied to a land-use dataset with a data volume of 128 MB, 127,836 polygons, and extending 1352 km², the algorithm achieves a topological accuracy of more than 99% when raster cell size is 30 m or smaller (100% for 5 and 10 m). The effects of cell size, polygon shape, and number of iterations on topological accuracy are also examined.     

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

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

基于数学形态学的TIN和GRID自动生成研究

在分析了数学形态学的基本原理的基础上,提出了一种基于数学形态变换自动生成Delaunay三角网(TIN)和规则格网(GRID)的数字高程模型的算法,这种算法将离散的地面点的图像集合进行骨架化并自动构成Thiessen多边形,然后,通过序贯条件形态变换,自动建立TIN和GRID.在建立Thiessen多边形的过程中,提出了用逐点生成数字圆盘的方法来保证变换过程的各向同性;在建立Delaunay三角网的过程中,提出了利用正交结构元素进行条件膨胀,从而保证了相邻点之间的正确位置关系.该方法能保持Thiessen多边形和Delaunay三角网的拓扑关系,因而能保证DEM 的高精度,而且具有数据结构简单、运算速度快的特点.最后,给出了试验结果并与有限元法的结果进行了比较.结果表明,这种方法用于建立DEM具有良好的应用前景.     

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

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