[cotseec]

Всем доброго...
Имеется задача:
есть массив данных вида 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 примет свое максимальное значение, то перебор затянется надолго, у кого есть какие мысли на этот счет?
может представлять данные не массивом, а вогнать в базу данных? или еще есть какой-то вариант?

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

[AlexSku]

Для начала лучше перейти от single к integer (как координаты пикселей в Windows), т.к. для сравнения дробей нужно знать точность.

[AlexSku]

Сообщение от cotseec

фигура может быть, например, квадратом, прямоугольником, трапецией или треугольником

Я бы первые три случая (тут ещё ромб, прямоуг. параллелепипед и "кривой" 4-хугольник) объединил в один: четырёхугольник (т.к. нет задачи измерять углы и стороны). Кстати, невыпуклый четырёхугольник (песочные часы) тоже годится?

[cotseec]

Сообщение от AlexSku

Для начала лучше перейти от single к integer (как координаты пикселей в Windows), т.к. для сравнения дробей нужно знать точность.

от single к integer перейти нельзя (из соображений совместимости выходных данных с алгоритмом работы другой программы) такой тип данных выбран не случайно, а по поводу сравнения дробей - введена некоторая ошибка (KoordError), которая определяет точность сравнения. а вообще если отрезки связанные, то координаты конца одного отрезка равны координатам второго отрезка с точностью до последнего знака числа (работа алгоритма, по которому заполняется массив)

Сообщение от AlexSku

Я бы первые три случая (тут ещё ромб, прямоуг. параллелепипед и "кривой" 4-хугольник) объединил в один: четырёхугольник (т.к. нет задачи измерять углы и стороны).

я привел пример фигур, которые считаю замкнутыми (естественно не перечислял все возможные фигуры)

Сообщение от AlexSku

Кстати, невыпуклый четырёхугольник (песочные часы) тоже годится?

годиться любая замкнутая фигура, задача найти четыре (или три) отрезка, которые составят эту фигуру, потом уже можно упражняться во всяких определениях вида фигур

привязываться на определение вида фигуры, на точность равенства координат и прочее не обязательно, смысл в том, чтобы на выходе были номера отрезков, а перебирать все возможные варианты из 10000 отрезков (при полном заполнении массива) долго, в принципе, если иных вариантов нет, то придется использовать алгоритм перебора, просто хотелось бы прочитать мнения на альтернативные возможности решения данной задачи.

вопрос к знатокам SQL запросов: возможно ли составить запрос к базе данных (любой БД, на данный момент не критично), который бы осуществил требуемый поиск средствами БД если данные будут представленны в БД, а не массивом?

[AlexSku]

Вот как раз я и хотел сразу предложить вариант с SQL запросом (только пока не делал, а могу предложить подход). Во-первых, сам цикл писать не надо, пишешь только условия (select ... where <условия>). Конечно, в базе данных будет этот цикл перебора, но всё-таки базу данных писали программисты и математики, поэтому они постарались провести оптимизацию. Во-вторых, (напр. у MS SQL Server) есть анализатор. Если он покажет длинный кусок, можно постараться сделать что-то по-другому. Итак, решение - это формирование промежуточных наборов данных (подзапросов). Сначала можно получить набор отрезков, имеющих ровно одну общую вершину (назовём этот набор "галочки"). Затем из набора галочек получить набор двойных галочек, имеющих общее ребро. Мы почти закончили (для треугольников). Осталось выяснить, чтобы у последнего набора вершина из первого набора галочек совпадала с вершиной из другого набора галочек (обе эти вершины не принадлежат общему ребру). Пример. У галочки ABC и галочки XYZ есть общее ребро (BC = XY) и совпадают вершины A и Z.

[AlexSku]

Ещё добавлю по методологии. Советую запрос сделать только один раз. Потом в базе данных хранить фигуры. Тогда при добавлении данных, фигуры легко можно будет выводить и анализировать их рёбрышки.