请求解析加性加权Voronoi算法与非加权版本的差异及Fortune算法

• 距离计算逻辑不同：非加权Voronoi用纯欧氏距离划分区域——点p属于点v的区域，当且仅当p到v的距离比到其他所有点都近。加性加权版本则是欧氏距离加上点的权重，即p属于v的区域当且仅当 d(p, v) + w_v 小于 d(p, u) + w_u（w是对应点的权重）。
• 区域边界形态不同：非加权的Voronoi边是直线，严格来说是两点的垂直平分线；加性加权的边是双曲线的一支，这也是你疑惑的核心原因。
• 区域特性差异：非加权的每个Voronoi区域都是凸集；加性加权的区域可能非凸，甚至会出现某个点的区域被其他区域完全包裹的情况（只要它的权重足够大）。

用数学推导就能明白：
假设有两个加权点a(x₁,y₁)（权重wₐ）和b(x₂,y₂)（权重wᵦ），边界上的点p(x,y)必须满足：
√[(x-x₁)² + (y-y₁)²] + wₐ = √[(x-x₂)² + (y-y₂)²] + wᵦ
移项后得到：
√[(x-x₁)² + (y-y₁)²] - √[(x-x₂)² + (y-y₂)²] = wᵦ - wₐ
这完全符合双曲线的定义——到两个焦点的距离差为定值的点的轨迹。所以这条边界自然是双曲线的一支，而非直线。

Fortune算法的核心是「扫描线+海滩线（抛物线构成的上包络）」，加性加权版本的改动全围绕权重对抛物线和事件逻辑的影响：

1. 海滩线的抛物线定义变了 #

非加权时，扫描线y=l，点v对应的抛物线是「到v和到扫描线距离相等的点的轨迹」，方程是 (x - vₓ)² = 2(vᵧ - l)(y - l)。
加性加权时，每个点v的权重wᵥ会改变抛物线的定义：到v的距离加上wᵥ 等于到扫描线的距离（扫描线在p上方，所以到扫描线的距离是l - pᵧ）。写成方程就是：
√[(x - vₓ)² + (y - vᵧ)²] + wᵥ = l - y
两边平方化简后得到：
(x - vₓ)² = 2[(vᵧ + wᵥ) - l](y - l) + (wᵥ² - 2wᵥ(vᵧ - l))
权重wᵥ会直接影响抛物线的顶点位置和开口大小，权重越大，抛物线的形态偏移越明显。

2. 事件处理的调整 #

站点事件（Site Event） #

当扫描线扫过一个加权点v时，把对应的加权抛物线插入海滩线。和非加权逻辑类似，但插入的是上面说的加权版抛物线，需要计算它和相邻抛物线的交点——这些交点就是潜在的Voronoi边起点，要加入事件队列。

圆事件（Circle Event） #

非加权时，圆事件是三个抛物线的公切点对应的外接圆与扫描线相切时触发，生成Voronoi顶点。
加性加权时，圆事件的条件变成：存在三个加权点v₁、v₂、v₃，存在点p使得 d(p,v₁)+w₁ = d(p,v₂)+w₂ = d(p,v₃)+w₃ = l - pᵧ（l是当前扫描线位置）。当扫描线到达 l = pᵧ + d(p,v₁)+w₁ 时，触发圆事件，生成对应的Voronoi顶点。
这里的「圆」是广义上的——满足到三个点的加权距离相等的点，所以计算逻辑要把权重纳入考量。

3. Voronoi边的生成 #

处理完所有事件后，海滩线上相邻抛物线的交点连起来就是Voronoi边，这些边是双曲线的一段，和我们之前推导的结论完全一致。

内容的提问来源于stack exchange，提问作者Stapton