这是本节的多页打印视图。 点击此处打印.

返回本页常规视图.

几何算法

描述

一整套的几何算法, 所以, 应该有一个几何算法的系统只是, 有次第地进行学习

关键词条

渐进快速的精确算法

假设

一切的问题都可以被几何的语言描述的话

一些常见的问题的抽象

  • 半平面区域技术问题
  • 运动规划问题

1 - 划分树

2 -

2.1 -

2.2 - 装配问题(Casting Problem)

描述

3 - 多层划分树

4 - 平面凸包的求解

描述

针对 平面点集凸包的构造问题 的众多解决方法

  • Graham scan
  • Preparata 和 Hong 提出的分治算法
  • 递增式算法
  • dynamic convex hull
  • Jarvis 提出的 包扎技术(wrapping) — Jarvis march

对点的集合进行的 “字典序” 排列

有一种 P 进制数的概念, 其中还有 左进制数, 右进制数

SlowConvexHull

Input: 平面点集 P

Output: 描述凸包的点集 l

  1. \( E \gets \emptyset \)
  2. \( \textbf{for} (每一有序对(p,q) \in P \times P, p \ne q) \)
  3. \( \quad \textbf{do} \ valid \gets true\)
  4. \( \quad \quad \textbf{for} (除 p 和 q 之外的所有点 r \in P)\)
  5. \( \quad \quad \quad \textbf{do \ if (r位于p和q所确定的有向直线的左侧)}\)
  6. \( \quad \quad \quad \quad \textbf{then} \ valid \gets fale\)
  7. \( \quad \quad \quad \quad \quad \textbf{if} \ (valid) \ \textbf{then} \ 将所有有向边 \overline{pq} 加入到 E \)
  8. \( 根据集合E中的各边, 找出CH(P)的所有顶点, 并按照顺时针方向将它们组织为列表 l\)

ConvexHull

Input: 平面点集 P

Output: 描述凸包的点集 l

  1. 根据 \(x-\) 坐标, 对所有的点进行排序, 得到序列 \(p_1, \dots, p_n\)
  2. \(在 \ l_{upper} \ 中加入 p_1 和 p_2 (p_1在前)\)
  3. \(\textbf{for} ( i \gets 3 \ \textbf{to} \ n\))
  4. \( \quad \textbf{do} \ 在 \ l_{upper} \ 中加入 \ p_i \)
  5. \( \quad \quad \textbf{while} \ ( l_{upper} \ 中之至少还有三个点, 而且最末尾的三个点所构成的不是一个右拐) \)
  6. \( \quad \quad \quad \textbf{do} \ 将倒数第二个顶点从 \ l_{upper} \ 中删去 \)
  7. \( 在 \ l_{lower} \ 中加入 \ p_{n} 和 p_{n-1} (p_{n} \ 在前) \)
  8. \( \textbf{for}( i \gets {n-2} \ \textbf{downto} \ 1) \)
  9. \( \quad \textbf{do} \ 在 l_{lower} \ 中加入 \ p_i \)
  10. \( \quad \quad \textbf{while}(l_{lower} \ 中之至少还有三个点, 而且最末尾的三个点所构成的不是一个右拐) \)
  11. \( \quad \quad \quad \textbf{do} 将倒数第二个顶点从 \ l_{lower} \ 中删去 \)
  12. \( 将第一个和最后一个点从 \ l_{lower} \ 中删去(以免在上凸包与下凸包联结之后, 出现重复顶点) \)
  13. \( 将 \ l_{lower} \ 联结到 \ l_{upper} \ 后面(将由此得到列表记为 \ l) \)
  14. \( \textbf{return}(l) \)

Pseudo Code

算法: SLOWCONVEXHULL(P)

Input: 平面点集 P

Output: 由\(CH(P)\)的顶点沿顺时针方向排列成的队列 \(l\)

$$\displaystyle \begin{aligned} E \gets \emptyset \\ for(每一有序对(p, q) \in P \times P, p \ne q) \end{aligned}$$

5 - 退化和鲁棒性

描述

退化和鲁棒性, 是为了构建完备的几何算法而需要具备的敏感性

所谓退化, 其关联计算机处理浮点数计算过程中的舍入误差而使得几何计算的结果在进入下一次计算时候带来的可能的影响

鲁棒性, 多是因为在构建算法之初, 为了平衡(问题的几何描述的逻辑性而做出的)一些一般性假设与实际问题上的偏差, 对算法的稳定性的度量.

因为实际问题在某个算法的应用场景是有界的, 所以提出一种上帝几何算法的可能, 是有限的.

6 - 线性规划-铸模制造

Terms

  • 二维小平面(facet)
  • 顶面(top face): 有且仅有一个小平面
  • 普通面(ordinary facet)
  • 半平面(): 在平面上位于某条直线左(或右)侧的部分
  • 可铸造的(castable)
  • 外法矢(outward normal)

Theories

4.1 沿某个方向\(\vec{d}\)通过一次平移, 多面体\(P\)能够从其铸模中抽取出来, 当且仅当相对于\(P\)的每一张普通面的外法矢, 移动方向\(\vec{d}\)v 与之所呈的角度都至少为 90度

由4.1 可推出: 若可以通过多次小幅度的平移将 p 抽取出, 则必然可以仅通过一次平移就将其抽取出来(向量的合成)

IntersectHalfPlanes(H)

Input: 由平面上 n 张半平面组成的一个集合 H

Output: 凸多边形区域 C

  1. \(\)
  2. \(\)
  3. \(\)
  4. \(\)
  5. \(\)
  6. \(\)

7 - 专题图的叠合

Description

专题图的叠合（也称为地图的叠加或图层叠加）是地理信息系统（GIS）中一种常用的技术, 地理信息系统将（不同类型的）信息划分为若干层（layer）, 每一层都是一幅专题图（thematic map）(存放某一特定类型的信息), 用于将多种地理数据的图层组合在一起, 以分析、比较和可视化不同类型的数据。通过叠合，可以发现不同数据集之间的关系、趋势和模式。这种技术广泛应用于城市规划、环境管理、资源评估等领域。

7.1 - 线段求交

描述

给定由平面上 \(n\) 条闭线段构成的一个集合 \(S\), 求出 \(S\) 中个线段之间 的所有交点. 其中闭线段是指不同线段端点的重合也将被视为交点

“输出敏感"的算法

我们所希望得到的算法，其运行时间不仅取决于输入中线段的数目，还取决于（实际的）交 点数目。这样的算法，被称为“输出敏感的”算法（output-sensitive algorithm）⎯⎯ 也就 是说，这种算法的运行时间对（实际）输出的大小很敏感。也可以称这样一个算法是“交点 敏感的”（intersection-sensitive）⎯⎯ 因为，输出的大小就是由交点的数目决定的

引理 2.1

设两条非水平的线段 \(si\) 和 \(sj\) 只相交于其内部的一点 \(p\)，而且，任 何第三条线段都不经过 \(p\)。则在（扫描线到达）高于 \(p\)$ 的某个事件点处（ 时），\(si\) 和 \(sj\) 必然会彼此紧邻，并因此接受相交测试（于是对应的交点 将被发现）。

几何分析

  • 将一条线段在y轴上的正交投影, 定义为该线段的 y-区间, 任何两条线段, 只要其y-区间没有重叠部分, 则一定不会相交

事件队列(Event Queue)

在该算法中的队列是一个有序队列, 且在该队列中的查找是基 于平衡二分查找树(balanced binary search tree).

  • Enqueue: 来存放（当前已被检测出来，但尚未发生的）事件。
  • Dequeue: 把即将发生的下一事件从 Q 中删除掉，并将它返回（给主程序），以便对它进 行处理。
  • Insert:
  • Sort:

状态结构(Status Structure)

状态(是与当前扫描线相交的所有线段构成的有序序列), 通过一个状态结构（status structure），可以访问某一给定线段\(s\)的（左、右）邻居.

在插入一个线段\(s\)之后, 就可以立即进行相应的相交测试

这个状态结构式动态的, 当有某条线段开始（或不再）与扫描线相交，就应将它插入到状 态结构中（或从状态结构中删去）

在任一时刻(在某一事件点), 状态结构中的所有线段之间具有一个定义明确的次序(与当前 扫描线相交的每条线段，都按照其次序，)，因此可以使用一棵平衡二分查找树来实现状 态结构

平面扫描线算法(plane sweep algorithm)

  • 扫描线(sweep line)
  • 扫描线的状态(status): 当前扫描线相交的所有线段构成的集合
  • 事件点(event point): 扫描线的状态进行更新

只有在扫描线触及某个事件点的时候，算法才会进行实质的处理⎯⎯更新扫描线的状态，并进行一些相交测试

算法: \(FINDINTERSECTIONS(S)\)

Input：平面线段集 S

Output: S 中各线段之间的所有交点（以及穿过各交点的线段的信息）

  1. 初始化一个空的事件队列 \(Q\), 然后，将所有线段的（上、下）端点插入 \(Q\) 中；对于上端点，还要记录其对应的线段
  2. 初始化一个空的状态结构 \(T\)
  3. \(\textbf{while} (Q 非空)\)
  4. \(\quad \textbf{do} 找出 Q 中的下一事件点 p，将其删除\)
  5. \( \quad \quad HANDLEEVENTPOINT(p)\)

事件的处理方法

  • 若是线段的端点，则需要在状态结构 T 中插入或删除线段
  • 若是交点，则需要交换(对应的)两条线段的次序
  • 在事件发生后，对每一对新近成为邻居的线段, 都要进行相交测试

算法: \(HANDLEEVENTPOINT(p)\)

  1. \(令 U(p) 为所有以 p 为上端点的线段构成的集合; \ 这些线段都与事件点 p 存放 在一起 (若是水平线段，则以其左端点做为上端点)\)
  2. \(在 T 中找出包含 p 的所有线段 (\textbf{在 T 中，这些线段是(依次)相邻的})在 所找出的线段中 将那些以 p 为下端点的线段组成集合 L(p) 将那些在内部包含 p 的线 段组成集合 C(p)\)
  3. \(\textbf{if}(L(p) \cup U(p) \cup C(p) 包含不止一条线段)\)
  4. \(\quad \textbf{then} 报告“发现交点 p”; 同时返回 L(p), U(p) C(p)\)
  5. \(将 L(p) \cup C(p)中的线段从 T 中删除\)
  6. \(将 U(p) \cup C(p)中的线段插入到 T 中 (_ T 中各线段的次序，必须与它们和扫描 线刚离开 p 之后的相交次序一致 ) ( 若存在水平的线段，则将它排在包含 p 的所有 线段 2 的最后 _)\)
  7. \(\)
  8. \(\)
  9. \(\)
  10. \(\)
  11. \(\)
  12. \(\)
  13. \(\)
  14. \(\)
  15. \(\)
  16. \(\)

查找新交点

判断两条直线是否相交, 如果存在交点, 分两种情况: 1. 已被处理, 2. 未被处理. 另外, 如果两条直线中存在水平直线时候(因为扫描线与 x 轴平行), 即出现与扫描线 y 坐标相同 的事件点时, 按照从左向右的顺序处理

算法: FindNewEvent(sl, sr, p)

$$1. \textbf{if} (sl 和 sr 相交于当前扫描线的下方 \\ (或者交点正好落在当前扫描线上并且在当前事件点的右侧)，\\ 而且该交点尚未做为一个事件出现在 Q 中) \\ 2. then 将这个交点做为一个事件，插入到 Q 中$$

引理 2.2

算法 FINDINTERSECTIONS 能够正确地计算出所有的交点，并能同时给出穿过各交点的线 段。

引理 2.3

对于由平面上任意 n 条线段组成的集合 S，算法 FINDINTERSECTIONS 的运行时间都是 O(nlogn + Ilogn)，其中 I 为 S 中各线段之间的交点总数

引理 2.4

给定由平面上任意 n 条线段构成的一个集合 S。可以在 O(nlogn + Ilogn)时间内，使用 O(n)空间，报告 出 S 中各线段之间的所有交点，以及与每个交点相关的所有线段。其中 ，I 为实际的交点总数