1

什么是使用boost而不递归遍历Voronoi图边缘的好算法？

我知道它必须检查单元格中的无限边缘，然后检查其邻居并从那里重复，但我更喜欢不需要递归的方法，因为我正在处理大量数据。

这可能没有递归吗？

编辑，以获得更多说明：

这是一种获取所有边缘单元的方法：

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

上述方法的问题是它不会以任何特定的顺序遍历边缘单元格，例如顺时针方向。

递归实现会做类似于这个（仓促编写和未经测试的）代码的事情：

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

这将遍历 Voronoi 图的边缘，直到它回溯到第一个单元格，然后停止，一路填满堆栈。

非递归实现将对第二个示例进行建模，以顺时针或逆时针顺序生成边缘单元的列表，而不使用递归。

4

1 回答 1

3

您只有一个递归调用，findNext因此可以应用return findNext(...)所谓的尾调用优化。您的编译器可能会在 -O3 处执行此操作。但是，如果您不相信编译器会这样做，您可以手动完成。下面是转换后的函数，不再递归：

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

这个函数和你写的函数是等价的，所以你可以用同样的方法来使用它，而且你确定不涉及递归。该bool标志是必要的，因为continue跳转到循环的测试而不是它的主体（参见此处），因此当我们更改参数并调用 continue 时，测试甚至可能在循环开始之前失败。

这是一种通用技术，并非特定于图遍历，而是所有递归算法。当然，如果您有许多函数参数和大量代码，则转换是繁重的，但在这种情况下，我认为这是一个很好的匹配。

在更复杂的情况下，当递归不是尾调用时，您仍然可以通过维护自己的堆栈来“取消递归”任何函数。这样做的好处是，用优先级fifo替换堆栈结构可能会以比递归可以（容易）实现的方式更微妙的方式改变遍历顺序。

于 2013-11-26T10:16:02.673 回答