Найти все пересечения в N полигонов

Question

Учитывая N полигонов, которые представлены точками границы, найти всю группу пересекающихся полигонов.

Например, введите [polygon_A, polygon_B, polygon_C, polygon_D], как показано ниже, выведите [(polygon_A, polygon_B), (polygon_B, polygon_C)] (Примечаниечто polygon_A является структурой, которая содержит uniq_ID и list[points].)

Возможно ли, что я могу обрабатывать быстрее, чем O (n ^ 2) (Предполагается, что каждый многоугольник содержит не более 10 точек)

Answer 1

Вы можете рассматривать контуры как наборы независимых отрезков и находить все пересечения, используя (например) технику развёртки.Сложность достигает O((n+k) log n), где k - эффективное число пересечений.

https://en.wikipedia.org/wiki/Line_segment_intersection https://fr.wikipedia.org/wiki/Algorithme_de_Bentley-Ottmann

В вашем случае, если многоугольники компактны и разбросаны,Вы также можете рассмотреть их выровненные по оси ограничивающие рамки и найти перекрытия.Алгоритм O(n log n + k) известен.