非凸多角形のジオ座標からエリアを計算する

Question

GPSトラックから取得するポリゴンの面積を計算したいと思います。だから、基本的に私は一定の時間が経過した後、デバイス/ユーザーの位置を保存します、5秒としましょう。

このトラックのポリゴンのうち、トラックがある領域を計算したいと思います。 凸面ポリゴンの場合、三角形の面積を計算する必要があるので、これは問題ではありません最初の点の1つの開始点）。基本的に左の画像に表示されています。 （黄色のポリゴンはGPS-Locationsで作られたポリゴンであり、暗い線は面積計算のための三角形を示し、明るい黄色は希望の領域です）

しかし、昨夜私はその考えにバックグラウンドを発見しました。凸状。ポリゴンの外側にある部分（左上）がその領域で計算されるだけでなく、ポリゴンの一部の領域が複数回測定されます（左下の重なっている三角形を見てください）。

誰が、私はこれを達成する方法についてのアイデアを持っていますか？私はポリゴンがS字型のようなものであれば、どの領域を計算すべきかを知ることはまだ難しいということです。（しかし、私はそれで生きることができます...（ほぼ）ポリゴンで十分な結果が得られる限り、

多角形の凸包を計算し、その上で面積計算を行うという私の他の考え方は、多角形が凸でない場合でもうまくいきません。しかし、右の画像のように、私はそれがより大きな面積を計算するだろう

誰もこれで私を助けることができれば素晴らしいことだおかげ

Answer 1

あなたは、多角形領域の一般式を見ている可能性があります。！！： http://mathworld.wolfram.com/PolygonArea.html。これは非凸多角形の場合にも当てはまります（自己交差しない限り）。

Answer 2

たとえば、zカーブやヒルベルトカーブなどのスペース充填カーブを見たいとします。 sfc曲線は、多くのタイルでサーフェスを細分化し、2次元問題を1次元問題に縮小します。あなたは、空間インデックスhilbert curveとquadtreeに関するNickのブログを検索したいと思う。

Answer 3

C/C++ではGEOS、JavaではJTS、PythonではShapelyのようなライブラリを使用しているため、これはいつも行いますが、アルゴリズムはわかりません。

余計な依存関係を取る余裕があれば、計算が堅牢で、テストされており、オープン標準入力形式（Well-Known Text）をとり、奇妙で異常なジオメトリ穴など）。いったんこの作業をすれば、幾何学を使ってあらゆる種類の奇妙で素晴らしいことを行うことができます。

Answer 4

少し遅れましたが、私はgps座標のJavaでこれを実装しました。ここで説明するように、GPS座標を正規化する必要があります：Polygon area calculation using Latitude and Longitude generated from Cartesian space and a world file。うまく働くが、デカルト座標は理想的な地球半径に基づく近似であるため、約0.005％の誤差がある。以下のコードでは、geojsonスタイルの[経度、緯度]のペアを想定していますが、それ以外の方法ではありません。

public static double area(double[][] polygon) { 
    Validate.isTrue(polygon.length > 3,"polygon should have at least three elements"); 

    double total=0; 
    double[] previous=polygon[0]; 

    double[] center = polygonCenter(polygon); 
    double xRef=center[0]; 
    double yRef=center[1]; 


    for(int i=1; i< polygon.length;i++) { 
     double[] current = polygon[i]; 
     // convert to cartesian coordinates in meters, note this not very exact 
     double x1 = ((previous[0]-xRef)*(6378137*PI/180))*Math.cos(yRef*PI/180); 
     double y1 = (previous[1]-yRef)*(Math.toRadians(6378137)); 
     double x2 = ((current[0]-xRef)*(6378137*PI/180))*Math.cos(yRef*PI/180); 
     double y2 = (current[1]-yRef)*(Math.toRadians(6378137)); 

     // calculate crossproduct 
     total += x1*y2 - x2*y1; 
     previous=current; 
    } 

    return 0.5 * Math.abs(total); 
}