c++ - 如何将由矩形(边界框)裁剪的 voronoi 图转换为一组多边形？

Question

我是 CGAL 的新手，最近我一直在尝试使用 CGAL 来计算由 C++ 代码中的边界框(矩形)裁剪的 Voronoi 图，我成功了。我利用了 CGAL documentation 中可用的示例代码.这是代码:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <iterator>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
typedef K::Iso_rectangle_2 Iso_rectangle_2;
typedef K::Segment_2 Segment_2;
typedef K::Ray_2 Ray_2;
typedef K::Line_2 Line_2;
typedef CGAL::Delaunay_triangulation_2<K> Delaunay_triangulation_2;
//A class to recover Voronoi diagram from stream.
//Rays, lines and segments are cropped to a rectangle
//so that only segments are stored
struct Cropped_voronoi_from_delaunay{
  std::list<Segment_2> m_cropped_vd;
  Iso_rectangle_2 m_bbox;
  Cropped_voronoi_from_delaunay(const Iso_rectangle_2& bbox):m_bbox(bbox){}
  template <class RSL>
  void crop_and_extract_segment(const RSL& rsl){
    CGAL::Object obj = CGAL::intersection(rsl,m_bbox);
    const Segment_2* s=CGAL::object_cast<Segment_2>(&obj);
    if (s) m_cropped_vd.push_back(*s);
  }
  void operator<<(const Ray_2& ray) { crop_and_extract_segment(ray); }
  void operator<<(const Line_2& line) { crop_and_extract_segment(line); }
  void operator<<(const Segment_2& seg){ crop_and_extract_segment(seg); }
};
int main(){
  //consider some points
  std::vector<Point_2> points;
  points.push_back(Point_2(0,0));
  points.push_back(Point_2(1,1));
  points.push_back(Point_2(0,1));
  Delaunay_triangulation_2 dt2;
  //insert points into the triangulation
  dt2.insert(points.begin(),points.end());
  //construct a rectangle
  Iso_rectangle_2 bbox(-1,-1,2,2);
  Cropped_voronoi_from_delaunay vor(bbox);
  //extract the cropped Voronoi diagram
  dt2.draw_dual(vor);
  //print the cropped Voronoi diagram as segments
  std::copy(vor.m_cropped_vd.begin(),vor.m_cropped_vd.end(),
            std::ostream_iterator<Segment_2>(std::cout,"\n"));
}

现在我打算生成 voronoi 面并将它们转换为多边形，以便在多边形上使用 CGAL::intersection bool 运算。 A similar question以前曾被问过，但没有提供 CGAL 解决方案。需要考虑两组多边形；首先是边界框内的一组完整的 voronoi 单元，它们与裁剪矩形没有交叉点。第二组将由实际上被边界框剪裁的 voronoi 单元组成。非常感谢任何评论或提示。

Answer 1

这里有一些实验代码:http://code.google.com/p/cgal-voronoi-cropping将 voronoi 图裁剪成矩形，结果是 HDS。查看测试目录下的main.cpp。