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

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

利用化简分割生成示意性网络地图

从整体到局部相互协调是示意性网络地图的关键所在,已有方法多是单纯地将线段作为示意基本单元,当空间要素分布不均衡时,容易产生示意结果全局表达不一致以及局部要素过于紧凑而变形的现象。考虑网络连通与网络闭合这两个性质,提出了一种化简分割生成方法,核心思想是根据连通化简网络,进而依据闭合构建网眼与线段两种基本示意单元。首先,对网络节点化简以及方向、长度调整,形成整体一致的化简网络;其次,将化简网络分割为网眼集合与线段集合;第三,建立从网眼至线段的示意化过程,通过网眼局部控制以避免要素过于紧凑。实验讨论了本文方法在不同示意约束规则之下的表现效果,与经典迭代寻优方法的对比分析表明,在网络整体形态保持与局部要素布置方面具有一定的优势。     

地理信息系统中由线段数字化记录重建多边形的方法

本文研究由地图数字化线段记录重新形成多边形的方法。从结点、线段和多边形的拓扑关系出发,着重分析线段的连接、多边形组成线段的序列寻找、岛状多边形的处理、多边形属性编码等,为向量结构地理信息系统建立有关多边形的数据库记录提供算法基础。所述的方法无需规定线段数字化的方法与次序。     

顾及路网结构保持的城镇居民地自动综合

以往居民地自动综合的研究多集中于建筑物的多边形化简,较少考虑到其与街区、道路网的联系。提出了顾及路网结构保持的城镇居民地自动综合模型,此模型包含道路选取和街区内部结构概括两方面。前者基于网眼密度并结合路划功能选取道路数据,用于街区合并;后者则主要涉及建筑物多边形化简,通过改进矩形差分组合方法,在原有面积阈值的基础上添加距离阈值,并提供新的分层化简思路。以1:1万地图数据到1:5万比例尺的自动综合实验验证了本文算法的可行性和有效性。     

针对复杂道路网络的车辆轨迹地图匹配算法

针对高度城市化地区存在的复杂道路网络环境下,如何高效地进行车辆轨迹数据的地图匹配问题,该文提出了一种针对复杂道路网络的车辆轨迹数据地图匹配算法。该算法以车辆轨迹序列为匹配对象,通过环形轨迹的识别把车辆轨迹序列划分为无环路轨迹段,并用道路拓扑关系来计算轨迹序列的最优匹配路线,实现在复杂道路网络中的车辆轨迹数据地图匹配。为了验证本算法的性能,以上海市道路网络为实验区,以约1.3万辆出租车在2015年4月的轨迹数据为数据源,进行实证研究。实验结果显示,该文提出的地图匹配算法在复杂的道路网络中有较高的匹配成功率和匹配效率。     

道路与建筑物空间冲突的几何相似性移位算法

保持建筑物群的空间分布模式一致是道路与建筑物空间冲突处理问题的难点。按道路对建筑物的包围程度,将道路与建筑物之间的关系类型划分为开放型、半开放型和闭合型。本文提出了基于几何相似性的建筑物移位算法,并以距离、角度和面积作为满足几何相似性的约束条件。以道路网眼为单位,采用最小生成树的方法生成建筑物群的骨架,以骨架的长度和角度特征分别作为建筑物移位的距离和角度约束条件,以建筑物与网眼的面积比作为建筑物移位的面积约束条件。针对可能出现的次生冲突,探讨了次生冲突的处理方法。试验结果表明,本文方法能够消除因道路拓宽导致的道路与建筑物冲突,并能完备地保持建筑物群的空间分布模式。     

基于C4.5算法的道路网网格模式识别

道路网模式的识别对于地图综合、数据匹配和空间分析具有重要意义。网格模式是道路网中的典型模式之一。本文提出一种基于C4.5算法的网格模式识别方法。该方法以道路网中的网眼多边形为基本单元,根据上下文关系将其标识为属于网格模式和不属于网格模式两类。首先采用形状参量和关系参量描述网眼多边形,然后,基于决策树C4.5算法分别对5维参量和3维参量构造分类器,运用10折交叉验证获得具有说服力的结果,其Kappa值分别为0.63和0.66,正确率分别为81.7％和82.9％,置信度90％的置信区间分别为[0.785, 0.846]和[0.797, 0.857]。在新数据上进行了识别效果的验证,结果表明该分类器可用于网格模式的识别。研究试图将传统模式识别和数据挖掘的理论方法应用于空间问题的解答中。     

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

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

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

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

土地利用数据库综合中图斑拓扑关系的创建和一致性维护

以LANDUSE-DAT文件为例，论述了土地利用地图综合中图斑多边形拓扑关系的特点、数据结构定义及生成方法，阐述了土地数据库综合过程中图斑拓扑关系一致性的维护方法。     

Stroke构造、移位一体化的道路网示意化方法

针对当前常用示意性地图生成方法中往往存在简化程度不够、未考虑长度信息以及时间效率低等问题,提出了stroke构造、移位一体化的道路网示意化方法。该方法在对道路网进行stroke划分构造的同时,直接对其进行渐进式的移位示意化及拓扑检查。同时本文还提出利用相似分形维数来定量比较并验证不同示意化方法的有效性。试验表明,本算法在考虑原始线形的基础上,示意化过程简单,时间效率较高,减少了拓扑冲突问题,保证了拓扑一致性及路网的均衡分布,具有较好的清晰度和认知度。     

道路网示意性地图的渐进式综合研究

研究并总结了示意性道路网地图的制图规则,量化了约束条件,提出了一种道路网渐进式图形简化方法和移位方法,并研究了拓扑关系检查方法。在具体实验中,通过对道路网上点的分类,依据约束条件,快速生成有效的道路网示意性地图,同时保证了原始道路图与示意性道路图之间的拓扑关系一致性。     

Automated Generation of Schematic Network Maps Adaptive to Display Sizes

Schematic maps have been popularly used for the representation of metro (or underground) lines and nowadays have also been used for the representation of other network maps. This paper presents a strategy for automated generation of schematic network maps for different display sizes, based on a redistribution of line density. This strategy consists of three steps: (a) estimation of spatial density of the network maps, (b) automated redistribution of line density in order to improve map clarity, for different display sizes, and (c) automated generation of schematic representations. An experimental evaluation has been carried out by using two sets of real-life network data. The results indicate that this strategy is able to generate schematic maps with much improved clarity for different display sizes and well-preserved map recognition.     

基于蚁群算法的土地利用(图)图斑合并方法

很多地图综合问题可以应用优化算法解决,土地利用(图)图斑合并也可以看作是一个优化问题。本文提出了基于蚁群算法的土地利用(图)图斑合并方法。实验结果表明,基于蚁群算法的图斑合并方法优于普通的迭代方法,该方法使综合后各地类面积变化较小且图斑紧凑性较好,是解决土地利用(图)图斑合并问题的一条可行之路。     

道路地图示意性表达的可用性评估

当前示意性地图表达主要针对公共交通网络,缺乏对道路地图示意性表达可用性评估研究。本文选取景区和街道两个典型道路场景,采用最新的自动示意化方法生成示意地图,以主观问卷调查结合客观眼动试验的方式,评估道路地图示意性表达的可用性。试验结果表明:①示意性表达能够提升道路地图的简化度、清晰度及用户满意度,尤其对于原始道路形状较为复杂的情况;②示意地图中路径形状简化会造成不同路径感知长度差异的改变,从而影响到人们路径抉择行为;③对于路径示意性结果增加了道路网密集程度的情况,会降低示意地图认知效率。本文研究成果有助于道路地图自动示意性表达规则完善和方法优化,能够进一步提升地图示意性表达的实用性。     

Schematic road network map progressive generalization based on multiple constraints

Multiple constraints for schematic road network map cartographic design are analyzed and summarized. Based on this, a set of quantitative criteria are set up and a new road network generalization method including progressive selection and displacement is proposed. Furthermore, topological checking methods for road networks are researched. Based on these constraints, the points in a road network are classified, and a satisfactory and effective schematic map is designed in a concrete experiment while maintaining topological consistency of the road network between the original and the schematic map.     

多约束条件下示意性道路网地图渐进式综合(英文)

Multiple constraints for schematic road network map cartographic design are analyzed and summarized. Based on this, a set of quantitative criteria are set up and a new road network generalization method including progressive selection and displacement is proposed. Furthermore, topological checking methods for road networks are researched. Based on these constraints, the points in a road network are classified, and a satisfactory and effective schematic map is designed in a con- crete experiment while maintaining topological consistency of the road network between the original and the schematic map     

面向道路网络地图示意化的线形简化方法

针对当前示意网络地图线形状简化方法中存在需要人工干预或地图认知度低的问题,本文提出自动化程度高并能保证良好地图认知的线形状简化方法.该方法通过合理设定线形状简化中所需的阈值以避免人工干预,提高了线形状简化过程的自动化程度,并通过在简化过程中应用平滑算法,以减少示意结果中线对象在方向上的转折数,从而提高了简化度和清晰度.试验表明该方法不仅可以生成清晰的示意结果,并且能够保证良好的地图认知度.     

Cartographic reconstruction of building footprints from historical maps: A study on the Swiss Siegfried map

Extracting features from printed maps has been a challenge for decades; historical maps pose an even larger problem due to manual, inconsistent drawing or scribing, low printing quality, and geometrical distortions. In this article, a new workflow is introduced, consisting of a segmentation step and a vectorization step to acquire high‐quality polygon representations of building footprints from the Siegfried map series. For segmentation, an ensemble of U‐Nets is trained, yielding pixel‐based predictions with an average intersection over union of 88.2% and an average precision of 98.55%. For vectorization, methods based on contour tracing and orientation‐based clustering are proposed to approximate idealized polygonal representations. The workflow has been tested on 10 randomly selected map sheets from the Siegfried map, showing that the time required to manually correct these polygons drops to about 45 min per map sheet. Of this sample, approximately 10% of buildings required manual corrections. This workflow can serve as a blueprint for similar vectorization efforts.     

示意性地图自动设计初探

分析并总结示意性地图的理论基础和基本设计原则。在几种基于矢量制图信息的典型示意性地图设计方法的基础上,提出基于几何、语义多约束条件下的示意性地图的设计方案。采用迭代优化算法,自动生成满足几何、语义和审美要求的示意性地图。