Voronoi Basic Tutorial

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

In the example that goes through this tutorial (voronoi_basic_tutorial.cpp) we are going to construct the Voronoi diagram of a few points and segments. On the image below one may see the corresponding rendered Voronoi graph. The primary Voronoi edges are marked with the black color, non-primary with green, input geometries have blue color. We split each input segment onto three sites (segment itself and both endpoints), edges that go between the sites corresponding to the same segment are considered to be non-primary.

And before you proceed don't forget to:

#include "boost/polygon/voronoi.hpp"
using boost::polygon::voronoi_builder;
using boost::polygon::voronoi_diagram;

Preparing Input Geometries

Below is the example of how the user provided point and segment classes might look like:

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));

Construction of the Voronoi Diagram

At this point we are ready to construct the Voronoi diagram:

voronoi_diagram<double> vd;
construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &vd);

Traversing Voronoi Graph

Voronoi graph traversal is the basic operation one would like to do once the Voronoi diagram is constructed. There are three ways to do that and we are going to cover all of them:

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;
}

This should give a very nice idea on how to do the Voronoi diagram traversal. Notice that while the output from the first two methods should be the same, it wouldn't for the third one. The reason is that in the last case we will iterate only once through the edges with a single finite endpoint and will skip all the edges with no finite endpoints.

Associating User Data with Voronoi Primitives

A few simple cases of associating the user data with the Voronoi primitives are following:

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.

We will consider the first example and will associate the total number of incident edges with each cell.
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");
}

Accessing Input Site inside the Voronoi Cell

As explained in the Voronoi diagram section, Voronoi cells don't contain coordinates of the input geometries directly. Instead they contains source index and source category that uniquely identify input site. The below routines traverses over the all Voronoi cells, fetches input geometry corresponding to the Voronoi cell and prints coordinates of the input site.

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;
}

Voronoi Diagram Rendering

There are two main issues that don't allow to strictly render the resulting Voronoi diagram using such rendering tools as OpenGL or DirectX. Those are:

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

Note: This would be the issues not only for rendering tools. Basically every task that requires diagram to be represented as a set of finite segments will fall into this category. voronoi_visualizer.cpp contains a simple fully featured implementation of the Voronoi diagram renderer using the Qt libraries. It was used to generate all the .png drawings under the boost/libs/polygon/example directory.

Summary

I hope the reader managed to get to this point and found the basic tutorial to be useful (in the end it's not so basic). Worth to notice that construction of the Voronoi diagram takes only two lines of code, everything else is about initializing input data structures, traversing Voronoi graph, associating data with the diagram primitives. In the default mode the Voronoi diagram operates with the signed int (32-bit) input coordinate type and double (64-bit) output coordinate type. In the advanced Voronoi tutorial we explain why this is enough for the 95% of cases and how to expand the algorithm coordinate types for the other 5%.

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)