Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library

Subject: Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library
From: Andrii Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2012-05-21 18:15:39

On Mon, May 21, 2012 at 7:33 PM, Jeffrey Lee Hellrung, Jr. <
jeffrey.hellrung_at_[hidden]> wrote:

> I may have some suggestions on how to implement this user data, but yes,
> Luke's suggestion looks to be the simplest solution. Andrii, do you have an
> example use case for storing the data in situ with the voronoi primitive
> objects? Looking at a concrete use case might help ground the discussion.
>

There are two examples on data association usage:

1) Basic tutorial (non-practical examples that shows how to use this
functionality):
http://svn.boost.org/svn/boost/trunk/libs/polygon/doc/voronoi_basic_tutorial.htm
Section: "Associating User Data with Voronoi Primitives".

2) Voronoi visualizer:
http://svn.boost.org/svn/boost/trunk/libs/polygon/example/voronoi_visualizer.cpp
Uses depth first search to remove Voronoi edges outside of the polygon
bounds.
The data field is used to mark edges as visited (I added some comments):

void remove_exterior(const VD::edge_type* edge) {
    if (edge->data()) // visited edge, don't proceed
      return;
    edge->data(&edge); // mark edge as visited
    edge->twin()->data(&edge); // mark twin edge as visited also
    const voronoi_diagram<double>::vertex_type* v = edge->vertex1();
    // if the edge doesn't have endpoint or is not primary stop
    if (v == NULL || !edge->is_primary())
      return;
    // recursively run dfs for each Voronoi edge around current edge endpoint
    const voronoi_diagram<double>::edge_type* e = v->incident_edge();
    do {
      remove_exterior(e);
      e = e->rot_next();
    } while (e != v->incident_edge());
}

While this example doesn't directly associate any data with Voronoi
edges, it shows additional usage of this field that appeared to be
practical.

Regards,
Andrii