Что такое аккуратный алгоритм для поиска перекрывающихся интервалов?

Я уверен, что этого, должно быть, задавали раньше, но я не нахожу его: я нахожу только связанные, но более сложные вопросы.

У меня есть четыре точки, представляющие две строки:

       A         C      B   D
|------*---|-----+----|-*---+---|----------|
0          10         20        30         40

Итак, в примере AB = {7, 21} и CD = {16,26}. (Линии могут быть в любом отношении друг к другу и в любом размере.) Я хочу выяснить, перекрываются ли они или нет, и насколько это возможно. (В примере ответом будет 5.) Мое текущее решение включает в себя сложную сложную операцию if/then, и я не могу не думать о хорошем арифметическом решении. Есть?

(P.S. Действительно, я делаю пересечение с ограничивающими прямоугольниками, но если я могу получить его в одном измерении, то другое будет очевидно.)

Ответ 1

Попробуйте следующее:

intersects = (max(a,b) > min(c,d)) && (min(a,b) < max(c,d))
overlap = min(max(a,b), max(c,d)) - max(min(c,d), min(a,b))

Если вы можете предположить a <= b и c <= d:

intersects = (b > c) && (a < d)
overlap = min(b, d) - max(c, a)

Вы также можете рассчитать intersects следующим образом:

intersects = (overlap > 0)

Ответ 2

Линейный отрезок - это пересечение двух противоположных лучей (две полубесконечные линии в противоположных направлениях). У вас есть два отрезка линии, чтобы пересечь - результатом является пересечение всех 4 лучей. Таким образом, вы можете указать свой код как три последовательных пересечения лучей: слева от левых лучей, пересекающихся с правым направлением лучей.

(Это еще один способ изложить принятый в настоящее время ответ.)