Вы просили, скажем, растровый алгоритм, но давайте попробуем обобщить эту проблему.
Давайте предположим, что мы всегда помним схему занятой (красной) области и сохраняем ее в графике, который выглядит как круговой связанный список. Каждый узел имеет координаты (x, y)
. Итак, у нас есть что-то вроде этого:
A2 -- A3 -- A4
/ \
A1 A5
\ /
A7 -------- A6
В то же время мы помним одну точку внутри стартовой области.
Каждый раунд в этой игре начинается где-то на схеме, либо на существующем узле, либо на новом узле между существующими двумя, и заканчивается, когда обнаружено пересечение вектора движения и цепи. Этими узлами являются P
и R
. Весь маршрут, нарисованный в этом раунде, создает новую часть трассы. Вектор движения - это шаг, сделанный «головой» в каждом такте времени.
Начальный узел P
разбивает ребро A3 - A4
на два ребра A3 - P
и P - A4
, которые добавляются к графику. Край A3 - A4
удален с графика.
Каждый шаг движения добавляет следующее ребро: P - B1
, B1 - B2
, ... В конце концов мы обмениваем ребро A6 - A7
на A6 - R
и R - A7
.
После каждого раунда график выглядит так:
B1 -- B2 -- B3
/ \
A2 -- A3 -- P -- A4 B4
/ \ |
A1 A5 |
\ / B5
A7 ------ R --- A6 /
\ /
B7 --------- B6
Теперь пришло время пройтись по графику и собрать посещающие узлы в новую схему. Эта прогулка описана в ряде алгоритмов объединения многоугольников или здесь (шаги 3 и 4).
Когда у нас есть новый контур, мы можем нарисовать его и выполнить заливку, начиная с запомненной точки.