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

Question

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

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

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

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

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

Answer 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)

Answer 2

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

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