LINUX.ORG.RU

Алгоритм заливки полигона, не могу понять один момент :(

 ,


0

1

Доброго времени суток, мне требуется коллективный разум. Суть в следующем: имеется документ с описанием нескольких алгоритмов заливки полигона http://www.fit.com.ru/Surveys/Course/Lecture_05_Part_2.doc Конкретно разбираю алгоритм построчной заливки с активными рёбрами(пункт 2.2). Для примера, я набросал простейший полигон с тремя вершинами, чтобы было попроще http://itmages.ru/image/view/2415642/8b32f19c Алгоритм по сути состоит из 2 основных этапов:

  • Заполнить список ребёр(вернее информацией о рёбрах) и упорядочить этот список по y1, т.е по у-координате начала ребра.
  • В цикле от верха до низа(по y координате) полигона, если достигли вершины, вычислить список активных рёбер, далее для них найти точки пересечения по оси х и закрасить эти промежутки линиями.

Вроде как всё просто. Проблема заключается в том, что я немного не догоняю, как найти ВСЕ активные рёбра для вершины. Попробую пояснить. По алгоритму(этап II), при достижении вершины полигона, т.е y_curr(тек. позиция скан.линии) = y1( у- координата начала) вершины, это ребро мы добавляем в список активных. Но фишка в том, что в этом случае, в списке акт. ребёр у нас будет всего одно ребро, а не два, как должно быть. Для приведённой картинки, это будет ребро AB, хотя, туда же должно добавиться ребро CA. Потому что, у ребра CA, точка начала, находится в вершине С, а не А, соответственно при сканировании, когда ещё «скан-линия» находится в точке А, координата(у) начала ребра CA ни как не может быть равна y_curr, ей может быть равна y-координата конца, но не начала. И ьак получается для любого ребра, по мере прохождения «скан-линии» сверху вниз.

Почему так получается: потому что ребра рисуются по о череди, и в кажой вершине не могут быть одновременно кординаты начала одного и другого ребра(вернее могут, но не в случае выпуклого многоугольника)... Собственно что я упускаю? Растолкуйте :(

★★★★★

список «активных» ребер (САР), в котором будем хранить информацию обо всех ребрах многоугольника, пересекаемых текущей строкой.

Deleted ()
Ответ на: комментарий от Deleted

Конкретно смутила строка коде на псевоязыке: «Добавить в САР все ребра из y-списка, у которых ребро.y = y, » Т.к в момент, когда сканлиния в вершине, она по сути пересекает только одно ребро(у которого x1 равно y_curr). В этом и суть алгоритма, что когда достигли вершины, перестраиваем таблицу активных ребер(и до следующей вершины работаем только с ними), но ребер активных то одно :) Или при достижении вершины, специально сдвигаться на одну строку вниз и сканировать все рёбра на предмет пересечения, и добавлять в список активных те что пересекаются?

xterro ★★★★★ ()
Ответ на: комментарий от xterro

только одно ребро(у которого x1 равно y_curr)

ты щас что написал?

Deleted ()
Ответ на: комментарий от xterro

ну и что тебя смущает? если не понимаешь алгоритм то тупо пройти его вручную используя бумагу и ручку:

1 итерация. берем точку с максимальным Y - в ней (в примитивном случае) два ребра, значит добавляем оба

....

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

Deleted ()
Ответ на: комментарий от Deleted

Почему с максимальным? Ну вот, например, пойдём по той картинке, которую я нарисовал. 1. Заносим в список все рёбра и упорядочиваем их по y1(по возрастанию, т.е от меньшего к большему). Соответственно, в списке ребер у нас будет AB, CA, BC, в таком порядке(отсортированное) 2.Далее смотрим: «Добавить в САР все ребра из y-списка, у которых ребро.y = y, сохраняя упорядоченность САР по возрастанию x» Хорошо, бежим мы по нашему списку ребёр, но «ребро.y = y» равно только для первого ребра-AB, его то и добавляем в CAP, далее надо вроде как нарисать линию, но рисовать её мы не можем, т.к в CAP только одно ребро.

Судя по алгоритму, второе ребро: CA, будет добавлено в CAP только когда y == C.y, но к этому моменту мы уже половину полигона пробежали и он получается не закрашен.

xterro ★★★★★ ()
Ответ на: комментарий от xterro

«ребро.y = y» равно только для первого ребра-AB

Тебе срочно надо в школу, ты уже хренову тучу часов не можешь понять что достигнув вершины А в твоем рисунке тебе надо брать оба ребра из этой вершины, потому что у них обоих y1 == y_curr

если ты и щас не понял, то я тебе ничем не помогу тут только эфтаназия

Deleted ()

Шикин Е.В., Боресков А.В. - Компьютерная графика. Полигональные модели.

mv ★★★★★ ()
Ответ на: комментарий от Deleted

потому что у них обоих y1 == y_curr

С какой радости?

Например, зададим точки:

poly = TR_Polygon()
poly.add_point(150, 100)  # A
poly.add_point(250, 200)  # B 
poly.add_point(180, 150)  # C 
Соответственно, при отрисовке, т.е идём по списку точек и отрисовываем рёбра в таком порядке:
AB (x1y1-x2y2) : (150, 100) - (250, 200)
BC (x1y1-x2y2) : (250, 200) - (180, 150)
CA (x1y1-x2y2) : (180, 150) - (150, 100)
Как видно, y1 координата начала рёбер AB и CA разная 100 и 150. Или надо как-то по особому рёбра рисовать и располагать в списке? Или проверять координату начала и координату конца ребра? В этом случае ещё можно учесть ребро CA.

xterro ★★★★★ ()
Последнее исправление: xterro (всего исправлений: 1)
Ответ на: комментарий от Deleted

если не понимаешь алгоритм то тупо пройти его вручную используя бумагу и ручку

+1, клетка = пиксель и вперед

I-Love-Microsoft ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.