CGAL二维周期正则三角剖分：实现方法或替代方案咨询

核心思路：基于现有组件组合实现 #

CGAL没有直接提供Periodic_2_regular_triangulation_2类，但可以通过周期Delaunay剖分框架 + 加权点幂距离适配来实现——正则三角剖分本质是加权点幂图的对偶结构，利用这一特性就能复用CGAL已有组件搭建所需功能。

步骤1：选择基础周期剖分类 #

以CGAL::Periodic_2_Delaunay_triangulation_2为基础框架，它原生支持二维周期域内的Delaunay剖分，我们只需要为其适配加权点的处理逻辑。

步骤2：定义适配幂距离的几何 traits #

正则三角剖分依赖幂距离替代欧氏距离，因此需要结合两类traits：

• 复用CGAL::Regular_triangulation_traits_2，它已经封装了幂距离的计算逻辑。
• 自定义周期剖分兼容的traits，确保周期平移操作能正确作用于加权点。

步骤3：代码实现示例 #

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Periodic_2_Delaunay_triangulation_2.h>
#include <CGAL/Regular_triangulation_traits_2.h>
#include <vector>

// 基础kernel，按需选择精确/近似构造类型
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
// 正则三角剖分traits，提供幂距离计算
typedef CGAL::Regular_triangulation_traits_2<K> RT_traits;
// 加权点类型
typedef RT_traits::Weighted_point Weighted_point;
// 周期域偏移向量类型
typedef K::Vector_2 Vector;

// 自定义兼容周期剖分的traits
struct Periodic_RT_traits : public RT_traits {
  // 实现加权点的周期平移逻辑
  Weighted_point transform(const Weighted_point& wp, const Vector& v) const {
    return Weighted_point(RT_traits::Point_2(wp.point() + v), wp.weight());
  }
};

// 定义最终的二维周期正则三角剖分类型
typedef CGAL::Periodic_2_Delaunay_triangulation_2<Periodic_RT_traits> P2RT;
typedef P2RT::Point Point;

int main() {
  // 初始化周期域（示例为单位正方形 [0,1)^2）
  P2RT p2rt(CGAL::Square_2<Point>(Point(0,0), Point(1,1)));

  // 准备加权点集，超出周期域的点会被自动映射到域内
  std::vector<Weighted_point> weighted_points;
  weighted_points.emplace_back(Point(0.2, 0.3), 0.01);
  weighted_points.emplace_back(Point(0.7, 0.5), 0.02);
  weighted_points.emplace_back(Point(1.1, 0.8), 0.005); // 自动映射到(0.1,0.8)
  weighted_points.emplace_back(Point(0.4, 1.3), 0.015); // 自动映射到(0.4,0.3)

  // 插入所有加权点
  p2rt.insert(weighted_points.begin(), weighted_points.end());

  // 验证剖分有效性
  assert(p2rt.is_valid());

  // 遍历有限面（对应正则三角剖分的三角形）
  for (auto face = p2rt.finite_faces_begin(); face != p2rt.finite_faces_end(); ++face) {
    Weighted_point wp0 = p2rt.point(face, 0);
    Weighted_point wp1 = p2rt.point(face, 1);
    Weighted_point wp2 = p2rt.point(face, 2);
    // 此处添加业务处理逻辑
  }

  return 0;
}

关键注意事项 #

• 周期域映射：Periodic_2_Delaunay_triangulation_2会自动将超出边界的点映射到周期域内，加权值不受平移影响。
• traits兼容性：自定义的Periodic_RT_traits必须实现周期剖分所需的transform方法，确保加权点平移后属性正确。
• 精度选择：根据场景替换kernel，比如Exact_predicates_exact_constructions_kernel适合高精度需求，但运行速度会降低。

替代方案：手动扩展周期逻辑 #

如果上述组合方式遇到兼容性问题，可尝试简单但效率较低的手动实现：

• 对原始加权点进行周期复制，在周期域的8个相邻副本中生成对应点。
• 使用普通的CGAL::Regular_triangulation_2进行剖分，再手动过滤掉跨周期边界的三角形，只保留原周期域内的有效剖分。

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