CGAL users discussion list

[Bob Bill <>]

Dear all,

Given a polygon P, I need to compute the vertices of the segment Voronoi diagram.

I am using the 2D Segment Delaunay Graph package, but I am not able to find the vertices of the Voronoi diagram.

To give a concrete example, consider a pentagon P. I want to print its Voronoi nodes. Following this example in the documentation CGAL 5.6 - 2D Segment Delaunay Graphs: Segment_Delaunay_graph_2/sdg-voronoi-edges.cpp, I am just building the pentagon by hand by providing its edges (see code at the end of the message).

Unfortunately, it's only displaying the vertices of P many times, and I don't see coordinates that are inside the polygon P. Is there something I am missing? How can I actually compute the Voronoi nodes?

Best,

Bob

#include <CGAL/Simple_cartesian.h>

#include <cassert>

#include <fstream>

#include <iostream>

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;

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.5, 1.5});

std::pair<Gt::Point_2, Gt::Point_2> segm3({0.5, 1.5}, {0, 1});

std::pair<Gt::Point_2, Gt::Point_2> segm4({0, 1}, {0, 0});

segments.push_back(segm0);

segments.push_back(segm1);

segments.push_back(segm2);

segments.push_back(segm3);

segments.push_back(segm4);

SDG2 sdg;

std::size_t n_segments =

sdg.insert_segments(segments.begin(), segments.end());

assert(sdg.is_valid(true, 1));

std::cout << std::endl;

std::string inf_vertex("infinite vertex");

char vid[] = {'A', 'B', 'C', 'D'};

SDG2::Finite_edges_iterator eit = sdg.finite_edges_begin();

std::vector<Gt::Point_2> voronoi_points;

for (int k = 1; eit != sdg.finite_edges_end(); ++eit, ++k) {

SDG2::Edge e = *eit;

// get the vertices defining the Voronoi edge

SDG2::Vertex_handle v[] = {

e.first->vertex(sdg.ccw(e.second)), e.first->vertex(sdg.cw(e.second)),

e.first->vertex(e.second), sdg.tds().mirror_vertex(e.first, e.second)};

for (int i = 0; i < 4; i++) {

// check if the vertex is the vertex at infinity; if yes, print

// the corresponding string, otherwise print the site

if (sdg.is_infinite(v[i])) {

} else if (v[i]->site().is_point()) {

std::cout << vid[i] << " (point) : " << v[i]->site().point()

<< std::endl;

voronoi_points.push_back(v[i]->site().point());

}

}

return 0;

}