嘿，别发愁！你用Bowyer-Watson做Delaunay三角剖分的路子完全没问题，根本不用换算法——问题出在没利用好Delaunay和Voronoi的对偶关系，这才是构建多边形最直接的方式，比你之前的边拼接朴素算法靠谱多了。

核心原理：对偶关系的应用 #

每个Delaunay三角形的外接圆圆心就是Voronoi图的一个顶点；而两个相邻Delaunay三角形共享的边，它的垂直平分线就是一条Voronoi边。更关键的是：每个原始随机点对应的Voronoi多边形，就是由所有以该点为顶点的Delaunay三角形的外接圆圆心，按顺序连接而成的闭合图形。

具体实现步骤 #

• 计算所有Delaunay三角形的外接圆圆心
  对每个Bowyer-Watson生成的三角形，算出它的外接圆圆心（这就是Voronoi顶点）。给定三个点(x1,y1),(x2,y2),(x3,y3)，解两条边的垂直平分线交点即可，网上能找到成熟的计算逻辑。
• 建立原始点到Voronoi顶点的映射
  遍历所有Delaunay三角形，把每个三角形的外接圆圆心，关联到该三角形的三个原始顶点上。比如一个三角形由点A、B、C组成，那它的圆心就要同时加到A、B、C对应的Voronoi顶点列表里。
• 对Voronoi顶点列表排序，形成闭合多边形
  这是避免边拼接乱序的关键：
  1. 对每个原始点对应的Voronoi顶点列表，以原始点为中心，计算每个顶点相对于它的极角（用atan2(dy, dx)计算）
  2. 按极角从小到大（或从大到小）排序这些顶点，排序后依次连接，就能得到一个闭合的多边形
  3. 注意：边界上的Voronoi多边形会延伸到你设定的1000×1000平面外，这时候需要额外计算Voronoi边和平面边界的交点，把这些交点补充到顶点列表里，才能让多边形在平面内闭合。

伪代码示例（Python风格） #

import math
from collections import defaultdict

# 假设你已经有了Delaunay三角形的列表，每个三角形包含三个原始点和外接圆圆心
# 每个三角形结构：(point1, point2, point3, circumcenter)
# point和circumcenter都是带x、y属性的对象
delaunay_triangles = [...]

# 第一步：建立原始点到Voronoi顶点的映射
point_to_voronoi_vertices = defaultdict(list)
for tri in delaunay_triangles:
    p1, p2, p3, cc = tri
    point_to_voronoi_vertices[p1].append(cc