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

Question

Вот задача, которую я пытаюсь решить:
Для данного многоугольника A с N вершинами и многоугольника B с M вершинами найдите все пересечения между сегментом в A и сегментом в B.
И A, и B могут быть невыпуклыми.

Пока что я реализовал очевидное решение (проверьте каждое ребро в A с каждым ребром в B, O (M * N)).
Теперь для некоторых полигонов фактически возможно, что есть (почти) M * N пересечений, поэтому наихудший случай для любого такого алгоритма - O (M * N).

Мой вопрос:
Существует ли алгоритм определения точек пересечения двух невыпуклых многоугольников со сложностью в среднем случае, который меньше, чем O (N * M)

Если да, то, пожалуйста, дайте мне название алгоритма, если нет - какой-нибудь ресурс, который доказывает, что это невозможно.

Answer 1

Отрывок из статьи о алгоритме обрезки многоугольника Грейнера-Хорманна (PDF) :

... если у нас есть многоугольник с n ребрами и другой с m ребрамиколичество пересечений может быть нм в худшем случае.Таким образом, среднее число пересечений растет порядка O (нм).

Существует хорошо известный результат в вычислительной геометрии, основанный на алгоритме плоской развертки, который говорит, что если есть N отрезков, генерирующих k пересечений, то об этих пересечениях можно сообщить за время O ((N + k) log (N)) [7].Обратите внимание, что в худшем случае это соотношение создает еще худшую сложность.

Я считаю, что N во втором абзаце - это m + n из первого абзаца.Среднее время зависит от среднего значения k, количества пересечений.Если имеется только несколько пересечений, время переходит к O (N log N).

Ссылка на "общеизвестный" результат:

[7] FPПрепарата и М.И. Шамос.Вычислительная геометрия: введение.Тексты и монографии в области компьютерных наук.Springer, Нью-Йорк, 1985.

Вот документ об алгоритме строчной развертки .