¿Qué es un algoritmo ordenado para encontrar intervalos superpuestos?

Question

Estoy seguro de que esto debe haberse preguntado antes, pero no lo estoy encontrando: solo estoy encontrando preguntas relacionadas, pero más difíciles.

Tengo cuatro puntos, lo que representa dos líneas de este tipo:

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

Así, en el ejemplo, AB = {7, 21} y CD = {16,26}. (Las líneas podrían estar en cualquier relación entre sí, y de cualquier tamaño.) Quiero saber si se superponen o no, y por cuánto si es así. (En el ejemplo, la respuesta sería 5.) Mi solución actual implica un montón de pasos complicados si/entonces, y no puedo evitar pensar que hay una buena solución aritmética. ¿Esta ahí?

(Sal. En realidad, estoy haciendo cuadro delimitador intersección, pero si lo puedo conseguir en una sola dimensión, el otro será el mismo, obviamente)

Answer 1

Prueba esto:

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

Si se puede suponer a <= b y c <= d:

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

también puede calcular intersects de la siguiente manera:

intersects = (overlap > 0) 

Answer 2

Un segmento de línea es la intersección de dos rayos opuestos (dos líneas de medio infinito en direcciones opuestas). Tienes dos segmentos de línea para intersecar, el resultado es la intersección de los 4 rayos. Por lo tanto, puede factorizar su código como tres intersecciones de rayos sucesivas: la izquierda de los rayos orientados hacia la izquierda se cruzan con la derecha de los rayos orientados hacia la derecha.

(Esta es otra forma de expresar la respuesta aceptada ahora.)