数字制图题库-地图数据转换-度量空间欧式空间拓扑空间-DCEL模型.doc

数字制图题库 地图数据转换 度量空间欧式空间拓扑空间 DCEL模型 作者： 日期：2 个人收集整理 勿做商业用途1.数字地图、电子地图、模拟地图的概念？数字地图是在一定坐标系统内具有确定坐标和属性标志的制图要素和离散数据在计算机可识别的存储介质上概括而有序的集合。具有计算机可识别性、可量算性、可分析性、可传输性及数字与模拟地图的互转性，是生产电子地图和纸质地图的基础。 电子地图：是数字地图在计算机屏幕上的符号化显示,是计算机条件下的空间信息可视化，是人眼直接可视的，包括二维、三维电子地图模拟地图：是利用经过人工抽象和符号化了的图形及线划描述制图内容的地图，它是可视的地面图像的模拟，来源于地面（或照片）又高于地面(或照片）。数字地图与模拟地图特征对比类别项目 数字地图模拟地图可读性计算机可读目视可读可传输性利用现代通讯技术传输靠人工传输设备要求要求高要求低与现代设备搭配使用可以一般不宜地图更新简单、快捷慢、繁可分析性便于分析是特长人工目视判别分析存储与显示的可分离性可分离不可分离2.地图数据几何变换有哪些类型，如何以矩阵形式表示？图形可以用点集来表示。对图形的变换,只要变换点就可以实现。1、 二维基本变换：（x，y)为变换后坐标，T为变换矩阵 ，且变换矩阵中a,b,c，d可取不同的值，从而实现不同的变换,以达到对图形进行变换的目的. 、 平移交换与齐次坐标平移变换用于移动坐标系的原点.变换前后的坐标必须满足 ：因子Tx为正，原点往左移，Tx为负，则往右移。当因子Ty为正,原点往下移，Ty为负，则往上移. 把2x2矩阵扩充为3x2矩阵？见书P21、 齐次坐标、 旋转变换：、 缩放变换：、 错切变换2、 二维组合变换:3.线、面几何形态的量度方法有哪些？线：线是由直线段依序近似表达的，长度即所组成矢量（直线段的模的和），用公式表达如下： 面的量度方法有：三角形方法： 梯形方法： 栅格方法：面积单元的个数（1/2)bc1 ，b是多边形边界上网格点 数目，c是多边形内部网格点的数目 4.点面关系的计算方法有几种，原理如何？射线法：从待判别点v发出射线,求交点个数k。K的奇偶性决定了点与多边形的内外关系，偶数个交点点在多边形外，奇数个交点-点在多边形内。累计角度法:从v点向多边形P顶点发出射线，形成有向角PiVPi+1（i=0，1，n)规定：绕点逆时针角度为正,顺时针为负.计算有向角的和,得出结论：5。不规则多边形的质心如何确定？质心的确定（确定内点）利用MBR（最小包围矩形）方法(不含内岛）对MBR在X方向的长度DX与Y方向的宽度DY进行比较如DXDY,在DX/2处作垂直于X轴的直线,求取该直线与多边形的交点Y坐标系列，并对Y坐标排序，形成排序Y坐标系列Y1,Y2，Yn,其中Y1最大，Yn最小。然后，奇偶配对，如Y1与Y2，Y3与Y4等，求取间距最大区间，设为Yi与Yi+1，则多边形的内点坐标为(Xmin+Xmax)/2，（Yi+Yi+1）/2进一步改进可处理含内岛的多边形6.多边形布尔运算有哪几种类型，各自的原理如何？如果集合A是具有a属性的集合,集合B是具有b属性的集合,分别用两个圆来表示,各种简单的布尔逻辑运算结果（阴影部分）可表示为下图所示。 1。布尔逻辑叠置模型它是将输入数据层变成二值图层（0,1),然后进行布尔逻辑运算得到输出数据层。基本步骤是：首先按是否满足规定条件,将各个输入数据层中的所有多边形赋值为1(真)或0（假）,变成二值图（0，1）。A B NOT A A AND B A OR B A XOR1 1 0 1 1 01 0 0 0 1 10 1 1 0 1 10 0 1 0 0 0然后，对各个输入数据层进行“逻辑交”、“逻辑并、“逻辑补等运算，输出数据层是一个二值图。7。比较度量空间、欧氏空间和拓扑空间各自的特点; 度量空间(metric): 能实施距离量算(方位不一定)，如旅行时间（对称性）。在数学中是指一个集合,并且该集合中的任意元素之间的距离是可定义的。设X为一个集合，一个映射d：XXR。若对于任何x,y，z属于X，有（I）（正定性)d（x，y)0，且d（x，y）=0当且仅当 x = y； (II）（对称性）d（x,y)=d(y,x)； （III）（三角不等式）d（x，z）d（x,y)+d(y,z） 则称d为集合X的一个度量(或距离）。称偶对（X，d）为一个度量空间，或者称X为一个对于度量d而言的度量空间。 欧式空间(Euclidean）：能实施通常的长度、方位运算的空间表达为坐标元组集。 设d为定义在集合Rn上的距离函数,d: RnR，对于Rn中的任意元素x, y，x=（x1， x2， , xn）， y=(y1， y2， , yn)， 有d（x， y）= 则En=（Rn， d) 称为n维欧氏空间,Rn的每个元素称为空间En的点，d称为Rn上的欧氏距离.当n=2时，E2 称为欧氏平面。 欧氏空间把欧几里德对于距离、长度和角度以及相关的概念，转换成任意数维的坐标系. 拓扑空间(topological）: 拓扑变换,橡皮几何,如 邻近性、连通性表达 。拓扑空间是欧几里得空间的一种推广，具有拓扑结构的集合。如果对一个非空集合X给予适当的结构，使之能引入微积分中的极限和连续的概念，这样的结构就称为拓扑，具有拓扑结构的空间称为拓扑空间。给定任意一个集，在它的每一点赋予一种确定的邻近结构便成为一个拓扑空间，构造邻近结构有多种方法，如邻域系、开集系、闭集系、闭包系、内部系等不同方法.8。DCEL模型的原理DCEL（DoublyConnectedEdge-List)表示模型是对连通平面图提供的拓扑关系表达.（一)弧段的邻接关系假设C的方向从pN到sN，则与其相邻的多边形RP位于右边，LP位于左边。弧段C是由围绕点sN处的下一个逆时针弧段RC和围绕点pN的下一个逆时针弧段LC界定的边界之内。所谓下一弧段表示了在终结点sN关联的弧段中，该弧段逆时针方向的第一条弧段RC，而所谓上一弧段则表示了在始结点pN关联的弧段中，该弧段逆时针方向的第一条弧段LC. 如果沿着多边形RP顺时针移动，那么弧段RC紧位于C后； 如果沿着多边形LP顺时针移动，那么LC紧位于C后。(二）多边形的邻接关系环R构成多边形P,环R是由弧段构成的的循环表，即由一系列首位相连的弧段或点组成。一个复杂多边形是由包含边界点的无序环序列组成。地图目标及其拓扑关系构成了在不同矢量数据模型中实现空间表达的基础.这些数据模型将转换成计算机环境下进行地理底图数据组织的数据结构。 9。路径拓扑、网络拓扑各有哪些类型，原理是什么，应用如何路径拓扑数据模型包括面条模型、多边形模型、点位字典模型、弧段/点位字典模型网络拓扑数据模型包括DIME模型、POLYVRT模型、结点模型、扩展弧段模型面条模型（Spaghetti Model）：在这个模型中，面状单元间的边界作为坐标记录下来，没有关于坐标串与单个多边形间关系的相应信息。应用：地理底图的轮廓线可以从这种数据模型中轻易获取，但是很难基于这种结构执行任何多边形操作 多边形模型（Polygon Model)：记录和存储了每个多边形的外轮廓线（即为组成外轮廓坐标的一个或多个循环表).这个模型很容易标识每个多边形实体，但其存储空间却迅速扩大，因为多边形间的公共边被存储两次；对数字图形的编辑也极易造成多边形公共边坐标的不匹配，通常会产生叠置空隙或裂片。应用:每一邻接关系要通过搜索多边形的轮廓表,从中寻找两个多边形间相匹配的坐标串来识别。点位字典模型：该模型是对多边形模型的一个改进，它记录的是各多边形边界上各点的编码ID并构成循环表，同时以数据字典方式记录下各点的坐标值，利用字典就可通过点的编码找到其相应的坐标.应用：多边形的显示都包含一个复杂的检索过程，首先从多边形表中得到点ID，再根据点ID获得坐标值。弧段/点位字典模型：弧段/点位字典模型表达了多边形与弧段，以及弧段与点的构成和组成关系,在弧段/点位字典模型中，每个多边形由弧段的循环表组成，而每条弧段又由一列点组成.应用：多边形轮廓线的提取分三个步骤：首先从多边形表中得到弧段ID值，然后根据弧段的ID值获取点ID值，最后由点ID值得到相应的坐标.这样可以很好解决裂隙问题，因为公共边上所有弧段的相同点的ID值相同.DIME模型：DIME文件是最早的矢量模型中含有多边形间邻接关系的模型.DIME文件的基本单元是DIME段,一个DIME段即是一部分街道、行政区界、水涯线或铁路线等的直线段；对于每个段，两个端点ID分别为有方向性的“起始”和“终止”.基于这个方向，多边形ID相应地记录为左或右多边形（针对该DIME段)。应用：在DIME中，获取多边形轮廓线过程如下：第一阶段是要找出所有的DIME段及其左右多边形；第二阶段,这些段按以下顺序排列，第一段的止点是后一段的起点，最后一个段的止点是第一个段的起点，这样便形成了一个循环表，在这个过程中，起、止点是可以按需切换的，以使多边形始终位于每个段的右边。POLYVRT模型:POLYVRT模型是基于弧段结构构造的拓扑模型，它将弧段的关系按DIME段给出，弧段的端点被称为结点而不是点，在这个系统中，结点与点严格区分。应用：POLYVRT模型综合了弧段/点位字典模型和DIME模型,但它的点位字典划分为独立的点和结点。因此，POLYVRT模型与DIME模型的区别在于边的不同选择，而该边是用来描述多边形之间的关系并作为关系文件记录的基本单元.结点模型（NODE模型）：NODE模型是链式文件结构,称结点的邻域关系文件.每个多边形边界的检索就是通过交叉引用该文件和包含每个多边形起结点ID值的多边形文件来实现的。应用：若给定一个多边形P的起始结点的ID值，就可以通过扫描结点的ID记录来查找多边形P。多边形P边界的下一个结点是以P为右多边形的邻接结点，由此就找出了第一条弧段。通过扫描当前结点的内容可以找到下一条弧段和新的结点ID的指针，如此结点与弧段的穷举式依次搜寻P的边界，直到下一结点ID与初始结点ID值相同，从而最终确定P的位置。扩展弧段模型：扩展弧段模型是对DIME和POLYVRT结构的改进，弧段之间的连接关系隐含在构成多边形轮廓线的弧段循环表中。弧段的邻域可加以扩展，从而包含围绕某一结点的下一逆时针弧段的ID。当沿着某一多边形轮廓顺时针方向前进时,这些弧段将依顺序成为下一条弧段.应用:每一弧段的邻域关系包括了第一和最后一个结点,左、右多边形以及相应的左、右弧段（LC和RC）；右弧段依顺序是右多边形的下一条弧段，左弧段依顺序是左多边形的下一条弧段。10.4叉树编码的原理四叉树分割的基本思想是首先把一幅图像或一幅栅格地图（*，k1）等分分成四部分，逐块检查其格网值。四个等分成为四个象限,按顺序为左上、右上、左下、右下,可以用树结构表示。如果某个子区的所有格网值都含有相同的值,则这个子区就不再往下分割；否则,把这个区域再分割成四个子区，这样递归地分割，直到每个子块都含有相同的灰度或属性值为止。其中四叉树包括常规四叉树与线性四叉树常规四叉树除记录叶结点外，还记录中间结点，每个结点由父结点指针（前趋），四个子结点指针（后继）和本结点的灰度或属性值。线性四叉树只存储最后叶节点的信息，包括叶节点的位置、深度和本节点的属性或灰度值。11.数据测量尺度有哪四种，各自的适应性如何?测量尺度由粗略至详细依次分为：命名或类型、次序、间隔以及比例。w 命名量：定性而非定量，不能进行任何算术运算；只对特定现象进行标识，赋予一定的数值或符号而不定量描述；这些数值之间无数量关系，对命名数据的逻辑运算只有“等于”或“不等于”两种形式,而其近似均值只能使用众数.w 次序量：线性坐标上不按值的大小，而是按顺序排列的数，序数值相互之间可以比较大小,但不能进行加、减、乘、除等算术运算。次序测量尺度是基于对现象进行排序来标识的，对次序数据的逻辑运算除了“等于”与“不等于”之外,还可以比较它们的大小,即“大于”或“小于”。w 间隔量：不参照某个固定点,而是按间隔表示相对位置的数；按间隔量测的值相互之间可以比较大小，并且它们之间的差值大小是有意义的。间隔测量尺度与比例测量尺度相似，但是间隔尺度的测量值无真的零值；间隔量中的零值往往是人为规定的.间隔数据可用于加、减等运算。w 比率量：比例测量尺度的测量值指那些有真零值而且测量单位的间隔是相等的数据，比例测量尺度与使用的测量单位无关；与某一固定点的比值计算，支持多种算术操作，如加、减、乘、除等。12.GIS环境下，尺度概念的内涵与外延 地图制图学:地图图面距离与实际距离的比率 （比例尺） 在地球空间信息科学领域，尺度概念超出了“距离比率”的意义，更多的有含义“抽象程度”,从认知科学的观点，它体现了人们对空间事物、空间现象认知的深度与广度。 尺度的内涵（三要素） （1） 广度： 覆盖、延展、存在的范围、期间、领域； （2) 粒度： 记录、表达的最小阈值（大小、特征的分辨率）； （3） 频度： 采样、选取的频率GI领域研究的数据对象具有：空间特征、时态特征、语义特征。三个特征都需要尺度来度量,因此，尺度的外延：时间尺度、空间尺度、语义层次尺度 （三维）13。地图综合，它与数据压缩、比例尺缩放 地图综合与数据压缩：相似之处：都导致信息量的减少,都是为了缩小存储空间和节省计算处理时间而去掉繁杂细节。 不同之处：数据压缩一般是在无损图解精度的前提下去掉“贡献”小而用插值方法可近似恢复的数据元素，即数据压缩可用数据的插值加密手段进行逆处理,而制图综合除了与数据压缩有相似性外，还有某些特殊性质，即不受图解精度约束，被删除或被派生的信息不可逆. 地图综合与比例尺缩放：随着比例尺的缩小，比例尺缩放的原信息量不变，但是地图综合的原信息量一般会减少。14。地图载负量与比例尺的关系，与注记的关系地图载负量是衡量地图内容多少的数量标志，是衡量地图表达到何种程度、表达多少合适的一个重要指标, 是研究地图内容综合的直接依据。为了使载负量的概念规格化，使其与图幅大小无关，从而便于进行比较，采用百分比或“每平方厘米中的数量”的形式表示，它往往带有平均性质.根据所编图的用途、比例尺等的不同,可采用不同的数学方法来确定所编图上所应保留的信息量或其等价物地图载负量。由于名称注记在地图比例尺逐级缩小时，它的尺寸缩小得很慢,达到最小尺寸后，就无法随比例尺缩小而再缩小，从而引起名称注记载负量随比例尺缩小而迅速增涨，在广阔地区的小比例尺地图上，它可达90% 关于地图载负量的变化，当其它条件（地图用途,地区特征等）相同时，比例尺(1M）就是一个决定性的因素。我们把比例尺序列粗略地划分成为我们所特别定义的大，中，小三个区间，并取比例尺分母的对数把比例尺的几何级数变化转换成算术级数来处理。在大比例尺区间,地物几乎全部选取，且基本上均按比例符号表示，这使得资料图与新编图的对应图形基本上呈现为相似关系：全取虽然使单位面积上的物体个数（数值载负量)呈几何级数增加，而物体图形也同时按几何级数缩小。因此，面积载负量保持不变，同时，在此阶段注记载负量所占的百分比又极其小，因此在这个区间，总载负量保持不变或变化甚微。在小比例尺区间,由于符号与注记的继续缩小受到限制，尽管单位面积中所选物体的数量在急剧减少,而总载负量趋于饱和，围绕着极限载负量在波动.在中比例尺区间，呈过渡性质.15。开方根规律的推导过程因为成图的方式有两种：一种是从实地测图，另一种成图方式是从图到图，这是中小比例尺成图所最为常用的方式。制图综合中的开方规律研究的是基本图（资料图）与派生图(新编图）制图物体数量的变化规律，因为这一规律密切的联系着两种地图的比例尺分母的开方根，故称制图综合的开方根规律.它是由 F。Toepfer 于 1961 年研究所发现。后又进行了多年探讨和用多种地图作品进行验证.总体上说，该模型原理清晰,可操作性好。在一定程度上反映了中比例尺范围内地图载负量渐增的总趋势(选取数量的减少慢于比例尺的缩小）,在国际上受到重视和大多数专家学者的认可。Toepfer 在建立开方根规律时,是从平板仪测图的高程中误差与地图比例尺分母之间的统计关系出发的.这里通过地图信息综合的机理分析，形成综合准则的数学上下界：两个反向不等式,对所得的两个反向不等式取其最为简单的平均数 几何平均数，得出地图尺度规律：线符地图尺度规律与面符地图尺度规律。当严格按照地图比例尺1/M表示时，图上符号的长度、宽度与间隔等线性尺寸s与实地尺寸之S间的关系为 S A = s A M A ，S F = s F M F式中下标A，F分别代表资料图与新编图.由于地物的实地尺寸是不变的，即SF = S A , 进而有 s F = s A (M A/M F) 即线状地物的线宽尺寸严格地随比例尺变化.当比例尺缩小到一定程度后，线状地物（如公路）的符号宽度无法严格按比例尺表示，而必须作一定程度的放大，即 s F sA（M A/ M F) （I） 同时，随着比例尺的缩小，图上的面积越来越珍贵,符号应相对精细以便能表达更多的地物。即后继比例尺地图的符号尺寸小于比例尺较大的资料图上的符号尺寸： s F s A (II） 为满足上述两个不等式条件(I）, （II），最为简单的方法就是取它们的几何平均数： s F = s A（M A/M F)1/2 这就是线状地物线宽尺度变化的地图尺度规律。用类似的途径可以得出面状地物符号f变化的尺度规律：当严格遵守比例尺变化时有 f F = f A (M A/ M F)2 由于有与线状符号变化同样的原因，fF就大于严格按比例尺的缩小尺寸，即 f F f A (M A/ M F)2 (I)同时，应该小于资料图上的尺寸，即 f F 0, ABC呈逆时钟，顶点为凸。S0， ABC呈顺时钟，顶点为凹。S=0, ABC共线。缓冲取边线的自相交：当轴线的弯曲空间不允许双线的边线无压的通过时，就会产生若干个自相交多边形.重叠多边形与岛屿多边形:岛屿多边形是缓冲区边线的有效组成部分；重叠多边形不是缓冲区边线的有效组成部分,不参与缓冲区的最终构建。重叠多边形与岛屿多边形的自动判别：首先定义轴线坐标点序为其方向,缓冲区双线分成左右边线,左右边线自相交多边形的判别情形恰好相反。对于左边线,岛屿自相交多边形呈逆时钟方向.重叠自相交多边形呈顺时钟方向.23