Есть ли хоть одно пересечение: статус по высоте и проверка соседей

Если ты знаешь, как устроен статус по высоте, почему достаточно проверять соседей и на каких событиях это делать, листай до «Теперь сам».

Как думаешь, кого проверять

Перед тобой 400 отрезков, и надо ответить одним словом: есть ли среди них хоть одна пересекающаяся пара? Перебор - 79 800 пар. Заметающая прямая из прошлого урока здесь не годится как есть: отрезки наклонные, и «статус - набор высот» не работает - отрезки идут под углом, и их порядок по высоте зависит от того, где стоит прямая.

Ответь себе до чтения: если прямая знает порядок отрезков по высоте в точке, где она стоит, - какие пары достаточно проверять? Все пары из статуса? Пары, близкие по высоте? Ответ урока: только соседние, и только в тот момент, когда они становятся соседями. На 400 отрезках это 920 проверок.

На что это похоже

Шоссе с несколькими полосами, все едут слева направо. Две машины могут столкнуться, только оказавшись в соседних полосах: чтобы врезаться в машину через полосу, надо сначала перестроиться к ней - и в этот момент машины станут соседями. Регулировщику не нужно следить за всеми парами машин - достаточно смотреть на соседей, а при каждом перестроении или съезде машины с шоссе проверять новую пару соседей.

Отрезки - машины, порядок по высоте - полосы, концы отрезков - въезды и съезды.

Механизм: статус по высоте и самая левая точка

Статус. В месте, где стоит прямая, каждый активный отрезок имеет высоту, и отрезки упорядочены снизу вверх. Пока они не пересекаются, порядок не меняется - он меняется ровно в точках пересечения. Новый отрезок вставляется по его левому концу p: позицию находит двоичный поиск, сравнение - знак поворота p относительно отрезка статуса (выше или ниже). Это точное сравнение без деления и без вычисления высот.

События и проверки.

левый конец отрезка s:   вставить s в статус;
                         проверить s с соседом снизу и сверху
правый конец отрезка s:  соседи s снизу и сверху становятся соседями -
                         проверить их друг с другом; удалить s
нашли пересечение - ответ «да»;  кончились события - ответ «нет»

Почему соседей достаточно. Пусть пересечения есть, и q - самая левая точка пересечения, отрезков s и t. Чуть левее q других пересечений нет, и порядок в статусе правильный. Если между s и t в статусе кто-то есть, он пересекает прямую между ними и не может дойти до q, не пересекая s или t раньше q, - а раньше пересечений нет. Значит (если в q не сходятся три отрезка - этого нет в общем положении), он кончается до q, и в его правом конце s и t становятся соседями. Если же между ними никого не было с самого начала, они стали соседями при вставке более позднего из них. В любом случае некоторое событие левее q их проверит. (Если q - конец одного из отрезков, это касание; учебная версия считает, что касаний нет, а в полной их ловит проверка «конец на отрезке» при вставке.)

Довод показывает и цену: событий 2n, на каждом - вставка или удаление в статусе и не больше двух проверок. В сбалансированном дереве вставка и удаление стоят log n, итого n · log n.

Правило

Чтобы узнать, есть ли пересечение среди n отрезков, проведи заметающую прямую по концам отрезков и держи статус - активные отрезки по высоте. При вставке проверь новый отрезок с соседями снизу и сверху, при удалении - двух соседей удаляемого друг с другом. Первое найденное пересечение - ответ «да». Время O(n · log n).

Разбор: пересечение, которое видно только после удаления

Пять отрезков. Отрезки 0 и 1 пересекаются, но между ними лежит короткий отрезок 2. В программе статус - обычный список номеров снизу вверх; в настоящей реализации это сбалансированное дерево, а здесь важен порядок событий, а не скорость вставки.

def povorot(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def na_otrezke(a, b, c):
    v_x = min(a[0], b[0]) <= c[0] <= max(a[0], b[0])
    return v_x and min(a[1], b[1]) <= c[1] <= max(a[1], b[1])

def peresekayutsya(s, t):
    a, b = s
    c, d = t
    d1 = povorot(c, d, a)
    d2 = povorot(c, d, b)
    d3 = povorot(a, b, c)
    d4 = povorot(a, b, d)
    if d1 * d2 < 0 and d3 * d4 < 0:
        return True
    if d1 == 0 and na_otrezke(c, d, a):
        return True
    if d2 == 0 and na_otrezke(c, d, b):
        return True
    if d3 == 0 and na_otrezke(a, b, c):
        return True
    return d4 == 0 and na_otrezke(a, b, d)

def est_li(otrezki, zhurnal):
    # отрезки [[x1, y1], [x2, y2]], x1 < x2, вертикальных нет
    sobytiya = []
    for i in range(len(otrezki)):
        a, b = otrezki[i]
        sobytiya.append([a[0], 0, a[1], i])
        sobytiya.append([b[0], 1, b[1], i])
    sobytiya.sort()
    status = []
    proverok = 0
    for x, vid, y, i in sobytiya:
        if vid == 0:
            p = otrezki[i][0]
            lo = 0
            hi = len(status)
            while lo < hi:
                mid = (lo + hi) // 2
                a, b = otrezki[status[mid]]
                if povorot(a, b, p) > 0:
                    lo = mid + 1
                else:
                    hi = mid
            status.insert(lo, i)
            pary = [[lo - 1, lo], [lo, lo + 1]]
        else:
            k = status.index(i)
            status.pop(k)
            pary = [[k - 1, k]]
        for u, v in pary:
            if 0 <= u and v < len(status):
                proverok = proverok + 1
                s = status[u]
                t = status[v]
                if peresekayutsya(otrezki[s], otrezki[t]):
                    return [min(s, t), max(s, t), proverok]
        if zhurnal:
            print(x, ["начало", "конец"][vid], i, status)
    return [-1, -1, proverok]

otrezki = [[[0, 0], [12, 6]], [[2, 8], [12, 0]], [[1, 3], [5, 3]],
           [[3, -2], [11, -1]], [[4, 10], [9, 9]]]
print(est_li(otrezki, True))

0 начало 0 [0]
1 начало 2 [0, 2]
2 начало 1 [0, 2, 1]
3 начало 3 [3, 0, 2, 1]
4 начало 4 [3, 0, 2, 1, 4]
[0, 1, 5]

Строки - события после обработки: координата, вид, отрезок, статус. Отрезок 2 вставлен над 0, отрезок 1 - над 2, и пара 0-1 при этом не проверялась: они не соседи. На событии «конец 2» при x = 5 они стали соседями, проверка нашла пересечение - программа вернула пару 0, 1 после пяти проверок. Строки для этого события в журнале нет: функция вернула ответ раньше, чем дошла до печати.

Поиск позиции при вставке идёт поворотом: p выше отрезка ab, если povorot(a, b, p) > 0. Высот никто не считал - они дробные, а поворот целый.

Разбор: 400 отрезков без пересечений

Самый дорогой случай - ответ «нет»: алгоритм обязан дойти до конца. Сетка 20 × 20 клеток, в каждой свой отрезок, - пересечений нет по построению. Потом добавим один длинный отрезок через половину поля.

def povorot(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def na_otrezke(a, b, c):
    v_x = min(a[0], b[0]) <= c[0] <= max(a[0], b[0])
    return v_x and min(a[1], b[1]) <= c[1] <= max(a[1], b[1])

def peresekayutsya(s, t):
    a, b = s
    c, d = t
    d1 = povorot(c, d, a)
    d2 = povorot(c, d, b)
    d3 = povorot(a, b, c)
    d4 = povorot(a, b, d)
    if d1 * d2 < 0 and d3 * d4 < 0:
        return True
    if d1 == 0 and na_otrezke(c, d, a):
        return True
    if d2 == 0 and na_otrezke(c, d, b):
        return True
    if d3 == 0 and na_otrezke(a, b, c):
        return True
    return d4 == 0 and na_otrezke(a, b, d)

def est_li(otrezki, zhurnal):
    # отрезки [[x1, y1], [x2, y2]], x1 < x2, вертикальных нет
    sobytiya = []
    for i in range(len(otrezki)):
        a, b = otrezki[i]
        sobytiya.append([a[0], 0, a[1], i])
        sobytiya.append([b[0], 1, b[1], i])
    sobytiya.sort()
    status = []
    proverok = 0
    for x, vid, y, i in sobytiya:
        if vid == 0:
            p = otrezki[i][0]
            lo = 0
            hi = len(status)
            while lo < hi:
                mid = (lo + hi) // 2
                a, b = otrezki[status[mid]]
                if povorot(a, b, p) > 0:
                    lo = mid + 1
                else:
                    hi = mid
            status.insert(lo, i)
            pary = [[lo - 1, lo], [lo, lo + 1]]
        else:
            k = status.index(i)
            status.pop(k)
            pary = [[k - 1, k]]
        for u, v in pary:
            if 0 <= u and v < len(status):
                proverok = proverok + 1
                s = status[u]
                t = status[v]
                if peresekayutsya(otrezki[s], otrezki[t]):
                    return [min(s, t), max(s, t), proverok]
        if zhurnal:
            print(x, ["начало", "конец"][vid], i, status)
    return [-1, -1, proverok]

import random
random.seed(8)
otrezki = []
for i in range(20):
    for j in range(20):
        # отрезок внутри своей клетки 50 × 50 - соседей он не заденет
        x1 = 50 * i + random.randint(1, 20)
        x2 = 50 * i + random.randint(30, 49)
        y1 = 50 * j + random.randint(1, 49)
        otrezki.append([[x1, y1], [x2, 50 * j + random.randint(1, 49)]])
n = len(otrezki)
print(n, est_li(otrezki, False), n * (n - 1) // 2)
otrezki.append([[620, 10], [980, 990]])
print(est_li(otrezki, False))

400 [-1, -1, 920] 79800
[240, 400, 585]

Ответ «нет» после 920 проверок соседей - против 79 800 пар у перебора. Длинный отрезок пересекает 12 коротких, а алгоритм остановился на первом найденном - паре 240, 400 - после 585 проверок.

Граница приёма: он отвечает «есть ли», а не «сколько» и не «какие все». Найденная пара - не обязательно самая левая: проверка на событии может поймать и другое пересечение, лежащее правее. Перечислить все пересечения, не скатившись в n², - задача следующего урока.

Что ломается без этого

Сравнение по высоте в float. Высота отрезка на прямой - дробь, и два почти равных значения сравниваются как попало: отрезок вставляется не на своё место, и проверка соседей промахивается. Поворот левого конца относительно отрезка статуса считает то же точно.

Проверка только при вставке. Второй довод - удаление делает соседями тех, кого разделял удалённый отрезок. Без проверки при удалении первый разбор ответил бы «нет».

Общие концы и вертикальные отрезки. Учебная версия считает, что их нет. В настоящих данных они есть: вертикальный отрезок вставляют по нижнему концу, а события с одним x упорядочивают так, чтобы касания в конце ловились, - в учебниках этим тонкостям отводят отдельные абзацы и упражнения.

Зачем это в работе

Проверка «простой ли многоугольник» на миллионе вершин - это ровно эта задача на его рёбрах (с исключением соседних рёбер), и проверка валидности контуров в геобиблиотеках решает её тем же способом: не перебирая пары, а упорядочив рёбра. Редактор карт так же проверяет, не пересекаются ли проведённые границы участков. Трассировщик плат проверяет, что новая дорожка не задевает ни одной из тысяч старых.

Теперь сам

1. Статус снизу вверх: a, b, c, d. Удаляется b. Какую пару надо проверить?
2. Почему при вставке отрезка не нужно проверять его со всеми отрезками статуса, а только с двумя?
3. В первом разборе отрезок 2 убрали из набора. На каком событии найдётся пересечение 0 и 1?