In this tutorial we will cover the basic usage of the Boost.Polygon
Voronoi library that should be enough for the 95% of cases. Below we will
discuss the following topics:

- preparing input geometries

- Voronoi diagram construction
- Voronoi graph traversal

- associating the user data with the Voronoi primitives
- accessing input site inside the Voronoi cell
- Voronoi diagram rendering

And before you proceed don't forget to:

#include "boost/polygon/voronoi.hpp"

using boost::polygon::voronoi_builder;

using boost::polygon::voronoi_diagram;

struct Point {

int a;

int b;

Point (int x, int y) : a(x), b(y) {}

};

struct Segment {

Point p0;

Point p1;

Segment (int x1, int y1, int x2, int y2) : p0(x1, y1), p1(x2, y2) {}

};

As we are going to use the default routines defined in the voronoi.hpp header to construct the Voronoi diagram, we are required to map our point and segment classes to the corresponding Boost.Polygon concepts:

template <>

struct geometry_concept<Point> { typedef point_concept type; };

template <>

struct point_traits<Point> {

typedef int coordinate_type;

static inline coordinate_type get(const Point& point, orientation_2d orient) {

return (orient == HORIZONTAL) ? point.a : point.b;

}

};

template <>

struct geometry_concept<Segment> { typedef segment_concept type; };

template <>

struct point_traits<Segment> {

typedef int coordinate_type;

typedef Point point_type;

static inline coordinate_type get(const Segment& segment, direction_1d dir) {

return dir.to_int() ? segment.p1() : segment.p0();

}

};

It's also possible to use the native Boost.Polygon types as point_data and segment_data, that won't require the above mapping.

So once we are done we can create the sample input:

std::vector<Point> points;

points.push_back(Point(0, 0));

points.push_back(Point(1, 6));

std::vector<Segment> segments;

segments.push_back(Segment(-4, 5, 5, -1));

segments.push_back(Segment(3, -11, 13, -1));

voronoi_diagram<double> vd;

construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &vd);

- simply iterating over the Voronoi edges (counts each edge twice):

int iterate_primary_edges1(const voronoi_diagram<double> &vd) {

int result = 0;

for (voronoi_diagram<double>::const_edge_iterator it = vd.edges().begin();

it != vd.edges().end(); ++it) {

if (it->is_primary())

++result;

}

return result;

}

- iterating over the Voronoi cells and then traversing edges around
each cell (counts each edge twice):

int iterate_primary_edges2(const voronoi_diagram<double> &vd) {

int result = 0;

for (voronoi_diagram<double>::const_cell_iterator it = vd.cells().begin();

it != vd.cells().end(); ++it) {

const voronoi_diagram<double>::cell_type &cell = *it;

const voronoi_diagram<double>::edge_type *edge = cell.incident_edge();

// This is convenient way to iterate edges around Voronoi cell.

do {

if (edge->is_primary())

++result;

edge = edge->next();

} while (edge != cell.incident_edge());

}

return result;

}

- iterating over the Voronoi
vertices and then traversing edges around each vertex (the number of the
iterations through each edge is equal to the number of finite endpoints
of the edge):

int iterate_primary_edges3(const voronoi_diagram<double> &vd) {

int result = 0;

for (voronoi_diagram<double>::const_vertex_iterator it = vd.vertices().begin();

it != vd.vertices().end(); ++it) {

const voronoi_diagram<double>::vertex_type &vertex = *it;

const voronoi_diagram<double>::edge_type *edge = vertex.incident_edge();

// This is convenient way to iterate edges around Voronoi vertex.

do {

if (edge->is_primary())

++result;

edge = edge->rot_next();

} while (edge != vertex.incident_edge());

}

return result;

}

- associating number of incident edges with each cell, vertex;
- associating color information with each edge;
- using DFS or BFS on the Voronoi graph requires to mark visited edges/vertices/cells.

Note: Each Voronoi primitive contains mutable color member, that allows to use it for the graph algorithms or associate user data via array indices.

// Using color member of the Voronoi primitives to store the average number

// of edges around each cell (including secondary edges).

{

printf("Number of edges (including secondary) around the Voronoi cells:\n");

for (voronoi_diagram<double>::const_edge_iterator it = vd.edges().begin();

it != vd.edges().end(); ++it) {

std::size_t cnt = it->cell()->color();

it->cell()->color(cnt + 1);

}

for (voronoi_diagram<double>::const_cell_iterator it = vd.cells().begin();

it != vd.cells().end(); ++it) {

printf("%lu ", it->color());

}

printf("\n");

printf("\n");

}

unsigned int cell_index = 0;

for (voronoi_diagram<double>::const_cell_iterator it = vd.cells().begin();

it != vd.cells().end(); ++it) {

if (it->contains_point()) {

if (it->source_category() ==

boost::polygon::SOURCE_CATEGORY_SINGLE_POINT) {

std::size_t index = it->source_index();

Point p = points[index];

printf("Cell #%u contains a point: (%d, %d).\n",

cell_index, x(p), y(p));

} else if (it->source_category() ==

boost::polygon::SOURCE_CATEGORY_SEGMENT_START_POINT) {

std::size_t index = it->source_index() - points.size();

Point p0 = low(segments[index]);

printf("Cell #%u contains segment start point: (%d, %d).\n",

cell_index, x(p0), y(p0));

} else if (it->source_category() ==

boost::polygon::SOURCE_CATEGORY_SEGMENT_END_POINT) {

std::size_t index = it->source_index() - points.size();

Point p1 = high(segments[index]);

printf("Cell #%u contains segment end point: (%d, %d).\n",

cell_index, x(p1), y(p1));

}

} else {

std::size_t index = it->source_index() - points.size();

Point p0 = low(segments[index]);

Point p1 = high(segments[index]);

printf("Cell #%u contains a segment: ((%d, %d), (%d, %d)). \n",

cell_index, x(p0), y(p0), x(p1), y(p1));

}

++cell_index;

}

- Some of the Voronoi edges are infinite, so should be clipped;
- Some of the Voronoi edge are parabolic arcs, so should be discretized.

Copyright: | Copyright © Andrii Sydorchuk 2010-2012. |
---|---|

License: | Distributed under the Boost Software
License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
http://www.boost.org/LICENSE_1_0.txt) |