Алгоритм определения множества пар видимых ребер между двумя вогнутыми многоугольниками

Question

Допустим, у нас есть два вогнутых 2-мерных полигона (A, B), которые не пересекаются.Задача состоит в том, чтобы найти набор пар ребер (каждая пара состоит из одного ребра из многоугольника A и ребра из многоугольника B), которые имеют следующее свойство: каждый элемент в паре должен быть виден друг другу.Один край виден другому, если между ними нет препятствий (на рисунке есть три случая, отмеченные красным крестом, когда это правило нарушено) между ними.

Я знаю, как решить эту проблему в O (n ^ 2), используя лучи и вершины ребер.Но это слишком медленно.

Answer 1

Не думаю, что это можно сделать быстрее, чем O (n ^ 2).

См. Рисунок ниже.Есть гипербола и два многоугольника.Вершины каждого многоугольника находятся на ветви гиперболы.

В этом случае ребра двух многоугольников видны попарно (кроме двух ребер сзади),Тогда результирующий набор будет содержать O (n ^ 2) пар ребер.