Закраска области заданной цветом границы

Лекция 23.11.2008

Вычерчивание отрезков (задачи принадлежности).

Необходимость отсечь изображение по границам видимой области встречается часто.

Алгоритм Сизирленда-Кахина для прямоугольника.

Путь область отсечения ограниченна прямоугольником. Определённым:

a1(x1,y2) & a2(x2,y2)

4 линии, образующие прямоугольник, делят плоскость на 9 областей которые можно закодировать тетрадей соде. Каждый бит имеет смысл:

0 - т выше

1- точка выше

2 - точка правее

3 - точка ниже

Тогда для токи на M()€L можно определить тетраду принадлежности прямоугольника.

0000 - точка внутри, иначе вне.

Определение принадлежности точки внутренности многоугольника (любого).

В общем случае многоугольник ограничивается ломаной П1 - пн.

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

Лучше горизонтальный/вертикальный луч.

Тогда:

Вариант А: луч не проходит через вершину, то условие принадлежности - нечётное число пресечений луча со сторонами многоугольника, если чётное - точка вне многоугольника.

Вариант Б: луч проходит через вершину, то возможны варианты.

М и м2 - простые случаи: ребра выходящие из вершины лежат по одну сторону луча (М1) - четность инвертируется и либо по разные стороны - чётность сохранена и определяется только нижним ребром (экстремальный случай). Для м3 и м4 такой подход не годится и требуется заменить луч( на перпендикулярный или в обратном направлении)

Алгоритм в общем виде:

- все отрезки ломанной, кроме горизонтальных проверяются на пересечение с горизонтальным лучом из точки М.

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

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

1. Алгоритм "растекания цвета":

1) Организовать цикл закраски пикселей до достижения границ области

2) Закрасить пиксели М(ху) заданным цветом

3) Закрасить соседние пиксели в смысле 4-х 8-мисвязности

Неэффективен, так как для уже закрашенного пикселя функция закраски выполняется >=3 раз

2. Алгоритм "штриховка"

1) Для заданной точки М определить и закрасить максимальный горизонтальный отрезок внутри области

2) Проверить отрезки выше и ниже в поисках незакрашеных пикселей

3) Если пиксели найдены то пункт 1)

Алгоритм работает эффективно для области любой формы