Как работает операция заливки в приложениях для рисования?

Question

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

Несколько вещей, о которых я могу быстро подумать:

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

Образец изображения

Answer 1

Многие реализации выполнены как рекурсивный алгоритм завоевания и разделения. Если вы сделаете быстрый поиск по «алгоритму заливки», вы найдете множество ресурсов, включая отличную страницу википедии по в теме .

Answer 2

Чаще всего используется алгоритм Flood Fill. Ниже приведена наивная версия из моего старого университетского учебника «Компьютерная графика с OpenGL» Хирна Бейкера, 3-е изд:

void floodFill4 (int x, int y, int fillColor, int interiorColor)
{
  int color;

  /* Set current color to fillColor, then perform the following operations */
  getPixel(x, y, color);
  if (color == interiorColor) 
  {
    setPixel(x,y);  // Set color of pixel to fillColor.
    floodFill4(x + 1, y, fillColor, interiorColor);
    floodFill4(x - 1, y, fillColor, interiorColor);
    floodFill4(x, y + 1, fillColor, interiorColor);
    floodFill4(x, y - 1, fillColor, interiorColor);
  }
}

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

Answer 3

Такие алгоритмы подробно обсуждаются в Компьютерная графика: принципы и практика . Я настоятельно рекомендую эту книгу, если вам интересно понять, как растеризовать линии, заполнить многоугольники, написать 3d-код без использования API-интерфейсов DirectX или OpenGL. Конечно, для реальных приложений вам, вероятно, захочется использовать существующие библиотеки, но если вам интересно, как работают эти библиотеки, это отличное чтение.

Answer 4

Общая идея описывается как Алгоритм заполнения потока , и в него есть различные модификации. Распространенным является сканирование по линии. См. Связанный вопрос Как работают движки 2d рендеринга на основе Scanline?

Answer 5

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

Статья в Википедии.

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

Answer 6

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

1) хранение логической памяти о том, какие ячейки вы уже посетили: Vis[]

2) ведение списка пунктов, которые вы уже посетили, но еще не отметили соседей для: Busy[]

3) запустить оба из них как пустые

4) добавить вашу начальную точку к Busy

5)

while you have a point P in Busy:
{
    for each neighbour N of the point P for which Vis[N] is still false
    {
       if appropriate (not crossing the boundary of the fill region)
       {
           set Vis[N] to true
           update the colour of N in the bitmap
           add N to the end of Busy[]
       }
       remove P from Busy[]
    }
}