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

所以我有一些功能，收到N隨機2D點。是否有任何計算給定座標的形狀區域的算法來定義形狀？

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

來源

2010-03-12 Rella

你的問題是準確，你說的是什麼樣的廣場？ – 2010-03-12 11:49:42

這是不是很清楚你要求什麼，最小邊界正方形/矩形可能？ – 2010-03-12 11:50:53

你的意思是「計算形狀的平方」？你的意思是這個地區？如果是這樣，你用什麼方法來確定「形狀」是什麼？ – Jens 2010-03-12 11:51:20

你想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); 
}

來源

2010-03-12 11:58:58

+1我認爲大家都忙於實施upvote你！ :) – 2010-03-12 12:18:38

當我睡覺我的夢想代碼 – 2010-03-12 12:23:10

我夢見天體;） – 2010-03-12 12:30:10

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

來源

2010-03-12 12:35:58 Nathan

「具有直線邊界的最小區域」具有區域0幷包含最小生成樹。 – Svante 2010-03-12 12:55:11

是的，公平的評論。我認爲可以有合理的約束條件來解決這個問題，以便給出凸包以外的解決方案（例如，通過允許任意邊限制邊的數量爲O（n^{1/2}）），但是任何這樣的問題可能都非常難以解決。 – Nathan 2010-03-12 14:08:51

在這裏採摘尼特，但具有最短直線邊界的區域實際上是一個斯坦納樹，它通常比MST短。 – user287792 2010-03-12 14:28:26

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

來源

2010-03-12 13:50:06 Boolean

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

來源

2010-03-12 14:57:54 Jacob

我發現了另一個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); 
}

來源

2016-06-24 23:00:16 jcuriel

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

回答

相關問題