Нерекурсивный алгоритм для прохождения краев диаграммы Вороного с boost :: polygon

Question

Какой хороший алгоритм для прохождения краев диаграммы Voronoi с использованием boost без рекурсии?

Я знаю, что мне нужно будет проверить наличие бесконечных ребер в ячейке, а затем проверить его соседи и повторить оттуда, но я бы предпочел метод, который не требует рекурсии, поскольку я имею дело с большими наборами данных ,

Возможно ли это без рекурсии?

Edit, для более разъяснений:

Это способ получить все края клетки:

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

Это траверс бы края диаграммы Вороного, пока не прослеживает его путь назад к первой ячейке и затем останавливается, заполняя стек полностью.

Внерекурсивная реализация будет моделировать второй пример, создавая список ячеек краев по часовой стрелке или против часовой стрелки, без использования рекурсии.

Answer 1

У вас есть только один рекурсивный звонок в findNext, и это return findNext(...), так что может быть применена так называемая оптимизация tail-call. Ваш компилятор может сделать это на -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 переходит к тесту цикла, а не к его телу see here, поэтому тест может завершиться неудачно, прежде чем цикл начнется даже после изменения аргументов и продолжения вызова.

Это общая техника, не специфичная для обхода графика, а для всех рекурсивных алгоритмов. Конечно, если у вас много аргументов функции и большой объем кода, трансформация тяжелая, но в этом случае я думаю, что это хороший матч.

В более сложных случаях, когда рекурсия не является хвостовым вызовом, вы все равно можете «дезактивировать» любую функцию, сохраняя свой собственный стек. Это имеет то преимущество, что замена структуры стека, скажем, приоритетом fifo, может изменить порядок обхода более тонкими, чем может (легко) достичь рекурсия.