几何问题

总述

处理类似于点、线、多面体这样的几何对象

最近对问题

给定平面上的n个点中,距离最近的两个点

  • 点数量n不大3时,可以通过蛮力算法求解的
  • 假设集合中每个点均不相同、点按其x坐标升序排列
  • 另外使用算法得到点按照y坐标升序排列的列表Q

蛮力算法

算法

1
2
3
4
5
6
7
8
9
BruteForceClosestPoints(p)
// 蛮力算法求平面中距离最近的点
// 输入:n个点的列表p;p_i = (x_i, y_i)
// 输出:两个最近点的距离
d = \infty
for i = 1 to n -1 do
for j = i+1 to n do
d = min(d, sqrt((x_i - x_j)^2 + (y_i - y_j)^2))
return d

改进

  • 忽略平方根函数,只比较平方

分治法

  • 在点集在x轴方向中位数m作垂线,将点集分成大小为 $\lceiling n/2 \rceiling, \lfloor n/2 \rfloor$两个子集 $P_l, P_r$,然后递归求解子问题$P_l, P_r$得到最近点问题解

  • 定义$d=min{d_l, d_r}$

    • d不一定是所有点对最小距离
    • 最小距离点对可能分别位于分界线两侧,在合并子问题的 解时需要考虑
  • 只需要考虑关于m对称的2d垂直带中的点,记S为来自Q、位于 分隔带中的点列表

    • S同样升序排列
    • 扫描S,遇到距离更近的点对时更新最小距离$d_{min}=d$
    • 对于S中点P,只需考虑在其后、y坐标差小于$d_min$ 的矩形范围内点(因为S有序,P前的点已经考虑过)
    • 该矩形范围内点数目不超过6个(包括P),所以考虑下个点 前,至多考虑5个点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
EfficientClosestPair(P, Q)
// 分治法解决最近点问题
// 输入:P存储平面上n个点,按x轴坐标升序排列
Q存储和P相同的n个点,按y坐标升序排列
/// 输出:最近点直接欧几里得距离
if n <= 3
return 蛮力法最小距离
else
将P前ceiling(n/2)个点复制到P_l
将Q相应的ceiling(n/2)点复制到Q_l
将P余下floor(n/2)个点复制到P_r
将Q余下floor(n/2)个点复制到Q_r

d_l = EfficientClosestPair(P_l, Q_l)
d_r = EfficientClosestPair(P_r, Q_r)
d = min{d_l, d_r}

m = P[ceiling(n/2) - 1].x
将Q中所有|x-m|<d的点复制到数组S[0..num-1]

dminsq = d^2
for i=0 to num-2 do
k = i+1
while k <= num-1 and (S[k].y - S[i].y)^2 < dminsq
dminsq = min((S[k].x - S[i].x)^2 + (S[k].y - S[i].y)^2, dminsq)
k = k+1
return sqrt(dminsq)

算法特点

  • 算法时间效率

    • 将问题划分为规模相同子问题、合并子问题解,算法都只 需要线性时间
    • 运行时间递推式$T(n) = 2T(n/2) + f(n)$,其中 $f(n) \in \Theta(n)$,则$T(n) \in \Theta(nlogn)$
    • 已经证明在对算法可以执行的操作没有特殊假设情况下, 这是可能得到的最好效率

应用

  • 聚类分析

凸包问题

寻找能把给定集合中所有点都包含在里面的最小凸多边形

  • 设集合S中点按照x坐标升序排列,存储在列表P中 (x坐标相同,按y坐标升序)

蛮力算法

算法

  • 对于n个点集中两个点$p_i$、$p_j$,当且仅当集合中其他点 都位于穿过这两点的直线同侧时,其连线是该集合凸包边界 一部分
  • 检验每对点,满足条件的点即构成凸包边界

特点

  • 算法时间效率为$O(n^3)$

快包算法(分治法)

算法

  • $p_1、$p_n$显然是凸包顶点,且$\overrightarrow{p_1p_n}$ 将点集分为左右两部分$S_1$、$S_2$

    • 其上的点不是凸包顶点,之后不必考虑
    • S的凸包也被划分为upper hull、lower hull,可以使用 相同的方法构造
  • 若$S1$为空,则上包就是线段$p_1p_n$;否则寻找距离 $p_1p_n$最大点$p{max}$,若有多个,则选择使得夹角 $\angle p_{max}p_1p_n$最大点

    • $p_max$是上包顶点
    • 包含在$\triangle p1p{max}p_2$中的点不是上包顶点, 之后不必考虑
    • 不存在同时位于$\overrightarrow{p1p{max}}$、 $\overrightarrow{p_{max}p_n}$左侧的点
  • 对$\overrightarrow{p1p{max}}$及其左侧点构成的集合 $S{1,1}$、$\overrightarrow{p{max}pn}$及其左侧的点构成 集合$S{1,2}$,重复以上即可继续得到上包顶点

  • 类似的可以对$S_2$寻找下包顶点

向量左侧、距离计算参考线代

算法特点

快包和快排很类似

  • 最差效率$\Theta(n)$,平均效率好得多
  • 也一般会把问题平均的分成两个较小子问题,提高效率
  • 对于均匀分布在某些凸区域(园、矩形)的点,快包平均效率 可以达到线性

应用

  • 计算机动画中使用凸包替换物体本身,加快碰撞检测速度
  • 车辆路径规划
  • 地理信息系统中根据卫星图像计算accessibility map
  • 数理统计中用于进行异常值检测
  • 计算点集直径的高效算法中需要用到

欧几里得最小生成树问题

给定平面上n个点,构造顶点为这n个点的总长度最小的树

参考

二维散点

Convex Hull

凸包:包含点集S的最小凸集合

  • 离散点集:包含所有点的最小凸多边形
  • 最小:凸包一定是所有包含S的凸集合的子集
  • 凸包能方便地提供目标形状或给定数据集地一个近似

Extreme Point

极点:对于任何以集合中点为端点的线段,不是线段中点的点

  • 极点有一些特性是凸集中其他点不具备的性质

    • 单纯形法:如果存在极值,则一定可以在极点处取到
    • 找到极点、极点排序方向即可解决凸包问题
  • 举例

    • 三角形中3个顶点
    • 圆周上所有点
Author

UBeaRLy

Posted on

2019-03-21

Updated on

2019-02-22

Licensed under

Comments