Пересечение нескольких отрезков прямой - Multiple line segment intersection - Wikipedia
В вычислительная геометрия, то пересечение нескольких отрезков прямой проблема предоставляет список отрезки линии в Евклидова плоскость и спрашивает, есть ли двое из них пересекаться (Пересекать).
Простые алгоритмы исследуют каждую пару сегментов. Однако, если необходимо проверить большое количество возможно пересекающихся сегментов, это становится все более неэффективным, поскольку большинство пар сегментов не расположены близко друг к другу в типичной входной последовательности. Наиболее распространенный и более эффективный способ решить эту проблему для большого количества сегментов - использовать алгоритм линии развертки, где мы представляем линию, скользящую по сегментам линии, и отслеживаем, какие сегменты линии она пересекает в каждый момент времени, используя динамическую структуру данных на основе деревья двоичного поиска. В Алгоритм Шамоса – Хои[1] применяет этот принцип для решения проблемы обнаружения пересечения линейных сегментов, как указано выше, для определения того, имеет ли набор линейных сегментов пересечение; то Алгоритм Бентли – Оттмана работает по тому же принципу, чтобы перечислить все пересечения в логарифмическом времени за пересечение.
Рекомендации
- ^ Shamos, M. I .; Хои, Д. (1976). "17-й ежегодный симпозиум по основам информатики (sfcs 1976)" (PDF): 208. Дои:10.1109 / SFCS.1976.16. Цитировать журнал требует
| журнал =(помощь) Глава: «Задачи геометрического пересечения»
дальнейшее чтение
- Марк де Берг; Марк ван Кревельд; Марк Овермарс; и Отфрид Шварцкопф (2000). Вычислительная геометрия (2-е изд.). Springer. ISBN 3-540-65620-0. Глава 2: Пересечение отрезков линии, стр. 19–44.
- Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест, и Клиффорд Штайн. Введение в алгоритмы, Второе издание. MIT Press и McGraw-Hill, 1990. ISBN 0-262-03293-7. Раздел 33.2: Определение, пересекаются ли какие-либо пары сегментов, стр. 934–947.
- Дж. Л. Бентли и Т. Оттманн. Алгоритмы составления отчетов и подсчета геометрических пересечений // IEEE Trans. Comput. C28 (1979), 643–647.
внешняя ссылка
- Пересечения линий и плоскостей Алгоритмы и пример кода Дэна Сандэя
- Роберт Плесс. Примечания к лекции 4. Вашингтонский университет в Сент-Луисе, CS 506: Вычислительная геометрия (кешированная копия ).
- Пересечение отрезка прямой в CGAL, Библиотека алгоритмов вычислительной геометрии
- «Пересечение отрезка линии» конспекты лекций Джеффа Эриксона.
- Метод пересечения линий с примером кода C Дарел Рекс Финли
 | Этот алгоритмы или же структуры данных -связанная статья является заглушка. Вы можете помочь Википедии расширяя это. |