GIS算法基础整理(填空)

1、第1章l 算法设计的原则：P1（）、（）、（）l 算法的复杂性：P2（）复杂性和（）复杂性l 时间复杂性定义：P2利用某算法处理一个问题规模n的输入所需要的时间l 空间复杂性定义：P8算法在运行过程中临时占用的存储空间的大小第2章l 维数拓展的9交模型：P15 I内部、B边界、E外部，内部包括左边界和下边界l 模型示例P16：II,IB,IE,BI,BB,BE,EI,EB,EEl T,F,*,0,1,2的含义P16-17l 空间关系判定：P17 相离、（）、（）、（）、（）。l P表示零维几何体，L一维，A二维l 用DE-9IM模型表示：P17-20相离FF*FF*相接FT*或( )或( )

2、（除P/P）相交T*T*（P/L P/A L/A）,（ ）(L/L)真包含T*F*F*叠置T*T*T* (A/A P/P) ( ) (L/L)包含a.Contains(b)b.Within(a)相交a.Intersects(b)!a.Disjoint(b)l 矢量叉积定义：P22由（ ）、（ ）、（ ）所组成的平行四边形的带（ ）的面积。l 顺逆时针关系：P22 P×Q>0，P在Q的（ ）方向，反之，P在Q的（ ）方向，若为0，则（ ），可能（ ）也可能（ ）l 折线段的拐向判断：P23 若大于0，则拐向（ ），反之拐向（ ），等于零，三点共线。l 快速排斥试验P23-24图l

3、 跨立试验：P23(P1-Q1)×(Q2-Q1) ×(Q2-Q1) ×(P2-Q1)0P1P2跨立Q1Q2l 前方交会基本概念P40-41l 距离交会基本概念P41-43第3章l 平面坐标变换矩阵：P45 T=adgbehcfi，abde缩放、旋转、对称、错切变换，cf平移变换，gh投影变换，i伸缩变换l 几个变换矩阵：P46-49l 相对于某个点的变换：P49 先把坐标系原点平移到某个点，在新的坐标系下做比例或旋转变换后，再将坐标原点平移回去。l 常用的球面坐标系：P50 ( )坐标系，（ ）坐标系，（ ）坐标系。l 仿射变换的概念：P54 在保留（ ）条件下，

4、仿射变换允许对长方形目标做（ ）、（ ）、（ ）、（ ）变换。l 仿射变换的性质：笔记 点变（ ），直线变（ ），点与直线的（ ）关系不变。l 控制点估算：P54至少需要（ ）个控制点用于估算才有效，用（ ）个或更多控制点来减小测量误差。l 地图投影变换的方法：P55 解析变换法、（ ）法、（ ）法。l 一些常识：笔记 北京54坐标系克拉夫斯基椭球参数西安80坐标系1975国际椭球参数GPS WGS-84l 在何种比例尺用何种投影：P62-69小比例尺：( )投影大比例尺：( )投影、( )投影第4章l 矢量线栅格化的方法：P71 ()栅格化、（）栅格化、恒密度栅格化。l 内部点扩散法：P73

5、-74 由每个多边形一个内部点（种子点）开始，向其8个方向的邻点扩散，判断各个新加入的点是否在多边形边界上。若在边界上，则该新加入点（）。否则把（ ）作为新种子点与原有种子点一起进行新的扩散运算，并将该种子点赋以该多边形的编号。重复上述过程直到（ ）并遇到边界停止为止。l 边界代数法：P75-77 单个多边形：初始化的栅格阵列个栅格值为零，以栅格行列为参考坐标轴，由多边形边界上某点开始（ ）时针搜索边界线，当边界上行时，位于该边界左侧的具有相同行坐标的所有栅格被（ ）a（a为多边形编号），当下行时，该边界左边（前进方向看为右侧）所有栅格点（ ）a，边界搜索完毕则完成了多边形的转换。多个多边形：

6、当边界弧段上行时，该弧段与左图框之间的栅格增加一个值（左多边形编号减去右多边形编号）；当边界弧段下行时，该弧段与左图框之间栅格增加一个值（右多边形编号减去左多边形编号）。l 栅格数据矢量化的基本步骤：P78 1. 边界提取采用高通滤波将栅格图像（ ）或以（ ）标识边界点。2. 边界线（ ）对每个（ ）由一个结点向另一个结点搜索，通常对每个（ ）需沿除了进入方向的其他7个方向搜索下一个边界点，直到连成边界弧段。3. ( )生成对于矢量表示的边界弧段数据，判断其与原图上各（ ）的空间关系，以形成完整的拓扑结构并建立与（ ）的联系。4. 去除多余点及（ ）由于搜索是逐个（ ）进行的，必须去除由此造成

7、的（ ）记录，以减少（ ）；搜索结果，曲线由于（ ）的限制可能不够圆滑，需采用一定的插补算法进行光滑处理。l 距离变换法：P79 距离变换图是一种栅格图像，其中每个像元的灰度值等于它到栅格地图上相邻物体的（ ）。l 距离变换法基本思想：P79 反复进行“（ ）”和“将（ ）结果和（ ）结果这两个栅格图像做（ ）”两种基本运算。 终止条件是“若对原图再（ ），将成为（ ）”。l 骨架图：P79 从距离变换图中提取具有（ ）的那些像元所组成的图像。l 多边形栅格转矢量的双边界搜索算法基本步骤：P841. （ ）和（ ）提取2. （ ）搜索与（ ）信息记录3. （ ）去除第5章l 矢量数据的压缩包括

8、那些内容：P90 一是在不扰乱（ ）的前提下，对（ ）进行合理的抽稀；二是对（ ）重新进行编码，以减少所需要的（ ）。l 矢量数据压缩的特点：P90 不可逆，数据压缩后，数据量变小，数据的精度降低。l 曲线压缩算法的种类：P90-95 间隔去点法、垂距法和偏角法、道格拉斯-普克法、光栏法。l 曲线压缩算法的比较：P95-96（ ）方法压缩效果占优但工作量大，其次是（ ）、（ ）。（ ）算法严密，运算量少。l 栅格数据的压缩：P98-102 四叉树编码在第7章整理，其它了解一下。l 拓扑关系自动生成算法的一般过程：P1031. （ ），使整幅图形中的所有弧段，在除端点处相交外，没有其他交点，即没

9、有相交或自相交的弧段。2. （ ），建立结点、弧段关系。3. （ ），以左转算法或右转算法跟踪，生成多边形，建立多边形与弧段的拓扑关系。4. 建立（ ）与（ ）的拖布关系。调整弧段左右多边形标识号。多边形内部标识号自动生成。l 左转算法P114-116第6章l 两个三维矢量的矢量积的模等于两矢量构成的平行四边形的面积。P120 其余自己看。第7章l 空间索引：P135 依据空间对象的（ ）和（ ）或空间对象之间的某种空间关系，按一定的顺序排列的一种数据结构。其中包括空间对象的（ ），如对象的标识、外接矩形及指向空间对象实体的（ ）。l B树和B+树不适应空间数据的管理。 P135l R树的定义

10、：P141-142 R树的结点由若干个结构为(I,PointerToChild)的单元组成。非叶子结点中，I为包含其所有子结点的最小包含矩形（MBR）。在叶子结点中，I为空间对象的MBR。 PointToChild是个指针，指向（ ）。但在叶子节点中，是空间对象的标识符（identifier，ID）。根据ID，可以检索到空间对象的详细信息。l R树的性质：P142 设M为结点中单元的最大数目，m（1mM/2）为非根结点中单元个数的下限。1. 每个叶子结点中包含的单元个数介于（ ）和（ ）之间，除非它同时是根节点。2. 每个叶子结点中的单元（I, SpatialObjectID）中，I是包含（

11、）的MBR，SpatialObjectID是该空间对象的ID。3. 每个非叶子结点的子节点数介于（ ）和（ ）之间，除非它是根节点。4. 每个非叶子结点的单元(I,PointerToChild)中，I是包含（ ）的MBR，PointerToChild是指向子节点的指针。通过该指针能访问到子节点。5. 根节点最少有（ ）个子结点，除非它同时是叶子结点。6. 所有的叶子结点都处于树的同一层上。l R树的搜索算法：P142-143l R树的插入算法：P143-144l R树的删除算法：P144l 常用线性四叉树的编码方法：P151-155 基于（ ）的线性四叉树编码、基于（ ）进制的线性四叉树编码、

12、基于（ ）进制的线性四叉树编码。 其基本思想自己看。第8章l 空间数据内插的方法：P159 几何方法、统计方法、空间统计方法、函数方法、随机模拟方法、物理模型模拟方法和综合方法。l 地理学第一定律：P159 邻近的区域比距离远的区域更相似。l 常用的几何方法：P159 泰森多边形（最近距离法）和反距离加权方法。l 常用的统计方法：P160 趋势面方法和多元回归方法。l 空间统计方法：P160 以克里金法及其各种变种为代表。l 常用的函数方法：P160 傅里叶级数、样条函数、双线性内插、立方卷积法。l 常用的随机模拟方法：P161高斯过程、马尔科夫过程、蒙特卡罗方法、人工神经网络法。l 确定性模

13、拟可研究山区气候。P161第9章l 不规则三角网（TIN）的特点：P1721. TIN是由点生成的，每个点具有一个反映高程值的连续型实数值。2. TIN是根据采样的数据点的值计算出来的，表现为一个连续的三维的表面。3. TIN是一系列非重叠的三角形或面，这些三角形或面完全填充一个区域。l 泰森多边形（Voronoi图）P173-174l Delaunay三角网是一系列相连的但不重叠的三角形的集合，而且这些三角形的外接圆不包含这个面域的其他任何点。其性质：P1741. 保证最邻近的点构成三角形，即三角形的边长之和尽量最小，且每个Delaunay三角形的外接圆不包含面内的其他任何点，称之为Dela

14、unay三角网的空外接圆性质，这个特征已经作为创建Delaunay三角网的一项判别标准。2. 最大最小角性质：在由点集V中所能形成的三角网中，Delaunay三角网中三角形的最小内角尽量最大，即三角形尽量接近等边三角形。第10章l 缓冲区分析：P185 是地理信息系统中使用非常频繁的一种空间分析，是对空间特征进行度量的一种重要方法。l 缓冲区：P185 是根据空间数据库中的点、线、面地理实体或规划目标，自动建立其周围一定宽度范围的多边形。l 几个概念：P185-1871. 轴线的左侧和右侧轴线（ ）方向的左侧为轴线的左侧。2. 多边形的方向多边形边界（ ）方向为正方向。计算面积为正的多边形称为

15、正向多边形。3. 缓冲区的外侧和内侧缓冲区的外边界是正向多边形，（ ）边界是负向多边形。以多边形的前进方向为准，多边形的左侧成为缓冲区的（ ）侧。4. 轴线(边界)转折点的凹凸性右手螺旋法则，如图。PiPi+1Pi-1凹凸 PiPi+1Pi-1凹凸l 圆弧弥合的方法：P187 将（ ）等分，用等长的弦代替（ ），即用均匀步长的直线段逼近圆弧段。l 凸角圆弧法的基本思想：P188 在轴线两端用半径为（ ）的圆弧弥合；在轴线的各转折点，首先判断该点的（ ），在（ ）侧用半径为缓冲距的圆弧弥合，在（ ）侧用与该点关联的前后两相邻线段的偏移量为缓冲距的两平行线的交点作为（ ）顶点。这样，在凸侧用圆弧弥

16、合，保证平行线与轴线等宽；在凹侧平行线交点在角平分线上。l 凸角圆弧法的关键算法：P189-190 1. 判断轴线转折点的凹凸性若Pi-1以最小的角度扫向Pi时为逆时针，则该点左侧为（ ）右侧为（ ）。2. 求与转折点相邻的两线段的方向角3. 求与Pi相邻的两线段平行线交点4. 确定圆弧弥合的起始点、终止点和方向起始点（终止点）的转折点沿前（后）一线段的法线方向向远距离轴线方向平移一个缓冲距得到的点。为保证生成的缓冲区边界是顺时针方向，轴线左侧圆弧弥合是（ ）方向，右侧是（ ）方向。l 自相交处理的基本思想：P194 求出缓冲区边界上的（ ），判断这些点是入点还是出点，判断自相交点之间确定的自

17、相交多边形的性质，是（ ）则保留，否则保留面积最大的（ ）为外边界l 自相交处理的关键算法： P1941. 判断自相交点是入点还是出点入点是从缓冲区外侧进入内侧的自相交点，出点是从缓冲区内侧到外侧的自相交点。2. 判断自相交多边形是岛屿还是重叠区经过处理生成的缓冲区多边形是（ ）方向。边界自相交形成的多边形中，负向多边形是（ ），正向多边形中，面积最大者为（ ），其他都是重叠区。l 四弧段结点的定义：P196 由四条弧段构成的节点。 由四条以上（必须是偶数）弧段构成的结点称为非四弧段结点。l 缓冲区多边形的重叠合并的分类：P197 两个（ ）缓冲区多边形的重叠合并、一（ ）一（ ）、两个（ ）。l 四弧段结点上的弧段取舍规则：P197-198 当一个弧段的左弧段为来向弧段而右弧段为去向弧段，此弧段为需保留弧段，否则此弧段为需删除弧段。第11章l 网络分析是基于（ ）数据的。P201l 最佳路径是指从始点到终点的最短距离或者（ ）的路线。P201l 最佳布局中心位置是指各中心所覆盖范围内任一点到中心的距离最近或（ ）。P201l 网络流量是指从网络上从起点到终点的（ ）。P201l 路径分析是GIS最基本功能，其核心是对（ ）和（ ）的求解。P203l 几个名词P2041. 静态求最佳路径由用户确定权值关系后，即给定每