几何问题

总述

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

最近对问题

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

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

蛮力算法

算法

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个点

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个顶点
  • 圆周上所有点