【计算几何】平面凸包、上凸包、下凸包

本文涉及知识点

数学
几何

预习知识

预备知识一：任意凸多边形P的的顶点集pts。对于任意$pt{s}_i$都存在直线L,使得pts都在L一侧,L=$p_i{p}_{i-1}$就是。P内任意一点q，一定不存在直线L，pts所有点都在一侧。下面用反证法证明。令直线L与P的边界交于$q_1和q_2$，如果pts都在直线的一侧时，则$q_1顺时针（逆时针）沿着P的边界移动时，$没有经过其它顶点。即直线段$q_1{q}_2$是边界线，$\to$q在边界线上。和q在P内矛盾。

定义及基础性质

有的书籍也成为凸壳、上凸壳、下凸壳。
给定一组点，凸包是包括这些点且面积最小的凸多边形。 类比：墙上有若干钉子，弹性无限好的橡皮筋从外面套住这些钉子，橡皮筋最终形成的形状就是凸包。
性质一：P的端点是pts的子集。

令P上一点p1不在pts中，其相邻的两点为$p0,p2,线段p3p4平行于p_0{p}_2，距离p_1无穷小$，用$p_3{p}_4代替p_1$面积更小。代替前是n个半平面的交集，代替后是n+1个半平面的交集，故仍然是凸多边形。
性质二：将pts以x为第一关键字排序，y为第二关键字排序。凸包P顶点必定包括pts[0]。
过L做竖直线，pts都在L右侧。根据预备知识一，故pts[0]一定不在pts的某些点组成的凸多边形内。
性质三：以pt0为起点，P逆时针的端点依次为$p{t}_1,p_{t}2\cdots p{t}_{n-1}$。以$p{t}_1$为极点，则$p{t}_{2\cdot n}$的极角$\in [-\frac{\pi }{2},\frac{\pi }{2}]$。所有点都在L的右侧。
极角单调性：凸多边形逆时针顶点为$p_1,p_2\cdots p_n$。则以pt0起点，$p{t}_i$极角单调变化。下面用数学归纳法证明：
n=3式，成立。
n>4，假设n-1多变形成立。凸n边型，可以拆分成凸n-1$p_1{P}_3\cdots p_n$,三角型$p_1{p}_2{p}_3$
对于三角型,$p_2的极角<p_3极角$；对于n-1边型，$p3的极角<p4的极角\cdots$。
假定L方向向下,L逆时针旋转，在任意时刻，不会经过3或更多P的端点。否则就存在三点共线。

推论一：以y最小的点为$p_1$，$p_{2\cdots n}在[0,\pi ]$间单调上升。

Jarvis March（礼品包装算法）

时间复杂度：O(hn)，n是点数，h是P的端点数。由于h是未知的，故确切的时间复杂度是O(nn)。
最大的优点是容易理解。
令P的端点按逆时针顺序为$p_1,p_2\cdots p_n$，则p1=pts[0]。已知$p_{1\sim i}$,求$p_{i+1}$。根据凸多边型的半平面定义，P所有的端点都$\overrightarrow{p_i{p}_{i+1}}$左侧。
next(i)=pts[i]如果在P上，则逆时针下一个端点在pts中的下标。
推论：任意$p_i$都是唯一，更换会造成旧$p_i$在凸包之外。

利用滑动窗口及化环为链求next(i)

以pts[i]为极点，求其它各点极角angs。如果这些极角的跨度超过$\pi$,则任意经过pts[i]的直线都会将P分成两部分，即pts[i] 一定不是凸包的一点。
angs是环型数组，如果$angs[j\cdots j-1]<\pi$，则anlge[j]对应的点是next(i)。
$\forall angs$，最多只有一个合法的j。令j1是合法解，则$ang{j}_1到an{g}_j>\pi ,j\ne j1$，必定包括此段。
时间复杂度不变，运行速度加快。即运行速度常量提升。如果优化的话，就是成了下面的扫描线算法。

扫描线算法（Graham Scan）

时间复杂度：O(nlogn)
一，以y为第一关键字x为第二关键字，对pts排序。p0=pts[0]。
二，对pts[$1\sim n-1]$按极角排序，p0是极点。
三,pt[$0\sim 2]$入栈。
四，依次处理pts[i],i=$3\sim n-1$
令栈顶元素是b，栈顶元素的前一个元素是a。c=pts[i]。
当 $\overrightarrow{ab}\times \overrightarrow{bc}\le 0$时,b出栈。即非左转出栈。
c入栈。
栈中元素就是P的顶点，逆时针。

容易理解的证明

证明一：是凸多边形。
栈中多边型是凸多变形，栈初始是凸多边形，三角型一定凸多边型。增加左转的点后，一定是凸多边形。

由于$\overrightarrow{p3p4}$左转，故$\angle p2p3p4<\pi$。
由于p4的极角$\le pi$,p3的极角$\ge 0$，$p4=\pi ,p3=0$不会同时存在，否则共线。故：$\angle p3p4p0<\pi$。
$p4\ne pi$,否则和p4的x小于p0，与假设矛盾。故$\angle p4p0p1<\pi$
证明二：被抛弃的点一定在P内。

p3在凸多变形P1=$p0p1p2p4$中，故凸多变形P包括P1，则包括P1中任意一点。$\angle p0p4p2<\pi$见证明一。根据极角单调性，以p1为极点,p2的极角<p4的极角，故p4 p0都在$\vec{p}1p2$，故$\angle p1p2p4<\pi$

严格正确性证明

令从栈底部到栈顶为$q_0,q_1\cdots q_{n_1}$,令$pt{s}_i是q_n$。令某次操作前，这些点组成的多边形是Q；操作后，这些点组成的多边形为Q‘。
性质一：$\forall Q$都是凸多边形。初始三角形是凸多边形。增加$q_n$及对应出栈，确保顶角$q_{1\sim n-1}$是凸角。以$q_0为原点$，其它点在第一、第四象限，故顶点$q_0$也是凸角。如果$q_n$是凹角则，则$q_n$的极角小于$q_{n-1}$，与扫描线方法矛盾。
性质二：Q‘包括整个pts。增加$q_n$，增加$△q_0{q}_{n-1}{q}_n$。删除$q_{n-1}$，增加$△q_{n-2}{q}_{n-1}{q}_n$。
性质三:当$p_i变成q_n$是，Q包括$p_i$，由于只增加范围不减少范围，故$\forall Q$都包括$p_i$。
性质四：由于凸包的顶点序就是极角序，故顺序不会错。
性质五：令$p_i{p}_j$是凸包的两个相邻顶点，则$p_0{p}_i\cdots p_j$一定有凹角或$p_i{p}_j$之间没有其它顶点，否则就是凸多边形。对角线(非相邻顶点)将凸变形分成两部分，即部分顶点在凸包外面，与凸包包括所有顶点矛盾。将$p_j和p_j$之间的凹角顶点删除，直到$p_i{p}_j$相邻。这意味着Q没有多余的顶点。

上下凸壳（单调链）

详细证明：计算几何–算法与应用 邓俊辉译(第三版) 第一章 凸包与导言
时间复杂度：O(nlogn)，和扫描线相比，不需要调用三角函数。
性质一：x=x0 和 凸多边P最多只有两个交点。假定有三个交点，依次为p1p2p3，p4和p5是x=x0上距离p2无穷近的点。由于p1p2在P上，故p4在P上；由于p3p4在P上，故p5在P上。即p2两个无穷近的点都在P内，矛盾。
性质二：如果x=x0和P只有一个交点p0，则P所有的横坐标都小于x0或都大于x0。令p1和p2的横坐标分别大于0，小于0。连接p1p2，和x=x0相交于p3，由于P和x=x0，只有一个交点，故p0=p3。即p3两个无穷近的点都在P内，矛盾。
横坐标最小的点，y小的是plb,y大的时plt；类似横坐标最大的点为prt,prb。plb逆时针到prb经过的端点是下凸壳；prt逆时针到plt是上凸壳。
性质三：x=x0和上凸壳（下凸壳）顶多只有一个交点。令P最小最大横坐标分别是x1,x2。上凸壳和下凸壳都是x1到x2连续，故x=x0和下凸壳有交点，则和上凸壳也有交点。故x=x0和下凸壳有2个交点，则和上凸壳至少有一个交点，即至少3个交点。与性质一矛盾。
性质四：下凸壳横坐标升序，下凸壳横坐标将序。令下凸壳，逆时针相邻的3个端点为x0,x1,x2。如果x0<x1,x2<x1。则x=x1-无穷小和下凸壳相交了2次，与性质三矛盾。

算法流程

以x为第一关键字,y为第二关键字对pts排序。
第一轮：按顺序对pts[i]按扫描线的方式出栈入栈。
第二轮：逆序对pts[i]按扫描线的方法出栈。
注意：除掉重复的端点。
性质五：某凸多边形P,其顶点逆时针为$p_1{p}_2\cdots p_m\cdots p_n$。则$p_1\cdots p_m$和$p_m\cdots p_1$也是凸多边形。$\angle p_1,\angle p_m$被拆分，其它角不变。之前内角和小于180，之和也小于180。
凸多变形扔掉任意一个三角型后，仍然是凸多边形。变化的两个内角变小。
正确性证明：根据性质五，下凸壳端点按顺序组成多边形是凸多边形，下凸壳也是。分别求然后合并。
性质六：pts依次三个点为ABC。
情况一：A在下凸壳，BC在上凸壳。以A为极点，根据极角单调性，C到B逆时针。即C在AB右。
情况二：AC在下凸壳，B在上凸壳。

沿着B做x轴的垂线，和AC交于D。BD是垂线和P的两个交点，B在上凸壳，C在下凸壳。故B在D上面。如果B和D重合，则$\overrightarrow{AB}\overrightarrow{BC}$ 不旋转。B在D上，顺时针旋转。

代码

C#

自己接的某个项目，用到了凸包。

namespace QinShiMath
{
    public static class CGeometry
    {
        public static List<SPoint2D> ConvexHull(List<SPoint2D> pts)
        {
            int n = pts.Count();
            // 1. 按 X 坐标排序，X 相同则按 Y 排序
            pts.Sort((a, b) =>
            {
                int cmp = a.X.CompareTo(b.X);
                return cmp != 0 ? cmp : a.Y.CompareTo(b.Y);
            });

            // 3. 构建下凸包（从最左到最右）
            var hull = new List<SPoint2D>(n * 2);
            for (int i = 0; i < n; i++)
            {
                while (hull.Count >= 2 &&
                    (hull[hull.Count - 1]- hull[hull.Count - 2]).CrossMul ( pts[i]- hull[hull.Count - 1]) <= 0)
                {
                    hull.RemoveAt(hull.Count - 1);
                }
                hull.Add(pts[i]);
            }
            // 4. 构建上凸包（从最右到最左）
            int lowerCount = hull.Count + 1;
            for (int i = n - 2; i >= 0; i--)
            {
                while ((hull.Count >= lowerCount)&&((hull[hull.Count - 1] - hull[hull.Count - 2]).CrossMul(pts[i] - hull[hull.Count - 1]) <= 0))
                {
                    hull.RemoveAt(hull.Count - 1);
                }
                hull.Add(pts[i]);
            }
            // 5. 移除最后一个点（与第一个点重复）
            hull.RemoveAt(hull.Count - 1);
            return hull;
        }
  
    }
}

扩展阅读

计算几何为骨，排样优化为魂
作品一：亲士套料工具箱 作品二： 亲士CAD工具箱
经典文章推荐：二维排样
万物皆数学
查阅鄙人的博文，请点击博文下载学院导航
活到老，学到老。明朝中后期，大约50%的进士能当上堂官(副部及更高)；能当上堂官的举人只有十余人。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/he_zhidan/article/details/156185051