какой алгоритм заливки лучше для производительности?

Question

Я пытаюсь реализовать алгоритм, который похож на флуд. проблема в том, что я не уверен, каким образом мне следует это реализовать, например, рекурсивно - нерекурсивно.
я знаю, что у каждого есть свои недостатки, но один из них должен быть быстрее другого. рекурсивный открывает новую функцию в стеке, когда нерекурсивный каждый раз выделяет 4 новые точки.
пример для не итеративного:

Stack<Point> stack = new Stack<Point>();
    stack.Push(q);
    while (stack.Count > 0)
    {
        Point p = stack.Pop();
        int x = p.X;
        int y = p.Y;
        if (y < 0 || y > h - 1 || x < 0 || x > w - 1)
                continue;
        byte val = vals[y, x];
        if (val == SEED_COLOR)
        {
                vals[y, x] = COLOR;
                stack.Push(new Point(x + 1, y));
                stack.Push(new Point(x - 1, y));
                stack.Push(new Point(x, y + 1));
                stack.Push(new Point(x, y - 1));
        }
    }

edit: я собираюсь применить следующий алгоритм на карте 600X600 пикселей. хотя заливка не будет применяться на всей карте, она должна покрывать около 30% - 80% карты за каждую итерацию. моя цель - обнаружить ребра на карте высот и пометить эти ребра для дальнейшего использования.

Answer 1

это представляется наиболее эффективной реализацией заливки, которую я нашел ...

Я упоминаю технику заполнения границ, упомянутую в в этом ответе , как хорошую, но не такую ​​хорошую, как быстрая заливка.

Answer 2

Сделать маску - параллельный 2-х мерный массив байтов. Байт непроверенных областей имеет 0, для новой границы затопленной области он будет иметь значение 1. Для внутренней части затопленной области - значение 2. И сохранить список текущих пограничных точек тоже.

В любом конце внешнего цикла у вас есть маска с отмеченной текущей границей, внутри и снаружи области, и массив точек границы. Поэтому вы будете проверять наличие новых точек только на границе. И, проверяя первый массив пограничных точек, вы создаете второй пограничный массив и вторую маску. На следующем шаге вы воссоздаете первый массив границ и маску. Таким образом, мы можем использовать простой цикл while вместо рекурсии, поскольку структура данных, которую вы проверяете на любом этапе, очень проста.

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

Что касается циклического прохождения всех соседних точек, посмотрите на мой алгоритм здесь

Answer 3

Компьютеры очень эффективно обрабатывают циклы XY и двумерные массивы.

Если вы можете использовать циклы XY и двумерные массивы для прохода через заливку, а не все виды пошаговой логики, скорее всего, это будет очень быстро.

Простейшей пошаговой логикой является рекурсивная функция заливки, которая проверяет только 4 соседей.Это то, что я использовал для достижения 9 миллионов пикселей в секунду на процессоре i7 2017 года.Вот видео, чтобы объяснить простоту логики.он использует 2D-массивы, а не память (очень эффективно) и циклы: https://www.youtube.com/watch?v=Xddws-50Igs

Вот страница с видео, чтобы доказать, что я получил 4 миллиона вокселейв секунду для этого алгоритма на процессоре FX 2012. (33 миллиона вокселей заполнено за 7 секунд) https://unity3dmc.blogspot.com/2017/02/ultimate-3d-floodfill-scanline.html?showComment=1537614917045#c9221615743847221048

Answer 4

Рекурсивная заливка может переполнить стек, если изображение сложное.Используйте нерекурсивную заливку.

Если вы заботитесь о распределениях, вы можете представить точку в виде упакованного значения типа long и кодировать свой собственный LongStack, который внутренне хранит длинные значения в массиве.