Triangulation_2示例中获取Voronoi单元与窗口边界交点的方法

你需要先定义当前渲染窗口的轴对齐视口包围盒，坐标范围记为[x_min, x_max] × [y_min, y_max]，以下两种方法都基于该包围盒实现。

方法1：拓扑遍历+射线求交法（适配CGAL Triangulation_2原生接口） #

• 遍历所有Voronoi单元对应的Delaunay顶点，对每个顶点关联的Voronoi单元，先遍历它的所有Voronoi边：
  • 若Voronoi边为有限边，直接保留落在视口内的端点
  • 若Voronoi边为无限边，本质是一条从有限Voronoi顶点出发的射线，方向为对应Delaunay边的垂直平分线向外方向，直接求该射线与视口四条边的交点，作为该段的边界点
• 按Voronoi单元的边的顺序，依次连接收集到的有限内部顶点和射线与视口的交点，最后闭合得到窗口裁剪后的Voronoi单元多边形

提示：CGAL的Triangulation_2类提供了is_infinite()接口，可以直接判断面、半边、顶点是否为无限元素，无需自行推导拓扑关系。

方法2：双包围盒裁剪法（适配通用多边形裁剪库） #

• 先根据输入点集的全局包围盒，向外扩展2~3倍点集对角线长度，构造一个足够大的全局外包围盒
• 用该外包围盒裁剪所有无边界Voronoi单元，得到临时闭合多边形
• 再将临时多边形和你的窗口视口包围盒做二次裁剪，得到最终窗口内的Voronoi单元形状
• 该方法可以直接复用Sutherland-Hodgman等通用多边形裁剪算法，不需要单独处理射线相交逻辑，开发成本更低

裁剪后质心计算 #

拿到闭合的多边形顶点序列p_1(x_1,y_1), p_2(x_2,y_2), ..., p_n(x_n,y_n)（按顺/逆时针顺序排列，p_{n+1}=p_1），直接用多边形质心公式计算即可：

1. 计算多边形面积：A = 0.5 * abs( sum_{i=1到n} (x_i*y_{i+1} - x_{i+1}*y_i) )
2. 质心x坐标：Cx = (1/(6*A)) * sum_{i=1到n} (x_i + x_{i+1}) * (x_i*y_{i+1} - x_{i+1}*y_i)
3. 质心y坐标：Cy = (1/(6*A)) * sum_{i=1到n} (y_i + y_{i+1}) * (x_i*y_{i+1} - x_{i+1}*y_i)

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