双边界直线搜索法

格式：doc
大小：22.00 KB
文档页数：1

下载文档原格式

/ 1

双边界直线搜索法

栅格向矢量转换中最为困难的是边界线搜索、拓扑结构生成和多余点去除。

一种栅格数据库数据双边界直接搜索算法（Double Boundary Direct Finding，缩写为DBDF），较好地解决了上述问题。

双边界直接搜索算法的基本思想是通过边界提取，将左右多边形信息保存在边界点上，每条边界弧段由两个并行的边界链组成，分别记录该边界弧段的左右多边形编号。

边界线搜索采用2×2栅格窗口，在每个窗口内的四个栅格数据的模式可以唯一地确定下一个窗口的搜索方向和该弧段的拓扑关系，这一方法加快了搜索速度，拓扑关系也很容易建立。

具体步骤如下：（1）边界点和节点提取：采用2×2栅格阵列作为窗口顺序沿行、列方向对栅格图像全图扫描，如果窗口内四个栅格有且仅有两个不同的编号，则该四个栅格标识为边界点并保留各栅格所有多边形原编号；如果窗口内四个栅格有三个以上不同编号，则标识为节点（即不同边界弧段的交汇点），保证各栅格原多边形编号信息。

对于对角线上栅格两两相同的情况，由于造成了多边形的不连通，也作为节点处理P72。

（2）边界线搜索与左右多边形信息记录：边界线搜索是逐个弧段进行的，对每个弧段从一组已标识的四个节点开始，选定与之相邻的任意一组四个边界点和节点都必定属于某一窗口的四个标识点之一。

首先记录开始边界点组的两个多边形编号作为该弧段的左右多边形，下一点组的搜索方向则由前点组进入的搜索方向和该点的可能走向决定，每个边界点组只能有两个走向，一个是前点组进入的方向，另一个则可确定为将要搜索后续点组的方向。

边界点组只可能有两个走向，即下方和右方，如果该边界点组由其下方的一点组被搜索到，则其后续点组一定在其右方；反之，如果该点在其右方的点组之后被搜索到（即该弧段的左右多边形编号分别为b和a），对其后续点组的搜索应确定为下方，其它情况依次类推。

可见双边界结构可以唯一地确定搜索方向，从而大大地减少搜索时间，同时形成的矢量结构带有左右多边形编号信息，容易建立拓扑结构和与属性数据的联系，提高转换的效率。

二进制搜索算法中的边界情况处理方法

二进制搜索算法中的边界情况处理方法二进制搜索算法是一种高效的搜索算法，它通过将搜索范围逐步缩小一半的方式，快速定位目标元素的位置。

然而，在实际应用中，边界情况的处理是一个非常重要且复杂的问题。

本文将探讨二进制搜索算法中的边界情况处理方法。

一、二进制搜索算法简介二进制搜索算法，也称为二分搜索算法，是一种在有序数组中查找目标元素的常用算法。

它的基本思想是将数组分成两部分，通过比较目标元素与数组中间元素的大小关系，确定目标元素可能存在的范围，然后逐步缩小搜索范围，直到找到目标元素或确定目标元素不存在。

二、边界情况的处理在二进制搜索算法中，边界情况的处理是一个关键问题。

边界情况包括数组为空、数组只有一个元素、目标元素小于数组最小值、目标元素大于数组最大值等情况。

下面将分别讨论这些情况的处理方法。

1. 数组为空当数组为空时，显然无法进行搜索操作。

因此，在进行二进制搜索之前，需要先判断数组是否为空。

如果数组为空，则直接返回搜索失败的结果。

2. 数组只有一个元素当数组只有一个元素时，可以直接判断该元素是否等于目标元素。

如果相等，则返回该元素的位置；如果不相等，则返回搜索失败的结果。

3. 目标元素小于数组最小值当目标元素小于数组最小值时，由于数组是有序的，目标元素必然不存在于数组中。

因此，可以直接返回搜索失败的结果。

4. 目标元素大于数组最大值当目标元素大于数组最大值时，同样由于数组是有序的，目标元素必然不存在于数组中。

因此，可以直接返回搜索失败的结果。

5. 正常情况在处理完以上边界情况后，可以进行正常的二进制搜索操作。

首先，确定数组的中间位置，并将中间位置的元素与目标元素进行比较。

如果相等，则返回中间位置；如果目标元素小于中间位置的元素，则将搜索范围缩小为左半部分，否则将搜索范围缩小为右半部分。

然后，重复以上步骤，直到找到目标元素或确定目标元素不存在。

三、总结二进制搜索算法是一种高效的搜索算法，但在实际应用中，边界情况的处理是一个非常重要的问题。

线搜索方法

也有类似定理3.2的结论成立,把它的证明留给大家. Theorem 3.3 设f 是连续可微函数,αˆ有定义且有限, 则在[0, αˆ]中存在一区间(a, b),满足对任何αk ∈ (a, b), 强Wolfe-Powell条件均成立.
&
%
本科生优化方法课程讲义
'
3.2 下降方法的收敛性
&
大连理工大学 27
$
(c) Goldstein原则
Goldstein原则
步长αk 满足 (1 − ρ)αk∇f (xk)T dk ≤ f (xk + αkdk) − f (xk) ≤ ραk∇f (xk)T dk,
其中ρ ∈ (0, 1/2). 可以证明下述的定理:
Theorem 3.1 设f 是下有界的连续可微函数, dk满足∇f (xk)T dk < 0, 则必存在αk > 0满足Goldstein原则.
f (x∗ + ∆x) = f (x∗) +
1 2
∆xT
∇2f
(x∗
)∆x
+
o(
∆x
2).
则存在r1 ∈ (0, r]满足:对于∆x ∈ Br1 (0),
f (x∗
+
∆x)
≥
f (x∗)
+
1 4
λ∗
∆x
2,
即f 在Br1 (x∗)上满足二阶增长条件.
&
%
本科生优化方法课程讲义
'
大连理工大学 8
$
满足∇f (x∗) = 0的x∗ ∈ n被称为函数f 的稳定点. 在f 是凸函数的前提下, 任何稳定点都是全局极小点.
$

ACMer需要掌握的算法讲解

ACM主要算法介绍初期篇一、基本算法(1)枚举(poj1753, poj2965)(2)贪心(poj1328, poj2109, poj2586)(3)递归和分治法(4)递推(5)构造法(poj3295)(6)模拟法(poj1068, poj2632, poj1573, poj2993, poj2996)二、图算法(1)图的深度优先遍历和广度优先遍历(2)最短路径算法(dijkstra, bellman-ford, floyd, heap+dijkstra)(poj1860, poj3259, poj1062, poj2253, poj1125, poj2240)(3)最小生成树算法(prim, kruskal)(poj1789, poj2485, poj1258, poj3026)(4)拓扑排序(poj1094)(5)二分图的最大匹配(匈牙利算法)(poj3041, poj3020)(6)最大流的增广路算法(KM算法)(poj1459, poj3436)三、数据结构(1)串(poj1035, poj3080, poj1936)(2)排序(快排、归并排(与逆序数有关)、堆排)(poj2388, poj2299)(3)简单并查集的应用(4)哈希表和二分查找等高效查找法(数的Hash, 串的Hash)(poj3349, poj3274, POJ2151, poj1840, poj2002, poj2503)(5)哈夫曼树(poj3253)(6)堆(7)trie树(静态建树、动态建树)(poj2513)四、简单搜索(1)深度优先搜索(poj2488, poj3083, poj3009, poj1321, poj2251)(2)广度优先搜索(poj3278, poj1426, poj3126, poj3087, poj3414)(3)简单搜索技巧和剪枝(poj2531, poj1416, poj2676, 1129)五、动态规划(1)背包问题(poj1837, poj1276)(2)型如下表的简单DP(可参考lrj的书page149)：1.E[j]=opt{D+w(i,j)} (poj3267, poj1836, poj1260, poj2533)2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列)(poj3176, poj1080, poj1159)3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]} (最优二分检索树问题)六、数学(1)组合数学1.加法原理和乘法原理2.排列组合3.递推关系(poj3252, poj1850, poj1019, poj1942)(2)数论1.素数与整除问题2.进制位3.同余模运算(poj2635, poj3292, poj1845, poj2115)(3)计算方法1.二分法求解单调函数相关知识(poj3273, poj3258, poj1905, poj3122)七、计算几何学(1)几何公式(2)叉积和点积的运用(如线段相交的判定，点到线段的距离等)(poj2031, poj1039)(3)多边型的简单算法(求面积)和相关判定(点在多边型内，多边型是否相交)(poj1408, poj1584)(4)凸包(poj2187, poj1113)中级篇一、基本算法(1)C++的标准模版库的应用(poj3096, poj3007)(2)较为复杂的模拟题的训练(poj3393, poj1472, poj3371, poj1027,poj2706)二、图算法(1)差分约束系统的建立和求解(poj1201, poj2983)(2)最小费用最大流(poj2516, poj2195)(3)双连通分量(poj2942)(4)强连通分支及其缩点(poj2186)(5)图的割边和割点(poj3352)(6)最小割模型、网络流规约(poj3308)三、数据结构(1)线段树(poj2528, poj2828, poj2777, poj2886, poj2750)(2)静态二叉检索树(poj2482, poj2352)(3)树状树组(poj1195, poj3321)(4)RMQ(poj3264, poj3368)(5)并查集的高级应用(poj1703, 2492)(6)KMP算法(poj1961, poj2406)四、搜索(1)最优化剪枝和可行性剪枝(2)搜索的技巧和优化(poj3411, poj1724)(3)记忆化搜索(poj3373, poj1691)五、动态规划(1)较为复杂的动态规划(如动态规划解特别的施行商问题等)(poj1191, poj1054, poj3280, poj2029, poj2948, poj1925, poj3034)(2)记录状态的动态规划(poj3254, poj2411, poj1185)(3)树型动态规划(poj2057, poj1947, poj2486, poj3140)六、数学(1)组合数学1.容斥原理2.抽屉原理3.置换群与Polya定理(poj1286, poj2409, poj3270, poj1026)4.递推关系和母函数(2)数学1.高斯消元法(poj2947, poj1487, poj2065, poj1166, poj1222)2.概率问题(poj3071, poj3440)3.GCD、扩展的欧几里德(中国剩余定理)(poj3101)(3)计算方法1.0/1分数规划(poj2976)2.三分法求解单峰(单谷)的极值3.矩阵法(poj3150, poj3422, poj3070)4.迭代逼近(poj3301)(4)随机化算法(poj3318, poj2454)(5)杂题(poj1870, poj3296, poj3286, poj1095)七、计算几何学(1)坐标离散化(2)扫描线算法(例如求矩形的面积和周长，并常和线段树或堆一起使用)(poj1765, poj1177, poj1151, poj3277, poj2280, poj3004)(3)多边形的内核(半平面交)(poj3130, poj3335)(4)几何工具的综合应用(poj1819, poj1066, poj2043, poj3227, poj2165, poj3429)高级篇一、基本算法要求(1)代码快速写成，精简但不失风格(poj2525, poj1684, poj1421,poj1048, poj2050, poj3306)(2)保证正确性和高效性(poj3434)二、图算法(1)度限制最小生成树和第K最短路(poj1639)(2)最短路，最小生成树，二分图，最大流问题的相关理论(主要是模型建立和求解)(poj3155, poj2112, poj1966, poj3281, poj1087, poj2289, poj3216, poj2446)(3)最优比率生成树(poj2728)(4)最小树形图(poj3164)(5)次小生成树(6)无向图、有向图的最小环三、数据结构(1)trie图的建立和应用(poj2778)(2)LCA和RMQ问题(LCA(最近公共祖先问题)，有离线算法(并查集+dfs)和在线算法(RMQ+dfs))(poj1330)(3)双端队列和它的应用(维护一个单调的队列，常常在动态规划中起到优化状态转移的目的)(poj2823)(4)左偏树(可合并堆)(5)后缀树(非常有用的数据结构，也是赛区考题的热点)(poj3415,poj3294)四、搜索(1)较麻烦的搜索题目训练(poj1069, poj3322, poj1475, poj1924,poj2049, poj3426)(2)广搜的状态优化：利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法(poj1768, poj1184, poj1872, poj1324, poj2046, poj1482)(3)深搜的优化：尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法(poj3131, poj2870, poj2286)五、动态规划(1)需要用数据结构优化的动态规划(poj2754, poj3378, poj3017)(2)四边形不等式理论(3)较难的状态DP(poj3133)六、数学(1)组合数学1.MoBius反演(poj2888, poj2154)2.偏序关系理论(2)博奕论1.极大极小过程(poj3317, poj1085)2.Nim问题七、计算几何学(1)半平面求交(poj3384, poj2540)(2)可视图的建立(poj2966)(3)点集最小圆覆盖(4)对踵点(poj2079)八、综合题(poj3109, poj1478, poj1462, poj2729, poj2048, poj3336, poj3315, poj2148, poj1263)附录：POJ是“北京大学程序在线评测系统”（Peking University Online Judge）的缩写，是个提供编程题目的网站，兼容Pascal、C、C＋＋、Java、Fortran等多种语言。

第二章最优化方法——直线搜索

单谷函数的这一性质可用来将搜索区间无限缩小，以至求到极小点。
本章下面就介绍的直线搜索法，第一步就是要找一个初始搜索区间，下面就介绍一种有效的找初始搜索区间的方法。
算法1：（搜索区间的确定）已知目标函数 (t ) 。
〈1〉选择初始点t0和步长 h.
〈2〉比较(t0 )和(t0 h) 的值，转<3>，<4> 〈3〉若 (t0 ) (t0 ，h)比较 (t0)和(t0 ，h) 转 <5>，
这是~(t0 )的唯一极小点，可作为 (t)极小点t*的一个近但似~t 。中因要此计想算到二用阶导数~t 。t一0 般作来为说初计始算步二长阶h。导数比较困
难，而一阶导数即使较困难，也可用差分近似，因此，要想办法避免二阶导数的计算。
假若似设对。某(个t)的~t极，小使值得可~以(~t估) 计出e ，来则，将如为~t作为e ，t*即的一 (个t*近) e
若仍然有 a t0,b t1，则取 t1 0 t2 t1 t
（或将t 放大一倍，即取 t2 t1 2t ）若t2 0则以
t1, t2 作区间[a,b]；否则继续下去。
对于 t0 0 的情况，可类似于上面在 t0 左侧取点。
若t1<t3< t2,也可将搜索区间 t1, t2记为 t1, t3, t2
单谷函数的性质：
设 a,b是单谷函数极小点的一个搜索区间。在
(a,b)上任取两点t1，t2，使t1< t2,若(t1) (t2 ) 则a, t2
是 (t) 极小点的一个搜索区间；若(t1) (t2 ) ，则t1, b
(t0 (2k 1)h), k 1,2,... ，直到有某个m（≥1）使 (t 0(2m1 1)h) (t0 (2m 1)h) (t0 (2m1 1)h)

3、临界、极值问题

O V0
d
c
◆带电粒子在三角形磁场区域中的运动
例6．如图所示，在边长为2a的等边三角形△ABC内存在垂直纸面向里磁感应强度为B的匀强磁场，有一带电量为q、质量为m的粒子从距A点 3a 的D点垂直于AB方向进入磁场。若粒子能从AC间离开磁场，求粒子速率应满足什么条件及粒子从AC间什么范围内射出？
d
缩放圆：变化1：在上题中若电子的电量e，质量 m，磁感应强度B及宽度d已知，若要求电子不从右边界穿出，则初速度V0有什么要求？
e B v0
d
B
变化2：若初速度向下与边界成 α = 60 0，则初速度有什么要求？
变化3：若初速度向上与边界成 α = 60 0，则初速度有什么要求？
变式、在真空中宽ｄ的区域内有匀强磁场Ｂ，质量为ｍ，电量为e，速率为ｖ的电子从边界ＣＤ外侧垂直射入磁场，入射方向与ＣＤ夹角θ，为了使电子能从磁场的另一侧边界ＥＦ射出，ｖ应满足的条件是：B Ａ.v＞eBd/m（1+sinθ） C E Ｂ.v＞eBd/m（1+cosθ） v Ｃ.v＞ eBd/msinθ θ O Ｄ.v＜ eBd/mcosθ
例题、如图所示．长为L的水平极板间，有垂直纸面向内的匀强磁场，磁感强度为B，板间距离也为L，板不带电，现有质量为m，电量为q的带正电粒子(不计重力)，从左边极板间中点处垂直磁感线以速度 v水平射入磁场，欲使粒子不打在极板上，可采用的办法是： AB A．使粒子的速度v<BqL/4m； O2 B．使粒子的速度v>5BqL/4m； r2 C．使粒子的速度v>BqL/m； v D．使粒子速度BqL/4m<v<5BqL/4m。 r2
2R
M
2R
O
R

检测两物体相对位置的算法

检测两物体相对位置的算法
有很多算法可以用来检测两个物体的相对位置。

以下是一些常见的算法：
1. 边界框检测：这是最简单和最常见的方法。

对于两个物体，可以绘制出它们的边界框（bounding box），然后比较这些边界框的位置和重叠程度来确定它们的相对位置。

2. 轮廓匹配：通过计算两个物体的轮廓，可以比较轮廓的形状和重叠程度来确定它们的相对位置。

3. 特征匹配：通过提取两个物体的特征点（例如角点或SIFT 特征），可以将这些特征点进行匹配，并使用匹配的结果来确定物体的相对位置。

4. 深度相机：使用深度相机（例如Kinect）可以获取两个物体的三维坐标信息，从而确定它们的相对位置。

这种方法通常用于机器人导航和虚拟现实等应用。

5. 光流法：通过分析图像中的像素点随时间的变化，可以推测物体的运动轨迹，从而确定物体的相对位置。

这只是一小部分常见的算法，实际上还有很多其他算法和方法可以用来检测两个物体的相对位置，具体选择哪种算法取决于应用场景和需求。

地理信息系统复习资料

8、GIS中为什么要进行地图投影？GIS以地图方式显示地理信息，而地图是平面，地理信息则在地球椭球上，因此地图投影在GIS中不可缺少。

GIS数据库中地理数据以地理坐标存储时，则以地图为数据源的空间数据必须通过投影变换转换成地理坐标；而输出或显示时，则要将地理坐标表示的空间数据通过投影变换变换成指定投影的平面坐标。

GIS中，地理数据的显示可根据用户的需要而指定投影方式，但当所显示的地图与国家基本地图系列的比例尺一致时，一般采用国家基本系列地图所用的投影。

2.1 常规的地理空间信息的描述方法2.1.1 地图对地理空间的描述地图是现实世界的模型，它按照一定的比例，一定的投影原则，有选择地将复杂的三维现实世界的某些内容投影到二维平面媒介上，并用符号将这些内容要素表现出来。

空间对象一般按地形维数进行归类划分为：：点：零维；线：一维；面：二维；体：三维时间：通常以第四维表达，但目前GIS还很难处理时间属性。

空间对象的维数与比例尺是相关的点实体包括：有位置，无宽度和长度；抽象的点；线实体包括：有长度，但无宽度和高度；用来描述线状实体，通常在网络分析中使用较多；度量实体距离面实体：连续变化曲面：如地形起伏，整个曲面在空间上曲率变化连续。

不连续变化曲面，如土壤、森林、草原、土地利用等，属性变化发生在边界上，面的内部是同质的。

2.2 地理信息数字化描述方法隐式：由一系列定义了起点和终点的线及某种连接关系来描述。

——矢量数据结构。

显式：即栅格中的一系列像元。

这些像元都给予相应的编码值R或相同的颜色、符号、数字、灰度值来表示。

——栅格数据结构。

空间对象的描述要素编码：区别不同的实体，包括分类码和识别码。

分类码表示空间对象的类别，而识别码对每个空间对象进行标识，是唯一的。

位置：坐标形式给出空间对象的空间位置类型：空间对象所属的实体类型，或由那些实体组成行为：空间对象所具备的行为和功能属性：空间对象所对应的非几何信息说明：实体数据来源、精度等关系：与其他实体之间的关系空间对象的编码编码方法：层次分类编码多源分类编码编码原则编码的系统性和科学性编码的一致性编码的标准化和通用性编码的简捷性编码的可扩展性层次分类编码分类对象的从属和层次关系有明确的分类对象类别和严格的隶属关系多源分类编码按空间对象不同特性进行分类并进行编码代码之间没有隶属关系，反映对象特性具有较大的信息量，有利于空间分析编码步骤1、列出全部制图对象2、根据制图对象分类、分级原则和指标，将制图对象进行分类分级3、拟定分类代码系统4、设定代码及格式，设定代码使用的字符和数字、码位长度，码位分配等。

无权双向最短路径算法

无权双向最短路径算法
无权双向最短路径算法（Unweighted Bidirectional Shortest Path Algorithm）是用于在无权图（即每个边的权重都相同）中寻
找两个顶点之间的最短路径的算法。

该算法的基本思想是从两个目标顶点开始，分别使用广度优先搜索（BFS）向外扩展，直到两个搜索队列相遇或者达到某个
终止条件为止。

具体步骤如下：
1. 初始化两个搜索队列分别用于正向搜索和反向搜索，并将两个目标顶点分别加入两个队列。

2. 分别对两个队列进行广度优先搜索，即不断从队列中取出顶点，将其邻居顶点加入队列，并标记它们距离起始顶点的距离。

3. 在每一步搜索过程中，检查正向搜索队列和反向搜索队列的顶点是否相遇，如果相遇，则找到了最短路径。

4. 在每一步搜索过程中，检查正向搜索队列和反向搜索队列的顶点是否有距离起始顶点更短的路径，如果有，则更新路径。

5. 重复步骤2~4，直到两个搜索队列相遇或者达到某个终止条
件为止。

该算法的时间复杂度为O(V + E)，其中V是顶点数，E是边数。

由于是无权图，每个顶点的邻居数一般较小，因此该算法通常比Dijkstra算法（用于有权图的最短路径算法）更高效。

需要注意的是，无权双向最短路径算法仅适用于无权图，对于有权图，需要使用其他算法，如Dijkstra算法或A*算法。

精确线搜索方法

三点二次插值法：主程序： function[k,j,min]= f1(h,a,b,c,e) k=1; A=feval(h,a); B=feval(h,b); C=feval(h,c); while(k<=100) d=((b^2-c^2)*A+(c^2-a^2)*B+(a^2-b^2)*C)/(2*((b-c)*A+(c-a)*B+(a-b)*C)); D=feval(h,d); if d>b if D<=B A=B;a=b;b=d;B=D; else
a(k+1)=a(k);b(k+1)=u(k);u(k+1)=r(k);r(k+1)=a(k+1)+0.382*(b(k+1)-a(k+1)); end k=k+1; end x=(b(k)+a(k))/2; min=feval(fun,x);%函数的极值目标函数 1： function y= fun(t) y=-sin(t)^6*tan(1-t)*exp(30*t); 目标函数 2： y=exp(-t)+exp(t);
分析：根据精确线搜索的换进分割法和逐次插值逼近法编写的 matlab 程序，比较发现，精度 e 越小（即接近于 0），越接近目标值，迭代次数越大；当精度 e 一定时，最优值和迭代次数不再变化，结果说明了三点二次插值法和 0.618 法的有效性，同时也表明了我们编写的程序的正确性
五、实验结果及分析
三点二次插值法： Max y=sin(x)^6*tan(1-x)*exp(30*x); [k,j,min]= f1('h',0,0.4,1,0.001) k =44 j =0.9707 min =4.1086e+010 Min y=1-t*exp(-t^2)； [k,j,min]= f1('h',0,0.5,1,0.001) k = 13 j =0.7071 min = 0.5711

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

栅格向矢量转换中最为困难的是边界线搜索、拓扑结构生成和多余点去除。

一种栅格数据库数据双边界直接搜索算法（Double Boundary Direct Finding，缩写为DBDF），较好地解决了上述问题。

具体步骤如下：
（1）边界点和节点提取：采用2×2栅格阵列作为窗口顺序沿行、列方向对栅格图像全图扫描，如果窗口内四个栅格有且仅有两个不同的编号，则该四个栅格标识为边界点并保留各栅格所有多边形原编号；如果窗口内四个栅格有三个以上不同编号，则标识为节点（即不同边界弧段的交汇点），保证各栅格原多边形编号信息。

对于对角线上栅格两两相同的情况，由于造成了多边形的不连通，也作为节点处理P72。

（3）多余点去除：多余点的去除基于如下思想：在一个边界弧段上连续的三个点，如果在一定程度上可以认为在一条直线上（满足直线方程），则三个点中间一点可以被认为是多余的，予以去除。

即满足：
由于在算法上的实现，要尽可能避免出现除零情形，可以转化为以下形式：
（x1-x2）（y1-y3）=（x1-x3）（y1-y2）
或
（x1-x3）（y2-y3）=（x2-x3）（y1-y3）
其中（x1，y1），（x2，y2），（x3，y3）为某精度下边界弧段上连续三点的坐标，则（x2，y2）为多余点，可予以去除。

多余点是由于栅格向矢量转换时逐点搜索边界造成的（当边界为或近似为一直线时），这一算法可大量去除多余点，减少数据冗余。

双边界直线搜索法

合集下载