---
tags: geometry, polygons
---

# Polígonos

## Definición
:::info
:information_source: **Definición:** Un **polígono** es una figura geométrica plana compuesta por una secuencia finita de segmentos de recta consecutivos que encierran una **región** del plano. Los segmentos se llaman **lados** o **aristas** y los puntos en los que se intersecan son los **vértices**.
:::

## Características
- Todo polígono tiene igual su número de vértices que de lados.
- Cada par de aristas consecutivas forma dos ángulos: el **ángulo interior** y el **ángulo exterior**.
- La suma de los ángulos internos de un polígono de $n$ lados es $180^\circ(n-2)$.
- Podemos ver a los ángulos exteriores como los ángulos que hay que "girar" para trazar el polígono.


## Clasificación
Los polígonos se pueden clasificar de varias maneras de acuerdo a sus propiedades:
- Por su número de lados: triángulo, cuadrilátero, pentágono, ...
- **Simple**: decimos que un polígono es simple si ningún par de aristas se corta, salvo las que son consecutivas en sus vértices. Es decir, su frontera solo tiene un contorno.
- **Convexo**: un polígono es convexo si cualquier segmento que une dos puntos dentro del polígono, cae totalmente dentro del polígono. En caso contrario, decimos que es **cóncavo**. Todos los polígonos simples y con ángulos internos menores o iguales a $180^\circ$ son convexos.


## Representación
Para representar un polígono de $n$ lados en cualquier lenguaje de programación, simplemente almacenamos en un arreglo los puntos de los vértices en orden, comenzando desde un vértice arbitrario. Hay dos formas de hacer lo anterior, podemos guardar dichos puntos en sentido antihorario o en sentido horario.

Si los vértices del polígono son $P_0$, $P_1$, $\ldots$, $P_{n-1}$, podemos considerar que los subíndices se interpretan módulo $n$ para resaltar la naturaleza cíclica del polígono, es decir, $P_n=P_0$, $P_{n+1}=P_1$, $\ldots$ Por lo tanto, en C++ simplemente usaremos ``vector<point>`` o ``point[]``.

Los lados del polígono podemos verlos como los vectores de desplazamiento entre vértices consecutivos, es decir, $\overrightarrow{P_0 P_1}$, $\overrightarrow{P_1 P_2}$, $\ldots$, $\overrightarrow{P_{n-1} P_0}$.


## Verificar si un polígono es convexo
**Problema:** dado un polígono de $n$ vértices, determinar si es convexo o no. Los vértices pueden estar en orden horario o antihorario.

- Imaginemos que caminamos sobre los lados del polígono. En el momento en que lleguemos a un vértice hay que realizar un giro para seguir avanzando por el siguiente lado.
- En un polígono convexo, dichos giros siempre son todos hacia un mismo lado. Si el polígono nos lo dan en sentido antihorario, los giros son a la izquierda. Si nos lo dan en sentido horario, los giros son a la derecha.
- Y también resulta que en un polígono cóncavo siempre habrá al menos un giro a la izquierda y otro a la derecha.
- Por lo tanto, solo hay que verificar que todos los productos cruz entre lados consecutivos tengan el mismo signo.



bool isConvex(vector<point> P){
	int n = P.size();
	bool hasPos = false, hasNeg = false;
	for(int i = 0; i < n; ++i){
		point first = P[(i+1)%n] - P[i];
		point second = P[(i+2)%n] - P[(i+1)%n];
		double sign = first.cross(second);
		if(sign > 0) hasPos = true;
		if(sign < 0) hasNeg = true;
	}
	return !(hasPos && hasNeg);
}

**Pregunta:** ¿qué pasa si tres vértices consecutivos en el polígono están alineados?

:::spoiler **Respuesta**
Si dos aristas están alineadas su producto cruz será 0 y no aportará a los giros positivos ni a los giros negativos. Esto quiere decir que dependerá de las demás aristas determinar si el polígono es convexo o no.
:::

## Perímetro
Hallar el perímetro de un polígono es fácil, solo hay que sumar las longitudes de todas las aristas:

double perimeter(vector<point> P){
	int n = P.size();
	double sum = 0;
	for(int i = 0; i < n; ++i){
		sum += (P[(i+1)%n] - P[i]).length();
	}
	return sum;
}

## Área
Hallar el área de un polígono también es fácil de implementar, pero la idea está muy interesante:
- Ya sabemos hallar el área de cualquier triángulo. Entonces podríamos dividir nuestro polígono en triángulos y sumar todas sus áreas, sin embargo hallar dicha triangulación no es sencillo.
- En lugar de eso, vamos a sumar y restar áreas de triángulos de una forma más astuta. Por ejemplo, consideremos este cuadrilátero:


- Sea $O$ el origen y consideremos los vértices $A,B,C,D$ en orden. Para cada par de puntos consecutivos $P_i$ y $P_{i+1}$, sumaremos el **área signada** del triángulo $\triangle O P_i P_{i+1}$, es decir, $\frac{1}{2} \overrightarrow{P_i} \times \overrightarrow{P_{i+1}}$, a la suma total. Haciendo esto, al final tendremos el área total del polígono. Veamos por qué:


- Los triángulos rojos son los que tienen área negativa y los azules tienen área positiva. De forma informal, las áreas rojas van a "cancelar" de forma exacta el exceso de las áreas azules, dando al final como resultado el área exacta del polígono.
- Este método funciona para cualquier tipo de polígono simple, no importa si es convexo o cóncavo.

double area(vector<point> P){
	int n = P.size();
	double sum = 0;
	for(int i = 0; i < n; ++i){
		sum += P[i].cross(P[(i+1)%n]);
	}
	return abs(sum / 2);
}

**Preguntas**:
1. ¿Qué pasa si usamos otro punto distinto del origen como referencia?
2. ¿Por qué hay que tomar el valor absoluto de la suma final?
3. Si todos los puntos del polígono tienen coordenadas enteras, ¿qué se puede decir sobre el área?

:::spoiler **Respuestas**
1. El área no se altera, ya que el origen fue un punto arbitrario para tomar los vectores de desplazamiento desde ahí a todos los vértices, pero pudo ser cualquier otro. Se escoge el origen para simplificar los cálculos.
2. Si el polígono está orientado en sentido antihorario el área será positiva, y negativa si está orientado en sentido horario. Si podemos asegurar que está orientado en sentido antihorario, no hace falta el valor absoluto. El signo del área antes del valor absoluto nos sirve para obtener la orientación del polígono.
3. El doble del área siempre será un número entero, es decir, el área siempre será un número entero o terminará en .5
:::

:::spoiler **Demostración formal de la fórmula del área**
Podemos parametrizar cada lado del polígono de la siguiente forma: $\vec{r_i} = \vec{P_{i}} + \left(\vec{P_{i+1}} - \vec{P_i}\right)t$, donde $0 \leq i < n$ y $0 \leq t \leq 1$. Sea $\Gamma = \bigcup\limits_{i=0}^{n-1} r_i$ la unión de todos los segmentos, es decir, todo el borde del polígono. El área $A$ del polígono es igual al area encerrada por $\Gamma$, y se puede expresar como una integral de superficie sobre todo el interior del polígono $P$:

$$
A = \iint_P dS
$$

Por el teorema de Green, podemos cambiar una integral de superficie a una de integral cerrada de línea de la siguiente forma: $\displaystyle \oint_\Gamma Mdx + Ndy = \iint_P \left( \dfrac{\partial N}{\partial x} - \dfrac{\partial M}{\partial y} \right) dS$. Queremos lograr que $\displaystyle \dfrac{\partial N}{\partial x} - \dfrac{\partial M}{\partial y} = 1$, una forma de hacerlo es a través de $N=\dfrac{x}{2}$ y $M=-\dfrac{y}{2}$. Por lo tanto:

$$
A = \dfrac{1}{2} \oint_\Gamma (x dy - y dx)
$$

Pero $\Gamma$ es la unión de todos los lados del polígono, entonces podemos partir la integral como una suma de integrales sobre cada lado:

$$
A = \sum_{i=0}^{n-1} \dfrac{1}{2} \oint_{r_i} (x dy - y dx)
$$

Supongamos que el segmento que estamos integrando actualmente es $\vec{r_i}=\vec{a}+(\vec{b}-\vec{a})t$, entonces $x=a_x+(b_x-a_x)t$ y $y=a_y+(b_y-a_y)t$, por lo tanto:

$$
\begin{align}
\dfrac{1}{2} \oint_\Gamma (x dy - y dx) &= \dfrac{1}{2} \int_0^1 \left[ (a_x+(b_x-a_x)t)(b_y-a_y) - (a_y + (b_y-a_y)t)(b_x-a_x) \right] dt \\
&= \dfrac{1}{2}(b_y-a_y) \left[ a_x t + (b_x-a_x)\dfrac{t^2}{2} \right] \Biggr|_0^1 - \dfrac{1}{2}(b_x-a_x) \left[ a_y t + (b_y-a_y)\dfrac{t^2}{2} \right] \Biggr|_0^1 \\
&= \dfrac{1}{2}(b_y-a_y) \left[ a_x + \dfrac{b_x-a_x}{2} \right] - \dfrac{1}{2}(b_x-a_x) \left[ a_y + \dfrac{b_y-a_y}{2} \right] \\
&= \dfrac{1}{4} (b_y-a_y) (a_x+b_x) - \dfrac{1}{4}(b_x-a_x)(a_y+b_y) \\
&= \dfrac{1}{4} (a_x b_y + b_x b_y - a_x a_y - a_y b_x - a_y b_x - b_x b_y + a_x a_y + a_x b_y) \\
&= \dfrac{1}{2}(a_x b_y - a_y b_x) \\
&= \dfrac{1}{2} \left( \vec{a} \times \vec{b} \right)
\end{align}
$$

Finalmente, al sumar todas las contibuciones tenemos que:
$$
\begin{align}
A &= \dfrac{1}{2} \sum_{i=0}^{n-1} \vec{P_i} \times \vec{P_{i+1}}
\end{align}
$$

:::

## Punto en polígono
Dado un polígono $P_0$, $P_1$, $\ldots$, $P_{n-1}$ y un punto $\vec{p}$, determinar si $\vec{p}$ está dentro, en el perímetro o fuera del polígono.

- El problema se simplifica si el polígono es convexo. Simplemente tenemos que sumar las áreas de todos los triángulos que se forman al unir $\vec{p}$ con cada vértice del polígono. Si dicha suma es igual al área del polígono, $\vec{p}$ está dentro o en el perímetro, de lo contrario está $\vec{p}$ fuera.
- Pero el siguiente método, conocido como *ray casting*, funciona para cualquier polígono:
- Vamos a trazar un rayo imaginario (semirrecta) desde $\vec{p}$ que se extienda al infinito a la derecha y contar cuántas veces interseca las aristas del polígono. Si este número es impar, $\vec{p}$ está dentro, si es par, $\vec{p}$ está fuera.

¿Cómo saber si dicho rayo cruza una arista fija, digamos $\overrightarrow{P_i P_{i+1}}$?:
- Una forma es colocar un punto $\vec{q}$ con la misma coordenada en $y$ que $\vec{p}$ y con una coordenada en $x$ muy grande positiva, de tal forma que simulemos el rayo infinito. Después, simplemente podemos llamar a la función de intersección de segmentos para saber si los segmentos $\overrightarrow{P_i P_{i+1}}$ y $\overrightarrow{pq}$ se intersecan.
- Pero una forma más fácil es ver que el rayo va a cruzar la arista si y solo si alguna de estas dos cosas ocurre:
- $P_i$ está debajo, $P_{i+1}$ está arriba y $\overrightarrow{p P_{i+1}}$ está a la izquierda de $\overrightarrow{p P_i}$.
- $P_i$ está arriba, $P_{i+1}$ está debajo y $\overrightarrow{p P_{i+1}}$ está a la derecha de $\overrightarrow{p P_i}$.

- Ejemplo de la primera condición:


En ambos vemos que $P_i$ está debajo del rayo y $P_{i+1}$ está arriba. En el primero vemos que sí hay intersección, pues $\overrightarrow{p P_i} \times \overrightarrow{p P_{i+1}} > 0$. Sin embargo, en el segundo no hay intersección, pues $\overrightarrow{p P_i} \times \overrightarrow{p P_{i+1}} < 0$.

- Ejemplo de la segunda condición:


En ambos vemos que $P_i$ está arriba del rayo y $P_{i+1}$ está abajo. En el primero vemos que sí hay intersección, pues $\overrightarrow{p P_i} \times \overrightarrow{p P_{i+1}} < 0$. Sin embargo, en el segundo no hay intersección, pues $\overrightarrow{p P_i} \times \overrightarrow{p P_{i+1}} > 0$.

- Al momento de implementar esta operación, necesitamos definir bien a qué nos referimos cuando decimos *arriba* y *abajo* del rayo para evitar casos especiales, como por ejemplo, cuando el rayo *toca* un extremo de un segmento. Si $\vec{p}=(p_x, p_y)$, entonces:
- La parte de abajo del rayo es la región $y < p_y$ del plano.
- La parte de arriba del rayo es la región $y \geq p_y$ del plano.
- Antes de verificar si el punto está en el polígono, primero verificaremos si está sobre su perímetro. Esto se logra simplemente iterando sobre todas las aristas y verificando si el punto pertenece a dicho segmento.

Entonces, la implementación queda como:

bool pointInPerimeter(vector<point> & P, const point & p){
	int n = P.size();
	for(int i = 0; i < n; i++){
		if(pointInSegment(P[i], P[(i + 1) % n], p)){
			return true;
		}
	}
	return false;
}

bool crossesRay(const point & a, const point & b, const point & p){
    point v1 = a-p;
    point v2 = b-p;
    if(a.y < p.y && b.y >= p.y && v1.cross(v2) > 0) return true;
    if(a.y >= p.y && b.y < p.y && v1.cross(v2) < 0) return true;
    return false;
}

int pointInPolygon(vector<point> & P, const point & p){
	if(pointInPerimeter(P, p)){
		return -1; //point in the perimeter
	}
	int n = P.size();
	int rays = 0;
	for(int i = 0; i < n; i++){
		rays += crossesRay(P[i], P[(i + 1) % n], p);
	}
	return rays & 1; //0: point outside, 1: point inside
}

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

## Queries de punto en polígono convexo
Dado un polígono **convexo** $P_0$, $P_1$, $\ldots$, $P_{n-1}$ y varios puntos $p_0$, $p_1$, $\ldots$, $p_{m-1}$, determinar para cada punto si pertenece al polígono o no.

Si usamos el algoritmo anterior para cada uno de los puntos, tendríamos una complejidad de $O(mn)$. Pero aprovechando el hecho de que el polígono es convexo, podemos hacer algo mejor:

- Preprocesemos el polígono tal que esté orientado en sentido antihorario y $P_0$ coincida con el punto más a la izquierda (y si hay empate, el que esté más abajo). Es decir, usando el comparador lexicográfico podemos hallar el mínimo punto y rotar la secuencia de vértices del polígono para forzar que ese sea el primero en la lista.
-

## Cortar polígono con una recta

## Convex Hull
:::info
:information_source: **Definición:** Sea $S$ un conjunto de puntos. Definimos al **convex hull** o a la **envolvente convexa** de $S$ como el mínimo subconjunto convexo de $S$ que contiene a todos los puntos de $S$.
:::

Una forma intuitiva de comprender la definición es imaginando que en cada punto de $S$ colocamos un clavo, y después estiramos una banda de goma de tal forma que abarque todos los puntos. Cuando la banda de goma trate de recuperar su forma original, adquirirá la forma del convex hull.


Para hallar el convex hull de un conjunto de $n$ puntos con complejidad $O(n \log n)$, usaremos un algoritmo llamado **Andrew's monotone chain**:
- Ordenamos los puntos de $S$ lexicográficamente: primero por su coordenada en $x$, y en caso de empate, por su coordenada en $y$. De esta manera quedan ordenados como si una línea vertical infinita barriera todo el plano de izquierda a derecha.
- Sea $L$ la parte de abajo del convex hull y $U$ la parte de arriba. Al principio están vacías.
- Para construir $L$ iteramos por todos los puntos de $S$. Sea $S_i$ el punto actual. Mientras la arista que forma el último punto de $L$ y $S_i$ esté a la derecha o sea colineal con la última arista de $L$, quitamos el último punto de $L$. Al final, insertamos $S_i$ a $L$.
- La construcción de $U$ es casi idéntica, solo que aquí iteramos los puntos de $S$ en reversa.
- Quitamos el último punto tanto de $L$ como de $U$, y la respuesta será la unión de $L$ con $U$. Dicha unión será un polígono convexo en orden antihorario.

vector<point> convexHull(vector<point> P){
	vector<point> L, U;
	sort(P.begin(), P.end());
	P.erase(unique(P.begin(), P.end()), P.end());
	int n = P.size();
	if(n <= 2) return P;
	
	for(int i = 0; i < n; ++i){
		while(L.size() >= 2 && (L[L.size()-1] - L[L.size()-2]).cross(P[i] - L[L.size()-1]) <= 0){
			L.pop_back();
		}
		L.push_back(P[i]);
	}
	
	for(int i = n-1; i >= 0; --i){
		while(U.size() >= 2 && (U[U.size()-1] - U[U.size()-2]).cross(P[i] - U[U.size()-1]) <= 0){
			U.pop_back();
		}
		U.push_back(P[i]);
	}
	
	L.pop_back(), U.pop_back();
	L.insert(L.end(), U.begin(), U.end());
	return L;
}