Я хочу Flood Fill без стека и без рекурсии - PullRequest
Новая
       30

Я хочу Flood Fill без стека и без рекурсии

3 голосов
/ 23 октября 2010

Я хотел знать, как применить заливку к массиву, мой массив двумерный, который содержит временную границу буквы нового шрифта Линия границы содержит 1 и внутри и снаружи все 0. Я хочу заполнить все 1 вместо 0 только внутри. Но мне нужна логика, которая не требует больше памяти. Так что избегайте рекурсии и стека или очереди

Ответы [ 4 ]

4 голосов
/ 23 октября 2010

Обычно я не делаю домашнее задание для других людей, но мне понравился вызов: 

int c = -1;
while (c < 0)
{    
    /* Store breadcrumb trail, look to carry on */
    a[x][y] = c--;
    if (!hunt(0))
    {
        /* Nowhere to go, so back-track by looking for breadcrumb */
        a[x][y] = 1;
        c += 2;
        hunt(c);
    }
}

bool_t hunt(int v)
{
    if (a[x-1][y] == v)  { x--; return TRUE; }
    if (a[x+1][y] == v)  { x++; return TRUE; }
    if (a[x][y-1] == v)  { y--; return TRUE; }
    if (a[x][y+1] == v)  { y++; return TRUE; }
    return FALSE;
}

Обратите внимание, что это не проверяет попадание по краям массива.Также предполагается, что ваши элементы массива равны, например, int s, и что вы используете только значения 0 и 1 в своем изображении.

1 голос
/ 23 октября 2010

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

Типичный схематический алгоритм для заполненного многоугольника выглядит следующим образом (стек или рекурсия не требуются), и его также можно применить к растровому изображению при определенных условиях (я приду к этому):

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

Предположим, что это (может быть средняя строка символа O): 

00010010001001000
   ^  ^   ^  ^
   |  |   |  stop
   |  |   start
   |  stop
   start

Результат: 

00011110001111000

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

0 голосов
/ 06 февраля 2011 
function LowMemFloodFill(pixel)
  FillPixel(pixel)
  Do
    didFill = false
    For each pixel
      If current pixel has been filled
        For each adjacent pixel
          If adjacent has not been filled
            FillPixel(adjacent)
            didFill = true
          End
        End
      End
    End
  While didFill
End

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

0 голосов
/ 23 октября 2010

Вы в принципе не можете.Вы должны хранить эту информацию где-то, потому что вы должны знать, где еще начинать заполнять после того, как вы закончите с вашим текущим разделом.Рекурсия позволяет вам делать это неявно.Сохранение вашего собственного стека позволяет вам делать это явно, возможно, с некоторым сохранением.Оли Чарльзуорт делает милую вещь, сохраняя массив того же размера, что и изображение, но он использует даже больше памяти, чем рекурсия или хранение стека позиций.

...