Показать сообщение отдельно
  #1  
Старый 23.10.2008, 00:45
Аватар для cotseec
cotseec cotseec вне форума
Активный
 
Регистрация: 16.07.2008
Сообщения: 353
Версия Delphi: D7,TDE06,RAD09
Репутация: 1443
Вопрос Теория графов на практике

Всем доброго...
Имеется задача:
есть массив данных вида A[0..N,0..3]: array of single;
массив содержит максимум 10000 элементов (N<=10000), элементы представляют собой координаты начала и конца отрезков, т.е.

A[0,0]:=X1;
A[0,1]:=Y1;
A[0,2]:=X2;
A[0,3]:=Y2;
...
A[N,0]:=Xn+1;
A[N,1]:=Yn+1;
A[N,2]:=Xn+1;
A[N,3]:=Yn+1;

Вопрос заключается в следующем:
как найти номера отрезков, которые в своей совокупности составляют замкнутую фигуру, причем отрезки, составляющие эту фигуру, могут идти в массиве не друг за другом и не обязательно X1 и Y1 cоответствуют началу отрезка (X1 и Y1 может быть концом отрезка), при этом доподлинно известно, что замкнутая фигура состоит максимум из четырех отрезков.
Вот такая вот задача.
По теории графов (с коей я не особо хорошо знаком) накидал алгоритм, который сводиться к почти тупому перебору, но в этом случае, если N примет свое максимальное значение, то перебор затянется надолго, у кого есть какие мысли на этот счет?
может представлять данные не массивом, а вогнать в базу данных? или еще есть какой-то вариант?

З.Ы. (для понимания определений, используемых в вопросе) считается, что фигура замкнутая, если конец одного отрезка, ее составляющего, является началом другого отрезка, также составляющего эту фигуру и конец последнего отрезка этой фигуры является началом первого отрезка этой фигуры, в данном случае таких отрезков может быть максимум четыре, т.е. фигура может быть, например, квадратом, прямоугольником, трапецией или треугольником
__________________
Понять, что хочет заказчик - бесценно, ведь он платит MasterCard
Ответить с цитированием