本文涉及知识点

数学 几何

预备知识

欧拉多面体公式：顶点数 - 棱数 + 面数 = 2，适用于凸多面体和与球面同胚的简单多面体。
平面图欧拉公式：对于任何一个连通平面图，V−E+F 的值恒等于 2，与图的形状无关。
棱(边)可以是非线段。

直线、射线、线段交点度数

一，直线与直线的交点度数是4。交点是射线起点。
二，直线和射线非端点交点，度数是4。交点是射线起点。

到一条定直线和一定点距离相等的点的轨迹是一条抛物线。

点到点和直线的距离相等，即：
$$\sqrt{(x-x_0{)}^2+(y-y_0{)}^2}=\frac{|ax+by+c|}{\sqrt{a^2+b^2}}$$
两边平方，消去根号和绝对值
$$(x-x_0{)}^2+(y-y_0{)}^2=\frac{(ax+by+c{)}^2}{a^2+b^2}$$

前言

我们希望了解的是，愿意从某一基点得到商品或服务的人们都居住在什么范围。做如下假设：
不同基点，价格相同。
获得任意商品或服务，需要支付的费用等于其本身的价格，再加上为抵达该基点需要支付的交通费用。
到达某一基点所需要的费用，等于顾客与该基点之间的欧氏距离乘以一个固定的单位距离价格。
在寻求某种商品或服务时，顾客们都会使其代价最小化。
这种模型将每个点都分配给与之距离最近的那个基点，我们称这一原则我Voronoi(沃罗诺伊)分配模型。根据这一模型得出的子区域划分，被称为这一基点的Voronoi图。如果两个子区域相邻于一段共同的边界，那么其对应的两个基点之间很可能存在有着直接的竞争，它们要争夺生活在这段边界附近的哪些客户。

1 定义及性质

任给平面上的两点p和q，所谓p和q的平分线，就是线段$\overline{pq}$垂直平分线。改平分线将平面划分为两张半平面。点p所在的那张半平面记作h(p,q)，点q所在的那张半平面记作h(q,p)。请注意：$r\in h(p,q)当且仅当dist(r,p)<dist(r,q)$。
$V(p_i)={\bigcap }_{1\le j\le n,j\ne i}h(p_i,p_j)$
也就是说,V(p_i)是n-1张半平面的交集，它也是一个（可能无界）开的凸多边形子区域，之多n-1个顶点和n-1边。
定理7.2：给定由平面上任意n个点构成的集合P。若所有的点都共线，则Vor§由n-1条平行直线构成；否则，Vor§将是连通的，而且其中的边不是线段就是射线。
任意Vor §一定n个面，任意点都在距离最近的基点所在平面。如果一个点距离两个基点最近则此点在边界线上。如果距离3个或更多基点的距离最近，则在边界点上。
定理7.3 若n$\ge 3$，则在于平面任意n个基点想对应的Voronoi图中，顶点的数目不会超过2n-5，且边的数量不会超过3n-6。
证明：如果基点共线，显然符合。如果Vor（P）有单向无限边，则在无穷远处增加一个顶点，所有单向无限边都指向此顶点。

e是原始图的边数，v是原始图的顶点数，对扩展后的Vor§图应用平面欧拉公式：
(v+1)-e+n=2 (7.1) 即e=n+v-1。
边数*2=各点度数之和。各点的度数$\ge 3$，故：
$2e\ge 3(v+1)$(7.2)
联合7.1和7.2 消除e 。
2n+2v-2$\ge$ 3v+3 $\to$v $\le 2n-5$
联合7.1和7.2消除v。
2e $\ge$ 3(e-n+2) $\to e\le 3n-6$

对于任何点q，我们将以q为中心，内部不含P中任何基点的最大圆，称为q关于P的最大空圆，记作$C_P(q)$。下面定理指出Voronoi图的顶点及边所具有的特征：
定理7.4:对于任一点集P所对应的Vor §图，下列命题成立：
1),点q是Vor §的一个顶点，当前仅当在其最大空圆的边界上，至少三个基点。
2),$p_i和p_j$之间的平分线确定了Vor §的一条边，当且仅当这条线上存在一个点q，$C_p(q)的边界经过p_i和p_j$，但不经过其它基点。

2 构造Voronoi图

容易想到的方法：第一层循环枚举基点i ，第二层循环枚举基点j,$i\ne j$, p是基点i和基点j中垂线。求i所p所在办平面h。
h的交就是基点i所在的子区域。利用前面区域的半平面求交算法，构造Voronoi的时间复杂度是O(nnlogn)。平面扫描算法-自诞生起一般都称为Fortune算法，可以在O(nlogn)时间内构造整个Voronoi图。不会有更快的算法，n个实数排序问题，可规约为Voronoi图构造的问题。通俗地说，如果存在更快的算法进行Voronoi构造，则可以以更短的时间内对n个实数排序。
平面扫描算法的策略，就是用一条水平直线–称为扫描线–自上而下扫过整个平面。在扫描线向下移动的过程中，只有某些特定的位置-称为时间点–这种信息才需要更新。
按一般一模式需要维护Voronoi图与当前扫描线的相交部分，这很难实现。因为Vor§为于扫描线l上方的结构，不仅取决于位于l上方的那些基点，而且也取决于下方的某些基点。故变通一下：维护位于l上方的那些基点对应的Voronoi图的局部。

图7-9解：曲线以上的部分的点，一定属于某个l以上基点所在子区域，因为这些点到直线 l的距离大于等于到l上面某个基点的距离，这意味着到l下面基点的距离更大，$|PB|\le |PD|\le |PC|$。

这一组依次相联的抛物线弧，称为海滩线(beach line)。可以从另一个角度来想象海滩线的样子；位于扫描线之上的每个基点$p_i$，都（与扫描线共同）确定了一条完整的抛物线${\beta }_i$；而海滩线就是这样一个函数：对于任一x-坐标，该函数的取值都是这些抛物线的最低者。

观察结论7.5：海滩线沿着x方向单调，它与任一垂线相交且仅相较于一点。
组成海滩线的抛物线弧依次收尾相联，其结合处称为断点(breakpoint)。每个断点都落在某条Voronoi边上。
首先考虑对应于海滩线出现新弧的事件，也就是在扫描线l触及某一新基点的时刻。在那一刹那，改基点对应于一条宽度为零的退化抛物线。随着扫描线继续下移，该抛物线逐渐伸展开来。对应于新基点的这类事件，称为基点事件。

当基点事件发生时，Voronoi图会相应地发生什么变化呢？我们记得，沿海滩线上各个点的运动轨迹，就勾勒出了Voronoi图的各边。每发生一个基点事件，就会生成两个新的断点，此后它们逐渐勾勒出同一条新边。

引理7.6：只有在发生某个基点时间时，海滩线上才会有新的弧出现。
组成海滩线的抛物线弧，总共不会超过2n-1段–只有遇到一个基点时，才会产生一条新的弧，同时最多将原有的某一条弧一分为而；而其它的时候，海滩线上都不可能会有新的弧出现。

平面扫描算法中的第二类事件，发生于原有的某段弧收缩为一点并即将消失时时。设此弧为${\alpha }^{\prime }$，且它消失之前弧$\alpha 和{\alpha }^{\prime \prime }$与之相邻。这三条弧必定分别定义不同点$p_i,p_j和p_k$。在$a^{\prime }$即将消失的那一刻，三个基点对应的抛物线交于一点q，则以p为圆心，穿过$p_i,p_j,p_k$的圆，且改圆在最低处与l相切。改圆的内部不可能有任意基点，否则此基点到p距离更短。此是q必是Voronoi图的一个顶点。海滩线上依次收尾相联的任何三段弧，其对应的三个基点都会确定一个外接圆；当扫描线触及这个类外接圆的最低点时，也就发生了一个圆时间(circle event)。
引理7.7：海滩线上已有的弧，只有在经过某次圆事件之后，才有可能消失。
引理7.9：Fortune算法运行时间为O(nlogn)，占用的空间为O(n)。

退化情况

本算法自上而下处理各事件，故若有两个或更多事件处于同一水平线，即出现退化情况。这些点的x互异，按任意顺序处理。算法一开始就遇到这个问题，则需要特殊处理，如：前两个点在同一水平线上。
存在四个或更多基点共圆，且改圆的内部不含任何基点，就会出现多个位置重合的圆时间。此时，改圆的中心也是Voronoi图的一个顶点。且该顶点的度数至少是4。可在事后处理，度数为4的顶点会被解析成两个度数为3的顶点。
某一基点$p_i$碰巧位于海滩线两段弧结合处断点的下方，算法可以在两段弧中任选其一，将其一分为二。当然其中一段为0—然后把对应于$p_i$的一段新弧插入其间。长度为0的那段弧，可以最终剔除掉。
海滩线上有依次首尾相联的三段弧，分别对应共线的三个基点。这三个基点不能确定一个圆，故并不会生成任何圆事件。

3 线段集Voronoi图

点以为其它物体也可定义Voronoi图。此时，平面上一点到物体的距离，定义为改点到物体上各点的最近距离。不相交线段之间的平分线更为复杂，它最多可以分为七段，每一段或是直线段或是抛物线弧。
各条线段仍然称为基点，而且以下将以基点端点、基点内部指代线段的端点、线段的内部。
海滩线仍由抛物弧和直线段组成。其中抛物弧上的每个点，到某一基点端点距离最近；直线段上的每个点，到某一个基点内部的距离最近。一旦某一基点内部与l相交，则海滩线上必有两条直线段以此交点为（共同的）端点。

海滩线上各抛物线与直线段之间的断点，分为五种类型。
1,若断点p到两个基点端点最近，且到它们与到l等距，则断点p将参与一条直线段的勾勒–此时与点基点的情况一样。
2，若断点p到两个基点内部最近，且到它们与l等距，则断点p将参与一条直线的勾勒。
3，若断点p到某个基点端点和另外一个基点内部最近，且到它们与l等距，则断点p将参与一条抛物线的勾勒。
4，若断点p到某一基点端点最近，且该距离由该线段基点的一条垂线实现，同时该距离等于p到l距离，则断点p将参与一条直线的勾勒。
5，若基点与扫描线相交于内部，则该交点就是一个断点，而且它将参与一条直线段的勾勒。
就第四和第五种情况而言，断点所勾勒的实际上并非Voronoi图的一段弧–因为这里仅涉及到一个基点。为了保证算法的正确性，有必要对类断点及其对应的时间进行处理。

与点基点的扫描线算法一样，这里也有基点事件和圆事件。扫描线每触及一个基点端点，就发生一次基点事件。显然，上端点所对应基点事件的处理方法，与下端有所不同。经过每一上段点后，海滩线的某条弧被一分为二，同时其间将有四条新弧出现。新弧之间的断点，都属于后两类。经过每一下端点之后，该基点内部与扫描线之间的交点所对应的断点，将被替换为两个第四类的断点，两者之间由(对应与这个新出线的基点端点的）一条抛物线联接。
圆事件也类似地分几类。无论那一类，对应于每一圆事件，海滩线上都会有某条弧消失。扫描线抵达每一空圆的底部，都会发生一次圆时间。每个空圆的中心，都会有两个相邻的断点汇合。根据汇合类型的不同组合，可分情况处理。若两个断点都属于前三类，则总共会涉及到三个基点。若其中之一属于第四类，则仅涉及到两个基点。在线段基点互不相交的前提下，第五类断点不会影响任何基点。
定理7.11：n条互不相交的线段基点所对应的Voronoi图，可以使用O(n)空间、在O(nlogn)时间内构造出来。
线段集Voronoi图的一个应用实例即运动规划。假定给定可表示为n条线段的一组障碍物，以及一个机器人R。再假定改机器人可以沿任意方向自由移动，而且可以很好地近似为一个包围圆D。假设需要在两个位置之间，为改机器人找出一条无冲突的运动路径，或者判断无路可通。

运动规划的技巧之一，就是所谓的收缩。其思路是：Voroni图中的各条弧给出了介于各线段基点之间的中间线，沿这些弧进行遇到障碍的可能性最小，因此其对应的路线也是最好的无冲突运动路径。
定理7.12: 对于任意n条互不相交的线段（障碍物)，以及一个圆盘形状的机器人，在机器人的两个位置之间是否存在一条无冲突的通道，可以使用O(n)空间，在O(nlogn)时间内判断。

4 最远点Voronoi图

所谓点集的圆度，可以定义为包含这些点的最窄圆环的宽度。这里的圆弧，是指介于两个同心圆之间的区域：所谓的圆环宽度，即这两个圆的半径之差。
作为最窄的圆环，其内、外边界（圆）必定穿过P中的点。将内、外边界所对应的圆分别记作内圆和外圆。内圆或外圆都必然会穿过P中任意一点。否则，可以膨胀内圆或收缩外圆。最窄环共有三种情况，这三种情况两个圆穿过点的总数都是4。

情况一：外圆经过3个点，确定了外圆半径，内外圆的圆心。内圆无法膨胀。否则唯一点不在环上。
情况二：内圆经过3个点，确定了内圆半径，内外圆的圆心。外圆无法收缩，否则唯一的点不在环上。
情况三：内外圆都经过了2个点。
找出最窄环，等价于找出其中心点。只要中心点(记之为q)固定了。只要中心点q固定了，最窄圆环也就确定了-其内、外圆分别由距离q最近、最远的点确定。如果已经构造出Voronoi图，则距离q最近的点，及包含q所在子区域对应的基点。实际上最远的点也对应某种几何结构。称最远点Voronoi图。点$p_i$所对应的最远点$Voronoi单元$，也是n-1张半平面的公共交集–这与标准的Voronio图一样。只不过采用的每条平分线的另一侧，就是距离$p_i$更远的那一侧平面。因此，最远点Voronoi图的每个单元都是凸的。在最远带点Voronoi图中，并非所有点都有一个单元，因为这些半平面交集可能为空。
观察结论7.13：给定平面点集P，其中任一点在最远点Voronoi图中拥有一个单元，当且仅当它是P凸包的一个顶点。

用反证法证明：令A是凸多边形内一点，O是A的最远 voronoi图对应子区域的一点。A是凸多边形内一点，故凸多边形被圆分成两部分，凸多边形圆外部分的顶点距离大于OA。与假设矛盾。
设$p_i\in P$落在凸包上，且平面上的点q距离p_i最远。则以q为段点，$p_{i}q$方向的射线全部距离$p_i$最远。
，这意味着每个单元都是无界的。

$|p_j{q}_0|<|p_{j}q|+|q{q}_0|=|p_{i}q|+q{q}_0|=|p_i{q}_0|$证明一
如果$p_i$是P凸包一点，则$p_i$在voronoi图对应的区域非空。
一，以$p_I$为中心旋转$p_{i+1}$使之竖直。如果所有点都在左半平面，以$p_i{p}_{i+1}$为轴翻转。移动原点到$p_i$。
二，$x_0=凸包顶点最大x+1$
三,Q = (x_0,0)，不断迭代Q=Q+(1,0)，至到Q距离$p_i$最远。如果$p_j和p_i在同一水平线，则P到p_i的距离比p_j远p_j.x$。否则根据证明一，$P到P_i$的距离增加更快。

最小包围圆其中心或是最远点Voronoi图的顶点，或是贡献了一条Voronoi边的两个基点的中点。请一种情形对应三个最远点，且最远距离相等；后一种情形对应两个。显然，作为最小包围圆的中心，距其最远的基点不可能只有一个。
最远点Voronoi图的顶点 有如下特征：到3个或更多基点的距离相等。且距离大于其它基点的距离。故以此顶点做圆，3个或更多基点在圆上，其它基点在圆内。
最远点Voronoi图的边 有如下特征：到2个基点AB的距离相等。且距离大于其它基点的距离。故以此顶点做圆，2个基点在圆上，其它基点在圆内。这两个点是圆的直径，可以使得半径最小。边和对应基点的连线的交点，就是以AB直径的圆的圆心。
最小外接圆的心一定不是最远点Voronoi图非顶点非边。否则，只有一点A在圆上，其它点在园内。 圆心向OA方向移动无穷小，半径也缩放小无穷小，这样A在圆上。不断操作，直到另外一点，也在圆上。操作结束时，所有点都在圆上或圆内，半径更小。操作一

定理7.14:对于平面上的任意n个点，都可以使O(n)的存储空间，在期望O(nlogn)时间内构造出其最远点Voronoi图。
最窄圆环的外圆一定是最远Voronoi图的顶点和边，否则按操作一，外环缩小半径s，内环增大半径s。根据证明一，所有点仍然在内圆外。
同理最窄圆环的内圆一定是Vononio图的顶点或边。
枚举可能的外圆圆心和内圆圆心，取交集便是答案。

最窄圆环的外圆不一定是最小外接圆

A在BCD的外接圆的圆小上，如果以最小外接圆为外圆，则内圆半径为0。半径差为|AD|。以AD为中心为圆心，内圆半径0.5|AD|，外圆半径小于1.5|AD|。

扩展阅读

算法为骨，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++**实现。