определение вложенности фигур

[asceus]

Здравствуйте, пробую найти способ разделения пересекающихся фигур в 2D плоскости, пример указан во вложенном файле. Известны все координаты фигур. Если у фигур есть точки пересечения или фигура лежит внутри другой фигуры – то эти фигуры тоже пересекающиеся.
В моем примере в итоге эти фигуры должны разделится на три массива
1- фигуры1,2,3,4,5,13,14 ,
2- фигуры 11 и 12 ,
3- фигуры 9 и 10.
Одиночные не пересекающиеся фигуры 6,7,8 не в счет – показал их для примера.
Для решения рассматривал алгоритм сканирующей прямой и алгоритмы проецирования сторон фигур на оси Х и У но они не подходят для ее решения, так как они не помогут разделить эти пересекающиеся фигуры на разные массивы.
Прошу вас подсказать как можно разделить такие фигуры. Спасибо.

[slavav]

Если нужно быстро, то алгоритм Бентли-Оттмана. В простейшем варианте он ищет пересечения отрезков. Есть модификация, которая строит подразбиение плоскости. Это такая структура в которой про каждый участок плоскости можно указать каким многоугольникам он принадлежал изначально. Это сложно, очень сложно.

Более простой алгоритм следущий: пересекаете фигуры попарно. Каждому пересечению сопоставляется ребро в графе, где вершины - сами фигуры. Компоненты связности графа - нужные вам "массивы".

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

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

[asceus]

да, я могу найти пересечения 2 любых фигур например:
фигура 13 с фигурой 14,
2 с 3,
1 с 2,
4 с 3 и т.д.
но, подскажите, пожалуйста, как мне определить , что 1,2,3,4,5,13,14 один общий (граф) массив?

[Null]

Поиск в глубину или ширину.

[asceus]

Null в сообщении #1519410 писал(а):

Поиск в глубину или ширину.

а вы не могли бы поподробнее описать свой ответ. Спасибо.

[slavav]

Поиск в глубину.

[asceus]

спасибо буду изучать

[asceus]

slavav в сообщении #1519399 писал(а):

Более простой алгоритм следущий: пересекаете фигуры попарно. Каждому пересечению сопоставляется ребро в графе, где вершины - сами фигуры. Компоненты связности графа - нужные вам "массивы".

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

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

Сделал по вашему совету определил соседние грани всех графов:
1,2
2,3
3,4
3,13
3,14
13,14
3,5
9,10
11,12
Только непонятно как отделить грани одного графа от другого ведь они у меня находятся в одном массиве? Спасибо.

[slavav]

Запускаете поиск в глубину с любой вершины графа. Когда он закончился, все фигуры из одного "массива" окрашены в чёрный. Удаляете их из графа, повторяете процесс.

[asceus]

slavav в сообщении #1519698 писал(а):

Запускаете поиск в глубину с любой вершины графа. Когда он закончился, все фигуры из одного "массива" окрашены в чёрный. Удаляете их из графа, повторяете процесс.

спасибо - буду пробовать

[Sender]

slavav в сообщении #1519399 писал(а):

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

Для ускорения можно построить BVH-дерево.

[asceus]

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

[slavav]

Это будет преждевременная оптимизация. Но можно. Смотрите предыдущий комментарий про BVH-дерево.

[asceus]

slavav в сообщении #1519873 писал(а):

Это будет преждевременная оптимизация. Но можно. Смотрите предыдущий комментарий про BVH-дерево.

вы не могли поподробнее объяснить ваш ответ - так как непонятно причем тут дерево ?- если я спрашиваю по каким признакам можно отличить одно дерево от другого, не проходя его?

[slavav]

Bounding volume hierarchy. В вашем случае вокруг каждого многоугольника строится ориентированный по осям прямоугольник. Затем эти прямоугольники объединяются в дерево, таким образом что можно быстро понять что два прямоугольника не пересекаются. BVH дерево строится до построения графа или графов.

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

Приведенная оптимизация не меняет О-большое, но может серьезно ускорить построение графа.

Построение полного BVH дерева может улучшить О-большое, так как вы сразу отбрасываете большое количество пар фигур, которые находятся далеко друг от друга, и поэтому для них не нужно обнаруживать пересечения.

Предостережение: это оптимизации, от проверки пересечения фигур и поиска компонент связности в графе они вас не спасут.