基于CGAL计算多边形Voronoi节点以求解最大内切圆半径问题

核心错误点 #

• 多边形边定义错误：你的正方形第四条边是对角线{1,1} -> {0,0}，而非正方形的左边界{0,1} -> {0,0}。错误的边会导致Segment Delaunay Graph（SDG）的结构完全偏离正方形边的Voronoi图。
• 输出内容错误：你当前输出的v[i]->site()是SDG的输入站点（原始线段或端点），而非Voronoi图的节点坐标。要获取Voronoi节点的位置，需要调用SDG的voronoi_vertex()方法。
• 遍历对象错误：你遍历的是SDG的有限边，而我们需要的是Voronoi图的顶点（对应SDG的有限顶点），应该遍历finite_vertices_begin()到finite_vertices_end()。

修正后的代码 #

#include <CGAL/Simple_cartesian.h>
#include <cassert>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>

typedef CGAL::Simple_cartesian<double> K;
#include <CGAL/Segment_Delaunay_graph_2.h>
#include <CGAL/Segment_Delaunay_graph_filtered_traits_2.h>
typedef CGAL::Segment_Delaunay_graph_filtered_traits_without_intersections_2<K> Gt;
typedef CGAL::Segment_Delaunay_graph_2<Gt> SDG2;

// 判断点是否在正方形[0,1]x[0,1]内部（含边界）
bool is_inside_square(const Gt::Point_2& p) {
  return p.x() >= 0 && p.x() <= 1 && p.y() >= 0 && p.y() <= 1;
}

// 计算点到线段的距离（开平方后的值）
double distance_to_segment(const Gt::Point_2& p, const std::pair<Gt::Point_2, Gt::Point_2>& seg) {
  return std::sqrt(CGAL::squared_distance(p, Gt::Segment_2(seg.first, seg.second)));
}

int main() {
  std::vector<std::pair<Gt::Point_2, Gt::Point_2>> segments;
  // 修正正方形边的定义
  std::pair<Gt::Point_2, Gt::Point_2> segm0({0, 0}, {1, 0});
  std::pair<Gt::Point_2, Gt::Point_2> segm1({1, 0}, {1, 1});
  std::pair<Gt::Point_2, Gt::Point_2> segm2({1, 1}, {0, 1});
  std::pair<Gt::Point_2, Gt::Point_2> segm3({0, 1}, {0, 0}); // 修正此处
  segments.push_back(segm0);
  segments.push_back(segm1);
  segments.push_back(segm2);
  segments.push_back(segm3);

  SDG2 sdg;
  std::size_t n_segments = sdg.insert_segments(segments.begin(), segments.end());
  assert(sdg.is_valid(true, 1));

  double max_radius = -1;
  Gt::Point_2 best_center;

  // 遍历SDG的有限顶点（对应Voronoi图的顶点）
  SDG2::Finite_vertices_iterator vit = sdg.finite_vertices_begin();
  for (; vit != sdg.finite_vertices_end(); ++vit) {
    // 获取Voronoi节点的坐标
    Gt::Point_2 voronoi_pt = sdg.voronoi_vertex(vit);
    
    // 筛选多边形内部的节点
    if (!is_inside_square(voronoi_pt)) {
      continue;
    }

    // 计算到各边的距离
    double d0 = distance_to_segment(voronoi_pt, segm0);
    double d1 = distance_to_segment(voronoi_pt, segm1);
    double d2 = distance_to_segment(voronoi_pt, segm2);
    double d3 = distance_to_segment(voronoi_pt, segm3);
    
    // 当前点能形成的内切圆半径是到各边距离的最小值
    double current_radius = std::min({d0, d1, d2, d3});
    if (current_radius > max_radius) {
      max_radius = current_radius;
      best_center = voronoi_pt;
    }

    // 打印候选点信息（可选）
    std::cout << "候选Voronoi节点: " << voronoi_pt << std::endl;
    std::cout << "到四边距离: " << d0 << ", " << d1 << ", " << d2 << ", " << d3 << std::endl;
    std::cout << "对应内切圆半径: " << current_radius << std::endl;
    std::cout << "-------------------------" << std::endl;
  }

  std::cout << "\n最大内切圆结果:" << std::endl;
  std::cout << "圆心坐标: " << best_center << std::endl;
  std::cout << "半径: " << max_radius << std::endl;

  return 0;
}

关键修改说明 #

1. 修正多边形边：将第四条边改为正方形左边界，确保输入是正确的封闭正方形边集合。
2. 获取Voronoi节点坐标：使用sdg.voronoi_vertex(vit)获取SDG顶点对应的Voronoi图节点坐标，这才是内切圆圆心的候选点。
3. 遍历SDG顶点：直接遍历有限顶点，每个顶点对应一个与多个边等距的Voronoi节点。
4. 筛选内部点：添加判断排除多边形外部的Voronoi节点，避免无效候选。
5. 计算最大内切圆：对每个内部候选点，取到所有边距离的最小值作为内切圆半径，记录最大半径及对应圆心。

输出结果说明 #

运行修正后的代码，会输出正方形中心(0.5, 0.5)，半径0.5，这正是正方形的最大内切圆参数。

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