Пересечение нескольких сегментов прямой

В вычислительной геометрии задача пересечения нескольких отрезков прямых предоставляет список отрезков прямой в евклидовой плоскости и спрашивает, пересекаются ли какие-либо два из них .

Простые алгоритмы проверяют каждую пару сегментов. Однако если необходимо проверить большое количество потенциально пересекающихся сегментов, это становится все более неэффективным, поскольку большинство пар сегментов не расположены близко друг к другу в типичной входной последовательности. Самый распространенный и более эффективный способ решить эту проблему для большого количества сегментов — использовать алгоритм развертки линии , где мы представляем линию, скользящую по сегментам линии, и отслеживаем, какие сегменты линии она пересекает в каждый момент времени. использование динамической структуры данных на основе двоичных деревьев поиска . Алгоритм Шамоса -Хоуи ^[1] применяет этот принцип для решения проблемы обнаружения пересечения сегментов линии, как указано выше, определения того, имеет ли набор сегментов линии пересечение или нет; Алгоритм Бентли-Оттмана работает по тому же принципу и составляет список всех перекрестков за логарифмическое время на каждое пересечение.

См. также

Алгоритм Бентли – Оттмана

Ссылки

^ Шамос, Мичиган; Хоуи, Д. (1976). «17-й ежегодный симпозиум по основам информатики (sfcs, 1976)» (PDF) : 208. doi : 10.1109/SFCS.1976.16 . S2CID 124804 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь ) Глава: «Геометрические задачи пересечения»

Дальнейшее чтение

Марк де Берг; Марк ван Кревелд; Марк Овермарс; и Отфрид Шварцкопф (2000). Вычислительная геометрия (2-е изд.). Спрингер. ISBN 3-540-65620-0 . Глава 2: Пересечение отрезков прямой, стр. 19–44.
Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 1990. ISBN 0-262-03293-7 . Раздел 33.2: Определение пересечения какой-либо пары сегментов, стр. 934–947.
Дж. Л. Бентли и Т. Оттманн, Алгоритмы сообщения и подсчета геометрических пересечений, IEEE Trans. Вычислить. С28 (1979), 643–647.

Внешние ссылки

Алгоритмы пересечения прямых и плоскостей и пример кода Дэна Сандея
Роберт Плесс. Конспект 4 лекции . Вашингтонский университет в Сент-Луисе , CS 506: Вычислительная геометрия ( кэшированная копия ).
Пересечение отрезков прямой в CGAL , библиотеке алгоритмов вычислительной геометрии
«Пересечение отрезков прямой» . Конспект лекций Джеффа Эриксона
Метод пересечения линий с примером кода C Дэрел Рекс Финли

Эта алгоритмам или структурам данных, статья, посвященная является незавершенной . Вы можете помочь Википедии, расширив ее .

[1] Шамос, Мичиган; Хоуи, Д. (1976). «17-й ежегодный симпозиум по основам информатики (sfcs, 1976)» (PDF) : 208. doi : 10.1109/SFCS.1976.16 . S2CID 124804 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь ) Глава: «Геометрические задачи пересечения»

[1]