泰森多边形生成器 - Voronoi图在线绘制

泰森多边形（Voronoi Diagram），又称Dirichlet镶嵌或Thiessen多边形，是一种空间分割方法。给定平面上的一组种子点（站点），Voronoi图将平面划分为多个区域，每个区域包含所有距离该区域种子点最近的点。这种分割方式在自然界中广泛存在——如蜻蜓翅膀的脉络、长颈鹿的斑纹、干裂的土地等，都呈现出类似Voronoi图的结构。

Voronoi图应用极为广泛：
🏙️ 城市规划：确定公共设施（医院、消防站）的最佳服务范围；
📡 通信网络：规划基站覆盖区域；
🧬 生物学：模拟细胞组织结构；
🎮 计算机图形学：生成程序化纹理、破碎效果；
🌧️ 气象学：根据分散的气象站数据估算区域降水量；
🗺️ GIS地理信息系统：空间插值与邻近分析。

Voronoi图和Delaunay三角剖分互为对偶图（Dual Graph）。如果将Voronoi图中相邻区域的种子点连接起来，就得到了Delaunay三角剖分。反之，Delaunay三角剖分中每条边的垂直平分线构成了Voronoi图的边界。两者在计算几何中密不可分，Delaunay三角剖分具有"最大化最小角"的优良特性，避免了狭长三角形的产生。

本工具采用逐像素最近邻算法：对画布上的每个像素，计算它到所有种子点的欧几里得距离，选择距离最近的种子点，将该像素着色为该种子点对应区域的颜色。随后通过检测相邻像素是否属于不同区域来勾勒边界线。对于中等规模的画布（约30万像素）和数十个种子点，该算法在毫秒级完成，适合实时交互。对于更复杂的场景，专业算法如Fortune扫描线算法（O(n log n)复杂度）更为高效。

"泰森多边形"（Thiessen Polygon）这一名称来源于美国气象学家Alfred H. Thiessen，他在1911年将这种方法引入气象学领域，用于根据离散气象站的数据估算区域平均降水量。而"Voronoi图"则得名于俄罗斯数学家Georgy Voronoi（1868-1908），他在1908年对n维空间中的此类分割进行了严格的数学定义。实际上，这一概念早在1644年就由笛卡尔在其著作中讨论过，可谓历史悠久。