---
tags: geometry, segments
---

# Segmentos

## Definición
:::info
:information_source: **Definición:** Sean $\vec{a}$ y $\vec{b}$ dos puntos. Definimos al **segmento** de $\vec{a}$ a $\vec{b}$ como $\vec{r} = \vec{a} + t\left(\vec{b} - \vec{a}\right)$, donde $0 \leq t \leq 1$. También podemos escribirlo como $\overrightarrow{ab}$.
:::

Básicamente un segmento es el vector de desplazamiento del punto $\vec{a}$ al punto $\vec{b}$, o bien, la recta que pasa por $\vec{a}$ y $\vec{b}$ limitada desde $t=0$ hasta $t=1$.

## Punto pertenece a segmento
Sea $\overrightarrow{ab}$ un segmento y $\vec{p}$ un punto. Para verificar si $\vec{p}$ pertenece al segmento, se tienen que cumplir dos condiciones:
- Que el punto pertenezca a la recta que pasa por $\vec{a}$ y $\vec{b}$. Ya vimos cómo saber eso: $\overrightarrow{ab} \times \vec{ap} = 0$.
- Que el punto esté justamente entre $\vec{a}$ y $\vec{b}$. Para verificar esto vamos a usar el producto punto: de la figura vemos que si $\vec{p}$ está a la izquierda de $\vec{a}$ o a la derecha de $\vec{b}$, entonces $\overrightarrow{pa} \cdot \overrightarrow{pb} > 0$. Por lo tanto, la condición es $\overrightarrow{pa} \cdot \overrightarrow{pb} \leq 0$.


Por lo tanto, la función queda como:

bool pointInSegment(point a, point b, point p){
	return (b - a).cross(p - a) == 0 && (a - p).dot(b - p) <= 0;
}

**Pregunta:** ¿Qué cambio hay que hacer para verificar que $\vec{p}$ esté *estrictamente* en el segmento $\overrightarrow{ab}$, es decir, que no incluya sus extremos?
:::spoiler **Respuesta**
Cuando $\vec{p}$ coincide con $\vec{a}$ o con $\vec{b}$, se cumple que $\overrightarrow{pa} \cdot \overrightarrow{pb} = 0$. Entonces, hay que cambiar la segunda condición a $\overrightarrow{pa} \cdot \overrightarrow{pb} < 0$.
:::

[**Ejemplo interactivo**](https://www.geogebra.org/classic/px4fsnwg)

## Intersección línea-segmento
Sea $\vec{r} = \vec{a} + t\vec{v}$ una línea y $\overrightarrow{cd}$ un segmento. Para saber si se intersectan, hay varios casos:
- Si ambos son paralelos, es decir, $\vec{v} \times \overrightarrow{cd} = 0$:
- El segmento está contenido totalmente en la recta, es decir, $\vec{v} \times \overrightarrow{ac} = 0$. Aquí hay infinitos puntos de intersección.
- El segmento no está contenido en la recta, es decir, $\vec{v} \times \overrightarrow{ac} \neq 0$. Aquí no hay puntos de intersección.
- Si no son paralelos, es decir, $\vec{v} \times \overrightarrow{cd} \neq 0$, basta ver que $\vec{c}$ esté de un lado de la recta y $\vec{d}$ del otro. O sea, que $\vec{v} \times \overrightarrow{ac}$ y $\vec{v} \times \overrightarrow{ad}$ no tengan el mismo signo.

La mplementación queda como:

int sgn(double x){
	if(x > 0) return 1;
	if(x < 0) return -1;
	return 0;
}
				
int intersectLineSegmentInfo(point a, point v, point c, point d){
	point v2 = d - c;
	double det = v.cross(v2);
	if(det == 0){
		if((c - a).cross(v) == 0){
			return -1; //infinity points
		}else{
			return 0; //no point
		}
	}else{
		return sgn(v.cross(c - a)) != sgn(v.cross(d - a)); // single point (1) or no point (0)
	}
}

Notemos que no hace falta una función adicional para obtener el punto de intersección entre la línea y el segmento, pues asumiendo que su intersección es única, la podemos hallar con la función que ya teníamos ``intersectLines()``.

[**Ejemplo interactivo**](https://www.geogebra.org/classic/dr7y73fr)

## Intersección de segmentos
Sean $\overrightarrow{ab}$ y $\overrightarrow{cd}$ dos segmentos. Para saber si se intersectan hay varios casos:
- Si el segmento $\overrightarrow{cd}$ está completamente del mismo lado que $\overrightarrow{ab}$, es decir, $\overrightarrow{ab} \times \overrightarrow{ac}$ y $\overrightarrow{ab} \times \overrightarrow{ad}$ tienen el mismo signo:
- Si el signo es cero quiere decir que los dos segmentos son paralelos: hay que revisar si algún segmento contiene un extremo del otro segmento. Si esto ocurre, hay infinitos puntos, si no, no se intersectan.
- Si el signo no es cero quiere decir que los segmentos no son paralelos, entonces no hay intersección.
- Si el punto $\vec{c}$ está de un lado del segmento $\overrightarrow{ab}$ y el punto $\vec{d}$ está del otro lado, basta con ver lo opuesto: es decir, que el punto $\vec{a}$ esté de un lado del segmento $\overrightarrow{cd}$ y el punto $\vec{b}$ esté del otro lado, o sea, que $\overrightarrow{cd} \times \overrightarrow{ca}$ y $\overrightarrow{cd} \times \overrightarrow{cb}$ no tengan el mismo signo.

La implementación queda como:

int intersectSegmentsInfo(point a, point b, point c, point d){
	point v1 = b - a, v2 = d - c;
	int t = sgn(v1.cross(c - a)), u = sgn(v1.cross(d - a));
	if(t == u){
		if(t == 0){
			if(pointInSegment(a, b, c) || pointInSegment(a, b, d) || pointInSegment(c, d, a) || pointInSegment(c, d, b)){
				return -1; //infinity points
			}else{
				return 0; //no point
			}
		}else{
			return 0; //no point
		}
	}else{
		return sgn(v2.cross(a - c)) != sgn(v2.cross(b - c)); // single point (1) or no point (0)
	}
}

De nuevo, no hace falta una función extra para obtener el punto de intersección entre ambos segmentos, basta con intersectarlos como si fueran líneas en caso de que exista la intersección y sea única.

[**Ejemplo interactivo**](https://www.geogebra.org/classic/cmpbw9gt)