Расстояние между двумя полилиниями

Ответ 1

Разделить и победить:

• Определите структуру данных, представляющую пару полилиний, и минимальное расстояние между их ориентированными по оси минимальными ограничивающими прямоугольниками (AAMBB): pair = (poly_a, poly_b, d_ab))

• Создайте пустую очередь для pair данных, используя расстояние d_ab в качестве ключа.

• Создайте структуру данных pair с исходными полилиниями и вставьте ее в очередь.

• Мы сохраним переменную с минимальным расстоянием между найденными до сих пор полилиниями (min_d). Установите его в бесконечное.

• Повтор:

  • Вывести из очереди элемент с минимальным расстоянием d_ab.

  • Если d_ab больше, чем min_d, мы закончили.

  • Если какая-либо из полилиний poly_a или poly_b содержит единственный отрезок:

    • Используйте грубую силу, чтобы найти минимальное расстояние между ними и обновить min_d соответственно.

  • В противном случае:

    • Разделите обе полилинии poly_a и poly_b пополам, например:

      (1-7) --> { (1-4), (4-7) }

      (8-12) --> { (8-10), (10-12) }

    • Сделайте кросс-произведение обоих наборов, создайте 4 новые структуры данных pair и затем вставьте в очередь Q.

В среднем случае сложность O (N * log N), худшим случаем может быть O (N²).

Обновить:

Ответ 2

"Стандартным" способом для таких задач является построение диаграммы Вороного геометрических объектов. Это можно сделать за время O (N Log N).

Но построение таких диаграмм для сегментов линии сложно, и вы должны прибегать к готовым решениям, таким как CGAL. ​​