Нерекурсивный алгоритм обхода границ диаграммы Вороного с помощью boost :: polygon
Какой хороший алгоритм для пересечения границ диаграммы Вороного, используя повышение без рекурсии?
Я знаю, что придется проверять наличие бесконечных ребер в ячейке, затем проверять ее соседей и повторять оттуда, но я бы предпочел метод, который не требует рекурсии, так как я имею дело с большими наборами данных.
Возможно ли это без рекурсии?
Редактировать, для уточнения:
Это способ получить все граничные ячейки:
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();
}
}
Это будет пересекать грани диаграммы Вороного до тех пор, пока она не обратится к первой ячейке, а затем остановится, полностью заполняя стек.
Нерекурсивная реализация будет моделировать второй пример, создавая список краевых ячеек в порядке по часовой стрелке или против часовой стрелки, без использования рекурсии.
Решение
У вас есть только один рекурсивный вызов 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 может изменить порядок обхода способами, более тонкими, чем то, чего может (легко) достичь рекурсия.
Другие решения
Других решений пока нет …