voronoi多边形数学原理

### Voronoi 多边形的数学原理

Voronoi 图是一种特殊的几何结构，它基于一组离散点（称为站点或种子点），将整个平面划分为若干个区域。每个区域内任意一点到该区域对应的种子点的距离小于等于其到其他任何种子点的距离。

#### 定义与性质

给定一个度量空间 \( X \)，以及一系列非空子集 \( (S_i)_{i\in K} \)，其中 \( S_i \subseteq X \) 并且互不相同，则第 i 个 Voronoi 单元定义如下：

\[ V(S_i)=\{p\in X : d(p,S_i)\leqslant d(p,S_j), j\not=i, j\in K\} \]

这里 \( d(x,A):=\inf _{y\in A}\|x-y\|\)[^4]表示点 x 到集合 A 中最近点的距离。因此，\( V(S_i) \) 就是由那些最靠近 \( S_i \) 而不是其它任何一个 \( S_j(j≠i) \) 的所有点组成的集合。

当所有的 \( S_i \) 都是单点时，上述表达简化为标准形式下的 Voronoi 图描述方式；此时，每个 Voronoi 区域由直线边界构成，这些直线上每一点到相邻两颗种子点具有相等距离。

#### 构建方法

构建 Voronoi 图的一个常用途径是从 Delaunay 三角剖分出发。具体来说，在二维情况下，先通过 Delaunay 三角化得到一组相互关联的三角形单元格，接着利用这些单元格的信息来推导相应的 Voronoi 边界线段。例如，对于每一个 Delaunay 三角形而言，可以找到它的外接圆心作为对应 Voronoi 边缘上的节点之一[^2]。

// C++ 实现部分功能片段展示如何获取三角形外接圆心用于生成 Voronoi 边
Point circumcenter(Point a, Point b, Point c){
    double D = 2 * ((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x));
    
    // Calculate the center of circle passing through points a,b,c.
    double Ux = (((pow(a.x,2)+pow(a.y,2))*(b.y-c.y))+
                 ((pow(b.x,2)+pow(b.y,2))*(c.y-a.y))+
                 ((pow(c.x,2)+pow(c.y,2))*(a.y-b.y))) / D;
                 
    double Uy = (((pow(a.x,2)+pow(a.y,2))*(c.x-b.x))+
                 ((pow(b.x,2)+pow(b.y,2))*(a.x-c.x))+
                 ((pow(c.x,2)+pow(c.y,2))*(b.x-a.x))) / D;

    return {Ux,Uy};
}

此代码展示了计算三个已知坐标点所围成圆形中心位置的方法，这对于后续创建 Voronoi 图至关重要。