Non-recursive algorithm to walk the edges of a Voronoi diagram with boost::polygon

Question

What's a good algorithm to traverse the edges of a Voronoi diagram using boost without recursion?

I know it'd have to check for infinite edges in a cell then check its neighbours and repeat from there, but I'd prefer a method that doesn't require recursion since I'm dealing with large sets of data.

Is this possible without recursion?

Edit, for more clarification:

This is a way to obtain all edge cells:

voronoi_diagram vd;
boost::polygon::construct_voronoi(in.begin(), in.end(), &vd);

std::vector<const voronoi_diagram::cell_type *> edge_cells;

for(const voronoi_diagram::edge_type & e : vd.edges())
  if (e.is_infinite())
    edge_cells.push_back(e.cell());

The problem with the approach above is that it will not traverse the edge cells in any specific order, say clockwise for example.

A recursive implementation would do something akin to this (hastily written and untested) code:

bool findNext(const voronoi_diagram::cell_type * c,
              std::list<const voronoi_diagram::cell_type *> & list)
{
  const voronoi_diagram::edge_type * e = c->incident_edge();
  do
  {
    // Follow infinite edges, adding cells encountered along the way
    if (e->is_infinite() && e->twin()->cell() != list.front() &&
      e->twin()->cell() != list.back())
    {
      list.push_back(c);
      return findNext(e->twin()->cell(), list);
    }
    else if (e->twin()->cell() == list.front())
    {
      list.push_back(c);
      return true; // we reached the starting point, return
    }      
    e = e->next();
  } while (e != c->incident_edge());
  return false;
}
// ...
std::list<const voronoi_diagram::cell_type *> edge_cells;
// ...
for(const voronoi_diagram::edge_type & e : vd.edges())
{
  // find first infinite edge
  if (e.is_infinite())
  {
    if (findNext(e.cell(), edge_cells))
      break;
    else
      edge_cells.clear();
  }
}

This would traverse the edges of the Voronoi diagram until it traces its way back to the first cell and then stops, filling the stack all the way.

A non-recursive implementation would model the second example, producing a list of the edge cells in a clockwise or counter-clockwise order, without using recursion.

Answer 1

You only have one recursive call in findNext and it is return findNext(...) so the so-called tail-call optimization can be applied. Your compiler might do it at -O3. But if you don't trust the compiler to do this, you can do it by hand. Below is the transformed function, no longer recursive:

bool findNext(const voronoi_diagram::cell_type * c, 
          std::list<voronoi_diagram::cell_type *> & list)
{
  const voronoi_diagram::edge_type * e = c->incident_edge();
  bool justCalled; // true when we repalce the tail call
  do
  {
    justCalled = false;
    // Follow infinite edges, adding cells encountered along the way
    if (e->is_infinite() && e->twin()->cell() != list.front() &&
        e->twin()->cell() != list.back())
    {
      list.push_back(c);
      c = e->twin()->cell();    // reassigns function argument
      e =  c->incident_edge();  // replay the initiaization (before do loop)
      justCalled = true;        // force the loop to continue
      continue;                 // jump to start of loop
      // everything happens as if we called findNext(e->twin()->cell(), list);
    else if (e->twin()->cell() == list.front())
    {
      list.push_back(c);
      return true; // we reached the starting point, return
    } 
    e = e->next();
  } while (justCalled || e != c->incident_edge());
  return false;
}

This function is equivalent to the one you wrote, so you'd use it the same and you're sure there's no recursion involved. The bool flag is necessary because continue jumps to the test of the loop and not its body see here, thus the test might fail before the loop even begins when we change arguments and call continue.

This is a general technique, not specific to graph traversal but to all recursive algorithms. Of course if you have many function arguments and a large body of code, the transform is heavy lifting, but in this case I think it's a good match.

In more complex cases when the recursion is not a tail call, you still can "de-recusify" any function by maintaining your own stack. This has the advantage that replacing the stack structure with say a priority fifo may change the traversal order in ways more subtle that what recursion can (easily) achieve.