本文基于CGAL 5.2 - 2D Apollonius Graphs (Delaunay Graphs of Disks) 进行翻译和学习
文章目录
定义
根据图片提出问题：
what is apollonius diagram？
what is apollonius graph？
已知apollonius graph和apollonius diagram是对偶的关系，下面就是针对上面的两个问题提出定义。
CGAL的2D Apollonius graph类旨在计算 Apollonius diagram或Additively weighted Voronoi diagram（加权voronoi图）的对偶
Apollonius diagrams
part 1
在图上有一组站点， P i = ( c i , w i ) , i = 1... n P_i=(c_i,w_i),i=1...n Pi=(ci,wi),i=1...n，其中 c i c_i ci是 P i P_i Pi的点(point)， w i w_i wi是 P i P_i Pi的权值(weight)。它把平面细分成相互连接的区域，称为细胞（cell），与站点相关的。(见 Figure 52.1 (left))
点 P i P_i Pi的 c e l l cell cell是平面上比点 P j P_j Pj更接近 P i P_i Pi的点的轨迹， j ≠ i j≠i j=i。
平面上点
x
x
x到点
P
i
P_i
Pi的距离
δ
(
x
,
P
i
)
δ(x,P_i)
δ(x,Pi)定义为:
δ
(
x
,
P
i
)
=
∥
x
−
c
i
∥
−
w
i
δ(x,Pi)=∥x−ci∥−wi
δ(x,Pi)=∥x−ci∥−wi
(本质即为 x x x 到 c i c_i ci 的距离 - w i w_i wi)
其中
∥
∥
∥为欧几里得范数。即
x
x
x是
n
n
n维向量
(
x
1
,
x
2
,
…
,
x
n
)
(x_1,x_2,…,x_n)
(x1,x2,…,xn)，
∣
x
∣
=
x
1
2
+
x
2
2
+
.
.
.
+
x
n
2
|x|=\sqrt{x_1^2+x_2^2+...+x_n^2}
∣x∣=x12+x22+...+xn2
很容易看出，voronoi图是此图的一种特殊情况，即 w i = 0 w_i=0 wi=0时，得到的是voronoi图。
然而，位点Pi可能有一个空单元格（ e m p t y c e l l empty\ \ cell empty cell）。这也可能发生在 p o w e r d i a g r a m power \ \ diagram power diagram的情况下，其对偶是规则的三角剖分( r e g u l a r t r i a n g u l a t i o n regular \ \ triangulation regular triangulation)
如果是这种情况，我们将站点称为隐藏的（ h i d d e n hidden hidden）(图52.1中的黑色圆圈)。一个不隐藏的站点将被称为可见的（ v i s i b l e visible visible）。
part 2 : 关于 w i w_i wi的讨论
如果所有权数 w i w_i wi都是非负的，那么Apollonius图可以看作是{P1，…，Pn}的圆集的Voronoi图，其中ci为圆心Pi, wi为圆心半径。
(可以理解为，设 x x x 到以 c i c_i ci为圆心， w i w_i wi为半径的圆的最短距离 = d i s t a n c e = distance =distance，则 δ ( x , P i ) δ(x,Pi) δ(x,Pi) = {圆外： d i s t a n c e distance distance || 圆内： − d i s t a n c e -distance −distance )
如果权数允许为负，我们需要到三维来解释Apollonius图在几何上的意义。
（这块负值这里我没有看懂）
我们把 二维欧几里得平面 与 三维中的xy平面 等同起来。
那么点集的Voronoi图可以看作是一组三维圆锥体的下包络线（the lower envelope of a set of 3D cones ）在xy平面上的垂直投影，定义如下 : 对于二维点集中的每个点 p p p，我们有一个顶点为 p p p的圆锥 C p C_p Cp。 C p C_p Cp的轴是一条直线平行于z轴通过 p p p, C p C_p Cp 的角度45∘角。最后， C p C_p Cp包含在正z半空间中。
Apollonius图相当于在z方向移动这些圆锥体的顶点用一个等于weight的量。权值为负的wi会产生顶点在负z-半空间的圆锥，权值为正的wi会产生顶点在正z-半空间的锥。以一种类似于点的方式，Apollonius图可以定义为移位的锥集的下包络线在xy平面上的垂直投影。
请注意，当所有顶点沿z方向平移相同数量时，锥集的下包络线的投影不会改变。特别地，我们可以将所有锥平移足够大的量，这样所有的顶点都在正z-半空间中。从代数上讲，这意味着如果我们把相同的量加到所有的权重上，Apollonius图不会改变，这特别意味着我们可以假设所有的权重都是正的。
根据以上的观察结果，为了简化我们对Apollonius diagrams的讨论，从现在开始，我们假设所有的权重都是正的，我们将把这些站点当作圆（refer to the sites as circles）。
Apollonius graph
part 1
The Apollonius diagram 是一个平面图, 它的对偶 the Apollonius graph 也是平面图。有很多方法可以将它嵌入到平面上，其中一种方法如Figure 52.1 (right).所示。
一旦我们有了Apollonius diagram，Apollonius graph就被唯一地定义了。如果这些圆的位置是一般的（ g e n e r a l p o s i t i o n general \ \ position general position）(请参阅下面的精确定义)，那么Apollonius graph是一些三角形面（远离 这些圆构成的凸包 ）所组成的图。在凸包 近处 ，我们可能有一些尖刺(即1度的顶点)。
(所谓三角形，我们指的是每个面恰好有三条边—不一定是直线边)。
为了统一我们对Apollonius graph的处理方法，我们在(有限的)圆的集合上加上一个无限大的虚构圆，我们把这个圆的位置称为无限大（ t h e s i t e a t i n f i n i t y the \ \ site\ \ at\ \ infinity the site at infinity）。
我们可以把 Apollonius graph 外表面的所有顶点都连接 t h e s i t e a t i n f i n i t y the \ \ site\ \ at\ \ infinity the site at infinity ，这样我们就得到了一个图，它所有的面都是三角形的。
然而，Apollonius graph 并不是一个三角剖分图，主要有两个原因：一是它的三角形边有曲线边；二是我们可能有一个图的两个面有两条共同的边，这在三角剖分中是不允许的。（ Figure 52.1（right）所示的Apollonius graph的圆集图，这两种特性就都出现了。）
part 2 ：general position
我们想通过讨论一般位置（ g e n e r a l p o s i t i o n general \ \ position general position）的概念来结束我们对 Apollonius graphs理论的简要介绍。
如果没有两个三元圆（triplets of circles）具有相同的相切圆（ tritangent circle），则称一组圆处于一般位置。这一陈述是相当专业的，最好在 点的环境下 中加以理解。对于点的等价表述是，我们没有定义同一个外圆的两个三连点（triplets of points），或者等价地说，没有四个点是同圆的。相反，当我们有退化位置的圆时（in degenerate position），Apollonius graph 的存在面有三条以上的边。我们可以通过任意方式简单地对相应的面进行三角化，得到一个图形的三角化版本。
事实上，在CGAL中实现的算法具有这样一个特性:它总是返回一个有效的 Apollonius graphs的三角化版本。这里的"有效"是指它包含了实际的Apollonius graph (也就是Apollonius diagram的实际对偶)，并且当存在面的边数大于三的时候，该面和构成它的面们，就被三角化了。它们被三角化的方式取决于图表中圆圈插入和删除的顺序。（这一段没有看懂）
part 3 ：hidden circles
最后一点是关于隐藏圆圈的（hidden circles）。首先，我们想要更精确地定义隐藏圆:如果一个圆的单元格内部是空的（empty interior），我们就说它是隐藏的。这个定义允许我们保证所有可见的圆圈都有二维区域的细胞。从几何学上讲，一个圆是隐藏的，这意味着它包含在另一个圆的圆盘的闭合中(参见图52.1)。注意，包含在几个圆盘的并集中的圆，而不包含在其中任何一个圆盘的闭包中，是不隐藏的。
隐藏的圆圈给我们的算法和软件设计带来了额外的困难。因为我们允许在希望的情况下插入和删除圆圈，所以在某个时间点隐藏的圆圈可能会在以后的时间点变得可见;例如，如果我们删除隐藏它的圆，就会发生这种情况。为了这个目的，我们储存隐藏的圆圈，当它们变得可见时，让它们重新出现。我们将在下面详细讨论这个问题。就目前而言，用户有能力控制这种行为就足够了。更具体地说，我们可以抛弃隐藏的圆圈。例如，当我们期望只做插入时，这种选择是完全自然的，因为在这种情况下，隐藏的圆将永远不会再次出现。另一方面，如果删除也是预期的，那么我们就失去了让隐藏的圆圈重新出现的能力。