91

自己交差しない 2 次元空間内の一連のポイントを想定すると、結果のポリゴンの面積を決定する効率的な方法は何ですか?

補足として、これは宿題ではなく、コードを探しているわけではありません。独自のメソッドを実装するために使用できる説明を探しています。ポイントのリストから一連の三角形を引き出すことについてのアイデアはありますが、凸面ポリゴンと凹面ポリゴンに関しては、おそらくキャッチできないエッジケースがたくさんあることを知っています。

4

16 に答える 16

119

これが標準的な方法であるAFAIKです。基本的に、各頂点の周りの外積を合計します。三角測量よりもはるかに簡単です。

（x、y）頂点座標のリストとして表されるポリゴンが与えられ、最後の頂点から最初の頂点に暗黙的にラップアラウンドするPythonコード：

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のコメント：このアルゴリズムが機能する理由について言及する価値があります。これは、関数-yおよびxに対するグリーンの定理の適用です。プラニメータの動作とまったく同じです。すなわち：

上記の式=
integral_over_perimeter(-y dx + x dy) =
integral_over_area((-(-dy)/dy+dx/dx) dy dx) =
2 Area

于 2009-01-16T18:39:05.157 に答える
14

クロス積は古典的です。

そのような計算を無数に行う必要がある場合は、必要な乗算が半分になる次の最適化されたバージョンを試してください。

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;

わかりやすくするために、配列の添え字を使用します。ポインタを使用する方が効率的です。ただし、優れたコンパイラがそれを行います。

多角形は「閉じている」と見なされます。つまり、最初の点を下付き文字 N の点としてコピーすることを意味します。また、多角形の点の数が偶数であると仮定します。N が偶数でない場合は、最初の点の追加のコピーを追加します。

このアルゴリズムは、古典的な外積アルゴリズムの 2 つの連続した反復を展開して結合することによって得られます。

2 つのアルゴリズムが数値精度に関してどのように比較されるかはよくわかりません。私の印象では、乗算は減算の精度の損失を回復する傾向があるため、上記のアルゴリズムは従来のアルゴリズムよりも優れています。GPU のように float を使用するように制限されている場合、これは大きな違いを生む可能性があります。

編集：「三角形と多角形の2Dおよび3Dの領域」は、さらに効率的な方法について説明しています

// "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;
于 2009-04-04T16:38:57.343 に答える
13

このページは、式が

ここに画像の説明を入力

次のように簡略化できます。

ここに画像の説明を入力

いくつかの項を書き出し、それらを の共通因数に従ってグループ化するとxi、等式は難しくありません。

nの代わりに乗算のみが必要なため、最終的な合計はより効率的です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

この単純化については、こちらの Joe Kington から学びました。

NumPy を使用している場合、このバージョンの方が高速です (非常に小さな配列を除くすべての場合):

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
于 2013-11-09T11:48:55.767 に答える
5

三角形と合計の三角形の領域を拡張するには、凸多角形がある場合、または多角形と交差する他のすべての点への線を生成しない点を選択した場合に、これらが機能します。

一般的な交差しないポリゴンの場合、aとbが互いに「隣接」しているベクトル（参照点、点a）、（参照点、点b）の外積を合計する必要があります。

ポリゴンを順番に定義するポイントのリストがあると仮定します（ポイントiとi + 1がポリゴンのラインを形成する順序）：

Sum（外積（（ポイント0、ポイントi）、（ポイント0、ポイントi + 1））for i=1からn-1。

その外積の大きさをとると、表面積が得られます。

これにより、適切な基準点を選択することを心配することなく、凹多角形を処理できます。ポリゴンの内側にない三角形を生成する3つのポイントには、ポリゴンの内側にある三角形の反対方向を指す外積があるため、領域は正しく合計されます。

于 2009-01-16T18:40:31.830 に答える
5

他の制約のないポイントのセットは、必ずしも多角形を一意に定義するとは限りません。

最初に、これらの点からどのポリゴンを構築するかを決定する必要があります。おそらく凸包ですか? http://en.wikipedia.org/wiki/Convex_hull

次に、三角測量して面積を計算します。 http://www.mathopenref.com/polygonirregulararea.html

于 2009-01-16T18:34:18.723 に答える
3

ポリゴンの面積を計算するには

http://community.topcoder.com/tc?module=静的&d1=チュートリアル&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);
}
于 2012-10-04T15:05:38.503 に答える
2

言語に依存しないソリューション：

与えられた：ポリゴンは常に重なり合わないn-2個の三角形で構成できます（n =点または辺の数）。1つの三角形=1つの側面のポリゴン=1つの三角形; 1つの正方形=4辺の多角形=2つの三角形; etc ad nauseam QED

したがって、三角形を「切り落とす」ことでポリゴンを縮小でき、総面積はこれらの三角形の面積の合計になります。一枚の紙とはさみで試してみてください。次の手順を実行する前に、プロセスを視覚化するのが最善です。

ポリゴンパスで3つの連続するポイントを取得し、これらのポイントで三角形を作成すると、考えられる3つのシナリオのうちの1つだけが発生します。

  1. 結果の三角形は完全に元のポリゴンの内側にあります
  2. 結果の三角形は完全に元のポリゴンの外側にあります
  3. 結果の三角形は、元のポリゴンに部分的に含まれています

最初のオプション（完全に含まれている）に該当する場合にのみ関心があります。

これらのいずれかを見つけるたびに、それを切り取り、その面積を計算し（簡単で、ここでは式を説明しません）、辺が1つ少ない新しいポリゴンを作成します（この三角形が切り取られたポリゴンに相当します）。三角形が1つだけ残るまで。

これをプログラムで実装する方法：

ポリゴンの周りのパスを表す（連続した）ポイントの配列を作成します。ポイント0から開始します。ポイントx、x + 1、およびx + 2から三角形を（一度に1つずつ）作成する配列を実行します。各三角形を形状から領域に変換し、ポリゴンから作成された領域と交差させます。結果の交差が元の三角形と同一である場合、その三角形は完全にポリゴンに含まれており、切り落とすことができます。配列からx+1を削除し、x=0から再開します。それ以外の場合（三角形が[部分的または完全に]ポリゴンの外側にある場合）、配列内の次のポイントx+1に移動します。

さらに、マッピングとの統合を検討していて、ジオポイントから開始する場合は、最初にジオポイントからスクリーンポイントに変換する必要があります。これには、地球の形状のモデリングと式を決定する必要があります（地球は球体と考える傾向がありますが、実際には、へこみのある不規則な卵形（卵形）です）。詳細については、多くのモデルがあります。重要な問題は、その領域を平面と見なすか、湾曲していると見なすかどうかです。一般に、ポイントが最大数km離れている「小さな」領域は、平面で凸状ではないと見なす場合、重大なエラーを生成しません。

于 2011-08-21T15:06:08.337 に答える
2

または輪郭積分を行います。ストークスの定理を使用すると、面積積分を等高線積分として表すことができます。小さなガウス求積法とボブはあなたのおじです。

于 2009-01-16T18:33:40.393 に答える
1
  1. 基点（最も凸の点）を設定します。これが三角形のピボット ポイントになります。
  2. 基点以外の一番左の点 (任意) を計算します。
  3. 左から 2 番目の点を計算して、三角形を完成させます。
  4. この三角領域を保存します。
  5. 反復ごとに 1 ポイント右にシフトします。
  6. 三角形分割された領域の合計
于 2009-01-16T18:25:57.320 に答える
1

デカルト空間で台形を合計することは、三角形を合計するよりも優れています。

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;
}
于 2009-01-16T19:34:35.870 に答える
1

これを行う 1 つの方法は、ポリゴンを三角形に分解し、三角形の面積を計算し、合計をポリゴンの面積として取得することです。

于 2009-01-16T18:24:40.113 に答える
0

それを行うCの方法：

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;
}
于 2015-12-02T21:27:54.327 に答える
0

私の傾向は、単純に三角形を切り落とし始めることです。ひどく毛むくじゃらになるのを避ける方法が他にあるとは思えません。

多角形を構成する 3 つの連続した点を取得します。角度が 180 未満であることを確認してください。これで、問題なく計算できる新しい三角形が作成されました。多角形の点のリストから中間点を削除します。残り3点になるまで繰り返します。

于 2009-01-16T18:23:55.047 に答える