c++ - 不規則な形状の領域

Question

画像上にあるポイントのセットがあります。これらの点のセットは、不規則な閉じた形状を形成します。この形の領域を見つける必要があります。面積の計算に使用される通常のアルゴリズムであるボディはありますか？または、ブーストなどのライブラリで利用可能なサポートはありますか？私はC++を使用しています。

Answer 1

ポリゴンが単純な場合 (連続するセグメントのペアを除いて共通点がない場合)、ウィキペディアが役に立ちます。

面積の公式は

（最後のポイントは最初のポイントと同じであると想定しています）

として簡単に実装できます。

float area = 0.0f;

for (int i = 0; i < numVertices - 1; ++i)
  area += point[i].x * point[i+1].y - point[i+1].x * point[i].y;

area += point[numVertices-1].x * point[0].y - point[0].x * point[numVertices-1].y;

area = abs(area) / 2.0f;

もちろん、頂点は、ポリゴン内の自然な追従に従って順序付けする必要があります..

Answer 2

そのための総和の公式があります。

Answer 3

グラフィカルな例を提供することで、より正確になりたいと思うかもしれません。

たとえば、ポイントが単なるピクセルである場合、ピクセル数は面積に等しくなります。しかし、点が多角形の角である場合、多角形の面積はそれほど簡単には決定できません。ポリゴン三角形分割を使用し、得られた三角形の面積を合計します。

Answer 4

謙虚にならずに、私はあなたに別の質問への私の答えを紹介します。重なり合う円の結合された領域。モンテカルロは堅牢で、並列化が容易であり、最終的には、必要な精度に対する答えを提供します。

Answer 5

これを行う最も簡単な方法は、おそらく形状を三角測量し、三角形の面積を計算することです。Dave Eberlyには、三角測量に役立つ可能性のある（Boostライセンス）というライブラリがあります。詳細については、こちらをご覧ください。たとえば、TriangulateECを探します。

Answer 6

注: ポイントの順序がわからず、ポリゴンが凸面であることを保証できない場合は、ポリゴンを生成するポイントの順序が複数ある可能性があるため、形状の順序を決定することはできません。多角形が凸面であることがわかっている場合、点の順序を決定するのは簡単です。ある特定の点からの角度で点を並べ替えるだけです。最初の点は、それ自体と最初の点との間に線を形成する点であり、他のすべての点が線の同じ側にあるようにします。このプロセスによって形成された三角形は、面積の計算にも使用できます。

Answer 7

Boost.Geometry でポリゴンの面積計算がサポートされています (これはまだ Boost に受け入れられておらず、使用するのが非常に混乱します)。それ以外の場合は、最初にポイントによって定義されるポリゴンを決定する必要があります。見た目からすると、すべてのポイントはポリゴンの頂点であるため、ポイント セットを正しく並べ替えるだけです。もう 1 つの可能性は、ポイント セットの凸包を探していることです ( http://en.wikipedia.org/wiki/Convex_hull_algorithmsを参照)。