#geometry #polygon
#геометрия #полигон
Вопрос:
Вот задача, которую я пытаюсь решить:
Учитывая многоугольник A с N вершинами и многоугольник B с M вершинами, найдите все пересечения между сегментом в A и сегментом в B.
Как A, так и B могут быть невыпуклыми.
На данный момент я реализовал очевидное решение (проверяю каждое ребро в A с каждым ребром в B, O (M * N)).
Итак, для определенных полигонов на самом деле возможно, что существует (почти) M * N пересечений, поэтому наихудший случай для любого такого алгоритма равен O (M * N).
Мой вопрос таков:
Существует ли алгоритм для определения точек пересечения между двумя невыпуклыми многоугольниками со сложностью в среднем случае, которая меньше, чем O (N * M)
Если да, то, пожалуйста, дайте мне название алгоритма, если нет — какой-нибудь ресурс, который доказывает, что это невозможно.
Комментарии:
1. Попробуйте проверить en.wikipedia.org/wiki/Vatti_clipping_algorithm и sourceforge.net/projects/polyclipping
2. Это одно из мест, на которые я смотрел. Я пытаюсь реализовать это, хотя: en.wikipedia.org/wiki/Weiler–Atherton
3. Кроме того, я только что прочитал статью , и кажется, что они делают то же самое, что и me — O (M * N)
Ответ №1:
Выдержка из статьи об алгоритме отсечения полигонов Грейнера-Хорманна (PDF):
… если у нас есть многоугольник с n ребрами, а другой с m ребрами, количество пересечений может составлять nm в наихудшем случае. Таким образом, среднее число пересечений растет порядка O (nm).
В вычислительной геометрии есть хорошо известный результат, основанный на алгоритме развертки плоскости, который гласит, что если существует N отрезков линии, генерирующих k пересечений, то об этих пересечениях можно сообщить за время O ((N k) log(N)) [7]. Обратите внимание, что это соотношение приводит к еще большей сложности в наихудшем случае.
Я полагаю, что N во втором абзаце равно m n из первого абзаца. Среднее время зависит от среднего значения k, количества пересечений. Если пересечений всего несколько, время идет на O (N log N).
Ссылка на «общеизвестный» результат является:
[7] Ф. П. Препаратаи М. И. Шамос. Вычислительная геометрия: введение. Тексты и монографии по информатике. Спрингер, Нью-Йорк, 1985.