algorithm - triangulo - como calcular el area de un poligono regular para niños

¿Cómo calculo el área de un polígono 2d?

Question

Suponiendo una serie de puntos en el espacio 2d que no se intersecan por sí mismos, ¿cuál es un método eficiente para determinar el área del polígono resultante?

Como nota al margen, esto no es tarea y no estoy buscando el código. Estoy buscando una descripción que pueda usar para implementar mi propio método. Tengo mis ideas acerca de extraer una secuencia de triángulos de la lista de puntos, pero sé que hay un montón de casos extremos con respecto a polígonos convexos y cóncavos que probablemente no atraparé.

Answer 1

Voy a dar algunas funciones simples para calcular el área del polígono 2d. Esto funciona tanto para polígonos convexos como cóncavos. simplemente dividimos el polígono en muchos sub-triángulos.

//don''t forget to include cmath for abs function
struct Point{
  double x;
  double y;
}
// cross_product
double cp(Point a, Point b){ //returns cross product
  return a.x*b.y-a.y*b.x;
}

double area(Point * vertices, int n){  //n is number of sides
  double sum=0.0;
  for(i=0; i<n; i++){
    sum+=cp(vertices[i], vertices[(i+1)%n]); //%n is for last triangle
  }
  return abs(sum)/2.0;
}

Answer 2

Código de Python

Como se describe aquí: http://www.wikihow.com/Calculate-the-Area-of-a-Polygon

Con los pandas

import pandas as pd

df = pd.DataFrame({''x'': [10, 20, 20, 30, 20, 10, 0], ''y'': [-10, -10, -10, 0, 10, 30, 20]})
df = df.append(df.loc[0])

first_product = (df[''x''].shift(1) * df[''y'']).fillna(0).sum()
second_product = (df[''y''].shift(1) * df[''x'']).fillna(0).sum()

(first_product - second_product) / 2
600

Answer 3

1. Establezca un punto base (el punto más convexo). Este será tu punto de pivote de los triángulos.
2. Calcule el punto más a la izquierda (arbitrario), que no sea su punto base.
3. Calcula el segundo punto más a la izquierda para completar tu triángulo.
4. Guarde esta área triangulada.
5. Cambia un punto a la derecha de cada iteración.
6. Suma las áreas trianguladas

Answer 4

Aquí está el método estándar , AFAIK. Básicamente, sume los productos cruzados alrededor de cada vértice. Mucho más simple que la triangulación.

Código de Python, dado un polígono representado como una lista de coordenadas de vértice (x, y), envolviendo implícitamente desde el último vértice al primero:

def area(p):
    return 0.5 * abs(sum(x0*y1 - x1*y0
                         for ((x0, y0), (x1, y1)) in segments(p)))

def segments(p):
    return zip(p, p[1:] + [p[0]])

David Lehavi comenta: Vale la pena mencionar por qué funciona este algoritmo: es una aplicación del teorema de Green para las funciones -y y x; exactamente en la forma en que funciona un planimeter . Más específicamente:

Fórmula arriba =
integral_over_perimeter(-y dx + x dy) =
integral_over_area((-(-dy)/dy+dx/dx) dy dx) =
2 Area

Answer 5

C manera de hacerlo:

float areaForPoly(const int numVerts, const Point *verts)
{
    Point v2;
    float area = 0.0f;

    for (int i = 0; i<numVerts; i++){
        v2 = verts[(i + 1) % numVerts];
        area += verts[i].x*v2.y - verts[i].y*v2.x;
    }

    return area / 2.0f;
}

Answer 6

Calcular el área del polígono

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry1#polygon_area

int cross(vct a,vct b,vct c)
{
    vct ab,bc;
    ab=b-a;
    bc=c-b;
    return ab.x*bc.y-ab.y*bc.x;
}    
double area(vct p[],int n)
{ 
    int ar=0;
    for(i=1;i+1<n;i++)
    {
        vct a=p[i]-p[0];
        vct b=p[i+1]-p[0];
        area+=cross(a,b);
    }
    return abs(area/2.0);
}    

Answer 7

El producto cruzado es un clásico.

Si tienes un trillón de esos cálculos para hacer, prueba la siguiente versión optimizada que requiere multiplicaciones de la mitad menos:

area = 0;
for( i = 0; i < N; i += 2 )
   area += x[i+1]*(y[i+2]-y[i]) + y[i+1]*(x[i]-x[i+2]);
area /= 2;

Utilizo el subíndice de matriz para mayor claridad. Es más eficiente usar punteros. Aunque buenos compiladores lo harán por ti.

Se supone que el polígono está "cerrado", lo que significa que copia el primer punto como punto con el subíndice N. También supone que el polígono tiene un número par de puntos. Agregue una copia adicional del primer punto si N no es par.

El algoritmo se obtiene desenrollando y combinando dos iteraciones sucesivas del clásico algoritmo de producto cruzado.

No estoy tan seguro de cómo los dos algoritmos se comparan con respecto a la precisión numérica. Mi impresión es que el algoritmo anterior es mejor que el clásico porque la multiplicación tiende a restaurar la pérdida de precisión de la resta. Cuando se obliga a usar flotantes, como con GPU, esto puede hacer una diferencia significativa.

EDITAR: "Área de triángulos y polígonos 2D y 3D" describe un método aún más eficiente

// "close" polygon
x[N] = x[0];
x[N+1] = x[1];
y[N] = y[0];
y[N+1] = y[1];

// compute area
area = 0;
for( size_t i = 1; i <= N; ++i )
  area += x[i]*( y[i+1] - y[i-1] );
area /= 2;

Answer 8

La implementación de la fórmula Shoelace podría hacerse en Numpy. Asumiendo estos vértices:

import numpy as np
x = np.arange(0,1,0.001)
y = np.sqrt(1-x**2)

Podemos definir la siguiente función para encontrar el área:

def PolyArea(x,y):
    return 0.5*np.abs(np.dot(x,np.roll(y,1))-np.dot(y,np.roll(x,1)))

Y obteniendo resultados:

print PolyArea(x,y)
# 0.26353377782163534

Al evitar el bucle, esta función es ~ PolygonArea más rápida que PolygonArea :

%timeit PolyArea(x,y)
# 10000 loops, best of 3: 42 µs per loop
%timeit PolygonArea(zip(x,y))
# 100 loops, best of 3: 2.09 ms per loop

Nota: He escrito esta respuesta para otra question , solo lo menciono aquí para tener una lista completa de soluciones.

Answer 9

Mejor que sumar triángulos es sumar trapecios en el espacio cartesiano:

area = 0;
for (i = 0; i < n; i++) {
  i1 = (i + 1) % n;
  area += (vertex[i].y + vertex[i1].y) * (vertex[i1].x - vertex[i].x) / 2.0;
}

Answer 10

Mi inclinación sería simplemente comenzar a cortar triángulos. No veo cómo otra cosa podría evitar ser terriblemente peluda.

Tome tres puntos secuenciales que componen el polígono. Asegúrese de que el ángulo sea inferior a 180. Ahora tiene un nuevo triángulo que no debería ser un problema para calcular, elimine el punto medio de la lista de puntos del polígono. Repita hasta que solo le queden tres puntos.

Answer 11

O haz un contorno integral. El teorema de Stokes le permite expresar una integral de área como una integral de contorno. Una pequeña cuadratura de Gauss y Bob es tu tío.

Answer 12

Para expandir las áreas triangular y sumar triángulos, funcionan si tienes un polígono convexo O si seleccionas un punto que no genera líneas en todos los demás puntos que se cruzan con el polígono.

Para un polígono general no intersecante, debe sumar el producto cruzado de los vectores (punto de referencia, punto a), (punto de referencia, punto b) donde a y b son "próximos" entre sí.

Suponiendo que tiene una lista de puntos que definen el polígono en orden (orden siendo los puntos i e i + 1 forman una línea del polígono):

Suma (producto cruzado ((punto 0, punto i), (punto 0, punto i + 1)) para i = 1 a n - 1.

Tome la magnitud de ese producto cruzado y tiene el área de superficie.

Esto manejará polígonos cóncavos sin tener que preocuparse por elegir un buen punto de referencia; cualquiera de los tres puntos que generan un triángulo que no está dentro del polígono tendrá un producto cruzado que apunta en la dirección opuesta a cualquier triángulo que se encuentre dentro del polígono, por lo que las áreas se suman correctamente.

Answer 13

Un conjunto de puntos sin ninguna otra restricción no necesariamente define un polígono de manera única.

Entonces, primero debes decidir qué polígono construir a partir de estos puntos, ¿quizás el casco convexo? http://en.wikipedia.org/wiki/Convex_hull

Luego triangula y calcula el área. http://www.mathopenref.com/polygonirregulararea.html

Answer 14

Una forma de hacerlo sería descomponer el polígono en triángulos , calcular el área de los triángulos y tomar la suma como el área del polígono.

Answer 15

solución independiente del lenguaje:

DADO: un polígono SIEMPRE puede estar compuesto por n-2 triángulos que no se superponen (n = número de puntos O lados). 1 triángulo = 3 lados del polígono = 1 triángulo; 1 cuadrado = polígono de 4 lados = 2 triángulos; etc ad nauseam QED

por lo tanto, un polígono se puede reducir cortando triángulos y el área total será la suma de las áreas de estos triángulos. pruébalo con un trozo de papel y tijeras, es mejor si puedes visualizar el proceso antes de seguirlo.

si toma 3 puntos consecutivos en una ruta de polígonos y crea un triángulo con estos puntos, tendrá uno y solo uno de los tres posibles escenarios:

1. triángulo resultante está completamente dentro del polígono original
2. el triángulo resultante está totalmente fuera del polígono original
3. El triángulo resultante está parcialmente contenido en el polígono original

solo nos interesan los casos que entran en la primera opción (totalmente contenidos).

cada vez que encontramos uno de estos, lo cortamos, calculamos su área (easy peasy, no explicaremos la fórmula aquí) y hacemos un nuevo polígono con un lado menos (equivalente al polígono con este triángulo recortado). hasta que solo nos quede un triángulo

cómo implementar esto programáticamente:

crea una matriz de puntos (consecutivos) que representan la ruta ALREDEDOR del polígono. comience en el punto 0. ejecute la matriz haciendo triángulos (uno a la vez) a partir de los puntos x, x + 1 y x + 2. transforma cada triángulo de una forma a un área e interseca con el área creada a partir del polígono. SI la intersección resultante es idéntica al triángulo original, dicho triángulo está totalmente contenido en el polígono y puede cortarse. elimine x + 1 de la matriz y comience nuevamente desde x = 0. de lo contrario (si el triángulo está fuera del polígono [parcial o completamente)], mueva al próximo punto x + 1 en el arreglo.

Además, si está buscando la integración con el mapeo y está comenzando desde los puntos geográficos, primero debe convertir de los puntos geográficos a los puntos de detección. esto requiere decidir un modelado y una fórmula para la forma de la tierra (aunque tendemos a pensar en la tierra como una esfera, en realidad es un ovoide irregular (forma de huevo), con abolladuras). hay muchos modelos por ahí, para más información wiki. un tema importante es si considerará o no que el área sea un plano o que sea curva. en general, las áreas "pequeñas", donde los puntos están a una distancia de algunos kilómetros, no generarán un error significativo si se consideran planas y no convexas.

Answer 16

Esta página muestra que la fórmula

se puede simplificar a:

Si escribe algunos términos y los agrupa según los factores comunes de xi , la igualdad no es difícil de ver.

La suma final es más eficiente ya que solo requiere n multiplicaciones en lugar de 2n .

def area(x, y):
    return abs(sum(x[i] * (y[i + 1] - y[i - 1]) for i in xrange(-1, len(x) - 1))) / 2.0

Aprendí esta simplificación de Joe Kington, here .

Si tiene NumPy, esta versión es más rápida (para todas las matrices, excepto las muy pequeñas):

def area_np(x, y):        
    x = np.asanyarray(x)
    y = np.asanyarray(y)
    n = len(x)
    shift_up = np.arange(-n+1, 1)
    shift_down = np.arange(-1, n-1)    
    return (x * (y.take(shift_up) - y.take(shift_down))).sum() / 2.0