CGAL users discussion list

[Pol Monsó Purtí <>]

In 2D (projected from 3D), I have a set of points (aka sites). With this points I generate a Voronoi diagram.

Typically, the points follow a certain line, like this:

·  ·    .   ·

Therefore the bissectors are usually unbounded

· | ·  / . \ ·

Now I have a perimeter Polygon_2 that mostly encloses the points, with the aggravation that some points could fall outside this perimeter. The perimeter is not necessarily convex.

I'd like to retrieve the polygons defining the connected components of this bounded voronoi graph.

I've thought many ways to achieve this, but I have trouble using the voronoi halfedges. I also wonder how are they defined when they are unbounded and have no source nor target, is it possible to get them in Ray_2 form (point and director vector)?

If I find out how to intersect a voronoi Halfedge with a Polygon_2 or its segments I could build those polygons.

The endgoal is to find the points that fall inside each voronoi region and perform some operations on them. With the constraint that each connected component has to be processed first before going to the next one. At the moment I traverse the space and I change the data depending on which voronoi region I'm in, but I'd like to prevent loading and unloading the data by finishing each region, as well as traversing the small as possible region, e.g. the voronoi region's bounding box.

I've taken a look at the cgal example http://doc.cgal.org/latest/Triangulation_2/Triangulation_2_2print_cropped_voronoi_8cpp-example.html and https://github.com/sloriot/cgal-voronoi-cropping

For the first, I would have to change from Voronoi_diagram_2 to delaunay, because

vd.dual() returns a const that discards qualifiers if I apply the draw_dual.

so this returns the discards qualifiers error:

vd.dual().draw_dual(vor).

Voronoi_diagram_2 has no method draw_dual as for now.

I could also get all the faces surrounding a site, but, again, I don't know how to intersect a possibly unbounded Face with a Segment.

Any ideas on how to achieve this or in particular find the intersection between a halfedge and a Polygon/segment?

Another doubt I have is how many faces has one 'voronoi region' as I've called them. From the definition on the manual I understand it's just one, but I'm not sure if the voronoi regions are splitted into triangular faces).

Some of my typedefs

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;

typedef CGAL::Projection_traits_xy_3<K>  Gt;

//cgal voronoi

typedef CGAL::Delaunay_triangulation_2<Gt>                                   DT;

typedef CGAL::Delaunay_triangulation_adaptation_traits_2<DT>                 AT;

typedef CGAL::Delaunay_triangulation_caching_degeneracy_removal_policy_2<DT> AP;

typedef CGAL::Voronoi_diagram_2<DT,AT,AP>                                    VD;

Cheers!

Pol