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

返回本页常规视图.

计算几何

实用几何算法

基本几何算法针对点、线、三角形、多边形等基本几何对象及其二维和三维属性，提供对其计算边界容器、凸包和折线简化的快速算法。

基本几何对象

  • 点
  • 线
  • 射线
  • 线段
  • 三角形
  • 多边形
  • 平面

基本几何属性

  • 面积
  • 距离
  • 集合关系

1 - 基础几何

1.1 - 基础几何数学

1.1.1 - 点

1.1.2 - 向量

1.1.3 - 矩阵

1.1.4 - 欧拉

1.1.5 - 四元数

1.2 - 基础几何结构

1.2.1 - 基础几何 --- 面

1.2.2 - 基础几何 --- 体

1.2.3 - 基础几何 --- 线

1.2.3.1 - 圆弧

圆弧的定义方法

圆弧的参数化表示方法

$$\vec{r}(t) = \vec{c} + r\cos{t}\vec{u} + r\sin{t}\vec{v}$$

其中, \(\vec{c}\) 是圆心位置向量, \(r\) 是半径, \(t\) 是参数(通常在 \([0,\theta]\))范围内, \(\theta\) 是圆弧的总角度, \(\vec{u}\) 和 \(\vec{v}\) 是与圆弧方向相关的单位向量

圆弧的离散与采样

圆弧的动态采样

圆弧的动态采样方法通常涉及根据弧线的曲率和长度智能地确定采样点的位置和数量

曲率评估

通过计算圆弧的曲率来决定采样点的密度。曲率 \kappaκ 可以用以下公式计算: \(k = \frac{1}{r}\) 曲率越大，表示圆弧的弯曲程度越大，因此在该处可能需要更多的采样点。

动态分段采样

将圆弧分成若干段，每段长度根据预设的最大误差或曲率变化来确定。在每段中，根据需要计算或保持一定的采样点密度。

适当选择参数步长

根据曲率和圆弧长度，选择适当的参数步长来控制采样点的分布。通常，在曲率较大的部分和细节较多的区域会使用更小的步长。

动态调整采样点数量

根据需要和计算能力，动态调整每段的采样点数量，以平衡精度和性能要求。

起始和结束点的特殊处理

始终确保始点和终点包含在采样点列表中，以确保完整性和准确性

1.3 - 实用几何算法

1.3.1 - 线和面的相交性

1.3.1.1 - 直线和线段的相交求解

描述

在求解 2D 和 3D 的线段与直线的相交性时, 一般采用 “参数方程” 来描述两者

参数方程

直线

$$P(s) = P_0 + s(P_1 - P_0) = P_0 + s*\vec{u} \\ 其中, s = d(P_0, P(s)) / d(P_0, P_1)$$

同理可定义另一条直线的方程 \(Q(t) = Q_0 + v(Q_1 - Q_0) = Q_0 + t*\vec{v}\)

平行线

当且仅当 \(\vec{u} = a\vec{v}, \ \vec{u} = P_1-P_0, \ \vec{v} = Q_1 - Q_0\)

非平行线

1.4 - 线性代数基础

1.4.1 - 点和向量

1.4.2 - 坐标系理论

描述

直角线性坐标(rectangular linear coordinate)

直角线性坐标系统具有一个固定的绝对参考点作为原点，以及一组非零的坐标轴作为方向向量，这些方向向量确定了测量的方向。

一个坐标系统通过有序的n元组\((x_1, x_2, … x_n)\)来指定n维空间中的点，数值规则为：在第一个轴上, 行动 \(x_1\) 的距离, 然后在第二个轴上, 行动 \(x_2\) 的距离, 一次类推到第n个轴上, 其中有序的数字集合\((x_1, x_2, … x_n)\)称为点的坐标。

所有这些点的集合称为坐标空间。

一组特定的坐标轴构成的坐标空间称为坐标参考框架或空间的基。

不同的坐标系统可以跨越相同的坐标空间。

如果坐标轴彼此独立，即没有任何坐标轴可以写成其他坐标轴的组合，则这些轴被称为独立轴。

当独立时，它们是坐标空间的最小轴集，轴的数量即为空间的维度。

极坐标(polar coordinate)

球坐标(spherical coordinate)

2 - 几何算法

描述

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

关键词条

渐进快速的精确算法

假设

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

一些常见的问题的抽象

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

2.1 - 划分树

2.2 -

2.2.1 -

2.2.2 - 装配问题(Casting Problem)

描述

2.3 - 多层划分树

2.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}$$

2.5 - 退化和鲁棒性

描述

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

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

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

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

2.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. \(\)

2.7 - 专题图的叠合

Description

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

2.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 为实际的交点总数

3 - MeshLab 实用指南

3.1 - Cleaning And Repairing

描述

  • Merge Close Vertices (合并接近的顶点)
  • Merge Wedge Texture Coord (合并楔形纹理坐标)
  • Remove Duplicate Faces (移除重复面)
  • Remove Duplicate Vertices (移除重复顶点)
  • Remove Isolated Folded Faces by Edge Flip (通过翻转边移除孤立折叠面)
  • Remove Isolated pieces(wrt Diameter) (按直径移除孤立部分)
  • Remove Isolated pieces(wrt Face Num.) (按面数移除孤立部分)
  • Remove T-Vertices (移除T型顶点)
  • Remove Unreferenced Vertices (移除未引用的顶点)
  • Remove Vertices wrt Quality (按质量移除顶点)
  • Remove Zero Area Faces (移除零面积面)
  • Repair non Manifold Edges (修复非流形边)
  • Repair non Manifold Vertices by splitting (通过分割修复非流形顶点)
  • Select Self Intersecting Faces (选择自相交面)
  • Snap Mismatched Borders (对齐不匹配的边界)

3.2 - Selection

描述

包含了一系列用于选择模型中特定部分的过滤器。这些过滤器可以帮助你精确地选择顶点、 边、面或体素，从而进行进一步的编辑或处理

3.2.1 - Conditional Face Selection

3.3 - Smoothing, Fairing and Deformation

3.3.1 -

3.3.2 - Laplacian Smooth

Laplacian Smooth

Laplacian Smooth(surface preserving)