Пересекаются ли два отрезка: четыре поворота и края

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

Как думаешь, пересекаются ли

Три пары отрезков:

1.  (0, 0)-(4, 4)   и   (0, 4)-(4, 0)
2.  (0, 0)-(4, 0)   и   (2, 0)-(2, 5)
3.  (0, 0)-(5, 5)   и   (2, 2)-(8, 8)

Первая пара - очевидный крест. Во второй вертикальный отрезок стоит на горизонтальном, как буква Т вверх ногами. В третьей два отрезка лежат на одной прямой и накрывают друг друга на участке от (2, 2) до (5, 5). Ответь себе: пересекаются ли отрезки во второй и третьей паре? И что скажет проверка «концы одного по разные стороны от другого»?

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

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

Две дороги на карте. Как понять, есть ли перекрёсток, не вычисляя его координат? Встань на первую дорогу и посмотри: начало второй дороги слева, конец справа - значит, вторая дорога где-то переходит через линию первой. Но линия первой дороги бесконечна, а сама дорога - нет: переход может случиться за её концом. Поэтому то же самое делают с другой стороны: встают на вторую дорогу и смотрят на концы первой. Если обе дороги «перерезают» линии друг друга - перекрёсток есть.

Механизм: две пары знаков и три края

Обозначим четыре поворота:

d1 = поворот(C, D, A)      d3 = поворот(A, B, C)
d2 = поворот(C, D, B)      d4 = поворот(A, B, D)

Общий случай. Если у d1 и d2 разные знаки (один плюс, другой минус) и у d3 и d4 разные знаки, отрезки пересекаются в одной точке, которая не совпадает ни с одним концом. Каждая пара отвечает за свою половину условия: d1, d2 - что AB пересекает прямую CD, d3, d4 - что CD пересекает прямую AB. Два «перерезания» вместе дают точку, лежащую на обоих отрезках.

Края. Если какой-то поворот равен нулю, соответствующий конец лежит на прямой другого отрезка. На отрезке он или за его концом - решает проверка координат из прошлого урока: обе координаты точки между координатами концов. Это и есть три вида краёв:

• конец одного отрезка лежит на другом - буква Т или общий конец;
• отрезки на одной прямой и накрывают друг друга - все четыре поворота нули, и хотя бы один конец лежит на другом отрезке;
• отрезки на одной прямой и не касаются - все четыре нули, но ни один конец не лежит на другом.

Правило

Отрезки AB и CD пересекаются, если выполнено одно из двух: d1, d2 разных знаков и d3, d4 разных знаков (крест) - или какой-то из четырёх поворотов равен нулю и соответствующий конец лежит на другом отрезке (касание или наложение). Других случаев нет. Точку пересечения считают дробью A + t · (B − A), где t = ((C − A) × (D − C)) / ((B − A) × (D − C)).

Разбор: семь пар и наивная проверка

peresekayutsya - правило целиком, naivno - только общий случай, без краёв.

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

def znak(z):
    if z > 0:
        return 1
    if z < 0:
        return -1
    return 0

def na_otrezke(a, b, c):
    # зовётся, только когда поворот уже равен нулю: c на прямой ab
    v_x = min(a[0], b[0]) <= c[0] <= max(a[0], b[0])
    v_y = min(a[1], b[1]) <= c[1] <= max(a[1], b[1])
    return v_x and v_y

def peresekayutsya(a, b, c, d):
    d1 = znak(povorot(c, d, a))
    d2 = znak(povorot(c, d, b))
    d3 = znak(povorot(a, b, c))
    d4 = znak(povorot(a, b, d))
    if d1 * d2 < 0 and d3 * d4 < 0:
        return "крест"
    if d1 == 0 and na_otrezke(c, d, a):
        return "касание"
    if d2 == 0 and na_otrezke(c, d, b):
        return "касание"
    if d3 == 0 and na_otrezke(a, b, c):
        return "касание"
    if d4 == 0 and na_otrezke(a, b, d):
        return "касание"
    return "нет"

def naivno(a, b, c, d):
    d1 = povorot(c, d, a)
    d2 = povorot(c, d, b)
    d3 = povorot(a, b, c)
    d4 = povorot(a, b, d)
    return d1 * d2 < 0 and d3 * d4 < 0

pary = [
    [[0, 0], [4, 4], [0, 4], [4, 0]],
    [[0, 0], [4, 4], [5, 0], [9, 3]],
    [[0, 0], [4, 0], [2, 0], [2, 5]],
    [[0, 0], [4, 0], [4, 0], [7, 3]],
    [[0, 0], [5, 5], [2, 2], [8, 8]],
    [[0, 0], [2, 2], [3, 3], [5, 5]],
    [[0, 0], [4, 2], [0, 1], [4, 3]],
]
for p in pary:
    a, b, c, d = p
    print(peresekayutsya(a, b, c, d), naivno(a, b, c, d))

крест True
нет False
касание False
касание False
касание False
нет False
нет False

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

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

Разбор: точка пересечения - дробь

Когда пересечение - крест (отрезки не параллельны), его точку находят из уравнения A + t · (B − A) = C + s · (D − C). Умножим обе части векторно на D − C: слагаемое с s исчезнет, потому что вектор, умноженный на самого себя, даёт ноль. Останется t · ((B − A) × (D − C)) = (C − A) × (D − C) - отсюда формула для t в правиле. Числитель и знаменатель целые, сама t - дробь. Если знаменатель равен нулю, отрезки параллельны: общих точек либо нет, либо это целый отрезок наложения - его концы ищут проверкой «конец на отрезке».

def vekt(u, v):
    return u[0] * v[1] - u[1] * v[0]

def nod(a, b):
    a = abs(a)
    b = abs(b)
    while b > 0:
        a, b = b, a % b
    return a

a = [2, 0]
b = [9, 6]
c = [7, 4]
d = [8, 9]
ab = [b[0] - a[0], b[1] - a[1]]
cd = [d[0] - c[0], d[1] - c[1]]
ac = [c[0] - a[0], c[1] - a[1]]
chisl = vekt(ac, cd)
znam = vekt(ab, cd)
print(chisl, znam)
x = a[0] + ab[0] * chisl / znam
y = a[1] + ab[1] * chisl / znam
print(x, y)
print((d[0] - c[0]) * (y - c[1]) - (d[1] - c[1]) * (x - c[0]))
# та же точка без деления: X = xc / znam, Y = yc / znam
xc = a[0] * znam + ab[0] * chisl
yc = a[1] * znam + ab[1] * chisl
g = nod(nod(xc, yc), znam)
print(xc // g, yc // g, znam // g)
cz = [c[0] * znam, c[1] * znam]
dz = [d[0] * znam, d[1] * znam]
print((dz[0] - cz[0]) * (yc - cz[1]) - (dz[1] - cz[1]) * (xc - cz[0]))

21 29
7.068965517241379 4.344827586206897
1.7763568394002505e-15
205 126 29
0

t = 21 / 29, точка (205/29, 126/29). Третья строка - проверка «лежит ли найденная точка на прямой CD» в float: ответ не ноль, а 1,8 · 10⁻¹⁵. По этому числу точка лежит СЛЕВА от прямой, хотя на самом деле лежит на ней: 205/29 нельзя записать двоичной дробью конечной длины, и округление сдвинуло её на крупинку. Последняя строка делает ту же проверку целиком в целых: все координаты умножены на знаменатель 29, и поворот равен ровно нулю.

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

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

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

Проверка по ограничивающим прямоугольникам. Перекрытие рамок - быстрый фильтр, а не ответ: диагонали (0, 0)-(4, 4) и (3, 0)-(4, 1) имеют пересекающиеся рамки и не пересекаются. Рамки годятся, чтобы быстро отбросить далёкие пары, а решение принимают повороты.

Сравнение float с нулём. Как в разборе: точка, вычисленная делением, «не лежит» на своей же прямой. Вместо == 0 начинают писать abs(...) < 1e-9, и это тихо ломает другие места - урок о точности разберёт почему.

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

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

На сотне рёбер достаточно перебрать все пары: это пять тысяч проверок по четыре поворота. На миллионе рёбер пар 5 · 10¹¹, и перебор уже не годится - для этого существует заметающая прямаяРазбирается в разделе 23, глава «Заметающая прямая - пересечения отрезков и двойственность»: Заметающая прямая: события, статус и одномерная разминка, которой посвящена глава о пересечениях отрезковРазбирается в разделе 23, глава «Заметающая прямая - пересечения отрезков и двойственность»: Есть ли хоть одно пересечение: статус по высоте и проверка соседей.

Теперь сам

1. Пересекаются ли (0, 0)-(6, 3) и (2, 3)-(4, 0)? Посчитай d1 … d4.
2. (1, 1)-(3, 3) и (3, 3)-(5, 1). Что вернёт наивная проверка и что верная?
3. Отрезки (0, 0)-(4, 0) и (5, 0)-(9, 0). Все четыре поворота нули. Почему ответ «нет»?