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

1.数字地图、电子地图、模拟地图的概念？
数字地图是在一定坐标系统内具有确定坐标和属性标志的制图要素和离散数据在计算机可识别的存储介质上概括而有序的集合。具有计算机可识别性、可量算性、可分析性、可传输性及数字与模拟地图的互转性，是生产电子地图和纸质地图的基础。
电子地图：是数字地图在计算机屏幕上的符号化显示，是计算机条件下的空间信息可视化，是人眼直接可视的，包括二维、三维电子地图
模拟地图：是利用经过人工抽象和符号化了的图形及线划描述制图内容的地图，它是可视的地面图像的模拟，来源于地面（或照片）又高于地面（或照片）。
数字地图与模拟地图特征对比
类别
项目
数字地图
模拟地图
可读性
计算机可读
目视可读
可传输性
利用现代通讯技术传输
靠人工传输
设备要求
要求高
要求低
与现代设备搭配使用
可以
一般不宜
地图更新
简单、快捷
慢、繁
可分析性
便于分析是特长
人工目视判别分析
存储与显示的可分离性
可分离
不可分离

2.地图数据几何变换有哪些类型，如何以矩阵形式表示？
图形可以用点集来表示。对图形的变换，只要变换点就可以实现。
1、 二维基本变换：(x′，y′)为变换后坐标，T为变换矩阵 ，且变换矩阵中a,b,c,d可取不同的值，从而实现不同的变换，以达到对图形进行变换的目的。

①、 平移交换与齐次坐标
平移变换用于移动坐标系的原点。变换前后的坐标必须满足 ：因子Tx为正，原点往左移，Tx为负，则往右移。当因子Ty为正，原点往下移，Ty为负，则往上移。
把2x2矩阵扩充为3x2矩阵？见书P21
②、 齐次坐标

③、 旋转变换：

④、 缩放变换：

⑤、 错切变换

2、 二维组合变换：

3.线、面几何形态的量度方法有哪些？
线：线是由直线段依序近似表达的，长度即所组成矢量（直线段的模的和），用公式表达如下：

面的量度方法有：三角形方法：

梯形方法：

栅格方法：面积单元的个数＝（1/2）b＋c－1 ，b是多边形边界上网格点 数目，c是多边形内部网格点的数目

4.点面关系的计算方法有几种，原理如何？
①射线法：从待判别点v发出射线，求交点个数k。K的奇偶性决定了点与多边形的内外关系，偶数个交点－－点在多边形外，奇数个交点——点在多边形内。

②累计角度法：从v点向多边形P顶点发出射线，形成有向角∠PiVPi+1（i=0,1,…,n）
规定：绕点逆时针角度为正，顺时针为负。计算有向角的和，得出结论：

5.不规则多边形的质心如何确定？
质心的确定（确定内点）
利用MBR（最小包围矩形）方法（不含内岛）
对MBR在X方向的长度DX与Y方向的宽度DY进行比较
如DX>DY，在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 XOR
1 1 0 1 1 0
1 0 0 0 1 1
0 1 1 0 1 1
0 0 1 0 0 0
然后，对各个输入数据层进行“逻辑交”、“逻辑并”、“逻辑补”等运算，输出数据层是一个二值图。

7.比较度量空间、欧氏空间和拓扑空间各自的特点；
① 度量空间(metric): 能实施距离量算（方位不一定），如旅行时间（对称性）。
在数学中是指一个集合，并且该集合中的任意元素之间的距离是可定义的。设X为一个集合，一个映射d：X×X→R。若对于任何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: Rn→R，对于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（Doubly-Connected-Edge-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叉树编码的原理
四叉树分割的基本思想是首先把一幅图像或一幅栅格地图（*，k>1）等分分成四部分，逐块检查其格网值。四个等分成为四个象限，按顺序为左上、右上、左下、右下，可以用树结构表示。如果某个子区的所有格网值都含有相同的值，则这个子区就不再往下分割；否则，把这个区域再分割成四个子区，这样递归地分割，直到每个子块都含有相同的灰度或属性值为止。
其中四叉树包括常规四叉树与线性四叉树
常规四叉树除记录叶结点外，还记录中间结点，每个结点由父结点指针（前趋），四个子结点指针（后继）和本结点的灰度或属性值。
线性四叉树只存储最后叶节点的信息，包括叶节点的位置、深度和本节点的属性或灰度值。
11.数据测量尺度有哪四种，各自的适应性如何？
测量尺度由粗略至详细依次分为：命名或类型、次序、间隔以及比例。
w 命名量：定性而非定量，不能进行任何算术运算；只对特定现象进行标识，赋予一定的数值或符号而不定量描述；这些数值之间无数量关系，对命名数据的逻辑运算只有“等于”或“不等于”两种形式，而其近似均值只能使用众数。
w 次序量：线性坐标上不按值的大小，而是按顺序排列的数，序数值相互之间可以比较大小，但不能进行加、减、乘、除等算术运算。次序测量尺度是基于对现象进行排序来标识的，对次序数据的逻辑运算除了“等于”与“不等于”之外，还可以比较它们的大小，即“大于”或“小于”。
w 间隔量：不参照某个固定点，而是按间隔表示相对位置的数；按间隔量测的值相互之间可以比较大小，并且它们之间的差值大小是有意义的。间隔测量尺度与比例测量尺度相似，但是间隔尺度的测量值无真的零值；间隔量中的零值往往是人为规定的。间隔数据可用于加、减等运算。
w 比率量：比例测量尺度的测量值指那些有真零值而且测量单位的间隔是相等的数据，比例测量尺度与使用的测量单位无关；与某一固定点的比值计算，支持多种算术操作，如加、减、乘、除等。

12.GIS环境下，尺度概念的内涵与外延
地图制图学：地图图面距离与实际距离的比率 （比例尺）
在地球空间信息科学领域，尺度概念超出了“距离比率”的意义，更多的有含义“抽象程度”，从认知科学的观点，它体现了人们对空间事物、空间现象认知的深度与广度。
尺度的内涵（三要素）
（1） 广度： 覆盖、延展、存在的范围、期间、领域；
（2） 粒度： 记录、表达的最小阈值（大小、特征的分辨率）；
（3） 频度： 采样、选取的频率
GI领域研究的数据对象具有：空间特征、时态特征、语义特征。三个特征都需要尺度来度量，因此，尺度的外延：时间尺度、空间尺度、语义层次尺度 （三维）

13.地图综合，它与数据压缩、比例尺缩放
地图综合与数据压缩：
相似之处：都导致信息量的减少，都是为了缩小存储空间和节省计算处理时间而去掉繁杂细节。
不同之处：数据压缩一般是在无损图解精度的前提下去掉“贡献”小而用插值方法可近似恢复的数据元素，即数据压缩可用数据的插值加密手段进行逆处理，而制图综合除了与数据压缩有相似性外，还有某些特殊性质，即不受图解精度约束，被删除或被派生的信息不可逆。
地图综合与比例尺缩放：
随着比例尺的缩小，比例尺缩放的原信息量不变，但是地图综合的原信息量一般会减少。

14.地图载负量与比例尺的关系，与注记的关系
地图载负量是衡量地图内容多少的数量标志，是衡量地图表达到何种程度、表达多少合适的一个重要指标， 是研究地图内容综合的直接依据。为了使载负量的概念规格化，使其与图幅大小无关，从而便于进行比较，采用百分比或“每平方厘米中的数量”的形式表示，它往往带有平均性质.
根据所编图的用途、比例尺等的不同，可采用不同的数学方法来确定所编图上所应保留的信息量或其等价物地图载负量.
由于名称注记在地图比例尺逐级缩小时，它的尺寸缩小得很慢，达到最小尺寸后，就无法随比例尺缩小而再缩小，从而引起名称注记载负量随比例尺缩小而迅速增涨，在广阔地区的小比例尺地图上，它可达90%
关于地图载负量的变化，当其它条件(地图用途，地区特征等)相同时,比例尺(1∶M)就是一个决定性的因素.我们把比例尺序列粗略地划分成为我们所特别定义的大，中，小三个区间，并取比例尺分母的对数把比例尺的几何级数变化转换成算术级数来处理.
在大比例尺区间，地物几乎全部选取，且基本上均按比例符号表示，这使得资料图与新编图的对应图形基本上呈现为相似关系：全取虽然使单位面积上的物体个数(数值载负量)呈几何级数增加，而物体图形也同时按几何级数缩小。因此，面积载负量保持不变，同时，在此阶段注记载负量所占的百分比又极其小，因此在这个区间，总载负量保持不变或变化甚微。
在小比例尺区间，由于符号与注记的继续缩小受到限制，尽管单位面积中所选物体的数量在急剧减少，而总载负量趋于饱和，围绕着极限载负量在波动。
在中比例尺区间，呈过渡性质。
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 < f A (II)
为满足上述两个不等式(I),(II)，同样取它们的几何平均值：
f F = f A (M A/ M F)
这称为面状地物符号的地图尺度规律。
制图物体的选取并不完全符合上述简单选取规律公式，因为选取制图物体的多少受到多种因素的影响：
——物体重要性；
——资料图与新编图的符号尺寸
——不同用途
——要素类型（当比例尺比率相同时，不同要素的选取程度是不同的。例如，对于岛屿与湖泊可以选取多一些。而对于居民地特别是用轮廓符号与圈形符号表示的居民地，它们的名称注记占有很大的面积载负量比例，则选取程度显然会小一些）。
为解决这个问题，F. Toepfer在简单选取规律公式中增加地物重要等级改正系数和符号尺寸改正数，即将简单选取规律公式加以扩展.扩展选取规律的通式为

N F = N A• C Z • C B

式中CZ 为符号尺度系数；CB 为物体重要性系数

16.线综合算法有哪些，各自的基本原理
综合算法分为五类（Weibel,1997）：
1) 独立点算法（independent point algorithms）
它不顾及相邻点之间的几何关系。如选取每第k点法，去掉其它点。还有随机取点法。显然，这些方法很难捕捉到特征点，因而会引起曲线的变形。仅当曲线采样点过密时，为了减少存贮、传输与处理等方面的开销，在保持所需精度的情况下，作为数据压缩的一种方法来使用。或者说，这种方法只能用于简单的数据压缩，而不能用于真正的地理信息综合。

2) 局部处理算法（local processing algorithms）
顾名思义，该方法在对顶点选择时顾及到直接相邻诸顶点的特征。在此，作为局部准则的例子有：
（1）最小距离法（Tobler (1965)。包括两种情况：

A．绘图线宽法：即当相邻点之间的距离小于绘图笔宽度时，则后一点 被舍弃。
B．距离限差法：当相邻两点间的距离小于给定限差时，则可去掉相邻的后点。
（2）最小垂距法（Jenks,1981），计算中间点到相邻两点连线的垂距与预给限差作比较，以决定该中间点的去留,即使用相邻点的三元组（triad）来决定中间点的去留。
(3) 转角变化法：三角形始点处张角法:当过第1与第3点的直线与过第1与第2点的连线之间的夹角（中点转角法）小于预给的阈值时，则可去掉第2 点。

三角形始点处张角法:当过第1与第3点的直线与过第1与第2点的连线之间的夹角（中点转角法）小于预给的阈值时，则可去掉第2 点。

经验研究表明，这些算法所产生的变形比独立点算法小。但比后继方法差。然而，鉴于这些算法的局部化性质，对于绘图时的轻微的在线数据压缩淘汰是有用的
3）约束扩展局部处理算法（constrained extended local processing algorithms）
这类方法在紧靠顶点的更大的范围对邻居点（超越直接邻居，用曲线的一个段落）进行搜索，以便对曲线段落进行评价。这种扩展局部处理算法在搜索范围上是受到某些限制的，包括：搜索的范围取决于距离、角度和顶点数目等准则。这类算法的主要代表是Opheim 算法（Opheim,1981,1982）和Lang算法(Lang ,1969)。

Lang 算法
该算法也是用欧氏距离尺度作坐标删除，其约束条件是搜索的坐标点数。
局部搜索的范围是由所谓“向前看”(look ahead) 参数来控制。是用垂直距离限差来滤掉中间各点。当在“向前看”范围内，只要有一点的垂距大于限差，则“向前看”范围缩回一点。这样迭代下去。
Lang算法往往被划入限差带算法（tolerance band algorithms）或带宽算法（bandwidth algorithms）。此外还有其它一些算法也是使用相对基线的垂直距离（如Douglas – Peucker 1973等）
Lang 算法把第一点初始化为锚定点,把距锚定点的第k个点定义为浮动点,然后考查介于锚定点与浮动点之间的所有中间点，以确定它们是否位于带宽（垂足限差）之内。如果它们不是位于带宽之内，则直接位于当前浮动点的前一点为浮动点。这个过程一直进行下去，直到所有的那些中间点位于连接当前锚定点与浮动点的带宽之内为止。这时，锚定点更新到当前的浮动点，而浮动点则重新设定为距当前锚定点为k个点的新点上。
4） 无约束扩展局部处理算法（unconstrained extended local processing algorithms）
这里也是超越当前点的直接邻居进行搜索并对曲线各段进行评价。但是此处的搜索范围取决于多种规则，其中包括曲线的复杂性。典型的例子是Reumann – Witkam算法和Roberge 算法等。
Reumann – Witkam（1974）算法
此处的搜索廊道是用偏移量e在数字曲线段两侧作平行线，向前延伸，直到其中一边与数字曲线边相交为止。除了廊道中的首末点以外，落入廊首中的其它中间点一律消除。
5） 全局算法（global algorithms）
全局算法是考察整条曲线，迭代式的选择特征点，消除小于限差的其它点。Douglas –Peucker算法是其中最知名的算法之一。如同Lang算法和Reumann – Witkam算法一样，该方法也是限差带算法的主要代表。
此外，Visvalingam and Whyatt (1993)也提出一种基于面积限差来控制面积移位的算法：最小有效面积删除法。此处提出一种他们认为更为合理的方法：可称之为“最小有效面积删除法”。除了首末点以外，为每一个顶点定义一个有效面积，它是该点与其前后直接相邻的两点所构成的三角形的面积。它表明如果当前点被删除后曲线的面积移位量。
Douglas-Peucker 算法
把首末点（X1，Y1），（XN,YN）连成直线，它是线状目标图形的极限综合状态。对于所有直线段，计算其间的所有中间点到该直线段的（垂距为最大值 dmax）的最大偏移点，该点对确保该子曲线段的的特征图形有不可替代的重要性：保留它，曲线段变形最小，去掉它，曲线段的主要特征未能保持。即是说，曲线段的最大偏移点对于子曲线段的构形，相对其它中间点来说，有最大的贡献。

17.地图综合的过程分为几个阶段,每一阶段的控制因素有哪些
地图综合过程中三个阶段的控制

18.多边形晕线填充有哪些方法
o 多边形的晕线填充算法要求代表某值的晕线与起点对齐。相邻区域如果属性值相同，这两个区域的晕线则完全对齐。从视觉上看，如果晕线不这样对齐，那么数据类别与值之间的一一对应关系则很难保持。
o 方法：通过固定晕线位置，使之同X轴平行就可以保持这种特性
o 首先将坐标轴按晕线的方向角旋转。然后在旋转后的坐标空间中找到多边形的最大Y坐标(YMAX)。穿过多边形的晕线中最顶端的那条Y坐标可以根据下式计算：
o Y*=INT [YMAX / DELTA ] × DELTA
o 其中INT是最大取整函数；
o DELTA是晕线间的垂直距离。
o 取得多边形晕线中的最高一条的Y坐标后，其他各晕线的Y坐标可以通过将Y*依次递减DELTA值来得到，这个过程直到该多边形中再没有晕线经过时停止。
o 单线法
o 首先将多边形先旋转一个方向角，
o 然后依序每次一条晕线地分别处理各线。
o 下一步检查多边形轮廓的每一段，判断其是否与所处理的晕线相交，保存交点并按X坐标排序。这种排序是为了通过一系列（移动，绘制）对操作来保证恰当地绘出晕线。
o 最后所有的交点旋转回原始多边形空间显示。
第一个交点(X1,Y1)是V4V5边与晕线的交点，第二个交点(X2,Y2)则是V5V6边与晕线的交点。我们不能移动到(X1,Y1)，然后画线到(X2,Y2)，因为这段线位于多边形之外。第一次移动必须从(X3,Y3)开始，这样依次进行（移动，绘制）对操作才不会出错。

19.等高线追踪过程中，鞍点的处理问题
等值线地图是指使用表示相同数值的线集合来描绘一连续表面的表达方法。
网格法:在一组z值的规则网格中追踪等值线.
通过网格追踪等值线方法的优点，在于网格可以按照行列编号隐式地建立起邻域间的位置关系
步骤：
一条等高线从网格单元(i,j)的四个邻接单元(i-1,j),(i+1,j),(i,j-1),(i,j+1)之一进入，应退出该单元并继续往其余三个网格单元追踪。
确定当前单元的哪条边作为退出边时，要看该边两端点的z值范围是否包含了zi值。
等值线在退出边上的准确位置通常使用内插方法确定，
该内插是在网格单元的边上进行的。在得到等值线与网格的交点以后可以按顺序直接绘出.网格法的一个缺点在于如果出现鞍点，决定追踪方向就会变得困难。
“鞍点”现象：一个网格单元内可能会出现多于一条的有相同z值的等值线段。
在图6－36中，值为50的等值线可以连接S1和S2，S3和S4，也可以连接S2和S4，S1和S3(图6－36b)。
而连接S1和S4，S2和S3(图6－36c)在数学上是可能的，但是从制图角度上说不行，因为等值线是不能交叉的。
出现“鞍点”时的追踪
基于四个端点的z值内插出网格单元的中心点的z值，然后把单元分成四个三角形(图6－36d)
对于每个三角形来说，由于其只有三边，就不存在难以确定追踪方向的问题；如果一条等值线从三角形的一边进入的话，只可能从另外两边的一边中出去。
网格中心点的z值为53，所以应该把S1与S2，S3与S4相连。

20.开窗裁剪的过程
只有位于用户窗口中的地图部分才显示，位于窗口外的地图部分要剪裁掉
对于栅格模式来说，剪裁操作相对容易：只需要显示位于硬件窗口内栅格位置上的内容
对于矢量模式来说，剪裁就要复杂一些。根据同用户窗口的关系，位于用户空间中的线段可能有以下三种情况：1)两端点都位于窗口内；2)一个端点位于窗口内，另一个在窗口外；3)两端点都位于窗口外。
由于位于窗口之外的空间目标同时也一定是位于视口之外，线段的剪裁就可能有两种方法
1)在端点坐标转换成硬件空间坐标之前就把位于用户窗口之外的线段剪裁掉；
2)先把各线段转换成为硬件空间坐标，再根据视口进行剪裁
显然前者的转换计算更少因而计算效率更高。
给定一个多条线段组成的线串可以一次性进行处理，先找到其外接矩形，如果外接矩形同窗口无交点，那么就把这个线串剪裁掉。
如果这个矩形同窗口有交点，则每条线段必须按次序分别处理。
位－平面方法剪裁线段的算法
窗口把这个平面分成九个区域。
点的x,y坐标如果都位于四个角区域中的任一个，那么该点位于窗口外。
如果点的x或y坐标位于四个边区域的任一个，那么这个点也在窗口外。
除了角区域和边区域，就是剪裁窗口了。
如果一条线段的端点都位于窗口的内部，那么这条线段就全部显示出来。
而两端点都位于窗口的同一条边界外，这条线段就要全部剪裁掉。
只有当端点一个位于窗口外，一个在窗口内，或者两端点都在窗口外但是线段穿过不同的窗口边界时才需要进一步处理。
当端点一个位于窗口外，一个在窗口内，或者两端点都在窗口外但是线段穿过不同的窗口边界时的处理：
线段需要通过计算与窗口边界的交点来打断以实现剪裁
当线段的两端点分别位于窗口的内、外侧，就会出现两种情形：
如果第二个端点位于边区域中，这时线段同窗口边界的交点就位于窗口与边区域的之间。
如果第二个端点位于角区域中，需要一个半平面检查来确定正确的相交边界
例如，B和C点都位于窗口的右上方的角区域中。首先计算连接P和C2(窗口的右上角)的直线。如果线段的另一个端点(点C)位于P到C2的直线的顺时针半平面内，线段同窗口的交点就位于右边界上；如果另一个端点位于半平面的逆时针方向(点B)，交点就会在上边界上。

如果两个端点都位于窗口外，也会出现两种情况
一个端点可以位于边区域中，另一个端点就必须落在其他相邻五个边区域或角区域的一个中，同样可使用半平面方法来检查线段同窗口的相交边界。
两个端点都可能位于相对的角区域中。仍然使用半平面方法确定相交的边界。

21.缓冲区的构建方法
矢量缓冲区常见的有角平分法和叠置算法。角平分法由三步组成，即逐个线段计算简单平行线，尖角光滑矫正和自相交处理。尖角光滑矫正除角平分线法之外，还可采取圆弧法，但矫正过程都很复杂，难以完备地实现。叠置方法分两步完成。首先求出点、线段等基本元素的缓冲区，然后通过对基本元素缓冲区的叠置运算，求解折线、面边界等复杂目标的缓冲区。

角分线法：难以保证双线的等宽性
叠置算法-基元的生成
假设圆半径是r,A的坐标为(A.x,A.y), B的坐标为(B.x,B.y)。 AB的倾角α=arctg((B.y-A.y)/(B.x-A.x))。Δx=|BD|=rsinα, Δy=|Db|=rcosα。基元矩形框顶点a,b,c,d的坐标为：
a.x=A.x+rsinα; a.y=A.y- rcosα
b.x=B.x+rsinα; b.y=B.y- rcosα
c.x=B.x- rsinα; c.y=B.y+rcosα
d.x=A.x- rsinα; d.y=A.x+rcosα
叠置算法-基元的合并：方法是在交点处将基元边界元素分裂打断，再判断其是否落入其它基元内部，并删除落入基元内部的边界元素。基本运算包括求交运算，以及点在多边形内的判断。
凸角圆弧化：d=r/sin(B/2)保证了平行曲线的等宽性
折点凸凹性的判断：把相邻两个线段看成两个向量，其方向取坐标点序方向。若前一个向量以最小角度转向第二个向量时呈逆时钟方向，则为凸顶点。反之为凹顶点。
折点凸凹性的判断：
AB=(XB-XA,YB-Y); BC=(XC-XB,YC-YB); S=AB X BC =(XB-XA)(YC-YB)-(XC-XB)(YB-YA)
S>0, ABC呈逆时钟，顶点为凸。
S<0, ABC呈顺时钟，顶点为凹。
S=0, ABC共线。
缓冲取边线的自相交：当轴线的弯曲空间不允许双线的边线无压的通过时，就会产生若干个自相交多边形。
重叠多边形与岛屿多边形：岛屿多边形是缓冲区边线的有效组成部分；重叠多边形不是缓冲区边线的有效组成部分，不参与缓冲区的最终构建。
重叠多边形与岛屿多边形的自动判别：首先定义轴线坐标点序为其方向，缓冲区双线分成左右边线，左右边线自相交多边形的判别情形恰好相反。对于左边线，岛屿自相交多边形呈逆时钟方向。重叠自相交多边形呈顺时钟方向。