awdec's Blog

凸包基础

定义

凸多边形

所有内角大小都在 $(0, π)$ 范围内的简单多边形

凸包

在平面上能包含所有给定点的最小凸多边形。

极点

凸包的顶点。

性质：若点 P 是点集 $S$ 的一个极点，那么存在一条经过点 P 的直线 $l$ ，使得点集 S 中除了 P 的所有点都在 $l$ 的同一侧。

极边

凸包的边。

性质：令凸包的点集为 $S$ ， $S$ 中除了极边上的点外都在极边所在的直线的同一侧。

求凸包

极点法

枚举每个点，判断每个点是否是极点。

依据：将凸包以凸包内一点为顶点进行三角剖分，非极点一定落在某个三角形内部，枚举另外三个点组成三角形，若点落在了某个三角形内部，则它不是极点。

时间复杂度： $O (n^{4})$ 。

极边法

枚举两点组成的边，判断它是否是极边。

依据：其它点在极边所在直线的同一侧。

时间复杂度： $O (n^{3})$ 。

增量法

每次用一个点去更新凸包。

若点在凸包内，舍弃
若点在凸包外，找凸包的切线

可推广至三维凸包、动态凸包。

判断点在凸包内： $n$ 次 to-left 测试， $O (n)$ 。

找凸包的切线：前驱和后继都在射线的同一侧，暴力 $O (n)$ 。

时间复杂度： $O (n^{2})$ 。

判断点在凸包内和找凸包的切线均存在 $O (n \log n)$ 做法。

Gift wrapping

从一条极边出发遍历其它点找到下一条极边。

时间复杂度： $O (n h)$ ，最坏 $O (n^{2})$ ， $h$ 表示凸包的极点数。

起点的确定：点集中最左/右/上/下的点一定是凸包的极点（若最左/右/上/下的点不唯一，则是极边上的点，此时取另一个方向上坐标最大/小的点）。

Graham scan

基于极角排序的求凸包算法。

算法流程：

以最左下角的点为极点，进行极角排序
将极点与极点的下一个点入栈
对于要入栈的下一个点，如果以栈顶连向该点需要顺时针旋转，则弹出栈顶
重复 3，直到从栈顶连向该点需要逆时针旋转
将下一个点入栈，回到 3

时间复杂度： $O (n \log n)$ 。瓶颈为极角排序。

Andrew’s algorithm

基于横坐标（x）排序的求凸包算法。

以最左最右两点为界，凸包可以分为上凸包和下凸包两部分。

算法流程：

对点集以横坐标（x）为第一关键字，纵坐标（y）为第二关键字排序。
正序遍历每个点，用栈维护下凸包。
倒序遍历每个点，用栈维护上凸包。

栈的维护方式与 Graham scan 一致。

时间复杂度： $O (n \log n)$ 。瓶颈为排序。

凸包进阶

凸包二分

判断点是否在凸多边形中

按横坐标（x）二分：

按最左和最右的点把凸包分成上凸壳和下凸壳。

通过一次 to-left 测试判断是在上半部分还是下半部分。

在对应凸壳上二分找到点在哪两条过相邻的极点的平行 $y$ 轴的竖线之间。

最后与找到的对应极边进行一次 to-left 测试，确定其是否位于凸多边形内。

时间复杂度： $O (\log n)$ 。

利用极角序二分：

从最下方的点出发向其它各点连射线，这些射线方向是按极角序排好的。

通过 to-left 测试与二分查找，可以找出点是在哪两条射线之间。

最后与找到的对应极边进行一次 to-left 测试，确定其是否位于凸多边形内。

时间复杂度： $O (\log n)$ 。

判断直线是否与凸多边形相交

找到与该直线平行的凸多边形的两条切线，判断该直线是否在两条切线之间。

凸多边形各边对应的向量是按照极角序有序的。

二分查找前驱和后继分别以向上和向下穿过直线的切点。

时间复杂度： $O (\log n)$ 。

过一点求凸多边形切线

存在切线当且仅当点严格在凸包外。

首先 $O (\log n)$ 地判断点是否在凸包外。

切线：切点前后的点在切线同一侧。

对于凸包上一点 $V_{i}$ ，如果 $V_{i + 1}$ 在射线 $P V_{i}$ 左侧，则 $V_{i}$ 点标记为 L，否则标记为 R。如果 $V_{i - 1}$ 的标记与 $V_{i}$ 不同，则 $V_{i}$ 是切点。

方法一：上下凸包：

情况一：

点在左极点左侧或右极点右侧。

此时，切点一个在上凸壳，一个在下凸壳。

上下凸壳的序列都满足 LLL...RRR... 或 RRR...RRR...，各自二分即可。

情况二：

两个极点均在上凸壳或下凸壳。

以上凸壳为例，此时的序列为：LLL...LLLRRR...RRRLLL...LLL。

二分找到横坐标（x）离该点最近的点，然后将上凸壳分为两部分，这两部分又可以各自二分找到切点。

方法二：射线划分：

点向凸多边形上任意一点作射线，将凸多边形分为左右部分。

在两部分上分别二分即可。

时间复杂度： $O (\log n)$ 。

方法三：射线划分·改：

以找到最左侧的切线为例。

情况一：

序列中第一个点是 R，则序列形如 RRR...RRRLLL...LLLRRR...RRR。

如果把最开始的几个 R 视作 L，那么序列则转化为可以二分的形式，并且可以二分找到切点。

最开始的几个 R，一定在第一条切线的右侧。

情况二：

序列中第一个点是 L，则序列形如 LLL...LLLRRR...RRRLLL...LLL。

如果把最后的几个 L 视作 R，那么序列则转化为可以二分的形式，并且可以二分找到切点。

最后的几个 L 一定在第一条切线的右侧。

时间复杂度： $O (\log n)$ 。

动态凸包（不删）

增量法求凸包，根据已有知识，可以做到 $O (n^{2})$ 。

维护一个数据结构，支持以下两个操作：

修改：在当前点集中加入一个点
询问：查询一点是否在当前点集的凸包内

以按横坐标（x）维护上凸壳为例，即 set 中的点按横坐标（x）维护。

询问，使用前文 $O (\log n)$ 判断点是否在凸包内的做法即可。
修改，二分找到横坐标（x）最近的点，然后分别向左向右遍历各点找切线，对于找到切线前的点将其删除。

特殊情况：点在凸包左极点左侧。

考虑一条切线即可，另一条切线在下凸壳考虑。

时间复杂度： $O (n \log n)$ 。

极角序维护方式同理。

凸包基础 ​

定义 ​

凸多边形 ​

凸包 ​

极点 ​

极边 ​

求凸包 ​

极点法 ​

极边法 ​

增量法 ​

Gift wrapping ​

Graham scan ​

Andrew’s algorithm ​

凸包进阶 ​

凸包二分 ​

判断点是否在凸多边形中 ​

按横坐标（x）二分： ​

利用极角序二分： ​

判断直线是否与凸多边形相交 ​

过一点求凸多边形切线 ​

方法一：上下凸包： ​

情况一： ​

情况二： ​

方法二：射线划分： ​

方法三：射线划分·改： ​

情况一： ​

情况二： ​

动态凸包（不删） ​

凸包基础

定义

凸多边形

凸包

极点

极边

求凸包

极点法

极边法

增量法

Gift wrapping

Graham scan

Andrew’s algorithm

凸包进阶

凸包二分

判断点是否在凸多边形中

按横坐标（x）二分：

利用极角序二分：

判断直线是否与凸多边形相交

过一点求凸多边形切线

方法一：上下凸包：

情况一：

情况二：

方法二：射线划分：

方法三：射线划分·改：

情况一：

情况二：

动态凸包（不删）