Найти перекрывающиеся выпуклые многоугольники

Question

У меня есть набор выпуклых многоугольников с умеренным числом сторон (скажем, от 4 до 30). Есть несколько десятых полигонов, скажем, от 100 до 1000. Большинство из них изолированы, но некоторые образуют небольшие группы от 2 до 10, которые пересекаются между ними.

Мне нужно эффективно идентифицировать эти группы перекрывающихся полигонов.

Есть ли классический алгоритм? (Я думаю о подходе с разметкой, но, может быть, есть и лучшее?) Было бы полезно заключить полигоны в коробки перед обнаружением?

Ниже представлен репрезентативный случай.

Answer 1

Один из традиционных подходов, который используется для решения этой проблемы в двух измерениях, - это создание квадродерева, которое иерархически делит ваше 2D-пространство на последовательно меньшие сегменты, пока в каждом блоке не будет небольшое количество объектов.

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

Здесь есть простое введение в построение и использование их для обнаружения столкновений: Быстрый совет: Используйте Quadtrees для обнаружения вероятных столкновений в 2D пространстве

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

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