Заполнение многоугольников. Алгоритмы заполнения по ребрам, с перегородкой, со списком ребер и флагом.
Алгоритм по рёбрам
фон = -закраска; закраска = -фон. Для каждой сканирующей строки, пересекающей ребро многоугольника, дополнить все пиксели, лежащие правее точки пересечения. Недостаток – каждый пиксель может перекрашиваться много раз.
Алгоритм с перегородкой
Для сокращения числа обрабатываемых пикселов используется ″перегородка". Рекомендуется проводить перегородку через одну из вершин многоугольника.
Если точка пересечения сканирующей строки с ребром лежит левее перегородки, то дополнить все пиксели правее точки пересечения, но левее перегородки. Если правее – дополнить левее пересечения, но правее перегородки.Недостатком алгоритма заполнения с перегородкой все же остается неоднократная обработка части пикселов.
Для того чтобы избавиться от этого, разработан модифицированный алгоритм заполнения сплошной области со списком ребер и флагом.
В обоих алгоритмах очерчивание границ не нужно.
Алгоритм с флагом
- Обработка ребер многоугольника, ограничивающего заполняемую область. Также, как в предыдущих алгоритмах, считается, что строки сканирования проходят через центр строк пикселов, то есть через середину интервала y. После определения пересечений вычисляем самый левый пиксел, расположенный правее точки пересечения, у которого абсцисса x больше абсциссы точки пересечения.
- Заполнение области. Для каждой строки сканирования, имеющей точки пересечения с многоугольником, ограничивающим область, выполняется следующая последовательность действий:
а) f=0, (f-промежуточная переменная (флаг), показывающая расположение очередного пиксела: fl=0 - пиксел лежит вне области заполнения, fl=1 - пиксел лежит внутри заполняемой области);
x=xl (xl - левая граница);
б) пока (x<=xr ) (xr - правая граница) выполнить следующие действия:
* если пиксел (x,y) имеет граничное значение , то проинвертировать значение переменной f (f=0, если было f=1; f=1, если было f=0);
* если f=1, то присвоить пикселу (x,y) цвет многоугольника, в противном случае, присвоить пикселу (x,y) цвет фона;
x=x+1.
в) переход к следующей сканирующей строке y=y+1.
Алгоритм заполнения с затравкой, простой алгоритм заполнения с затравкой.
|
|
|
Необходимо:
Задать область и координаты точки внутри области. Рассматриваются пиксели, соседние с данным. Используется стек.
Простой алогритм
- Задание исходных данных
- Поместить затравочный пиксель в стек
- Пока стек не пуст
- Извлечь (xy) из стека
- Цвет(xy)≠Закраска -> Цвет(xy):=Закраска
- Анализ 4 соседних пикселей. Цвет≠Закраска и Цвет≠Граница -> пиксель в стек
Алгоритмы заполнения с затравкой. Построчный алгоритм заполнения с затравкой.
|
|
|
Построчный алгоритм
Основное отличие от простого – ограниченное количество пикселей в стеке. Непрерывный интервал пикселей – группа прилегающих друг к другу пикселей, незакарашенных и неграничных, которые ограничены закрашенными или граничными пикселями. В стек помещается 1 пиксель группы.
pix = QPixmap()
paint = QPainter()
paint.begin(win.image)
stack = []
edge = QColor(0, 0, 255).rgb()
fill = QColor(0, 0, 0).rgb()
#paint.setPen(QPen(fill))
z = QPointF(win.p_x.value(), win.p_y.value())
stack.append(z)
# пока стек не пуст
while stack:
# извлечение пикселя (х,у) из стека
p = stack.pop()
x = p.x()
y = p.y()
# tx = x, запоминаем абсицссу
xt = p.x()
Fl = 0
# цвет(х,у) = цвет закраски
win.image.setPixel(x, y, fill)
# заполняем интервал слева от затравки
x = x - 1
while win.image.pixel(x, y) != edge:
win.image.setPixel(x, y, fill)
x = x - 1
# сохраняем крайний слева пиксел
xl = x + 1
x = xt
# заполняем интервал справа от затравки
x = x + 1
while win.image.pixel(x, y) != edge:
win.image.setPixel(x, y, fill)
x = x + 1
# сохраняем крайний справа пиксел
xr = x - 1
y = y + 1
x = xl
# ищем затравку на строке выше
while x <= xr:
Fl = 0
while win.image.pixel(x, y) != edge and win.image.pixel(x, y) != fill and x <= xr:
if Fl == 0:
Fl = 1
x = x + 1
if Fl == 1:
if x == xr and win.image.pixel(x, y) != fill and win.image.pixel(x, y) != edge:
|
|
|
stack.append(QPointF(x, y))
else:
stack.append(QPointF(x - 1, y))
Fl = 0
xt = x
while (win.image.pixel(x, y) == edge or win.image.pixel(x, y) == fill) and x < xr:
x = x + 1
if x == xt:
x = x + 1
y = y - 2
x = xl
while x <= xr:
Fl = 0
while win.image.pixel(x, y) != edge and win.image.pixel(x, y) != fill and x <= xr:
if Fl == 0:
Fl = 1
x = x + 1
if Fl == 1:
if x == xr and win.image.pixel(x, y) != fill and win.image.pixel(x, y) != edge:
stack.append(QPointF(x, y))
else:
stack.append(QPointF(x - 1, y))
Fl = 0
xt = x
while (win.image.pixel(x, y) == edge or win.image.pixel(x, y) == fill) and x < xr:
x = x + 1
if x == xt:
x = x + 1`
Дата добавления: 2019-01-14; просмотров: 1012; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!