线对象V-O分解与符号化算法

本文针对线符号中基本线型绘制质量与效率问题,对比分析了5种典型线对象分解与绘制方法。在V分解的基础上,提出一种V-O分解与绘制方法,提高了V分解方法三角化的适应性,减少了V分解方法的顶点、三角形以及三角形条带的个数。能够支持颜色线、纹理线、渐变线等基本线型的绘制,支持反走样。实验表明,本文方法具有较强的适应性和较高的绘制效率。     

GIS岛多边形三角剖分算法

结合Delaunay三角剖分原理,在多边形顶点关系的基础上,通过对多边形从外向内间隔相邻级环间的三角剖分,来实现岛多边形的剖分算法。算法涉及图形相交、相邻、相离、包含等几何关系分析,以及Delaunay三角形构建等过程。对图形几何关系判断和三角形构建等过程进行了优化处理,提高了岛内三角剖分的精度和速度,解决了GIS制图中存在的"岛中岛"等复杂几何图形的剖分问题,可以对任意凹凸多边形实现快速三角剖分。首先获取并存储shape文件中多边形的空间坐标数据,然后基于该算法在VC++开发环境中完成岛多边形的三角剖分和显示。通过对不同形状的岛多边形反复测试表明,该算法的三角剖分结果均可达到最优,且效率较高。     

利用自适应分块的任意多边形三角剖分算法

三角剖分算法是计算几何领域中的重要课题之一,针对现有多边形三角剖分算法大多不能同时兼顾算法的简单有效性、适用性以及三角网的质量问题,提出一种基于自适应分块的任意多边形三角剖分算法。多边形的自适应分块区别于传统的格子分块,它充分顾及了多边形边作为剖分三角网约束边这一特点,通过选择原始多边形一定数量的边,并对这些边构建最优三角形,将原始多边形分割成若干个小的简单多边形,这些简单多边形之间通过三角形进行连接。至此,原始多边形的三角剖分直接转化为这些简单多边形的三角剖分,这样由一条边寻找一顶点构建最优三角形,直接在该边所在的简单多边形内进行搜索,大大减少了点的搜索范围,提高了算法效率。利用基于边优先的多边形三角剖分算法对分块后的小多边形进行三角剖分,从而完成整个多边形的三角剖分。算法具有适用性广,剖分三角形网形稳定、最优,思路简单,易于实现,执行效率高的特点,最后通过实验证明了本算法的科学性和先进性。     

利用自适应分块的任意多边形三角剖分算法

三角剖分算法是计算几何领域中的重要课题之一,针对现有多边形三角剖分算法大多不能同时兼顾算法的简单有效性、适用性以及三角网的质量问题,提出一种基于自适应分块的任意多边形三角剖分算法.多边形的自适应分块区别于传统的格子分块,它充分顾及了多边形边作为剖分三角网约束边这一特点,通过选择原始多边形一定数量的边,并对这些边构建最优三角形,将原始多边形分割成若干个小的简单多边形,这些简单多边形之间通过三角形进行连接.至此,原始多边形的三角剖分直接转化为这些简单多边形的三角剖分,这样由一条边寻找一顶点构建最优三角形,直接在该边所在的简单多边形内进行搜索,大大减少了点的搜索范围,提高了算法效率.利用基于边优先的多边形三角剖分算法对分块后的小多边形进行三角剖分,从而完成整个多边形的三角剖分.算法具有适用性广,剖分三角形网形稳定、最优,思路简单,易于实现,执行效率高的特点,最后通过实验证明了本算法的科学性和先进性.     

顾及特征线和三角形形态最优的TIN三角网构建算法

传统三角形剖分方法只考虑三角网的形态最优,忽略了地形特征线的影响,导致构建的地形模型不能真实反映地形特征。文章提出既顾及特征线又满足三角形形态最优的TIN模型的构建方法。在研究了有关三角形形态理论的基础上,设计了数据结构,对如何利用该方法进行三角形剖分做了具体研究。实例证明,利用该方法进行三角形剖分,构建的TIN三角网模型既能满足三角形形态最优,又能避免特征线穿越三角形,能够真实反映地形特征。该三角形剖分方法对于地形较复杂区域的TIN模型构建具有很好的适用性。     

利用骨架线端点匹配进行面状要素渐变变换

面向空间数据连续地图综合问题,提出了一种基于骨架线端点匹配的面状要素渐变方法,通过在两个关键表达之间进行尺度内插,实时、动态地派生任意中间比例尺地图数据。首先,对面状要素在大小比例尺下的两重表达分别进行约束Delaunay三角网剖分并提取各自的骨架线特征;然后,使用最优子序双射优化技术对骨架端点进行匹配获得多边形边界上相对应的特征点序列;最后,在剖分边界的基础上进行分段常规线性内插,获得面状要素介于始末尺度之间的多尺度表达。实验结果表明,该算法充分顾及了空间数据弯曲结构特征,对于光滑边界面状要素的渐变变换具有良好的渐变效果,可用于空间数据的连续地图综合和多尺度表达。     

一种倾斜摄影模型精细融合方法

现有三维模型融合方法多采用对原有三角面片顶点重新构网的方式,容易导致原有模型几何特征丢失及纹理失真等。本文针对倾斜摄影模型自身特点,提出了一种模型精细融合方法。首先,以一个模型作为中心模型,并以另一模型与中心模型外轮廓的空间关系计算融合区域;然后,以中心模型外轮廓作为约束,对原始模型三角面片进行精细剖分;最后,基于精细剖分的三角面片进行纹理坐标的插值计算。以实际倾斜摄影数据进行试验的结果表明,本文方法融合后的网格模型拓扑结构正确,融合边界不存在漏洞、裂缝和错位等情况,而且纹理过渡自然,颜色无明显差异。     

地图目标群间骨架线提取的算法研究

基于Delaunay三角网提取的骨架线是地图综合中广泛应用的一种空间剖分结构。改进了一种基于约束Delaunay三角网的地图目标群间骨架线提取算法,从程序设计的角度详细描述了算法的数据结构和控制流程。按照三角网中三角形包含约束边的数目,将三角形分为0、1、2、3四类,将0类、2类和单连通的1类三角形视为骨架线追踪的起点或终点,将双连通的1类作为中间通道,对整个三角网进行遍历。针对三角网中的环路、3类三角形等特殊情况,在改进的算法中提出了相应的处理方法。该算法成功地用于等高线的内插和街区地图目标群的邻近分析,验证了算法的可行性和健壮性。     

影像三维重建的网格自适应快速优化

针对倾斜影像大场景三维重建过程中数据量大导致的三角网格优化效率低的问题,提出了一种平衡网格优化精度与优化效率的网格自适应快速优化方法。根据影像灰度信息计算沿着三角面法向量方向顶点梯度的初始值,根据每一个三角形的不同计算结果将三角形标记为活跃三角形与怠惰三角形,通过对网格中活跃三角形优化及放弃怠惰三角形优化的策略,在获得网格顶点最佳位置的同时自适应地实现优化效率的快速提升。标准三维重建影像数据集及真实无人机倾斜影像三维重建网格优化的实验结果表明了此方法的有效性。网格模型优化时间及精度对比的结果表明,该方法在优化三角网格的同时,较大幅度地提高了网格优化的计算效率,从而快速获得三维重建模型。     

基于边扩张算法和熵编码的3D网格模型的拓扑信息压缩

本文总结了三类不经三角剖分直接编码多边形网格模型拓扑信息的单分辨率压缩法,对其中基于边区域扩张的Face Fixer算法进行了研究,并分别应用同阶自适应区间编码法和算术编码法对三角形网格模型和多边形网格模型进行了压缩.实验结果表明:随着模型数据量的增大,区间编码的压缩率和压缩速度反而高于算术编码,因而对于大数据量的网格...     

Chain-based polyline tessellation algorithm for cartographic rendering

ABSTRACT

Although the extrusion of 1D polylines into a 2D polygon and the tessellation of the polygon into primitives has been performed in the field of computer graphics, the efficient, robust, and high-quality tessellation of thick polylines that supports various cartographic styles for polyline rendering remains a practical challenge. We examined and compared existing vertex-, segment-, and polygon-based algorithms, and present a chain-based tessellation algorithm for cartographic rendering: points in the polyline are classified into abrupt and smooth points according to their point spacing, angle and thickness. The polylines are then divided into abrupt and smooth chains by clustering points that are adjacent and of the same type. An optimal algorithm is also presented to continuously tessellate the smooth chains into minimum geometric primitives and efficiently tessellate the abrupt chains into geometric primitives. We implemented the proposed algorithm and present the results of robustness, efficiency, quality, and cartographic styling tests conducted on real-world polylines. The results indicate that this approach has substantial advantages when considering all four requirements (robustness, efficiency, quality, and the support for various cartographic styles).     

基于ArcGIS Objects的带状图生成算法研究

带状图具有折点难处理、生成算法复杂等特点,是城市地下管线信息系统建设的难点之一。本文提出了一种通过计算带状图图幅顶点坐标以生成带状图的方法,并对折线、折点处理进行了重点阐述,简单介绍了带状图的打印出图,最后利用ArcGIS Object平台与C#编程实现了地下管线数据带状图生成的实验验证。     

Star and polyline glyphs in a grid plot and on a map display: which perform better?

Glyphs are small geometric shapes that in geovisualization are often used to represent multidimensional spatial data. The aim of this study is to investigate the effectiveness of their two types – star and polyline glyphs, as they can encode the same message and can provide similar functionality. Thus, if the two glyph types are similar and can be used for the same data, the question arises as to which of them better facilitates various user tasks. To address this question, an empirical study of 26 individual users is conducted to investigate differences in user performance for polyline and star glyphs shown either in a grid plot or on a map display. In this study, a task-based approach with eye-tracking is applied, as well as a subjective questionnaire and a psychological test of cognitive style. The finding is that polyline glyphs better facilitate tasks when datapoint values in glyphs are to be read, whereas star glyphs are better when a visual search among glyphs is to be done. Moreover, the results reveal that the map display works better than the grid plot. If star glyphs are to be used, the key (legend) needs to be better incorporated into a visual interface.     

Area‐preservation Simplification of Polygonal Boundaries by the Use of the Structured Total Least Squares Method with Constraints

This article presents an area‐preservation approach for polygonal boundary simplification by the use of structured total least squares adjustment with constraints (STLSC), with the aim being to maintain the area of the original polygons after the simplification. Traditionally, a simplified line is represented by critical points selected from the original one. However, this study focuses on maintaining the areas of the polygons in the process of simplification of polygonal boundaries. Therefore, the proposed method in this article is a supplement to the existing line simplification methods, and it improves the quality of the simplification of polygonal boundaries in terms of positional and area errors. Based on the sub‐divisions of the original polyline, using the critical points detected from the polyline by the use of line simplification methods, the framework of the proposed method includes three main components, as follows: (1) establishment of the straight‐line‐segment fitting model based on both the critical and intermediate points on the sub‐polyline; (2) introduction of both area and end‐point constraints to reduce the geometric distortions due to the line simplification; and (3) derivation of the solution of boundary simplification by the use of STLSC. An empirical example was conducted to test the applicability of the proposed method. The results showed that: (1) by imposing the linear fitting model on both the critical and intermediate points on the sub‐polylines in the proposed STLSC method, the positional differences between the original points and the simplified line are approximately in a normal distribution; and (2) by introducing both end‐point and area constraints in the proposed STLSC method, the areas of the simplified polygons are the same as those of the original ones at different scales, and the two neighboring fitted lines are connected to each other at the optimized position.     

方向后交最佳点位分析

推导出方向后交点住精度的显函数公式;用解析法导出对称交会时最佳交会角和最佳点精度;用无约束最优化共轭梯度法,求出一般情况下方向后交最佳交会角和点位精度;求出同一三角形三个内角分别作顶角进行后交定位的最佳点位,得出三角形内只有一个最佳点位的结论,给出一种选择近似最佳点位的方法.     

线/面Voronoi图的分解合并生成算法

Voronoi图生成算法受到计算效率或生长源类型的限制,难以支撑线/面生长源Voronoi图的构建。本文提出一种生成线/面生长源Voronoi图的分解合并算法,其主要过程是将线/面生长源离散为特征点表达,通过特征点交叉建立最近特征点对,并以最近特征点对Voronoi子区域的交来部分地代替线/面生长源的等距离边界,算法以前后迭代离散计算的Voronoi子区域面积差分作为条件,可有选择地将部分生长源置入迭代过程,使线/面生长源Voronoi子区域逐步调整并达到精度要求。     

矢量GIS中随机折线定位不确定性的可视化模型

折线是ＧＩＳ中表达线形空间实体的基本制图要素。本文针对由随机折线点构成的折线要素建立了一种可视化误差模型。首先引入了随机折线要素误差带的基本概念,并导了误差带的边界线数学方程;然后针对开折线和闭折线两种情况绘出了误差带的可视化图形,并分析了形状特征,从而将单一随机折线元的误差带理论进一步扩展到一整条随机折线的一般情况。     

一种优化的基于倾斜刃边的点扩散函数重建方法

已有的倾斜刃边法受边缘亚像素定位精度、边缘扩散函数(ESF)样本质量及ESF曲线拟合方法的限制,点扩散函数(PSF)重建的稳定性和精度不高。为此,提出了一种优化的基于倾斜刃边的PSF估计方法,将梯度算子引入刃边直线拟合,对刃边边缘进行了高精度的亚像素位置修正;并采用基于移动窗口的ESF去噪及重采样方法精化ESF样本质量;最后通过高斯函数拟合得到稳健的PSF估计值。实验结果表明,改进算法的边缘直线拟合精度优化效果明显,且PSF重建精度较高,稳定性强。     

基于约束Delaunay三角网的斜坡符号生成算法

分析了地图自动成图中斜坡坡面符号生成算法的基本原理,据此将斜坡分成梯形斜坡、矩形斜坡、倒梯形斜坡三种类型,并概括了他们的特点,介绍了已有的斜坡坡面符号生成算法及其优缺点,在此基础上,提出了一种基于约束Delaunay三角网的斜坡坡面符号生成算法,对预处理后的上下坡脚线建立约束Delaunay三角网,根据三角形组合的不同特点,将三角形的组合分类成两种类型,依次寻找匹配点,最后生成斜坡符号线。此算法避免了斜坡坡面符号线相交等情况,亦可用于栅栏等地图符号的自动生成。     

GIS中基于εσ模型的随机折线元位置不确定性的可视化

首先研究基于εσ模型单一折线段不确定性误差带,导出误差带边界线的解析表达式;然后通过算例分析,针对开折线和闭折线两种情况,由单一折线段误差带边界线的解析表达式,编程绘出位置不确定性随机折线的可视化图形。理论分析和可视化图形表明,在两条相邻折线的公共端点处,前一线段的右误差半圆的半径和后一线段的左误差半圆的半径未必相等,实际分析中需考虑到这种情况。