Здравствуйте, уважаемые эксперты. Постигая азы компьютерной графики столкнулся с такой проблемой:
Существует алгоритм закраски многоугольника, как раз с этим алгоритмом, точнее с его реализацией и возникли трудности.
Я написал программу, которая, по идее, должна закрасить треугольник, но она некорректно работает.

Если я правльно разобрался, то алгоритм состоит из 3 шагов: на первом шаге ищутся точки пересечения сканирующей строки с ребрами, причем, как я понял можно искать точки пересечения сначала для первого ребра, потом для второго и т.д. ( как написано в книге Роджерса "Алгоритмечесие основы растровой графики" или Иванова и соавт. "алгоритмические основы растровой машинной графики" ), а можно найти точки пересечения сканирующей строки сразу со всеми ребрами ( что и рекомендует сделать Сиденко "Компьютерная графика и геометрическое моделирование" и Порев "Компьютерная графика" ). Я выбрал первый вариант, а чтоб уж было совсем просто отслеживать шаги выполнения программы, то в качестве многоугольника выбрал прямоугольный треугольник. И для каждого ребра занес х-координаты точек пересечения в массив.
На 2 шаге отсорировал массив, содержащий координаты точек в неубывающем порядке.
Ну, а на 3 шаге, вывел координаты тех линий, которые, по идее, должны закрасить треугольник. Разумеется координаты не верны.
С одной стороны, если создать два массива и заносить в первый массив х-координаты пересечения сканирующей строки с первым ребром, а во второй со вторым, а потом на 3 шаге выводить линию, взяв первую х-координату из первого массива, а второй х-координту из второго массива, то программа работает корректно, для данного случая, но ведь это не выход, ибо, если, скажем, будет 10 ребер, то в функцию надо будет дописать 10 массивов...
С другой стороны, что-то мне подсазыват, что надо использовать двумерный массив, который и будет являться той самой таблицей ребер, где в строке будет находиться y-координата сканирующей строки, а в столбце - x-координаты пересечения данной сканирующей строки с ребрами, но ведь двумерный массив необходимо инициализировать заранее, что весьма трудно, так как неизвестно число сканирующих строк...

Собственно мой вопрос в следующем: как мне реализовать таблицу ребер. Заранее спасибо.



Приложение:
#include <algorithm>
#include <vector>
#include <numeric>
#include <windows.h>
#include <set>
#include <map>
#include <cmath>
#include <list>

using namespace std;
void FillPoly( POINT p[],const int size, COLORREF col = RGB(0,0,0) )
{

vector<int> x_coord; // массив для хранения x координат точек пересечения

// шаг 1 поиск тт пересечений сканирующей строки с ребрами
// тт. пересечения с первым ребром

float dx = float ( p[1].x - p[0].x )/ ( p[1].y - p[0].y );
float scan_line = p[0].y;
float x = p[0].x;

while ( scan_line <= p[1].y )
{
x_coord.push_back(x);
x += dx;
scan_line++;
}
// тт. пересечения с третьим ребром ( 2 ребро горизональное - нет тт пересечения )
dx = float ( p[2].x - p[0].x )/ ( p[2].y - p[0].y );
scan_line = p[0].y;
x = p[0].x;

while ( scan_line <= p[2].y )
{
x_coord.push_back(x);
x += dx;
scan_line++;
}

// шаг 2 сортировка точек перечения в возрастающем порядке
sort ( x_coord.begin(), x_coord.end() );

// шаг 3 закраска многоугольника ( треугольника)
// начать заливку от минимальной у координаты
// до максимальной
scan_line = p[0].y;
cout << "Fill poly" << endl;
while ( scan_line <= p[2].y )
{
cout << " from: (" << x_coord[scan_line] << ", " << scan_line << ")";
cout << " to: (" << x_coord[scan_line+1] << ", " << scan_line << ")" <<endl;
scan_line++;
}


}
int main()
{
POINT pt[3] = { 1, 1, 1, 8, 5, 8 };
FillPoly( pt, 3 );

return 0;
}