是否有任何計算給定座標的形狀區域的算法來定義形狀？

Question

所以我有一些功能，收到N隨機2D點。

是否有算法來計算輸入點定義的形狀面積？

Answer 1

你想calculate the area of a polygon？

（從鏈路兩者，轉化爲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

定義您的點集合的「區域」可能很難，例如如果你想用包圍你的設置的直線邊界得到最小的區域，那麼我不知道如何繼續。可能你想要做的是計算你的一組點的凸包的面積;這是一個標準問題，Steven Skiena在Stony Brook Algorithms repository上給出瞭解決方案實現鏈接問題的描述。從那裏計算面積的一種方法（在我看來，這是顯而易見的方法）將是對區域進行三角測量並計算每個三角形的面積。

Answer 3

您可以使用Timothy Chan的算法在nlogh中查找凸包，其中n是點的數量，h是凸包頂點的數量。如果你想要一個簡單的算法，去格雷厄姆掃描。另外，如果你知道你的數據是像一個簡單的鏈一樣排序的，那麼點之間不會相交，你可以使用Melkman的算法計算O（N）中的凸包。另外，凸包的另一個有趣屬性是，它具有最小周長。

Answer 4

你的問題並不直接暗示有一個現成的多邊形（假設爲this answer）。我會建議一個三角測量，如Delaunay Triangulation，然後平均計算每個三角形的面積。 OpenCV（我用過大量的二維點，它非常有效），並且爲確定三角測量提供了出色的實現。

Answer 5

我發現了另一個function written in Java，所以我把它traslated到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); 
}