Пересечение отрезков

На карте две улицы пересеклись. Если это перекрёсток, в OpenStreetMap у них есть общий узел: машина может повернуть с одной на другую. Если общего узла нет, одна улица проходит над другой — по мосту или в тоннеле, — и у такой дороги должна быть пометка о слое. Ниже все улицы центра Алматы: 6275 линий, 37 316 отрезков между соседними точками. Программа нашла все места, где два отрезка встречаются без общего узла. Коснитесь кружка.

Пар отрезков здесь почти 700 миллионов, а программа посмотрела только на 146 150 — на пары, оказавшиеся в одной клетке сетки, — и точно проверила из них 52 018, у которых пересекаются прямоугольники. Пересечений без общего узла нашлось 166, и все до одного — мосты и тоннели: у пересекающихся улиц разные слои. Ни одного места, где улицы пересеклись бы в одном слое и забыли общий узел, в центре города нет. Зато нашлись две странности другого рода: кусок дороги, нарисованный дважды — два пути OpenStreetMap на одних и тех же двух узлах, — и два разных узла улицы Рыскулбекова в полутора сантиметрах друг от друга. Чтобы всё это найти, мало знать, пересекаются ли два отрезка: нужно понимать, как именно.

Идея

Пересекаются ли отрезки AB и CD, решают четыре векторных произведения: концы каждого отрезка должны лежать по разные стороны от другого. Это разобрано в статье о векторах и ориентации. Здесь следующий шаг: где именно они встречаются и что делать, когда отрезков тысячи.

Запишем отрезки как A + t·r и C + u·s, где r = B − A, s = D − C, а t и u пробегают от 0 до 1. Умножив равенство A + t·r = C + u·s векторно на s, получаем t = (C − A) × s / (r × s), а умножив на r — u = (C − A) × r / (r × s). Отрезки встречаются, если оба числа между 0 и 1. Знаменатель r × s равен нулю, когда отрезки параллельны, — это отдельный случай.

Для целых координат t и u — дроби с общим целым знаменателем, и сравнить их с 0 и 1 можно, не деля: 0 ≤ t_числ ≤ знаменатель. Точка пересечения A + t·r — тоже дробь. По тому, где лежат t и u, видно и как отрезки встречаются: оба строго внутри — крест; один на краю — буква Т; оба на краях — касание концами.

Все случаи

Тащите концы и проверьте каждый случай. Точка пересечения под картинкой записана точно, дробями, и рядом — десятичное приближение.

Когда r × s = 0, отрезки параллельны. Если при этом точка C не на прямой AB, они не встречаются. Если на прямой — все четыре точки на одной прямой, и вопрос сводится к отрезкам на числовой оси: упорядочим концы вдоль прямой по x (а для вертикальной — по y) и сравним. Общий кусок положительной длины — наложение, одна общая точка — касание, иначе зазор. Наложение — не точка, а отрезок, и программа, которая всегда возвращает «точку пересечения», на нём ошибается. В данных Алматы такое наложение одно: тот самый кусок дороги, нарисованный дважды.

Точка — дробь, и большая

Проверка «встречаются ли» в целых числах точна, а точка пересечения — дробь, и её числитель растёт быстро. При координатах до 10⁹ знаменатель r × s доходит до 8·10¹⁸ — на грани int64, а числитель координаты точки — до 10²⁸. В листинге ниже числитель y у отрезков с координатами около миллиарда — 27-значное число. Python считает это сам, в Go нужен math/big.

На практике поступают так: решают «встречаются ли и как» точно, в целых, а саму точку, если она нужна для рисования, считают в double. Наоборот нельзя: если найти точку в числах с плавающей точкой и потом спрашивать, лежит ли она на обоих отрезках, ответ у края решит погрешность — та же ловушка, что у поворота налево или направо. В картах с этим сталкиваются постоянно: у улиц Алматы, переведённых в дециметры, 47 508 пар отрезков касаются в общих узлах, и каждое такое касание — ровно на краю, при t = 0 или t = 1.

Код

Точка пересечения в дробях и все случаи из сцены, а в конце — отрезки с координатами около миллиарда.

А это первая сцена в цифрах: все улицы центра Алматы, сетка из клеток 50 × 50 м и разбор каждой встречи.

Много отрезков: сетка

Проверить все пары из n отрезков — n(n − 1)/2 проверок: для 37 316 отрезков это 696 223 270. Но встретиться могут только отрезки, которые лежат рядом. Разрежем карту на квадратные клетки и запишем каждый отрезок во все клетки, которые задевает его прямоугольник. Два отрезка, у которых есть общая точка, обязательно попадут хотя бы в одну общую клетку — ту, где эта точка лежит. Значит, проверять нужно только пары внутри клеток.

Одна тонкость: длинный отрезок лежит в нескольких клетках, и пара может встретиться не в одной из них. Чтобы не проверять её дважды, договоримся проверять пару только в клетке, где лежит левый нижний угол пересечения их прямоугольников, — он один. Заодно отсекаются пары с непересекающимися прямоугольниками. В листинге выше в общих клетках оказалось 146 150 пар — почти в пять тысяч раз меньше, чем всех, — а точная проверка понадобилась 52 018 из них.

Размер клетки — выбор. Подвигайте ползунок в первой сцене. В мелких клетках пар мало, но каждый отрезок записан во множество клеток, и работа уходит на раскладку: при клетке в 10 м записей в клетках в десять с лишним раз больше, чем самих отрезков. В крупных клетках записей мало, но в каждой — сотни отрезков: при клетке в километр пар в клетках больше шести миллионов, в сорок раз больше, чем при 50 м. Точных проверок при этом всегда одно и то же число: размер клетки решает только, сколько лишнего придётся отбросить. Хорошая клетка — порядка длины типичного отрезка. Сетка — это хеш-таблица, ключ которой — номер клетки, и у неё та же слабость: если отрезки сбились в одну клетку или есть очень длинные, гарантий нет, и в худшем случае снова O(n²).

Гарантию даёт заметающая прямая. Майкл Шеймос и Дэн Хоуи в 1976 году показали, как за O(n log n) узнать, есть ли среди n отрезков хоть одна пересекающаяся пара, а Джон Бентли и Томас Оттман в 1979 году — как найти все k пересечений за O((n + k) log n). Прямая идёт слева направо, держит отрезки, которые она сейчас пересекает, в порядке сверху вниз, и проверяет только соседей в этом порядке. Пересечься могут только отрезки, которые где-то оказались соседями. Этому посвящена отдельная статья.

Сколько это стоит

Одна пара — O(1): несколько умножений и сравнений. n отрезков перебором — O(n²) пар. Сетка — O(n + P), где P — пар в общих клетках; на улицах это сотые доли процента от всех пар, но в худшем случае P растёт как n². Заметающая прямая — O((n + k) log n); множитель k не убрать вовсе — все пересечения нужно хотя бы перечислить, а их бывает до n²/2. Оптимальное время O(n log n + k) даёт алгоритм Бернарда Шазеля и Герберта Эдельсбруннера (1992), но он сложен, и на практике хватает сетки или заметающей прямой.

Где работает

• Проверка карт. Валидатор редактора JOSM ищет дороги, реки и железные дороги, которые пересекаются в одном слое без общего узла, и советует указать слой — и, возможно, мост или тоннель. Ровно это и делает первая сцена; в центре Алматы таких ошибок не нашлось.
• Многоугольники. Прежде чем считать площадь или проверять точку внутри, проверяют, что стороны контура не пересекаются, — иначе обе формулы отвечают не на тот вопрос.
• Игры и роботы. Попала ли пуля в стену, видит ли охранник игрока, не заденет ли робот препятствие на пути — пересечение отрезка пути с отрезками стен, обычно с той же сеткой для отбора кандидатов.
• Чертежи и платы. Дорожки на печатной плате не должны пересекаться, а контуры детали — самопересекаться: программы проверяют это перед изготовлением.

Задачи

В первой задаче нужно найти, где встречаются два отрезка, — точно, дробями, с наложениями и координатами до миллиарда, когда числитель уже не помещается в 64 бита. Во второй — посчитать мосты: сколько пар отрезков среди десятков тысяч пересекаются без общего узла; перебор пар не уложится во время.