GIS算法基础重点 下载本文

相交的弧段2结点匹配,建立结点弧段关系3建立多边形,以左转算法或右转算法跟踪,生成多边形,建立多边形和弧段的拓扑关系4建立多边形与多边形的拓扑关系,调整弧段的左右多边形标号,多边形内部标识号的自动生成。空间索引:是指依据空间对象的位置和形状或空间对象之间的目中空间关系,按一定的顺序排列的一种数据结构,其中包括空间对象的概要信息。B树定义:一个M阶的B树1)树中每个结点至多有M棵子树2)若根结点不是叶子节点。至少有两棵子树3)除根之外的所有非终端节点至少有M/2(取整)棵子树4)所有的非叶结点中包含(A0,,…..)Ki为关键字,Ai为指针,Dn为数据指针5)所有的叶子节点都出现在同一层次上,并且不带信息。R树定义:1)每个叶子节点包含的单元个数介于m和M之间,除非它同时是根节点。2)每个叶子结点中的单元中,I是包含该n维空间对象的MBR,ID。3)每个叶子节点的子节点数介于m和M之间,除非它是根节点。4)每个非叶子节点的单元中,I是包含子节点的MBR,POINTER是指向子节点的指针,通过该指针能访问到子结点5)根节点最少有两个子结点,除非它同时是叶子结点6)所有的叶子节点都处于树的同一层上。

算法的设计原则是 正确性 、 确定性 、 清晰性 。

算法的复杂度包括 算法的时间复杂度 、 算法的空间复杂度 。 Egenhofer(1993)构造出一个由 边界 、 内部 、 外部 的点集组成的9—交空间关系模型(9IM)。

折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段P0P1和P1P2,通过计算(P2 - P0)×(P1 - P0)的符号便可以确定折线段的拐向:若(P2 - P0)×(P1 - P0) > 0,则P0P1在P1点拐向 右侧 后得到P1P2;若(P2 - P0)×(P1 - P0) < 0,则P0P1在P1点拐向 左侧 后得到P1P2;若(P2 - P0)×(P1 - P0) = 0,则 P0、P1、P2三点共线 。

在空间查询中,最常用的两种查询是 按属性信息的要求来查询定位空间位置 和 根据对象的空间位置查询有关的属性信息. 。

实现一种地图投影点的坐标变换为另一种地图投影点的坐标,就是要

?x?f1(?,?)找出 关系式,其方法有 解析变换法 、 数值解析

??y?f2(?,?)

变换法 和 数值变化法 。

设面状物体的轮廓边界由一个点的序列P1 (x1 , y1), P2 ( x2, y2 ), ?,

Pn (xn, yn)表示,其面积为 。

轴线或边界上的相邻三点Pi-1、Pi 、Pi+1,用 右手螺旋 法则判断轴线(边界)转折点的凸凹性,若拇指向下,则Pi点左侧为 凸 ,右侧为凹 。 在下面选项中,不属于数据挖掘步骤的是( B )。

A数据变换 B数据分类 C数据清理 D知识表示 有六种多项式时间算法最为常见,其关系为 ( D )。 A O(1)

B O(1)

1nxiS??2i?1xi?1yiyi?1我国现在采用的1980国家大地坐标系应用的是哪种地球椭球体参数( B )。 A克拉索夫斯基椭球 B 1975国际椭球 C WGS-84系椭球 D 1980国际椭球

磁盘访问次数是影响空间索引性能的关键指标,下面哪种空间索引方法是比较优秀的空间索引方法。(A )

A CELL树 B R树 C B+树 D R+树

( A)反映城市的带状延伸程度,带状延伸越明显则延伸率越大,反映城市的离散程度越大。

A 伸延率 B 紧凑度 C 紧凑度指数 D 放射状指数 在矢量缓冲区的实现算法中对于双线问题最简单的方法是( C )。 A 凸角圆弧法 B 叠置算法 C 角平分线法 D 圆弧拟合法 下图按照前序遍历的方法写出结果。( A ) A a + b * c - d - e / f B - + a * b - c d / e f C a b c d - * + e f / - D 没有正确答案

在下面选项中,不属于数据挖掘算法的是(B )。

A聚类分析 B叠置分析 C主成分分析 D层次分析法 下面关于点缓冲区边界生成算法的叙述哪一条正确?( A ) A 等分的圆心角越小,步长越小,误差越小; B等分的圆心角越大,步长越小,误差越小; C等分的圆心角越大,步长越小,误差越大; D等分的圆心角越小,步长越大,误差越小。 在下面选项中,不属于B-树的性质的是( D )。

A 多叉树 B 查找树 C 平衡树 D 二叉树 无向图的邻接矩阵是不对称的。 (× ) 在多边形的方向判断中,多边形边界顺时针方向称为负方向。 ( × ) 同样的一个算法可以用几种不同的形式来描述,也可能存在几种解决相同问题的

算法。 ( )

判断圆在矩形中的充要条件是:圆心在矩形中且圆的半径小于等于圆心到矩四边的距离的最小值。 ( )

网络数据结构的基本组成部分和属性是链和结点。 ( ) 所有元素存放在一片连续的存贮单元中,逻辑上相邻的元素存放到计算机内存仍然相邻这种存储方式是链接存储方式。 (× )

紧凑度是反映城市的紧凑程度,其中圆形区域被认为最紧凑,紧凑度为1。其它形状的区域,其离散程度越小则紧凑度越低。 (× ) 缓冲区实现算法有矢量方法和栅格方法两种。 ( ) 对于块式编码来说,图斑越碎,压缩比越高。 (× ) 矢量数据的压缩往往是不可逆的,数据压缩后数据量变小了, 但数据的精度不变。 (× )

维述扩展的9交集模型关系非常复杂,通过对大量的空间关系进行归纳和分类,得出5种基本的空间关系,这5种关系定义为空间关系的最小集,他们具有哪些特征?

(1)相互之间不能进行转化;(2)能覆盖所有的空间关系模式;(3)能应用于同维与不同维的几何目标;(4)每一种关系对应于唯一的DE-9IM矩阵; (5)任何其它的DE-9IM关系可以通过用这5种基本关系进行表达。 简述Dijkstra算法的步骤。

(1)引进一个辅助向量D,它的每个分量D[i]表示当前所找到的从起点 vm 到每个终点vi的最短路径的长度。

假设用带权的邻接矩阵arcs来表示带权有向图,arcs[i][j]表示弧

vj >上的权值。

不连通,则arcs[i][j]=∞。 那么D[i]的初值为:D[i]=arcs[m][i] vi∈V

此外,将已找到的从vm 出发的最短路径的终点的集合记为S,它的初始状态为空集。

(2)选择 vj 使得 D[j]=Min{D[i] | vi∈V-S}

Vj就是当前求得的一条从vm出发的最短路径的终点。其中j为这条最短路径的终点,将其加入到终点集合S,令S=S∪{j}

(3)修改辅助向量D,即修改从vm出发到集合V-S上任一顶点vk可达的最短路径长度。

显然,若D[j]+arcs[j][k]

D[k]=D[j]+arcs[j][k]

(4)重复操作第二步、第三步共n-1次。由此求得从v到图上其余各顶点的最短路径是依路径长度递增的序列。

在动态缓冲区生成算法中主要是针对哪两类特殊情况提出的?并写出他们的生成方法。

答:动态缓冲区生成是针对两类特殊情况提出的:

一类是流域问题:从流域上游的某一点出发沿流域下朔,河流的影响半径或流域的辐射范围逐渐扩大;相反,则逐渐缩小。

另一类是污染问题。污染源对邻近对象的影响程度随距离的增大而逐渐缩小。 (一)对于流域问题,可以基于线目标的缓冲区生成算法,采用分段处理的办法分别生成各流域分段的缓冲区,然后按某种规则将各分段缓冲区光滑连接;也可以基于点目标的缓冲区生成算法,采用逐点处理的办法分别生成沿线各点的缓冲圆,然后求出缓冲圆序列的两两外切线,所有外切线相连即形成流域问题的动态缓冲区。

(二)针对污染问题,根据物体对周围空间影响度变化的性质,通过引入一个影响度参数,给出了3种动态缓冲区分析模型:

(1)物体对周围空间的影响度Fi随距离di呈线性衰减: (2)物体对周围空间的影响度Fi随距离di呈二次函数衰减: