Geometría computacional

La geometría computacional podría fácilmente ocupar toda una asignatura; aquí sólo veremos unos conceptos en concreto basados en los vectores.

Producto escalar

El producto escalar entre dos vectores A=(a1,...,ak) y B=(b1,...,bk), ambos de dimensión k, es igual a

A·B=a1b1 + ... + akbk.

Una aplicación del producto escalar en la geometría es calcular la proyección de un punto en una línea. En la siguiente figura, el vector A describe un punto P, y el vector B describe una línea. El punto Q es la proyección de P sobre la línea.

Proyectar punto sobre linea

La distancia entre el origen y el punto Q es igual a x=|A|cosθ, donde |A| es la longitud del vector A y θ es el ángulo entre los vectores A y B. Para el producto escalar se cumple A·B=|A||B|cosθ=|B|x. La longitud |B| de B también se puede expresar por el producto escalar: B·B = |B|2. Por lo tanto podemos expresar x como

x = (A·B)/sqrt(B·B),

donde la función sqrt() calcula la raíz cuadrada. En tres dimensiones la idea es exactamente la misma.

Producto vectorial

En dos dimensiones, el producto vectorial A×B entre dos vectores A=(a1,a2) y B=(b1,b2) es un vector con longitud

|A×B|=|a1b2 - a2b1|.

La dirección del vector A×B, que es ortogonal a A y ortogonal a B, está dada por la regla de la mano derecha. De manera equivalente podemos determinar la dirección de A×B por el signo de a1b2 - a2b1. Si el ángulo θ entre A y B es en el rango (0°,180°), este signo es positivo, si θ es en el rango (-180°,0°) el signo es negativo, y si θ es exactamente 0° o 180°, el signo es 0.

Una aplicación del producto vectorial en la geometría es calcular la distancia y entre el punto P y su proyección Q en el ejemplo anterior. Primero notamos que y = |A|sinθ, y para el producto vectorial se cumple |A×B|=|A||B|sinθ = |B|y. Por lo tanto podemos expresar y como

y = |A×B|/sqrt(B·B).

El producto vectorial también está definido en tres dimensiones, y el resultado anterior sigue siendo válido en este caso.

Envolvente convexa

Otra aplicación del producto vectorial es calcular la denominada envolvente convexa. Dado un conjunto de puntos en el plano, la envolvente convexa es el subconjunto de puntos que forman un polígono convexo que envuelve todos los demás puntos, igual que muestra la siguiente figura:

Ejemplo de envoltura convexa

El algoritmo más básico para calcular la envolvente convexa se llama el método de Graham, y se describe por los siguientes pasos:

Si el polígono sigue convexo o no depende de los últimos dos puntos a y b de la envolvente convexa actual. El siguiente ejemplo muestra como el polígono sigue siendo convexo incluyendo el nuevo punto c:

Ejemplo

En cambio, en el siguiente ejemplo el polígono no sigue siendo convexo, por lo que se quita el último punto (b) de la envolvente convexa actual:

Ejemplo

Ejemplo

Resulta que el polígono sigue siendo convexo precisamente cuando el signo del producto vectorial entre los dos vectores (a,b) y (a,c) es positivo.

Algoritmo que implementa el método de Graham para calcular la envolvente convexa: convexhull.cpp

La misma idea se puede aprovechar para comprobar si un punto dado está en el interior de un polígono: si representamos todos los segmentos del polígono por vectores, un punto está dentro del polígono si el signo del producto vectorial es el mismo para todos los segmentos.

Problemas para resolver esta semana

Sencillos:

UVa logo 191 - Intersection
UVa logo 1206 - Boundary Points
OIE logo Intersecciones 1D 2D 3D

Avanzados:

UVa logo 155 - All squares
UVa logo 218 - Moth Eradication
UVa logo 634 - Polygon
UVa logo 681 - Convex Hull Finding
UVa logo 12278 - 3-sided dice
OIE logo De príncipes y princesas
OIE logo Convex Hull