Segmenting a space into polygon regions with voroni approximation given a set of points

Question

I am trying to partition a space into a set of polygons, where each polygon is approximately a voroni cell for one of a set of input points.

I was trying to use Boost::Voroni for this purpose, but the output of use of this library is complicated, requiring a lot of extra effort to get what I want.

I was wondering if anyone knows the best way to get what I want out of a BOOST::voroni diagram, or if someone knows of a simpler library than can get me what I'm looking for directly?

Here is some code showing what I am trying to do,

voronoi_diagram< float > vd;
construct_voronoi( gridPointPos.begin(), gridPointPos.end(), &vd );

int index = 0;
for (voronoi_diagram<float>::const_cell_iterator it = vd.cells().begin();
    it != vd.cells().end(); ++it, ++index ) {

    // if the voroni cell has infinite edges,
        // then clip them to a finite length

    // extract the voroni vertices of this cell

    // create a boost polygon from the extracted edges
} 

Because boost is overly general and complicated for my needs, I would prefer a library or algorithm that simply does all of this, returning only sets of polygons. What are my options?

Answer 1

You can try my implementation of the bowyer-watson incremental algorithm for a delaunay triangulation in PHP it also finds the voronoi diagram. You can download it at codeplex.com (http://voronoi.codeplex.com/).

Answer 2

I had the same question, but I couldn't really find anything light weight enough for my taste. So I created my own C implementation (a single header file), see https://github.com/JCash/voronoi

Given an array of points, and some draw_triangle function:

    jcv_diagram diagram;
    memset(&diagram, 0, sizeof(jcv_diagram));
    jcv_diagram_generate(count, (const jcv_point*)points, width, height, &diagram );

    const jcv_site* sites = jcv_diagram_get_sites( &diagram );
    for( int i = 0; i < diagram.numsites; ++i )
    {
        const jcv_site* site = &sites[i];

        unsigned char color_tri[3] = { 127, 127, 127 };
        const jcv_graphedge* e = site->edges;
        while( e )
        {
            draw_triangle( &site->p, &e->pos[0], &e->pos[1], image, width, height, 3, color_tri);
            e = e->next;
        }
    }

    jcv_diagram_free( &diagram );