Доброго времени суток, мне требуется коллективный разум. Суть в следующем: имеется документ с описанием нескольких алгоритмов заливки полигона 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-координата конца, но не начала. И ьак получается для любого ребра, по мере прохождения «скан-линии» сверху вниз.
Почему так получается: потому что ребра рисуются по о череди, и в кажой вершине не могут быть одновременно кординаты начала одного и другого ребра(вернее могут, но не в случае выпуклого многоугольника)... Собственно что я упускаю? Растолкуйте :(
