GIS算法原理知识点总结.docx

GIS算法原理知识点总结
算法设计和分析：
1、算法设计的原则：
正确性：若一个算法本身有缺陷，那么它将不会解决问题；确定性：指每个步骤必须含义明确，对每种可能性都有确定的操作。
清晰性：一个良好的算法，必须思路清晰，结构合理。
2、算法的复杂性包括：时间复杂性和空间复杂性。
3、时间复杂性：用一个与问题相关的整数量来衡量问题的大小，该整数量表 示输入数据量的尺度，称为问题的规模。利用某算法处理一个问题规模为n 的输入所需要的时间，称为该算法的时间复杂性。
4、算，去的概念：算法是完成特定任务的有限指令集。所有的算法必须满足下 面的标准：
性性性 入出确限效 输输明有有 ♦ ♦ ♦ ♦ ♦

GIS算法的计算几何基础1、理解矢量的概念：如果一条线段的端点是有次序之分的，我们把这种线段 称为有向线段(directed segment)«如果有向线段plp2的起点Pl在坐 标原点，我们可以把它称为矢量P2。

5. 矢量叉积：计算矢量叉积是直线和线段相关算法的核心部分。
设矢量P= (xl,yl), Q= (x2,y2)，则矢量叉积定义为(0,0)、pl、p2 和plp2所组成的平行四边形的带符号的面积，即PXQ = xby2-X2.yl, 其结果是个标量。显然有性质PXQ=- (QXP)和Px-Q=- (PxQ)o
P X Q〉0,则P在Q的顺时针方向；void CpntToDemDlg:: RecToDemO
3(
// TODO:在此添加控件通知处理程序代码
CDC *pDC-GetDC()；
FILE *OUt；
out=fopen ("d: Wraster. txt", "w");
Invalidate();
UpdateWindow();
UpdateData(true);
returnRecO ;
int dy»(ymax-ymin)/(row-);
int dx»(xmax-xmin)/(col-);
bool judge-false;
fprintf(out,"'d id\n",row,col);
for(int i=l;i<row+ ;i++)
(
for(int j« ;j<col+ ;j++)
{for(int n= ;n<cnt+ ;n++)
<if(arr[n].x>(xmin+(j- )*dx)&&arr[n].x<(xmin+j*dx)&&arr[n].y>(ymin+(i- )*dy)&& arr(nJ.y<(ymin+i*dy))
(judge-true;
break;if (judge)
{pDC->Rectangle(xmin+(j-：)*dx,ymin+(i・)*dy,xmin+j*dxzymin+i*dy); CRect rt(xmin+(j- )*dx,ymin+(i- )*dy,xmin+j*dx,ymin+i*dy); pDC->FinSolidRect(&rt,RGB(255, ,0));
fprintf(outz"%d ",1); judge=false;}
else{
pDC->Rectangle(xmin+(j- )*dxrymin+(i- )*dy,xmin+j*dxzymin+i*dy); fprintf(out,"%d ",0);judge=false;
}}
fprintf(out,"Xn");void CpntToDemDlg::returnRec(void)
xmax=arr[1].xzymax=arr[1].y; xmin=arr[1].xzymin=arr[1].y; for(int i=l;i<cnt+l;i++)
{
xmin=arr[i].x;
ymin=arr[i].y;
xmax=arr[i].x;
ymax=arr[i].y;
if(xmin>arr[i].x) if(ymin>arr[i].y) if(xmax<arr[i].x) if(ymax<arr[i].y)Col:

Col:
io
确定
取消
矢量数据的压缩：矢量数据的压缩包括两个方面的内容，一是在不扰乱拓扑关系的
前提下，对采样点数据进行合理的抽稀。二是对矢量坐标数据重新进 行编码，以减少所需要的存储空间。
1）间隔取点法：每隔K个点取一点，或舍去那些比规定距离更近的点，首末点 一定要保留。

2）垂距法:

原始曲线。"
.Q-一3
对点2测试距离大于规定的限差4
3b 2
。-一对点3测试距离小于规定的限差
,Q
4限差|

光栏法的基本思想是（上图）：定义一个扇形区域，通过判断曲线上的点在扇形外还是在扇 形内，确定保留还是舍去。设曲线上的点列为{pi}, i = 1, 2, n,光栏口经为d,可根据 压缩量的大小自己定义，则光栏法的实施步骤可描述为：
1。、连接p1和p2点，过p2点作一条垂直于p1p2的直线，在该垂线上取两点a1和a2,使 a1p2=a2p2=d / 2,此时a1和a2为“光栏”边界点，p1与a1、p1与a2的连线为以p1为 顶点的扇形的两条边，这就定义了一个扇形（这个扇形的口朝向曲线的前进方向，边长是任意 的）。通过p1并在扇形内的所有直线都具有这种性质，即p1p2±各点到这些直线的垂距都不 大于d您。
2。、若p3点在扇形内，则舍去p2点。然后连接p1和p3,过p3作p1p1的垂线，该垂线与 前面定义的扇形边交于c1和C2。在垂线上找到b1和b2点，使p3b1=p3b2=d/2,若b1 或b2点（（图4-4-3中为b2点）落在原扇形外面，则用c1或c2取代（图4-4-3中由c2取代b2）。 此时用p1b1和p1c2定义一个新的扇形，这当然是口径（b1c2）缩小了的“光栏”。
3。、检查下一节点，若该点在新扇形内，则重复第（2）步；直到发现有一个节点在最新定义的 扇形外为止。
4。、当发现在扇形外的节点，如图4-4-3中的p4,此时保留p3点，以p3作为新起点，重复 1。〜3。。如此继续下去，直到整个点列检测完为止。所有被保留的节点（含首、末点），顺序地 构成了简化后的新点列。
4）道格拉斯一普克法：
首先将一条曲线首、末点连一直线，求出各点到该直线的距离，选其最大者与规定的临 界值相比较若大于临界值，则离该直线距离最大的点保留，否则，将直线两端间各点全 部舍去，并将原线条分成两部分，对每部分线条再实施该抽稀过程，直到结束。抽稀结 果点数随选取限差临界值的增大而减少，应用时应根据精度要求来确定抽稀限差临界 值，以获得最好的结果。即道格拉斯一普克（Douglas-peuker）算法。

ResultP】
弦第一轮垂距
第二轮垂距I | 阈值
6. 栅格数据的压缩:
1）链式编码：

3,1,7,0,1,2,3,4,5,64,1,6,7,0,1,2,3,4,5费里曼链码（Freeman）
2）游程编码：所谓游程是指按行的顺序连续且属性值相同的若干栅格。
游程长度的记录方式有两种记录每个游程起（迄）列号
① 记录每个游程像元数

A
A
B
B
B
A
C
C
C
A
D
C
C
A
A
D
D
C
A
A
D
D
A
A
A

②记录每个游程像元数5, 5
2, AB
1, A3, C
1, AD
1, C2, A
3）块式编码：块式编码是将游程扩大到两维情况，把多边形范围划分成若干具

有同一属性的正方形，然后对各个正方形进行编码。 块式编码的数据结构由初始位置（行列号）、半径和属性代码组成。

1,
2,
M；
1,
3,
1,
R；
1,
1,
M；
1,
5,
1,
M；
1,
6,
M；
1,
7,
2,
M

3,
2,
R；
2,
5,
1,
M；
2,
1,
R

1,
1,
M；
3,
2,
1,
R；
3,
3,
R；
3,
8,
1,
M

1,
1,
M；
4,
2,
3,
R;

8,
1,
M

1,
1,
M：
5,
8,
1,
M

3）四叉树编码：四叉树又称四元树或四分树，是最有效的栅格数据压缩编码方
法之一。
四分树将整个图像区域逐步分解为一系列方形区域，且每一个方形区域具有单一的属性。最小区域为一个象元。
2 3 4 5 6 7 8
1
M M
M M
R
M
M
M
M M
M M
2
R
R
M
R
3
M
R
R R
R R
R R
R R
R
M
4
M
R
R
M
5
M
R
R R
R R
R R
R R
R
M
6
M
R
R
M
7
M M
M M
R
R
R
R
R
M
8
M
R
R
M
M
M
四叉树编码方法
记录每个叶子结点的地址和属性NW (0)
SW (2)200 201 202 203 230 231 232 233
NE (1)
SE (3)

7. 隔点取样法实例:
ttdefine Max 100-typedef struct
Ei{int x;int y;}Pnt;
Pnt arr[Max];Pnt arr2[Max];
int num=0; int num2=0; //定义俩数组 int n;void Ccompress2Dlg::OnBnClickedCompress()
{| // TODO:在此添加控件通知处理程序代码
CDC *pDC=GetDC();
//Invalidate();
//UpdateWindow();
UpdateData(TRUE);
for(int i=l;i<=num;i++)(if (i%n—1)
(num2++；arr2[num2]. x=arr[i]. x;
arr2[num2]. v=arr[i]・ v;})
if (num%n!=l)
( num2++;
arr2[num2]. x=arr[num]. x;
arr2[num2]. y=arr[num], y;}
for(int j=2;j<=num2;j++)
( CDC *pDC=GetDC();pDC->El 1 ipse(arr2[ j]. x-5, arr2[j]. y-5, arr2[j]. x+5, arr2[j]. y+5);
pDC->MoveTo (arr2 [ j-1 ]. x, arr2[ j-1]. y); pDC->LineTo(arr2[j]. x, arr2[j]・ y);}void Ccompress2Dlg::OnLButtonDown(UINT nFlags, CPoint point)
// TODO:在此添加消息处理程序代码和/或调用默认值
CDC *pDC=GetDC():
pDC->Rectangle(point, x-2, point, y-2, point, x+2, point, y+2); num++;
arr[num]. x=point. x;
arr[num]. y=point. y;
if(num>l)
(pDC->MoveTo(arr[num-1]. x, arr[num-1], y); pDC->LineTo(arr[num]. x, arr[num], y);}
CDialogEx::OnLButtonDown(nFlags, point);
空间数据内插算法1 .空间数据内插的定义：根据已知的空间数据估计(预测)未知空间的数据值。
2. 空间数据内插目标：
① 缺值估计：估计某一点缺失的观测数据，以提高数据密度。
② 内插等值线：以等值线的形式直观地显示数据的空间分布。
③ 数据网格化。把无规则分布的空间数据内插为规则分布的空间数据集，如规则矩形格网、三角网等。
3. 空间内插法的种类：儿何方法、统计方法、空间统计方法、函数方法、随机模拟方法、物理模型模拟方法和综合方法。
4. 优缺点比较：每一种方法均有其适用范围、算法和优缺点，因此，没有绝对最优的空间内插方法。
5. 如何选择：对数据进行空间探索分析，根据数据的特点，选择最优方法；同时，应对内插结果进行严格的检验。
6空间数据内插的分类依据：
① 确定或随机；点与面；
② 全局或局部等标准分类；内插方法的基本假设和数学本质。
3. 反距离权重插值算法：是一种局部插值算法，它假设未知值的点受较近控制点 的影响比较远控制点的影响更大。
反距离权重方法的通用方程是：
20
式中，Z0为点0的估计值；Z,为控制点，的z 值；，•为控制点i与点0间的趾离；s为在估算中 用到的控制点的数目；K为指定的慕。
部插值算法。
5反距离权重插值实例:
4. 双线性插值算法：是一种数字图像处理、DEM数据处理等方面使用较多的局
原理：如图8.5所示，设犬0, 0) = Z|, /(I, 0)=Z2, /(0, 1) = Z3, /(I, 1) = Z4,求f(x,y)点的值,其中知，e [0, l]o 将f(0, 0)、/(I, 0)、f(0, 1)、/(1, 1)代入双线 性内插方程：
J(x,y) = or + by + cxy + d
求出各参数小b、c、d的值，再将代入，解得 TUy)。
P X Q<(),则P在Q的顺逆针方向；
PX Q>0,则PQ共线，但可能同向也可能反向。
6、判断线段的拐向：折线段的拐向判断方法，可以直接由矢量叉积的性质推 出，对于有公共端点的线段pOpl和P1P2,通过计算(p2-p0) X(Pl-pO)的符 号便可以给出折线段的拐向。
pO
基(p2・p0) X(P1-p0)>0, 则 P0P1
在P1点拐向右侧后得到
P1P2
基(p2・p0) X(P1.pO)vO,则 POP1
在P1点拐向左侧后得到P1P2
po
基(p2-p0) X(P1-p0)=0,
则P0P1P2三点共线
理解矢量的概念通过矢量差积的方法就可以判断的拐向了。
7. 判断点是否在线段上：设点为Q,线段为Pl P2： (Q-Pl)X(P2-Pl)=O且Q在以Pl, P2为对角顶点的矩形内。前者抱走点在直线上，后者保 证点不在线段延长线或反向延长线上。
8、判断两线段是否相交(算法一)：
快速排斥实验：设以线段P1P2为对角线的矩形为R,设以线段Q1Q2为对角的矩形为T,如果R和T不相交，显然两线段不会相交
#include<math. h>
#define MAX 100 etypedef struct s {int x, y, z;} Pnt;
Pnt arr[MAX];
int num=0;-void CinterpolationDlg::OnLButtonDown(UINT nFlags, CPoint point)
{
// TODO:在此添加消息处理程序代码和/或调用默认值
CDC *pDC=GetDC();
pDC->El1 ipse(point, x-3, point, y-3, point, x+3, point, y+3);
num++;
arr[num]. x=point. x;
arr[num], y=point, y;
UpdateData(TRUE);
arr [num]. z=IDWy ； // IDWy就是IDWz,纯属手误
CString str;
str. Formatarr[num], z); pDC->TextOutA(arr[num]. x-30, arr[num], y-30, str);
CDialogEx::OnLButtonDown(nFlags, point);
J-void CinterpolationDlg::OnBnClickedButtonIDW()
(
// TODO:在此添加控件通知处理程序代码
double nAtor=0, dAtor=0;
double dis=0,Z;
CString str;
for(int i=l;i<=num;i++)
(dis=sqrtf((arr[i]. x-X)*(arr[i]. x-X) + (arr[i]. y-Y)*(arr[i]. y-Y)); str. Formatdis); nAtor +=(arr[i]. z/dis);
dAtor +=(1. 0/dis);
I }
Z=nAtor/dAtor;
str. FormatZ);
CDC *pDC二GetDCO ;
pDC->TextOutA(X,Y,str);
TIN、DEM、DAT数字高程模型概念与理解：高程常常用来描述地形表面的起伏形态，传统的高 程模型是等高线，其数学意义是定义在二维地理空间上的连续曲面函数，当此高 程模型用计算机来表达时，称为数字高程模型。
1. 数字高程模型：是通过有限的地形高程数据实现对地形曲面的数字化模拟或者 说是地形表面形态的数字化表示，英文为Digital Elevation Model,简称DEM。
2. 理解DEM和DTM：由于高程数据常常采用绝对高程或海拔（即从大地水准面起算的高 度），DEM也常常称为DTMo要说明的是由于“Terrain”一词的含义比较广泛，不同专业背 景对“Terrain”的理解也不一样，DTM趋向于表达比DEM更为广泛的内容，详见后文的分析。
表2数字地面模型有关术语
术语
全称
特点与含义
DEM
Digital Elevation Model
以绝对高程或海拔表示的地形模型
DHM
Digital Height Model
以任意高程表示的地形模型，包括绝对高 程和相对高程，为德国所使用
DGM
Digital Ground Model
具有连续变化特征的地表实体模型，为英 国所使用
Digital Geomorphology Model
除高程外的其他地貌形态模型，如坡度、 坡向等
DTM
Digital Terrain Model
泛指地形表面自然、人文、社会景观模型,
DTED
Digital Terrain Elevation Model
为美国国防制图局所使用的地形模型，强 调模型的格网结构特征c
TIN和规则DEM的区别：不规则三角网数字高程模型由连续的三角面组成，三角形的 形状、大小取决于不规则分布的点的位置和密度。地形变化越简单，采样点就越少，则单元 格就越大；反之地形变化比较复杂，数据点分布比较密集，格网单元就越小。
因此TIN与规则格网DEM显著不同之处在于TIN模型不需要维护模型的结构规则性，不但 能灵活地随地形的复杂程度而改变格网单元大小，避免平坦地形的数据冗余，而且又能按地 形特征点线如山脊点、山谷线、地形变化线等表示地形特征。
规则格网DEM
不规则三角网TIN
优点
优点
•简单的数据存储结构；
•与遥感影像数据的复合 性；
•6好的表面分析功能
•较少的点可获取较高的 精度・
•可隽分辨率；
•良好的拓扑结构
缺点
•i+W效率较低；
•数据冗余；
•格网结构规则
缺点
•i®分析能力较差；
•构建比较费时；
•算法设计比较复杂
5.DEM数据结构:
规则格网DEM数据结构不规则三角形DEM数据结构
6. 规则格网数据：由于DEM的边界范围一般是规则矩形，而实际地形范围却是 不规则的,还应考虑不在研究区域内的DEM高程值的表示方法（无效区域数据）, 一般是给出一个特殊的常数值，如-9999等。规则格网DEM的数据文件一般包 含用对DEM数据进行说明的数据头和DEM数据体两部分。
1）数据头：一般包括定义DEM西南角起点坐标、坐标类型、格网间距、行列 数、最低高程以及高程放大系数等内容；2）数据体：按行或列分布记录的高程数字阵列。

例
我15

25
敏
酮角格咐利蠕网
12345.0
B 酗角格怫无冷蠕处
54321.0
'、格网幄
10
里融幅靴
*9999

12,14,15,咛 6
£
•••
n 蚌倾的DEM蹴件
咖观・"3

困术
TIN：在TIN模型中，基本的结构元素有三角形顶点、边和面。它们之间存在 着点与线、点与面、线与面、面与面等拓扑关系。理论上，通过组成三角形的三 顶点可完整地表达三角形的构成以及三角形顶点、三角形边、三角形之间的拓扑 关系（下图），这种结构只需要两个文件，即三角形顶点坐标文件和组成三角形三 顶点（通常用点在坐标文件中的序号表示）文件。这种结构虽然简单，三角形结 构元素的拓扑关系却是隐含的，不利于TIN模型的检索与应用。因此，围绕三角 形的拓扑关系描述而产生了多种TIN的数据结构。
坐标表三角形表序
号
属
性
X
y
Z
1

2

3

4

5

6

序
号
属
性
X
y
Z
1

2

3

4

5

6

A
顶 点1
顶
点2
顶
点3
1
1
6
2
2
2
6
3
3
3
6
4
4
4
6
5
5
5
6
1

基本铤表结构
图TIN模型的基本链表结构TIN模型的面结构最大特点是：由于存储了三角形之间的邻接关系，TIN内插、检 索、等高线提取、显示以及局部结构分析都比较方便，不足之处是：存储量较大， 而且在TIN的编辑中要随时维护这种关系。
7. DEM数据获取：建立DEM的第一步是获取地形数据。DEM的数据源和数据获 取方式对于DEM的最终质量至关重要。DEM原始数据主要是高程和平面位置数 据，在可能条件下还应包括各种地形结构线如山脊线、山谷线、断裂线等。另外， DEM应用目的、数据采集效率和成本、技术熟练程度也影响着DEM数据采集的 方法和策略。
/*目前DEM的数据主要来源于地形图、摄影测量与遥感影像数据、地面测量、 既有DEM数据等。*/坡度：
(1) 坡度是地表形态最为重要的因子，通过坡度可以完整地形成地形曲面(Evans,1972； Strahler,1956)；坡度是地形曲面函数一阶微分的函数，表达了高程随距离变化的比率(坡 度定义为地面一点的切平面与水平面之间的夹角)，而坡度的变率是地形曲 面的二阶微分，进一步刻画了坡度的变化，从而反映地形的复杂程度；
(2) 大量的研究表明，区域DEM高程精度与平均坡度值之间存在强相关，通过 模型的平均坡度可预测DEM的精度(Ackermann,1979; Ley, 1986)；坡度通过相互垂直的两个坐标轴方向的高程变化表达地形曲面局部单元的 倾斜程度，也就是通过地形表面的凸面和凹面来描述地形表面特性，即地表 的陡峭方向和大小。
8. TIN数据的建立：基于不规则三角网的数字高程模型(Based on TriangulatedIrregular Network DEM,简写为 Based on TIN DEM,俗称 TIN)就是用一系列 互不交叉、互不重叠的连接在一起的三角形来表示地形表面。TIN是DEM的 又一个主要数据模型，TIN的特点在其字而意思中表露无遗。
11. TIN的三角剖分准则：TIN的三角剖分准则是指TIN中三角形的形成法则，它决定 着三角形的几何形状和TIN的质量。目前在GIS、计算几何和计算机图形学邻域常用的 三角剖分准则有以下儿种
(1) 空外接圆准则：在TIN中，过每个三角形的外接圆均不包含点集的其余任 何点，如图A所示；最大最小角准则:’在两相邻三角形形成的凸四边形中，这两三角形中的最 小内如一定大于交换凸四边形对角线后所形成的两三角形的最小内角，如图
B所示；最短距离和准则：图C,最短距离和就是指一点到基边两端的距离和为最 小；
(2) 张角最大准则：图D, —点到基边的张角为最大；面积比准则：图E,三角形内切圆面积与三角形面积或三角形面积与周长 平方之比最小；
(3) 对角线准则：图F,两三角形组成的凸四边形的两条对角线之比。超过给 定限定值时对三角形进行优化。

理论上可以证明：张角最大准则、空外接圆准则及最大最小角准则是等价的，其 余的则不然。
三角形剖分准则是建立三角形网络的基本原则，应用不同的准则将会得到不 同的三角形网络。一般而言，应尽量保持三角网的唯一性，即在同一准则下由不 同的位置开始建立三角形网络，其最终的形状和结构应是相同的，在这-点上, 张伯最大准则、空外接圆准则及最大最小们准则可以做到。对角线准则含有主观 因素，现今使用已不多。
通常将在空外接圆准则、最大最小角准则下进行三角剖分称为Delaunay 三角剖分，简称为DT,同时空外接圆和最大最小角也是Delaunay三角网的两个 基本性质。DT三角剖分是目前应用最为广泛的三角剖分方法，其特性是可最大 限度避免狭长三角形的出现以及不管从何处开始构网都能保持三角形网络的唯 一性，这一点在实际应用中相当重要。实际上，在任何三角剖分准则下得到的 TIN,只要用LOP法则（局部优化过程,local optimal procedure , LOP）对其进 行优化处理，就能得到唯一的DT三角网络。LOP法则是Lawson在1977年提出 的，其基本思想是运用DT三角网的空外接圆性质对由两个有公共边的三角形组 成的四边形进行判断。如果其中一个三角形的外接圆中含有第四个顶点，则交换 四边形的对角线。

无约束散点域的三角剖分算法与实现：
•分割合并算法*三角法生长算法
★逐点插入算法@1*分割合并算法：分割合并算法(divide and conquer delaunay triangulation algorithm)的思想最早是由Shamos和Hoey在1975年提出的，并将其应用于 V-图的构成(V-图是Vorinoi图的简称，是DT三角网的对偶图，为DT三角网 中相邻三角形边垂直平分线交点的连线所形成的多边形，有关V-图的定义、性 质和分割算法参见计算几何方面的书籍)。Lewis和Robinson于1978年将该方 法用来进行DT三角网的剖分，随后Lee和Schachler、Dwyer等相继对Lewis 和Robinson的算法进行了优化和改进，其中Lee和Schachter于1980年的算法 适合于无约束数据域的三角剖分，而Dwyer于1987年的算法则考虑了带约束条 件的LOP优化策略，因而能处理带约束条件的数据。
分割合并算法的思想很简单，就是将复杂问题简单化，首先将数据点分割成 易于进行三角剖分的子集，如一个子集中包括三个、四个点，然后对每个子集进 行三角剖分，并用LOP算法保证三角剖分为DT三角网。当每个子集剖分完成 后，对每个子集的三角剖分进行合并，形成最终的整体三角网。不同的实现方法 可有不同的点集划分方法、子三角网生成方法及合并方法等。
分割合并算法的基本步骤为：
第一步，把数据集以横坐标为主、纵坐标为辅按升序进行排序;
第二步，如果数据集中的数据个数大于给定的阈值，则把数据域划分为个数近似 相等的左右两个子集，并对每一子集做如下的工作，①计算每一子集的凸壳；② 以凸壳为数据边界，对每一数据子集进行三角剖分，并用LOP进行优化，使之 成为DT三角剖分；③找出连接左右子集两个凸壳的底线和顶线；④由底线到顶 线，合并两个子三角网；第三步：如果数据集中的数据个数小于给定的阈值，则直接输出三角剖分结果；
A= ♦制 B=
X
设左右凸壳分别为Z和夫，N和召分 别是Z和夫上的点，A. 8满足如下 条件：
Az AX=max{X[}底线查找：从N8有向线段开始， 对于夫中点，如果沿逆时针且与8 相邻的匕点位于43的右侧，则J5=F； 在新的方向上，如果顺时针且 与N相邻的X点位于48的右侧，则 A=X.直到，和人中没有位于
43线段右侧的点为止，4月为连接/ 和&的底线。
顶线查找：从义8有向线段开始， 对于夫中点，如果顺时针且与&相 邻的匕点位于幽的左侧，则8=1; 在新的方向上，如果逆时针且 与义相邻的X点位于48的左侧，则 A=X,直到£和夫中没有位于43线段左侧的点为止，48为连接E 和&的上线。
子三角网合并：合并的方式是同 层优先，从下至上的递归方式进 行（这是分割合并算法中“合并 一词的由来）。合并时先找出两 个相邻子三角网凸壳在上下（或 左右）的公共切线，这些公共切 线将是最终三角网的一部分。上 下公切线查找完后，即可从连接 两子三角网的底线开始，在两子 三角网中寻找与底线组成 Delaunay三角形的第三点，选 其中外接圆半径小的一个插入到 最终的三角网中。新生成的连接 左右两个子三角网的边成为新的 底线，逐步上推到顶线结束，如 图所示。
在第一步中，主要工作是对数据点进行排序，目的是使 子三角网不相互重叠和交叉。一般是以横坐标为主、纵 坐标为辅按升序进行排序，即数据点之间满足如下的条 件：
（也况）＜ 不等式成立的条件是
xt< x.+1 且 < z+i
水平线
循环删除非凸顶点％ Pt Pg，得到凸光顶点R・Pv
计算R和其余数据点/的连线与 水平线的夹角.并按夹伯进行排 序（央角相同.按距离排序）
将排序后的定点顺次连接成一个 多边形R. PiPio
排序的方法采用以递归方式进行的分割快速排序方法, 详见数据结构书籍的介瓦第二步是该算法 的主体，包括数 据集的连续分割、 凸壳生成、凸壳 三角剖分、子网 合并等内容，集 中体现了该算法 的基本思想，即 分割（数据点的 分割），合并
（子三角网的合 并）。
@2*三角网生长算法：顾名思义，三角网生长算法就是从一个“源”开始，逐步 形成覆盖整个数据区域的三角网。从生长过程角度，三角网生长算法分为收缩生 长算法和扩张生长算法两种。收缩生长算法是先形成整个数据域的数据边界（凸 壳），并以此作为源头，逐步缩小以形成整个三角网。收缩生长算法与数据点的 分布密度有关，实际情况往往比较复杂，例如当边界收缩后一个完整的区域可能 会分解成若干个相互独立的子区域，这就增加了三角剖分的复杂性扩张生长算法与收缩算法过程刚好相反，该算法是从一个三角形开始向外层层扩 展，最终形成覆盖整个区域的三角网，其主要步骤为：
第一步，生成初始三角形。在数据点中任取一点A （该点一般是位于数据点的几 何中心附近），并寻找距离此点最近的点8,两者相连形成初始基线AB,如图。 利用三角剖分准则（空外接圆准则或张角最大准则），在数据域中寻找第三点C, 从而形成第一个Delaunay三角形A8C。
第二步，扩展形成三角网。以初始三角形的三条边为初始基线，利用空外接圆准 则或张角最大准则，寻找能与该三条初始基线形成Delaunay三角形的。、£、F 点。
A
ACC
注意：（1）初始边界将整个数据域分成两个部分，搜寻第三点一般是在初始三角 形另一顶点的异侧范围进行。例如若初始三角形为ABC,初始边界为AB.第三 个顶点为C，能与三角形ABC共用48边的另一三角形他D,。点要位于福边的 另一侧，而不能与C同侧，判断方法为：
设直线两端点的坐标为』（”g）,3（喝力），另两点分别为C（xCfyc）fD（xD,yD'）可 通过下式判断点。刀在他的同异侧关系,
F（xty） = y-ax-b3 =。次£_小人）/（十位）.
在式中代入D坐标，则有
若F（Dc）与F（知,&）符号相同，则C、D位于AF的同一侧I
若F（xc，〉c）与尸（勺＞，&）符与相异，则D分别位于他的两侧：
若映，沁=。或夕（勺）,＞摄=0,则C成D与朋共线・跨立实验：如果两线段相交，则两线段必然相互跨立对方。若plp2跨立Q1Q2,
则矢量(P1-Q1)和(P2-Q2)位于矢量(Q2-Q1)的两侧，则(P1-Q1) X (Q2-Q1) X (P2-QI) X (Q2.Q1)〈O° 当(P1-Q1) X (Q2-Q1 ) 二0时，说明(Pl-Ql ) X (Q2-Q1)共线，但是因为已经通过快速 排斥实验，所以PI一定在线段Q1Q2上；同理(Q2-Q1) X (P2-Q1) =0说明P2 一定在线段Q1Q2上。
所以判断P1P2跨立Q1Q2的依据是：
(Pl-Ql) X (Q2-Q1) X (Q2-Q1) X (P2-Q1 30。
同理判断Q1Q2跨立P1P2的依据是
(Ql-Pl) X (P2-P1 ) X (P2-P1) X (Q2-P1) 30。
注意在进行“跨立判断”的时候是进行两次跨立判断
8. 判断矩形内是否包含点：只要判断该店的横坐标和纵坐标是否都夹在矩形的左右边和上下边之间。
9. 判断线段、折线、多边形是否在矩形中：因为矩形是个凸集，所以只
要判断所有端点都在矩形就行 了。
10. 判断矩形是否在矩形中：只要比较左右边界和上下边界就行了。
11. 判断圆是否在矩形中：圆心在矩形中且圆的半径小于或等于圆心到矩形四边的距离的最小值。
12. 判断点是否在多边形内:
1) 射线法：一条射线从点P开始，穿过多边形的边界的次数称为交点数目。当 交点数目是偶数时，点P在多边形外部；否则，为奇数时，在多边 形内部。
B〜Rz :多边形的顶点;①〜⑤,判断点；
⑥〜⑩:由判断点引出的射线
(a)位于预
侧(方向向下〉
(b)位于膜(c)位于滨点上下两
点
点下倒
(方向向上)
P.Q.#边形II点中与射线相交的康点美边
为避免三角形的交叉和重复，通过上述异侧点判别所选的第三点还要进行进 一步的认定。其方法是根据三角形任一条边最多只能与两个三角形所共用这个条 件，进行三角形的全等比较，即判断新三角形的三条边是否被前面所形成的三角 形共用过两次，如果是，则新三角形无效，否则为有效三角形。
@逐点插入算法逐点插入算法的过程非常简单，基本步骤为：
第一步，定义包含所有数据点的初始包容盒，并对该包容盒进行初始三角剖分； 第二步，对所有数据点进行循环，做如下工作(设当前处理的数据点为P),① 在已存在的三角网中，查找包含p的三角形t；②p与t的三个顶点相连，形成t 的三个初始三角剖分；③用LOP算法对初始三角剖分进行优化处理。
第三步，处理外围三角形。
12.规则格网DEM读取实例：
-void CDemView::OnDemDem()
(
// TODO:在此添加命令处理程序代码
CDC *PDC=GetDC();
int row=10, col=10;CString str;
int size=50;
//定义二维数组
int demtlOO][100];
char strrflOO]:
char *p;
FILE *in;
in=fopenCD:\\Upan\\GIS算法原理\\dem2. txt”, "r”);
fscanf(in, "%d %d\n", &row, &col);
for(int i=l;i〈=row；i++)fgets