---
tags: geometry, cross-product
---

# Producto cruz

## Definición
El otro "producto" entre vectores es el producto cruz. Tiene muchas propiedades interesantes además de las que nos da el producto punto, pero primero hay que definirlo:

:::info
:information_source: **Definición:** Sean $\vec{a}=(a_x, a_y)$ y $\vec{b}=(b_x, b_y)$ dos vectores. Definimos al **producto cruz** de $\vec{a}$ con $\vec{b}$ como:
$$
\vec{a} \times \vec{b} = a_x b_y - a_y b_x
$$
:::

De forma estricta, este producto sí es un vector, pero al trabajar en 2D y para lo que vamos a ver después, nos conviene que también sea un escalar.

## Implementación
Ahora vamos a agregar a nuestra estructura ``point`` un método para que calcule el producto cruz con otro vector:

double cross(const point & p) const{return x * p.y - y * p.x;}

Ejemplo:

point a(-5, 2), b(3, 1);
cout << a.cross(b) << "\n"; // Debería imprimir -11

## Propiedades
El producto cruz cumple con las siguientes propiedades:
- **Anticonmutativa:** $\vec{a} \times \vec{b} = -\vec{b} \times \vec{a}$, mucho cuidado con esta propiedad.
- **Distributiva por la izquierda:** $\vec{a} \times \left(\vec{b} + \vec{c}\right) = \vec{a} \times \vec{b} + \vec{a} \times \vec{c}$.
- **Distributiva por la derecha:** $\left(\vec{a} + \vec{b}\right) \times \vec{c} = \vec{a} \times \vec{c} + \vec{b} \times \vec{c}$.
- $\vec{a} \times \vec{a} = \vec{0} \times \vec{a} = 0$.

## Orientación
- Sean $\vec{a}$ y $\vec{b}$ dos vectores con un **ángulo dirigido** entre ellos igual a $\theta$. Este ángulo es casi el mismo que definimos en el producto punto, con la diferencia que será positivo si para ir de $\vec{a}$ a $\vec{b}$ tuvimos que girar en sentido antihorario, y será negativo si tuvimos que girar en sentido horario. Hay que darse cuenta que el orden en que definamos $\vec{a}$ y $\vec{b}$ es importante.
- Lo anterior es equivalente a decir que $\theta$ será positivo si $\vec{b}$ está a la izquierda de $\vec{a}$, y $\theta$ será negativo si $\vec{b}$ está a la derecha de $\vec{a}$.
- A esta regla se le conoce como la **regla de la mano derecha**.
- En inglés es común escribir sentido antihorario como *counter-clockwise* o *ccw*, y sentido horario como *clockwise* o *cw*.

:::info
:information_source: **Ejemplo:**
- En el primer caso, para ir de $\vec{a}$ a $\vec{b}$ tuvimos que girar en sentido antihorario un ángulo de $72^\circ$, por eso le toca un signo positivo.
- En el segundo caso, para ir de $\vec{a}$ a $\vec{b}$ tuvimos que girar en sentido horario un ángulo de $55^\circ$, por eso le toca un signo negativo.
:::

Con lo anterior, se cumple la siguiente propiedad del producto cruz:
$$
\vec{a} \times \vec{b} = \left\lVert{\vec{a}}\right\rVert \left\lVert{\vec{b}}\right\rVert \sin \theta
$$

:::spoiler **Demostración**
$$
\begin{align}
\left(\vec{a} \times \vec{b}\right)^2 &= (a_x b_y - a_y b_x)^2 \\
&= a_x^2 b_y^2 - 2a_x b_x a_y b_y + a_y^2 b_x^2 \\
&=\color{blue}{a_x^2 b_x^2} + a_x^2 b_y^2 + a_y^2 b_x^2 + \color{red}{a_y^2 b_y^2} - \color{blue}{a_x^2 b_x^2} - 2a_x b_x a_y b_y - \color{red}{a_y^2 b_y^2} \\
&= (a_x^2 + a_y^2)(b_x^2 + b_y^2) - (a_x b_x + a_y b_y)^2 \\
&= \left\lVert{\vec{a}}\right\rVert^2 \left\lVert{\vec{b}}\right\rVert^2 - \left(\vec{a} \cdot \vec{b}\right)^2 \\
&= \left\lVert{\vec{a}}\right\rVert^2 \left\lVert{\vec{b}}\right\rVert^2 - \left(\left\lVert{\vec{a}}\right\rVert \left\lVert{\vec{b}}\right\rVert\cos\theta\right)^2 \\
&= \left\lVert{\vec{a}}\right\rVert^2 \left\lVert{\vec{b}}\right\rVert^2 \left(1-\cos^2 \theta\right) \\
&= \left\lVert{\vec{a}}\right\rVert^2 \left\lVert{\vec{b}}\right\rVert^2 \sin^2 \theta
\end{align}
$$

Por lo tanto, $\vec{a} \times \vec{b} = \left\lVert{\vec{a}}\right\rVert \left\lVert{\vec{b}}\right\rVert \sin \left(\pm \theta\right)$, donde el signo correcto para $\theta$ se escoge con la regla de la mano derecha.
:::

- Del resultado anterior, vemos que el signo de $\theta$ siempre es el mismo que el de $\vec{a} \times \vec{b}$ debido a que el seno es una función impar. Entonces, con solo fijarnos en el signo de $\vec{a} \times \vec{b}$ podemos saber la orientación relativa de $\vec{b}$ respecto a $\vec{a}$.
- Ahora consideremos el caso en el que tenemos tres puntos $A$, $B$ y $C$, y queremos saber si $C$ se encuentra a la izquierda o a la derecha de la línea generada por $\overrightarrow{AB}$. Basta con hallar el producto $\overrightarrow{AB} \times \overrightarrow{AC} = \left(\vec{B} - \vec{A}\right) \times \left(\vec{C} - \vec{A}\right)$.
- Lo anterior tiene otra interpretación:
- El producto será positivo si para ir de $A$ a $B$ y luego a $C$ tuvimos que girar a la izquierda o en sentido antihorario.
- El producto será negativo si para ir de $A$ a $B$ y luego a $C$ tuvimos que girar a la derecha o en sentido horario.
- El producto será cero si $A$, $B$ y $C$ son colineales.

:::info
:information_source: **Ejemplo:**
- En el primer caso hicimos un giro a la izquierda, por lo tanto, $\overrightarrow{AB} \times \overrightarrow{AC} > 0$.
- En el segundo caso los tres puntos están alineados, por lo tanto, $\overrightarrow{AB} \times \overrightarrow{AC} = 0$.
- En el tercer caso hicimos un giro a la derecha, por lo tanto, $\overrightarrow{AB} \times \overrightarrow{AC} < 0$.
:::

Vamos a usar mucho esa función, así que conviene programarla de una vez:

double orient(point a, point b, point c){
	return (b - a).cross(c - a);
}

- Una propiedad interesante de esa función es que si rotamos cíclicamente los puntos, el valor no cambia, es decir: $\text{orient}(A, B, C) = \text{orient}(B, C, A) = \text{orient}(C, A, B)$.
- Otra es que si intercambiamos cualesquiera dos puntos, el valor cambia de signo. Por ejemplo: $\text{orient}(A, C, B) = -\text{orient}(A, B, C)$

**Ejercicio:** diseña una función que, dado un ángulo un ángulo formado por las semirrectas $\overrightarrow{AB}$ y $\overrightarrow{AC}$ (ambas se originan en $A$) y un punto $P$, determine si $P$ se encuentra dentro del ángulo o no.

:::spoiler **Solución**
Supongamos sin pérdida de generalidad que para ir de $\overrightarrow{AB}$ a $\overrightarrow{AC}$ hay que girar en sentido antihorario, pues si no fuera así, solo hacemos swap de $B$ y $C$. Luego, la condición es equivalente a que $\overrightarrow{AP}$ esté a la izquierda de $\overrightarrow{AB}$ y a la derecha de $\overrightarrow{AC}$. La implementación se queda como ejercicio.

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

## Áreas
Otra aplicación del producto cruz es que nos permite calcular el área de diversas figuras. Comencemos viendo cómo hallar el área de un triángulo dados sus tres vértices $A$, $B$ y $C$:

- Primero hallemos la altura del triángulo. Si nos fijamos en el triángulo rectángulo de la derecha, por definición de seno tenemos que $h = \left\lVert{\overrightarrow{AB}}\right\rVert \sin \theta$.
- Ya tenemos la base y la altura, por lo que el área es $[ABC] = \dfrac{1}{2} \left\lVert{\overrightarrow{AC}}\right\rVert h = \dfrac{1}{2}\left\lVert{\overrightarrow{AB}}\right\rVert \left\lVert{\overrightarrow{AC}}\right\rVert \sin \theta$.
- Pero por la propiedad del producto cruz, sabemos que $\overrightarrow{AB} \times \overrightarrow{AC} = \left\lVert{\overrightarrow{AB}}\right\rVert \left\lVert{\overrightarrow{AC}}\right\rVert \sin \theta$, por lo tanto el área es igual a $[ABC] = \dfrac{1}{2} \overrightarrow{AB} \times \overrightarrow{AC}$.
- Ok, esa es *casi* el área, pero recordemos que el ángulo $\theta$ en el producto cruz es dirigido, pero el que estamos usando aquí es no dirigido, por lo tanto solo tenemos que hallar el valor absoluto de la expresión anterior para garantizar que el área nunca sea negativa: $[ABC] = \dfrac{1}{2} \left\lvert{\overrightarrow{AB} \times \overrightarrow{AC}}\right\rvert$. El valor absoluto no será necesario si $\overrightarrow{AC}$ está a la izquierda de $\overrightarrow{AB}$, pero sí si está a la derecha, pues el producto cruz será negativo.

## Polar sort
Una aplicación de ambos productos (punto y cruz) es la siguiente: dado un conjunto de puntos $P$, un origen $O$ y un vector de dirección $\vec{v}$, ordenar los puntos de $P$ en el mismo orden en el que un rayo que comienza a girar en sentido antihorario con origen en $O$ y dirección $\vec{v}$ les pega.

En otras palabras, queremos ordenar los puntos en $P$ alrededor de $O$, tomando la dirección de $\vec{v}$ como primer ángulo.

Por ejemplo, en la siguiente figura se observan 24 puntos, etiquetados de acuerdo al tiempo en que el rayo de color rojo los toca. Aquí el rayo ya ha girado $143^\circ$:


Para resolver el problema usando solo números enteros, dividamos el plano en dos lados: todo lo que está del lado izquierdo será el lado 0, y todo lo que está del lado derecho será el lado 1. Lo que esté justo en la línea divisoria va a depender si está en el mismo sentido o en sentido contrario: lo que esté en el mismo sentido será del lado 0, y lo que esté en sentido contrario será del lado 1. De ese modo, en la figura los puntos del 1 al 12 serán del lado 0, mientras que del 13 al 24 serán del lado 1.

Para determinar en qué mitad está el $i$-ésimo punto, podemos usar producto cruz: el signo de $\vec{v} \times \overrightarrow{OP_i}$ nos dirá el lado:
$$
lado_i = \begin{cases}
0 &\mbox{si $\vec{v} \times \overrightarrow{OP_i} > 0$} \\
1 &\mbox{si $\vec{v} \times \overrightarrow{OP_i} < 0$}
\end{cases}
$$

Cuando $\vec{v} \times \overrightarrow{OP_i} = 0$ el punto está sobre la línea divisoria y necesitamos más información: si el punto está en el mismo sentido de $\vec{v}$ entonces el ángulo entre $\vec{v}$ y $\overrightarrow{OP_i}$ será de $0^\circ$, y en el caso contrario será de $180^\circ$. Eso es equivalente a fijarse en el signo de $\vec{v} \cdot \overrightarrow{OP_i}$: es positivo si está sobre el mismo sentido, y negativo si está en sentido contrario:

$$
lado_i = \begin{cases}
0 &\mbox{si $\vec{v} \times \overrightarrow{OP_i} > 0$} \\
1 &\mbox{si $\vec{v} \times \overrightarrow{OP_i} < 0$} \\
0 &\mbox{si $\vec{v} \times \overrightarrow{OP_i} = 0$ y $\vec{v} \cdot \overrightarrow{OP_i} > 0$} \\
1 &\mbox{si $\vec{v} \times \overrightarrow{OP_i} = 0$ y $\vec{v} \cdot \overrightarrow{OP_i} < 0$}
\end{cases}
$$

Ya que tenemos el lado por cada punto, hay dos casos para determinar el orden relativo entre dos puntos $P_i$ y $P_j$:
- si $lado_i < lado_j$ entonces $P_i$ irá antes que $P_j$, ya que están en distintos lados del plano y el punto $P_i$ es tocado primero que $P_j$ por estar del lado izquierdo.
- cuando $lado_i=lado_j$ quiere decir que están del mismo lado del plano, por lo que:
- $P_i$ irá antes que $P_j$ si $\overrightarrow{OP_j}$ está a la izquierda de $\overrightarrow{OP_i}$, es decir, $\overrightarrow{OP_i} \times \overrightarrow{OP_j} > 0$.
- si $\overrightarrow{OP_i} \times \overrightarrow{OP_j} = 0$ quiere decir que a ambos puntos puntos los toca al mismo tiempo el rayo, por lo que hay que usar otro criterio para desempatarlos, el más común es la distancia: $P_i$ irá antes que $P_j$ si $\lVert \overrightarrow{OP_i} \rVert < \lVert \overrightarrow{OP_j} \rVert$.

Finalmente, podemos implementar toda esta lógica de comparación dentro de un comparador personalizado en ``std:sort``, y la implementación queda como:

struct point{
    // ...

    // check whether this point is in the right half of v
    bool half(const point& v) const {
        return v.cross(*this) < 0 || (v.cross(*this) == 0 && v.dot(*this) < 0);
    }
    
    // ...
};

void polarSort(vector<point>& P, const point& o, const point& v){
    sort(P.begin(), P.end(), [&](const point& a, const point& b){
        // determine in which half each point belong
        bool half_a = (a - o).half(v);
        bool half_b = (b - o).half(v);
        // if the are on opposite halfs, the relative order of a wrt b is determined by the half of which they belong
        if(half_a != half_b) return half_a < half_b;
        // if they are on the same half, a goes first if b is on the right of a
        return (a - o).cross(b - o) > 0;
    });
}

logrando una complejidad de $O(n \log n)$, donde $n=|P|$.

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

[**Problema de práctica**](https://judge.yosupo.jp/problem/sort_points_by_argument)

## Resumen
- **Producto punto:** $\vec{a} \cdot \vec{b} = a_x b_x + a_y b_y = \left\lVert{\vec{a}}\right\rVert \left\lVert{\vec{b}}\right\rVert \cos \theta$
- **Producto cruz:** $\vec{a} \times \vec{b} = a_x b_y - a_y b_x = \left\lVert{\vec{a}}\right\rVert \left\lVert{\vec{b}}\right\rVert \sin \theta$
- El producto punto sirve para obtener el ángulo no dirigido entre dos vectores. No da información sobre la orientación relativa.
- El producto cruz nos da la orientación relativa entre dos vectores a través de su signo, pero no sirve para obtener el ángulo entre dos vectores. Un ejemplo de esto es suponer que el ángulo entre $\vec{a}$ y $\vec{b}$ es $\theta$, entonces tanto $\theta$ como $180^\circ-\theta$ serían ángulos válidos si lo obtenemos a través de $\arcsin$, produciendo ambigüedad, y esto se debe a que $\sin(\theta) = \sin(180^\circ-\theta)$.