GIS算法基础整理填空.docx

GIS算法基础整理填空.docx

《GIS算法基础整理填空.docx》由会员分享，可在线阅读，更多相关《GIS算法基础整理填空.docx（12页珍藏版）》请在冰点文库上搜索。

GIS算法基础整理填空

•算法设计的原则：

区|（x（x（）

•算法的复杂性：

巨|（）复杂性和（）复杂性

•时间复杂性定义：

巨）利用某算法处理一个问题规模n的输入所需要的时间

•空间复杂性定义：

国算法在运行过程中临时占用的存储空间的大小

第2章

•维数拓展的9交模型：

巨1|l内部、B边界、E外部，内部包括左边界和下边界

•模型示例网：

II,旧,1巳巳EI,EB,EE

•T.F,*,0,l,2的含义|P16-17

•空间关系判定：

卜7卜目毒、（X（X（）（）,

•P表示零维几何体，L一维，A二维

•用DE-9IM模型表示：

P17-20

相哀

FF*FF****

相接

FT*……或（）或（）（除P/P）

相交

T*T（P/LP/AL/A）,（）（L/L）

真包含

TT**F***

叠置

T*y*T***（A/AP/P）（）（L/L）

包含

a.Contains（b）<=»b.Within（a）

相交

a.lntersects（b）<=>!

a.Disjoint（b）

•顺逆时针关系：

巨|>xQ>0,p在Q的（）方向，反之，P在Q的（）方向，若为0,则（），可能（）也可能（）

•折线段的拐向判断：

囹若大于0,则拐向（），反之拐向（），等于零，三点共

线。

•快速排斥试验P23-24图

•跨立试验：

^23|（P1-Q1）x（Q2-Q1）x（Q2-Q1）x（P2-Q1）^0<=>P1P2跨立Q1Q2

•前方交会基本概念卜40-4”

•距离交会基本概念R41-43

第3章

।।[ad91

•平面坐标变换矩阵：

网T=beh,abde缩放、旋转、对称、错切变换，cf平移lcfi.

变换，gh投影变换，i伸缩变换

•几个变换矩阵：

P46・491

•相对于某个点的变换：

国先把坐标系原点平移到某个点，在新的坐标系下做比例或旋转变换后，再将坐标原点平移回去。

•常用的球面坐标系：

网（）坐标系，（）坐标系，（）坐标系。

•仿射变换的概念：

回在保留（）条件下，仿射变换允许对长方形目标做（X

（X（X（）变换。

•仿射变换的性质：

殛点变（）,直线变（），点与直线的（）关系不变。

•控制点怙算：

国至少需要（）个控制点用于估算才有效，用（）个或更多控制点来

减小测量误差。

•地图投影变换的方法：

国解析变换法、（）法、（）法。

•一些常识：

瓯1

北京54坐标系

克拉夫斯基椭球参数

西安80坐标系

1975国际椭球参数

GPS

WGS-84

•在何种比例尺用何种投影：

「62-69|

小比例尺：

（）投影大比例尺：

（）投影、（）投影

第4章

•矢量线棚格化的方法：

巨|（渊格化、（）栅格化、恒宓度栅格化。

•内部点扩散法：

373-74|由每个多边形一个内部煎（种子点）开始，向其8个方向的邻点扩散，判断各个新加入的点是否在多边形边界上。

若在边界上，则该新加入点（

，否则把（）作为新种子点与原有种子点一起进行新的扩散运算，并将

该种子点就以该多边形的编号。

重复上述过程直到（）并遇到边界停止为

止。

•边界代数法：

卜75-77忤个多边形:

初始化的栅格阵列个栅格值为零，以栅格行列为参考坐标轴，由多边形边界上某点开始（）时针箜索边界线，当边界上行时，位于该边界左侧的具有相同行坐标的所有栅格被（）a（a为多边形端号），当下行时，该边

界左边（前进方向看为右侧）所有栅格点（）a,边界搜索完毕则完成了多边形的转

换。

多个多边形：

当边界弧段上行时，该弧段与左图框之间的栅格增加一个值（左多边

形编号减去右多边形端号）;当边界弧段下行时，该弧段与左图框之间栅格增加一个值

（右多边形编号减去左多边形编号＞

•栅格数据矢量化的基本步景:

恒I

1.边界提取

采用高通滤波将栅格图像（）或以（）标

识边界点。

2.边界线（）

对每个（）由一个结点向另一个结点搜索，通

常对每个（）需沿除了进入方向的其他7个方

向搜索下一个边界点，直到连成边界弧段。

3.。

生成

对于矢量表示的边界弧段数据，判断其与原图上各

（）的空间关系，以形成完整的拓扑结沟并建

立与（）的联系。

4.去除多余点及（）

由于搜索是逐个（）进行的，必须去除由此造成的（）记录，以减少（”搜索结果，曲线由于（）的限制可能不够圆滑，需采用一定的插补算法进行光滑处理。

•距离变换法：

画距离变换图是一种栅格图像,其中每个像元的灰度值等于它到栅格地图上相邻物体的（b

•距离变换法基本思想：

国反复进行尸和“将（）结果和（）结果这两

个栅格图像做（J两种基本运算。

终止条件是“若对原图再（），将成为（%

•骨架图：

国从距离变换图中提取具有（）的那些像元所组成的图像。

•

多边形栅格转矢量的双边界搜索算法基本步探:

国

2.（

）搜索与（

）信息记录

3.（

）去除

•矢量数据的压缩包括那些内容：

瓯］一是在不扰乱（）的前提下，对（）进

行合理的抽稀；二是对（）重新进行编码，以减少所需要的（）»

•矢量数据压缩的特点：

画不可逆，数据压缩后，数据量变小，数据的精度降低。

•曲线压缩算法的种类：

瓯逅|间隔去点法、垂距法和偏角法、道格拉斯-普克法、光栏法。

•曲线压缩算法的比较中95阕（）方法压缩效果占优但工作量大，其次是（\

（'（）算法严密，运算量少。

•栅格数据的压缩：

「98-102|四叉树编码在第7章整理，其它了解一下。

•拓扑关系自动生成算法的一般过程：

叵|

1.（）,使整幅图形中的所有弧段，在除端点处相交外，没有其他交点，即没有

相交或自相交的弧段。

2.（），建立结点、弧段关系。

3.（）,以左转算法或右转算法跟踪，生成多边形，建立多边形与弧段的拓扑关

系。

4.建立（）与（）的拖布关系。

调整弧段左右多边形标识号。

多边形内部标

识号自动生成。

•左转算法巨~良-116

•两个三维矢量的矢量积的模等于两矢量构成的平行四边形的面积。

.1201其余自己看。

第7章

•空间索引：

巨可依据空间对象的（）和（）或空间对象之间的某种空间关系，

按一定的顺序排列的一种数据结构。

其中包括空间对象的（），如对象的标识、外

接矩形及指向空间对象实体的（、

•B树和B+树不适应空间数据的管理。

卜13目

•R树的定义：

卜⑷-阕R树的结点由若干个结彻为（IFointerToChlld）的单元组成。

非叶子结点中，1为包含其所有子结点的最小包含矩形（MBR，在叶子结点中，1为空间对象的MBRoPointToChild是个指针，指向（'但在叶子节点中，是空间对象

的标识符（identifier,ID）,根据ID,可以检索到空间对象的详细信息。

•R树的性质:

「142设M为结点中单元的最大数目，m（）为非根结点中单元

个数的下限。

1.每个叶子结点中包含的单元个数介于（）和（）之间，除非它同时是根节点。

2.每个叶子结点中的单元（I,SpatialObjectID）中，I是包含（）的MBR,

SpatialObjectID是该空间对象的ID。

3.每个非叶子结点的子节点数介于（）和（）之间，除非它是根节点。

4.每个非叶子结点的单元（IFointerToChild）中，I是包含（）的MBR,

PointerToChild是指向子节点的指针。

通过该指针能访问到子节点。

5.根节点最少有（）个子结点，除非它同时是叶子结点。

6.所有的叶子结点都处于树的同一层上。

•R树的搜索算法：

「142-143

•R树的插入算法：

卜143・144

•R树的删除算法：

目且

•常用线性四叉树的编码方法：

5151-155便于（）的线性四叉树编码、基于（）

进制的线性四叉树编码、基于（）进制的线性四叉树编码。

其基本思想自己看。

第8章

•空间数据内插的方法：

1591几何方法、统计方法、空间统计方法、函数方法、随机模拟方法、物理模型模拟方法和综合方法。

•地理学第一定律：

£国邻近的区域比距离远的区域更相似。

•常用的几何方法：

巨亘|泰森多边形（最近距离法）和反距商加权方法。

•常用的统计方法：

.160,势面方法和多元回归方法。

•空间统计方法：

160|以克里金法及其各种变种为代表。

•常用的函数方法：

卜160恰里叶级数、样条函数、双线性内插、立方卷积法。

•常用的随机模拟方法：

16”高斯过程、马尔科夫过程、蒙特卡罗方法、人工神经网络法。

•确定性模拟可研究山区气候。

•不规则三角网（TIN）的特点：

「172|

1.TIN是由点生成的，每个点具有一个反映高程值的连续型实数值。

2.TIN是根据采样的数据点的值计算出来的，表现为一个连续的三维的表面。

3.TIN是一系列非重叠的三角形或面，这些三角形或面完全填充一个区域。

•泰森多边形（Voronoi图）＞173-174

•Delaunay三角网是一系列相连的但不重叠的三角形的集合，而且这些三角形的外接圆不包含这个面域的其他任何点。

其性质：

巨可

1.保证最邻近的点构成三角形，即三角形的边长之和尽量最小，且每个Delaunay三角形的外接圆不包含面内的其他任何点称之为Delaunay三角网的空外接圆性质,这个特征已经作为创建Delaunay三角网的一项判别标准。

2.最大最小角性质：

在由点集V中所能形成的三角网中，Delaunay三角网中三角形的最小内角尽量最大，即三角形尽量接近等边三角形。

第10章

・缓冲区分析：

巨蚪是地理信息系统中使用非常频繁的一种空间分析，是对空间特征进行度量的一种重要方法。

・缓冲区：

运I是根据空间数据库中的点、线、面地理实体或规划目标，自动建立其周围一定宽度范围的多边形。

・几个概念：

h85-187

1.轴线的左斜和右侧

转线（）方向的左侧为轴线的左制。

2.多边形的方向

多边形边界（）方向为正方向。

计算面积为

正的多边形称为正向多边形。

3.缓冲区的外侧和内侧

缓冲区的外边界是正向多边形,（）边界是

负向多边形。

以多边形的前进方向为准，多边形

的左例成为缓冲区的（）斜。

4.轴线（边界）转折点的凹凸性

右手螺旋法则，如图。

/Pa】Pal

^l\®nnnn「。

n

P『1pj

•圆弧弥合的方法：

187帆（）等分，用等长的弦代替（），即用均匀步长的

直线段逼近圆弧段。

•凸角圆弧法的基本思想：

.188|在轴线两端用半径为（）的圆弧弥合；在轴线的各

转折点，首先判断该点的（），在（）侧月半径为矮冲距的圆弧弥合，在（）

侧用与该点关联的前后两相邻线段的偏移量为缓冲距的两平行线的交点作为（）顶

点。

这样，在凸例用圆加弥合，保证平行线与辅线等宽；在凹侧平行线交点在角平分线上。

•凸角圆弧法的关铤算法：

|P189-19O|

1.判断轴线转折点的凹凸性

若Pi-1以最小的角度扫向Pi时为逆时针，

则该点左侧为（）右侧为（）o

2.求与转折点相邻的两线段的方向角

3.求与Pi相邻的两线段平行线交点

4.确定圆弧弥合的起始点、终止点和方

向

起始点（终止点）的转折点沿前（后）一线段的法线方向向远距离轴线方向平移一个缓冲距得到的点。

为保证生成的缓冲区边界是顺时针方向，轴线左的圆弧弥合是（）方向，右侧是（）方向。

•自相交处理的基本思想：

目可求出媛冲区边界上的（），判断这些点是入点还是

出点，判断自相交点之间晒定的自相交多边形的性质，是（）则保留，否则保留面

积最大的（）为外边界

•自相交处理的关键算法：

£网

1.判断自相交点是入点还是出点

入点是从缓冲区外侧进入内侧的自相交点，出点是从缓冲区内例到外侧的自相交点。

2.判断自相交多边形是岛屿还是重叠区

经过处理生成的理冲区多边形是（）

方向。

边界自相交形成的多边形中，负向多边形是（），正向多边形中，面积

最大者为（），其他都是重叁区。

•四弧段结点的定义：

.196|由四条弧段构成的节点。

由四条以上（必须是偶数）弧段构成的结点称为非四弧段结点。

•缓冲区多边形的重叠合并的分类.197帆飞媛冲区多边形的重叠合并、一（）

-（八两个（）。

•四弧段结点上的弧段取舍规则:

E97-198|当一个弧段的左弧段为来向弧段而右弧段为

去向弧段，此弧段为需保留弧段，否则此狙段为需删除弧段。

第11章

•网络分析是基于（）数据的。

区回

•最佳路径是指从始点到终点的最短距离或者（）的路线。

巨目]

•最佳布局中心位置是指各中心所覆盖范围内任一点到中心的距离最近或（）o|P20l]

•网络流量是指从网络上从起点到终点的（）。

|p2o7|

•路径分析是GIS最基本功能，其核心是对（）和（）的求解。

际目

•几个名词旧丽

1.静态求最佳路径

由用户确定权宜关系后，即给定每条弧段的属性，当需要

求最佳路径时，读出路径的相关属性，求最佳路径。

2.动态分段技术

给定一条路径由多段联系组成，要求标注出这条路上的千米点或要求定位某一公路上的某一点，标注出某条路上从某一千米数到另一千米数的路段。

3.N条最佳路径分析

确定起点、终点，求代价较小的几条路径，因为在实践中往往仅求出最佳路径并不能满足要求，可能因为某种因素不走最佳路径，而走近似最佳路径。

4.最短路径

确定起点、终点和所要经过的中间点、中间连线，求最短

路径。

5.动态最佳路径分析

实际网络分析中权值是随着权值关系式变化的，而且可能会临时出现一些障碍点，所以往往需要动态地计算最佳路径。