本文涉及知识点

数学 几何

预备知识

矢量$\vec{u},\vec{v}$，如果u逆时针旋转不超过180${}^{\circ }$能够和v重合，则称v在u的逆时针平面。俗称左侧（u是竖直向上的向量)。逆时针旋转也称左拐。下侧是不规范的说法，尽量不使用。

点P和线段$\overrightarrow{AB}$的位置关系

double cross＝$\overrightarrow{AB}\times \overrightarrow{AP}$
cross>0，P在AB左侧；cross=0,P在AB上；cross<0，P在AB右侧。

ABC排序

以横坐标升序为第一关键字，纵坐标降序为第二关键字对点ABC排序。
预备知识一：如果B的纵坐标小于AC，则BC在AB的逆时针半平面或共线。
情况一：A.x < B.x < C.x。红角锐角，蓝角锐角。，故AB逆时针旋转不到180${}^{\circ }$可以和BC重合。

情况二：A.x=B.x<C.x。红角直角，蓝角锐角。
情况三：A.x<B.x=C.x。红角锐角，蓝角直角。
情况三：A.x=B.x=C.y。共线。
预备知识二：B的纵坐标小于等于AC也符合上述性质。
预备知识三：平移所有所有点$(x_0,y_0)$所有向量不变，令$A(x_1,y_1),B(x_2,y_2),移动前\overrightarrow{AB}=(x_2-x_1,y_2-y_1)$,移动后也是。
预备知识四：以原小为旋转为中心，旋转所有点$\theta$,所有的向量也旋转$\theta$。
$$旋转公式\{\begin{array}{l}{x}^{\prime }=x\cos \theta -y\sin \theta \\ y^{\prime }=x\sin \theta +y\cos \theta \end{array}$$
令$A(x_1,y_1),B(x_2,y_2)，移动后\overrightarrow{AB}$,
$$\{\begin{array}{l}\Delta x^{\prime }=x_2^{\prime }-x_1^{\prime }=(x_2-x_1)\cos \theta -(y_2-y1)\sin \theta =\Delta y\cos \theta -\Delta x\sin \theta \\ \Delta y^{\prime }=y_2^{\prime }-y_1^{\prime }=(x_2-x_1)\sin \theta +(y_2-y_1)\cos \theta =\Delta y\cos \theta +\Delta y\cos \theta \end{array}$$
即将向量旋转$\theta$
用线性代数证明，更简洁。令R是旋转矩阵，则：
BR-AR=(B-A)R
预备知识四：A,B,C是平面上的点，BC在AB的顺时针(逆时针)半平面，则AC在AB的顺时针(逆时针)半平面。
$\overrightarrow{AB}\times \overrightarrow{AC}=\overrightarrow{AB}\times (\overrightarrow{AB}+\overrightarrow{BC})=\overrightarrow{AB}\times \overrightarrow{AB}+\overrightarrow{AB}\times \overrightarrow{BC}=\overrightarrow{AB}\overrightarrow{BC}$即两者叉乘相等。
预备知识五：R是凸多边形P和Q的交集，则R是凸多边形。
$\forall p,q\in R,r\in pq,根据凸多边形的定义，r\in P,r\in Q\to r\in R$

引言

某张地图，将校园划分成若干区域，同一个区域最近的电话机相同。就是的Voronoi图（Voronoi diagram,沃罗诺伊图）。
给定一组几何形状不同的障碍物，我们需要在不与任何障碍物发生碰撞的前提下，找出联结任意两点的最短路。这就是运动规划（motion planning）,这在机器人学中至关重要的问题。
两张地图：一张描述各个建筑物，包括公用电话；另一张则画出校园内的道路。为了规划出通往公用电话的运动路径，我们需要将这两张地图叠合起来。
这一学科可定义为“针对处理几何对象的算法及数据结构的系统化研究”，其重点在于“渐进快速的精确算法”。
《计算几何》主要应用领域：机器人学、计算机图形学、CAD/CAM以及地理信息系统。

1 凸包的例子

凸多边形（convex polygon）凸包 Convex hull
对具有几何本质的算法问题，我的采用的解决方法大多需要具备两方面的要素：一是对该问题的几何特性的深刻理解，二是算法和数据结构的合理应用。
平面的一个子集S称为是“凸”的，当且仅当任意两点p,q$\in S$，线段$\overline{pq}$都完全属于S。集合S的凸包CH(S)就是包含S的最小凸集–更确切地说，它是所有包含S的所有凸集的交。
给定平面点集$P=p_2,\cdots p_n$，通过计算从P中选出若干点，它们沿顺时针方向依次对应与CH§的各顶点。
输入=平面上的一组点：$p_1,p_2,p_3,p_4,p_5,p_6,p_7,p_8,p_9$
输出=凸包的表示$p_4,p_5,p_8,p_2,p_9$
性质一：相对于CH§边界上任意一边所在直线,P中所有的点均居于同侧。
性质二：$p,q\in P,p\ne q$。如果所有点都在$\overline{pq}$同侧，则$\overline{pq}$是凸包的边界。
不严格的证明：
$\overline{pq}不是边界\to 存在r\in \overline{pq}是凸包内一点，两个方向延长pq，将凸包分成两个凸多边形H1,H2，$
$r沿pq法线方向移动无尽小，得到的点是s；r沿pq法线反方向移动无穷小，得到t。显然s,t分属于H1,H2$。
$H1,H2非空\to 除直线pq外，两侧都有点$。
小结： $p,q\in P,p\ne q$。如果所有点都在$\overline{pq}$同侧 $⟺$ pq是凸包的边界。
证明：
引理一：P凸包的顶点$\in P$。
如果所有的其它点都在pq左侧，则交换pq，这样所有的点都在新pq的右侧。根据凸多边形的定义，所有pq所在直线的半平面交际就是凸多边形。故所有点都在pq组成的凸多边形内。
凸包一定包括pq，否则q点在多边形外。pq所在直线将凸包分成H1,H2。根据引理一，H1,H2中的一个退化成直线，即pq就是边界。

暴力算法

时间O(n^3)的凸包算法，三层循环。第一层枚举p,第二层枚举q，第三层循环枚举其它点。合法的pq首尾相连就是凸包点的逆时针序。
处理三点共线：$r\in P,r\ne p,r\ne q$都是以下情况之一则pq是凸包的边：
一，r在pq 右则。
二，r在线段pq上。
一般情况下都用浮点数实现，故有舍入误差。下图pqr几乎共线，其他点都距离此三点较远。在误差的作用下，以下两种情况都有可能发生。一，所有点都在pr、pq、rq的右则。即这些边都是凸包的边，这显然是错误的。

二,r在qp左侧，p在rq左侧，q在pr侧。即这三条边都不是凸包的边，这显然是错误的。

Andrew 算法 (Andrew’s algorithm)单调链算法 (Monotone Chain algorithm)

$p_1到p_n以x为第一关键字,y为第二关键字排序$,即字典序排序。
性质三：p1一定是凸包的顶点。
用反正法证明。令凸包的点集是$Q=q_1,q_2\cdots q_k,p1\notin Q$。
则p1的凸组合为：$=\sum _{i=1}^k{\lambda }_i{q}_i=p_1+\sum _{i=1}^k{\lambda }_i{v}_i,v_i=q_i-p_1$
由于p1的x最小，古$v_i.x\ge 0$ 要想让左右式子的x相等，则${\lambda }_i或v_i.x$必定一个为0。即$p_1的任意凸组合，只包括横坐标和p1.x相同的点，而这些点的y>p1.y，故无法让左右式的y相等$。
同理$p_n$也一定是凸包的顶点。

求上凸包的过程

将p1加到L中。
将p2加到L中。
for( i =3 to n)
{
当 L的点数大于等于2 且$p_i不在L最后两个元素的右侧$，则L.pop_back()。 当表示循环
$p_n$加到L中。
}
L记录$p_1到p_n$的上凸包。
$线段p_1{p}_n将凸包拆分上凸包和下凸包$。
$A=p_i,B=p_j,C=p_k,i<j<k$ AC在上凸包，Ｂ在下凸包。

上凸包证明

令p的上凸包是q，共有m个点，$q_1=p_1,q_m=p_n$。上述代码处理完$p_i$L就是p的上凸包。

在$q_1\sim q_m$中依次增加$A(q_m.x,负无穷大),B(q_1.x,负无穷大)$形成的凸多变形L’，已经处理的点都在L’中。
证明一：L’是凸多边形。$\angle q_{1}BA=\angle q_{m}AB=90^{\circ }。由于已经字典序排序，故以q_1为原点，q2在第一四象限，故q_1的内角<180^{\circ }，同理q_m的内积也<180^{\circ }$

证明二；$p_i$淘汰一个点后，所有点都在新L’内部。因为新L’增加一个三角形和一个梯形，没有减少区域。

证明三：不删除只增加$p_i$，所有点都在新L’中。以为新L’只增加区域，没有减少区域。

总结：L’只会增加区域，不会减少区域，故包括所有点。

下凸包过程

在D中增加$p_n$
在D中增加$p_{n-1}$
for( i = n-2 to 1)
{
当 D中有两个元素，且$p_i$不在D最后两个元素的右则,D.pop_back()。
在D中增加p_i
}
D‘=D,在D’中增加$(D.back().x,无穷大),(D1.x,无穷大)$
类似上凸包，D’包括所有的点，所有点都在$D_i{D}_{i+1}$右则。

合并

H = L’和D’的交集，故H包括所有点，且是凸多边形。
H就是L和D的并集。H中的边都是凸包的边。
D去掉第一个元素和最后的元素，L+D 便是凸包节点的顺时针序。

特殊情况处理

上述算法已经考虑x相同。
三点共线不是右拐，也弹出（淘汰)。
三点构成右拐，但因为误差的原因变成左拐。计算结果比实际结果少一个顶点。
三点构成左拐，但因为误差的原因变成右拐，计算结果比结果多一个顶点，不在是凸多边形。解决方法：将靠近的顶点合并成一个顶点。
左拐(右拐)误判成右拐(左拐)往往是三个点比较接近，故误差不大。

退化及鲁棒性

一个几何算法的建立过程，往往经过三个阶段。
一，理解我们正在处理的几何概念。尽量忽略无关问题。
二，对算法进行调整，使之能正确处理退化情况。
三，具体实现。最典型问题“对实数进行精确运算”不现实，往往归结为鲁棒性问题。一，转成整数运算，支持精确运算的软件包。往往牺牲性能。二，调整算法，提前检测不一致的情况，仅仅避免程序不崩溃或无响应。无法保证结果正确。

主要应用领域

一，计算机图形学。
二，机器人学。
三，地理信息系统。
四，CAD/CAM。

扩展阅读

算法为骨，CAD为魂
亲士工具箱：支持中望CAD2024、AutoCad2013及以上，多年承接CAD项目的精华
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
活到老，学到老。明朝中后期，大约50%的进士能当上堂官(副部及更高)；能当上堂官的举人只有十余人。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

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

凸组合