Cargando...
 
Imprimir

Area de un polígono irregular: producto en cruz

Image
Hace algún tiempo, leí en un foro una discusión acerca de cómo calcular el área de un polígono irregular no necesariamente convexo. Por supuesto, todos los contertulios cayeron en la cuenta de que el área de del polígono debía calcularse por triangulación. Es decir, dividiendo el polígono en triángulos, calculando el área de cada triángulo y luego sumando todas las áreas.

Me llamaron tanto la atención las complicadas soluciones que se propusieron que me puse inmediatamente a buscar por internet para ver si encontraba alguna buena página acerca de ello. Como no la encontré, me animé a escribir este artículo, describiendo un algoritmo que me comentaron hace ya muchos años, pero que recuerdo especialmente por ser uno de los más ingeniosos que conozco.

Intentaré contarlo lo mejor que pueda.

Es evidente que el método para hallar este área de un polígono irregular debe diferir mucho de la que se utiliza para los polígonos regulares. Para calcular el área de un polígono regular, basta conocer un par de parámetros sobre ellos (por ejemplo, el número de lados y la longitud de uno de ellos) y aplicar una de las conocidas fórmulas que aprendimos en el cole.

Sin embargo, las aplicaciones del mundo real que trabajan con polígonos, suelen hacerlo sobre polígonos irregulares, de ahí su importancia.

Bien… el caso es que si contamos con un polígono irregular cualquiera…. Por ejemplo, éste...

Image
Si estamos resolviendo el problema con lápiz y regla… la solución es sencilla. Cogemos el polígono y lo dividimos arbitrariamente en una serie de triángulos. Da igual qué triángulos escojamos mientras al final sólo queden triángulos.

Image
Por ejemplo, así…

Ahora cogemos una escuadra y una regla y vamos triángulo por triángulo midiendo su base y su altura… y aplicamos esa fórmula que resuena en nuestra memoria como el tintineo de un martillo sobre un yunque: “Area del triángulo igual a base por altura partido por dos…”. Fantástico… una vez hallado el área de cada triángulo, sumamos todas las áreas y tenemos la del polígono entero.


El problema es que en las aplicaciones computacionales, los polígonos no están dibujados, así que no podemos sacar la regla para medir. Debemos recurrir a métodos computacionales.

En primer lugar, es necesario decir que los polígonos suelen definirse por las coordenadas en el plano de los puntos que conforman sus vértices. Uniendo cada punto con el siguiente y el último con el primero obtendremos una línea cerrada (una serie de segmentos, hablando con más propiedad) que conforma el polígono. Esa línea cerrada encierra una superficie plana que podemos medir. El resultado de esa medida será la extensión del área.

Empecemos por el principio… vamos a ver cómo calcular el área de un triángulo si tenemos las coordenadas de sus vértices, y luego veremos cómo utilizar ese método para hallar la de un polígono irregular.

Área de un triángulo

Tomemos un triángulo cualquiera en un plano… Por ejemplo…. Éste triángulo… para manejarlo computacionalmente, lo más frecuente es que almacenemos las coordenadas de sus vértices con respecto a algún sistema de referencia (los ejes que escojamos).

Image alt

A la vista de las coordenadas de sus vértices, está claro que si queremos aplicar la fórmula de base por altura partido por dos, lo tenemos complicado.

En el foro que comentaba anteriormente, alguien propuso escoger un lado y trabajar con los ángulos que formaban los otros dos para hallar la altura a través de trigonometría… Nadie puede decir que el planteamiento fuera incorrecto… pero existen métodos mucho más sencillos para calcular el área de un triángulo sin recurrir a trigonometría.

En el caso de que tengamos las coordenadas de sus vértices (como éste), vamos a llamarlas (x1, y1), (x2, y2) y (x3,y3) basta con colocarlas en una matriz cuadrada de 3 por 3 de ésta manera:

Image En la tercera fila, colocamos, a piñón, el valor ½.

Pues bien… si hacemos el determinante de M y tomamos valor absoluto, sale el área del triángulo. Parece magia ¿Verdad?... y nada de trigonometría.

Si recuerdas la regla de Sarrus(external link) para los determinantes de 3 por 3, el resultado sería:

det(M)=x1·y2·½ + x2·y3·½ + x3·y1·½ - y1·x2·½ - y2·x3·½ - y3·x1·½

Hmmm… El ½ está pidiendo a gritos que lo saquemos como factor común.

det(M)=(x1·y2 + x2·y3 + x3·y1 - y1·x2 - y2·x3 - y3·x1) · ½

Ya está. Finalmente, si el determinante sale negativo, tomamos valor absoluto y ese valor es el área del triángulo.

Vamos a probar con nuestro triángulo del principio… el que tenía de coordenadas de sus vértices los puntos (2,3), (7,1), y (5,7)
Image
Al hacer el determinante nos da 13. Ese es el área del triángulo en unidades al cuadrado. Es casi magia… casi. (Me temo que tiene más que ver con el producto escalar de vectores que con la magia)

Vamos a comentar una curiosa propiedad de ésta forma de calcular el área de un triángulo y que tiene que ver con el signo del determinante. Al colocar las coordenadas de los vértices en la matriz yo no he utilizado un orden concreto. Sin embargo, el determinante se comporta de forma distinta según se coloquen los puntos en la matriz:

Si utilizo (2,3), (7,1) y (5,7), como en este caso… el resultado es positivo.

Si utilizo (7,1), (5,7) y (2,3) también sale positivo, al igual que con (5,7), (2,3) y (7,1).

Sin embargo, si utilizo cualquiera de las tres combinaciones anteriores pero con los puntos ordenados al revés (7,1), (2,3) y (5,7), o (5,7),(7,1) y (2,3) o (2,3),(5,7) y (7,1) el resultado es negativo, es decir, -13.

El caso es que cuando se ordenan los puntos escogiéndolos en sentido antihorario (al revés de cómo van las agujas de un reloj) el resultado sale positivo, independientemente de por qué punto se empiece…. Pero si escojo los puntos en sentido horario (siguiendo el movimiento de las agujas de un reloj), el resultado es el mismo en valor absoluto, pero tiene signo negativo.

Curioso ¿Verdad?

En el caso de un triángulo, esta propiedad no tiene la mayor importancia… despreciamos el signo y ya está... pero va a ser de mucha importancia para obtener el área de un polígono de más de tres lados.

Cálculo del área de un polígno irregular cualquiera

Bueno… parece que lo más evidente una vez llegados aquí y conociendo una forma de hallar el área de un triángulo, ya podemos ponernos a calcular la de un polígono. Parece evidente que ya podemos dividir nuestro polígono en triángulos y calcular el área de cada uno de ellos.

Realmente, si cogemos lápiz y regla nos daremos cuenta de que hay muchas formas de triangular un polígono. Existen muchos algoritmos de triangulación (el de Delaunay, el de “cortar orejas”, también conocido como algoritmo de Van Gogh…), cada uno de ellos con un propósito concreto. Probablemente, el más sencillo de ellos sea el de “cortar orejas”. Pero para calcular el área, no será necesario utilizar ninguno de ellos. Vamos a utilizar un método todavía menos costoso computacionalmente hablando.

Volvamos a nuestro polígono del principio. En lugar de triangular arbitrariamente, vamos a aplicar otro sistema:

  • Escogemos uno de los vértices (uno cualquiera, el que mejor nos venga), y a ese lo vamos a llamar vértice 1. Luego, siguiendo un sentido antihorario, numeramos los demás… 2, 3, 4… los que sean.

  • A continuación, iremos formando todos los posibles triángulos que tengan en común al vértice 1. Dicho de otra manera: El triángulo formado por 1,2,3, luego 1,3,4, luego 1,4, 5, luego 1,5,6 … y así hasta el último.

  • De cada uno de ellos calcularemos el determinante como hemos visto en el apartado anterior, y la suma de todos los resultados será el área del polígono.

La explicación es que al formar los triángulos, en el orden escogido de vértices, algunos triángulos los recorremos en sentido horario y otros en sentido antihorario. Los triángulos que recorremos en sentido antihorario contribuyen a aumentar el area, el resultado del determinante es positivo, y los que recorremos en sentido horario contribuyen a “eliminar” los trozos que quedan fuera del polígono.

Observa esta animación, que seguro que resulta más clarificadora.
Reproductor Flash no disponible.


Cabe comentar que el algoritmo también puede aplicarse si en lugar de recorrer los vértices en sentido antihorario lo hacemos en el contrario. La diferencia es que el resultado final saldrá negativo. (Los triángulos azules contribuyen a calcular el area y los rojos a eliminar lo que queda fuera del polígono).

Así pues, no es necesario comprobar el sentido de los vértices en el plano. Aplicamos el algoritmo sumando el resultado de los determinantes, y finalmente tomamos el valor absoluto de la suma.

Ingenioso ¿Verdad? No sólo es ingenioso, sino que tiene una complejidad bastante baja, lineal, del órden de n, siendo n el número de vértices del polígono (O(n)).

Pero eso no es todo… este algoritmo aún se puede afinar más.

Optimización

Si desarrollamos la suma de determinantes, nos daremos cuenta de que hay términos que en un determinante aparecen sumando y en otro restando. (Cada determinante tiene tres términos que suman y tres que restan).

Por ejemplo, si los vértices del polígono están en las coordenadas (x1,y1), (x2,y2), (x3,y3), (x4,y4)… (xn, yn)

El primer determinante es

x1·y2·½ + x2·y3·½ + x3·y1·½ - y1·x2·½ - y2·x3·½ - y3·x1·½

y el segundo es

x1·y3·½ + x3·y4·½ + x4·y1·½ - y1·x3·½ - y2·x4·½ - y4·x1·½

Los términos subrayados se pueden eliminar, ya que en uno aparecen sumando y en otro restando (aunque estén escritos en otro orden, fíjate en que multiplicandos de cada término son los mísmos).

Cuando hacemos esto para todos los determinantes, resulta que podemos eliminar un montón de términos, y además, por supuesto, sacar como factor común el ½.

Si eliminamos todos esos términos que se anulan, el resultado de la suma de los determinantes es

x1·y2-y1·x2+
x2·y3-y2·x3+
x3·y4-y3·x4+

xn·y1-yn·x1

Todo ello multiplicado por ½.


Se le llama a menudo "producto en cruz”, por la forma que tiene si representamos los términos de esta manera. En éste gráfico, representamos las coordenadas de los vértices que forman un término. Las que están unidas por una línea roja son términos que suman, y las que están unidas por una línea azul son términos que restan (sin olvidarnos del ½ que lo multiplica todo).

Image

Así pues, y después de todo este rollo, el algoritmo para calcular el área de un polígono P conociendo las coordenadas de sus vértices ordenados en sentido horario o antihorario y expresadas como (x1,y1), (x2,y2) … (xn, yn) es

Image

Ingeniosísimo ¿Verdad?

Bueno... con esta última fórmula, ya tenemos bien sencillo utilizarla en cualquier programa.

Por ejemplo, observa cómo la hemos utilizado en esta clase Poligono, programada en C#. Básicamente, ésta clase contiene una lista de puntos ordenada. Cada punto representa a un vértice del polígono. Por supuesto, este ejemplo no es plenamente funcional, sólo es una mini demostración de cómo implementar el algoritmo descrito en éste artículo, pero puede servir de punto de partida para que lo adaptes a tus necesidades.

C# - Clases para representar un punto y un polígono
class Punto
{
  public double x, y;
 
  public Punto(double x, double y)
    {
      this.x=x;
      this.y=y;
    }
 
} //Punto
 
//-------------
 
class Poligono
{
  //lista de vértices
  //Suponemos que siguen sentido horario o
  //antihorario y que ningún segmento cruza a
  //otro. Cada vértice aparece una sola vez
  //en la lista. El último se une al primero
  List<punto> vertices = new List<punto>();
 
  public void nuevoVertice(Punto p)
  {
    vertices.Add(p);
  }
 
  public double area()
  {
    double suma=0;
    int i;
    //Sólo calculamos si el polígono tiene
    //al menos tres vértices
    if (vertices.Count>=3) {
      //producto en cruz desde 1 hasta n-1
      for(i=0;i<vertices.Count-1;i++) {
        suma+=vertices[i].x*vertices[i+1].y-
              vertices[i].y*vertices[i+1].x;
        }//for
      //ahora el último con el primero
      i=vertices.Count-1;
      suma+=vertices[i].x*vertices[0].y-
            vertices[i].y*vertices[0].x;
    }//if
    return Math.Abs(suma) / 2;
  }//area
}//class



Para probar, basta crear un polígono, y añadir unos cuantos vértices.

C# - Ejemplo de utilización
//ejemplo utilización
Poligono p = new Poligono();
p.nuevoVertice(new Punto(2, 3));
p.nuevoVertice(new Punto(7, 1));
p.nuevoVertice(new Punto(5, 7));
Console.WriteLine(p.area());


Ultima edición por vic .
Página última modificacion en Lunes 13 de Agosto, 2012 13:46:42 CEST.



¿Dónde estoy?

Estás en La tecla de ESCAPE, un sitio web personal en el que nos gusta hablar de algoritmos, metodología de la programación, personajes de informática, tecnología, ingeniería del software, internet, y cualquier otra tontería que se nos ocurra.
Leer más / Términos de uso (ToS)