i1 Next = n -1; // check for lower if ( p [i1].y == p [i1Next].y ) // horizontal break; // part
dx1 = fraction2Fixed (p[MNext].x-p[i1].x,
p[i1Next].y-p[i1].y);
}if ( у + 1 == p [i2Next].y ) {
12 = i2Next; // switch to next edge if ( ++i2Next >= n )
i2Next = 0;
// check for lower if ( p [i2].y == p [i2Next].y ) // horizontal break; // part
dx2 = fraction2Fixed (p [i2Next].x - p [i2].x,
p [i2Next].y - p [i2].y );
}
}
}Заполнение произвольного многоугольника, заданного выпуклой ло ей без самопересечений, будем осуществлять методом критических точе Критическая точка - это вершина, у-координата которой или является локальным минимумом или представляет одну точку из последовательного набора точек, образующего локальный минимум. В многоугольнике, представленном на рис. 6.11, критическими точками являются вершины 0, 2 и 5. Алгоритм начинается с построения массива критических точек и его сортировки по v-координате.
6. Растровые алгоритмы
Таблица активных ребер (Active Edge Table - АЕТ) инициализируется как пустая. Далее находятся минимальное и максимальное значения у. Затем для каждой строки очередные критические точки проверяются на принадлежность к этой строке. В случае, если критическая точка лежит на строке, отслеживаются два ребра, идущих от нее вниз, которые затем добавляются в таблицу активных ребер так, чтобы она всегда была отсортирована по возрастанию х. Далее для каждой строки рисуются все отрезки, соединяющие попарные вершины ребер из АЕТ. При этом проверяется, не попала ли нижняя точка какого-либо ребра на сканирующую прямую. Если попала, то ищется ребро, идущее из данной точки вниз. Если это ребро найдено, то оно заменяет собой старое ребро из АЕТ; в противном случае соответствующее ребро из таблицы активных ребер исключается.
У // File fillpoly.cpp
#include <graphics.h> #include <mem.h> #include "fixmath.h" #include «point.h»
struct AETEntry {
int from; // from vertex int to; // to vertex
Fixed x; Fixed dx; int dir;