Заливка в графическом редакторе. Алгоритм

  В Визуал Бейсике нет готовой функции заливки замкнутого контура произвольной формы. Поэтому заливку, если это необходимо, приходится организовывать поточечно.
  А поскольку графические операции чтения цвета и нанесения отдельной точки на рисунок в сравнении с числовыми математическими операциями в Бейсике проходят медленно*, то экономить время заливки нужно именно на графических операциях, стараясь по возможности исключить повторение этих операций для одной и той же точки.
_________
* время чтения – 7мкс, время нанесения - 5мкс


  Этому условию вполне отвечает алгоритм заливки площадей по строкам, с сохранением в стеке тех разветвлений, которые во время такой заливки возникают. Стек YXXk(5000, 3) содержит строки из 4-х целых чисел. Каждая строка указывает на координаты уже сделанной линии горизонтальной заливки ( Y, X1 начальный, X2 конечный пиксели), и на направление для продолжения заливки ( К = 1 вниз, К = -1 вверх).

  Заливка начинается с прочерчивания линии-затравки, проходящей через указанную стилусом точку. Данные об этой линии вносятся в стек в двух экземплярах – в первом экземпляре продолжение заливки указывается вверх, во втором – вниз. Далее строки из стека начинают считываться в обратном порядке. Ход расчёта поясняется рисунком иллюстрации.

  Считанное значение Y меняется на величину К, и анализируется цвет пикселя с координатой X1 при новом значении Y.
  Если этот цвет совпадает с цветом фона, то расчёт развивается по левой ветви – ищется начало фоновых пикселей слева от X1. Найденный начальный пиксель маркируется значением I1. Затем ищется окончание линейки фоновых пикселей. Это окончание маркируется значением I2. После окончания этого процесса пиксели на линии заполняются активным цветом. Заполнение линии делается не поточечно, а с использованием оператора Line, то есть, за один раз, и это ускоряет заливку.
 
  Если же цвет пикселя X1 не совпадает с цветом фона, то расчёт развивается по правой ветви – начальный пиксель I1 ищется справа от X1.

  Каждый раз, после определения очередной линии заливки, значения X1, X2, I1, I2 анализируются, и в стек записываются новые данные для продолжения заливки, включая возможные пути её разветвления.
  Максимальное поле заливки ограничено полем квадрата плюс, минус 100 пикселей от начальной точки, если этого поля не хватает, то заливку можно повторить.
  Максимальное заполнение стека даже на сложных фигурах не превышает нескольких десятков строк, а размер стека 5000 взят с большим запасом, заполнение 1500 наблюдается только при заливке фона размера 200х200 с очень частыми точками, такими, которые получаются от распылителя программы Паинт.  Время заливки в таких суровых условиях составляет 0.6 секунд. В других же случаях время заливки такого поля не более 0.08 секунд. То есть, на порядок меньше. Мало это или много? Для ручной заливки – прекрасно. Однако для векторной графики, когда нужно заливать несколько десятков графических элементов, поточечно-линейная заливка всё же оказывается довольно медленной.
  И это составляет проблему.

===
После небольшой модернизации метод позволяет делать градиентную заливку, а также фактурную заливку разных сортов - http://proza.ru/2020/11/04/2121

__________
16.10.2020

ПРИЛОЖЕНИЕ
Подпрограмма для заливки контура в среде VB6.

'==========
Public Sub ZAL(XX As Integer, YY As Integer) 'заливка

Dim Xo As Integer, Yo As Integer, Xm As Integer, Ym As Integer
Dim Y As Integer, X1 As Integer, X2 As Integer, K As Integer
Dim I As Integer, I1 As Integer, I2 As Integer, DW As Integer
Dim Ca As Long, Cb As Long, C As Long, P As Integer, Pm As Integer

  Ca = OldC: Cb = Form1.Picture1.Point(XX, YY) 'активный цвет и цвет фона
  If Cb < 0 Or Cb = Ca Then Exit Sub
  DW = Form1.Picture1.DrawWidth: Form1.Picture1.DrawWidth = 1:
  Xo = XX - 100: Xm = XX + 100: Yo = YY - 100: Ym = YY + 100:
  Y = YY: I = XX
2 I = I - 1: If I < Xo Then X1 = Xo: GoTo 3 'делаем линию-затравку ====
  C = Form1.Picture1.Point(I, Y): If C = Cb Then GoTo 2
  X1 = I + 1
3 I = XX
4 I = I + 1: If I > Xm Then X2 = Xm: GoTo 5
  C = Form1.Picture1.Point(I, Y): If C = Cb Then GoTo 4
  X2 = I - 1:
5 Form1.Picture1.Line (X1, Y)-(X2, Y), Ca
 P = 2: YXXk(1, 0) = Y: YXXk(1, 1) = X1: YXXk(1, 2) = X2: YXXk(1, 3) = -1
        YXXk(2, 0) = Y: YXXk(2, 1) = X1: YXXk(2, 2) = X2: YXXk(2, 3) = 1
       'записываем затравку в стек
         
10 If P < 1 Then   ‘показываем максимальное заполнение стека и выходим
     Form1.Picture1.DrawWidth = DW: Form1.Text2 = Str(Pm): Exit Sub
   End If
   If P > Pm Then Pm = P
   K = YXXk(P, 3): Y = YXXk(P, 0) + K: X1 = YXXk(P, 1): X2 = YXXk(P, 2):
   P = P - 1 'читаем из стека
   If Y < Yo Or Y > Ym Then GoTo 10
   I = X1: C = Form1.Picture1.Point(I, Y)
   
   If C = Cb Then 'ищем I1 слева =======================
   'Form1.Picture1.PSet (I, Y), Ca:
12 I = I - 1: If I < Xo Then GoTo 13
   C = Form1.Picture1.Point(I, Y): If C = Cb Then GoTo 12
13 I1 = I + 1: I = X1
14 I = I + 1: If I > Xm Then GoTo 15
   C = Form1.Picture1.Point(I, Y): If C = Cb Then GoTo 14
15 I2 = I - 1
   If I1 < X1 - 1 Then
      P = P + 1: YXXk(P, 0) = Y: YXXk(P, 1) = I1: YXXk(P, 2) = X1 - 2:
                YXXk(P, 3) = -K: End If 'ответвление
   GoTo 26: End If
   
22 I = I + 1: If I > X2 Then GoTo 10 'ищем I1 справа ==================
   C = Form1.Picture1.Point(I, Y)
   If C = Cb Then I1 = I: GoTo 23 Else GoTo 22
23 I = I + 1: If I > Xm Then GoTo 25
   C = Form1.Picture1.Point(I, Y)
   If C = Cb Then GoTo 23
25 I2 = I - 1:
26 If I2 > X2 + 1 Then
     P = P + 1: YXXk(P, 0) = Y: YXXk(P, 1) = X2 + 2: YXXk(P, 2) = I2:
                YXXk(P, 3) = -K: End If 'ответвление
   If X2 > I2 + 1 Then
     P = P + 1: YXXk(P, 0) = Y - K: YXXk(P, 1) = I2 + 1: YXXk(P, 2) = X2:
                YXXk(P, 3) = K: End If 'ответвление
   P = P + 1: YXXk(P, 0) = Y: YXXk(P, 1) = I1: YXXk(P, 2) = I2: YXXk(P, 3) = K 'основной путь
   Form1.Picture1.Line (I1, Y)-(I2 + 1, Y), Ca 'заливаем линию активным цветом
   GoTo 10
End Sub

'================