Форум по Delphi программированию

Delphi Sources



Вернуться   Форум по Delphi программированию > Все о Delphi > Разное
Ник
Пароль
Регистрация <<         Правила форума         >> FAQ Пользователи Календарь Поиск Сообщения за сегодня Все разделы прочитаны

 
 
Опции темы Поиск в этой теме Опции просмотра
  #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
Ответить с цитированием
 


Delphi Sources

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB-коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Быстрый переход


Часовой пояс GMT +3, время: 19:58.


 

Сайт

Форум

FAQ

Соглашения

Прочее

 

Copyright © Форум "Delphi Sources" by BrokenByte Software, 2004-2025