如何獲得在QT中顯示的某些點的Voronoi圖？

Question

我在QT的QGraphicsScene中繪製了一些點，並將它們封裝到點類中。我想計算並顯示這些點的Voronoi圖到場景中。做這個的最好方式是什麼？

我在考慮使用CGAL的，但我不能找到一個很好的辦法做到這一點..

Answer 1

如果你認爲使用CGAL庫，你讀過its section about Voronoi diagrams？在Software Design小節中，他們解釋了涉及的數據結構。從我讀的內容中，可以得到表示Dirichlet單元格的多邊形，並且從那裏您可以告訴Qt繪製並使用不同的顏色填充它們（某些世界地圖着色算法可能在此處很有用）。

Answer 2

你需要顯示的是Voronoi圖限於一個矩形（你的顯示窗口）。這是一個簡單的方法。

相關文件頁面here和there。

#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")); 
}