¿Hay algún algoritmo para calcular el área de una forma dadas las coordenadas que definen la forma?

Question

Así que tengo alguna función que recibe N 2D puntos al azar.

¿Hay algún algoritmo para calcular el área de la forma definida por los puntos de entrada?

Answer 1

¿Quiere calculate the area of a polygon?

(Tomado de enlace, convertidos a C#)

class Point { double x, y; } 

double PolygonArea(Point[] polygon) 
{ 
    int i,j; 
    double area = 0; 

    for (i=0; i < polygon.Length; i++) { 
     j = (i + 1) % polygon.Length; 

     area += polygon[i].x * polygon[j].y; 
     area -= polygon[i].y * polygon[j].x; 
    } 

    area /= 2; 
    return (area < 0 ? -area : area); 
} 

Answer 2

Definición de la "zona" de su colección de puntos puede ser difícil, por ejemplo, si desea obtener la región más pequeña con límites de línea recta que encierran su conjunto, entonces no estoy seguro de cómo proceder. Probablemente lo que quiere hacer es calcular el área del casco convexo de su conjunto de puntos; este es un problema estándar, una descripción del problema con enlaces a implementaciones de soluciones es dada por Steven Skiena al Stony Brook Algorithms repository. A partir de ahí, una forma de calcular el área (me parece que es la forma obvia) sería triangular la región y calcular el área de cada triángulo individual.

Answer 3

Puede usar el algoritmo de Timothy Chan para encontrar casco convexo en nlogh, donde n es el número de puntos, h es el número de vértices del casco convexo. Si quieres un algoritmo fácil, ve a Graham Scan.

Además, si sabe que sus datos se ordenan como una simple cadena, donde los puntos no se cruzan, puede usar el algoritmo de Melkman para calcular el casco convexo en O (N).

Además, una propiedad más interesante del casco convexo es que tiene el perímetro mínimo.

Answer 4

Su problema no implica directamente que haya un polígono listo para usar (asumido por this answer). Recomendaría una triangulación como Delaunay Triangulation y luego calcular trivialmente el área de cada triángulo. OpenCV (lo he usado con una gran cantidad de puntos 2D y es muy efectivo) y CGAL proporcionan implementaciones excelentes para determinar la triangulación.

Answer 5

he encontrado otra function written in Java, así que TRADUCIDO en C#

public static double area(List<Double> lats,List<Double> lons) 
{  
double sum=0; 
double prevcolat=0; 
double prevaz=0; 
double colat0=0; 
double az0=0; 
for (int i=0;i<lats.Count;i++) 
{ 
    double colat=2*Math.Atan2(Math.Sqrt(Math.Pow(Math.Sin(lats[i]*Math.PI/180/2), 2)+ Math.Cos(lats[i]*Math.PI/180)*Math.Pow(Math.Sin(lons[i]*Math.PI/180/2), 2)), 
     Math.Sqrt(1- Math.Pow(Math.Sin(lats[i]*Math.PI/180/2), 2)- Math.Cos(lats[i]*Math.PI/180)*Math.Pow(Math.Sin(lons[i]*Math.PI/180/2), 2))); 
    double az=0; 
    if (lats[i]>=90) 
    { 
     az=0; 
    } 
    else if (lats[i]<=-90) 
    { 
     az=Math.PI; 
    } 
    else 
    { 
     az=Math.Atan2(Math.Cos(lats[i]*Math.PI/180) * Math.Sin(lons[i]*Math.PI/180),Math.Sin(lats[i]*Math.PI/180))% (2*Math.PI); 
    } 
    if(i==0) 
    { 
     colat0=colat; 
     az0=az; 
    }   
    if(i>0 && i<lats.Count) 
    { 
     sum=sum+(1-Math.Cos(prevcolat + (colat-prevcolat)/2))*Math.PI*((Math.Abs(az-prevaz)/Math.PI)-2*Math.Ceiling(((Math.Abs(az-prevaz)/Math.PI)-1)/2))* Math.Sign(az-prevaz); 
    } 
    prevcolat=colat; 
    prevaz=az; 
} 
sum=sum+(1-Math.Cos(prevcolat + (colat0-prevcolat)/2))*(az0-prevaz); 
return 5.10072E14* Math.Min(Math.Abs(sum)/4/Math.PI,1-Math.Abs(sum)/4/Math.PI); 
}