Ya vimos como saber si dos rectas se intersectan, pero ahora nos interesa saber si dos segmentos lo hacen. Uno de los problemas más conocidos en la geometría computacional es el de encontrar en una colección de segmentos, cuantos y cuales se están intersectando. En esta sección sólo vamos a ver el caso de dos segmentos.

Lo primero que se nos puede ocurrir es modificar el algoritmo anterior y revisar si el punto donde se intersectan está en el segmento. Sin embargo, existe una forma más sencilla y eficiente para este caso.

Para resolver la intersección de dos segmentos, primero consideramos el siguiente problema: dados dos puntos que definen una recta y dos puntos arbitrarios, nos interesa saber si estos últimos están del mismo lado del plano que divide la recta (podemos verlo también como si existe una intersección entre la recta y un segmento). Para resolverlo, nombramos a la distancia entre los dos puntos de la recta como d. Hacemos lo mismo con la distancia de un punto a un punto de la recta, y del segundo punto al otro punto de la recta, llamándolos d₁ y d₂. A las componentes en x las llamaremos dx, dx₁ y dx₂, y a las componentes en y dy, dy₁ y dy₂.

Figura 7.1: Distancias entre los extremos de los segmentos

El resultado de (dxdy₁ - dydx₁) es cero cuando el primer punto está sobre la recta, positivo cuando está de un lado y negativo cuando está del otro. Podemos hacer lo mismo con el segundo punto y si ambos resultados tienen el mismo signo, entonces están en el mismo lado.

Teniendo una función que determina si los puntos están del mismo lado de una recta, podemos saber si dos segmentos se intersectan si primero consideramos a uno como los puntos y al otro como la recta, y después el caso contrario. Si en ambos casos, los puntos están en lados contrarios de la recta, entonces los segmentos se intersectan. El único fallo que tiene este enfoque es en el caso de que los segmentos sean colineales, ya que no distingue si se encuentran separados o no (este caso se puede revisar por separado si se requiere).




Solución: Tenemos un segmento y un rectángulo, que lo podemos ver como cuatro segmentos. Para saber si el segmento intersecta el rectángulo, revisamos la intersección entre el primero con las cuatro secciones del segundo. Existe un caso especial, que es cuando el segmento se encuentra dentro del cuadrado.





Empezamos definiendo la estructura del punto (líneas 1 a 4). En esta ocasión vamos a realizar todos los cálculos con número enteros y no vamos a calcular pendientes, por lo que no necesitamos las constantes. Las variables que vamos a declarar (líneas 6 a 8) son i para los ciclos, n para el número de casos, l1 y l2 para la línea, y c1, c2, c3 y c4 para el rectángulo.

La función lado (líneas 10 a 17) determina si dos puntos están de un mismo lado de una recta. La función es positiva cuando están en el mismo lado, negativa cuando están en lados opuestos y cero cuando son colineales.

Después tenemos la función entre que nos dice si el punto x3 está en el intervalo de x1 a x2. El punto se encuentra en el intervalo si el producto de las diferencias es menor o igual a cero.

Entre las líneas 24 y 28 tenemos la función dentro, con la que determinamos si el punto p3 o el p4 están dentro del rectángulo con esquinas opuestas p1 y p2. Para que un punto esté dentro del rectángulo, la coordenada en x y en y deben estar entre las dos esquinas.

En la función intersecta (líneas 30 a 37), determinamos si dos segmentos se intersectan. Sabemos que se intersectan cuando en ambos casos los puntos están de lados distintos de la recta. Para el caso especial de que los puntos sean colineales, revisamos que alguna de las esquinas de un segmento esté dentro del otro segmento (línea 36).

En la parte principal del código (líneas 39 a 52) comenzamos leyendo la cantidad de casos a procesar. Para cada caso, leemos las coordenadas del segmento y de las esquinas opuestas del rectángulo (línea 43), obtenemos las otras esquinas (línea 44 y 45), revisamos si el segmento intersecta a cualquiera de los lados del rectángulo (líneas 46 y 47) o si el segmento está dentro del rectángulo (línea 48). Terminamos escribiendo si el segmento intersecta o no al rectángulo (líneas 49 y 50).

Entrada:	3 4 9 11 2 1 5 7 1 5 5 5 5 4 4 6 6 0 2 0 3 0 0 1 1
Desarrollo:	intersecta(l1,l2,c1,c3): int1= 3773, int2=  480: false intersecta(l1,l2,c3,c2): int1= 2695, int2=  288: false intersecta(l1,l2,c2,c4): int1=  245, int2= -192: false intersecta(l1,l2,c4,c1): int1=  343, int2= -432: false dentro(c1,c2,l1,l2): false entre(1,7,4) : true; entre(5,1,9): false; entre(1,7,11): false; intersecta(l1,l2,c1,c3): int1=    0, int2=    4: false intersecta(l1,l2,c3,c2): int1=    0, int2=    4: false intersecta(l1,l2,c2,c4): int1=    0, int2=    4: false intersecta(l1,l2,c4,c1): int1=    0, int2=    4: false dentro(c1,c2,l1,l2): true entre(4,6,5) : true; entre(4,5,5): true; intersecta(l1,l2,c1,c3): int1=    0, int2=    0 dentro(l1,l2,c1,c3): false entre(0,0,0) : true; entre(2,3,0): false; entre(0,0,0) : true; entre(2,3,1): false; intersecta(l1,l2,c3,c2): int1=    0, int2=    2: false intersecta(l1,l2,c2,c4): int1=    1, int2=    1: false intersecta(l1,l2,c4,c1): int1=    0, int2=    6: false dentro(c1,c2,l1,l2): false entre(0,1,0) : true; entre(0,1,2): false entre(0,1,0) : true; entre(0,1,3): false
Salida:	F T F

Lenguaje	Fecha	Tiempos [s]				Memoria [Kb]
		Ejecución	Mejor	Mediana	Peor
Pascal	05-Jun-2006	0.000	0.000	0.002	0.541	Minimum
C	13-Jun-2006	0.002				Minimum

Valladollid: