71

ポリゴンの交差/クリッピングを計算するための非常に単純なアルゴリズムを探しています。つまり、与えられた多角形P、 、および に含まれるQ多角形を見つけたいと考え、すべての可能な多角形の中で最大になりたいと考えています。TPQT

実行時間は気にしません (非常に小さなポリゴンがいくつかあります)。また、ポリゴンの交点 (つまり、ポイントが少ないがポリゴンの交点にまだ含まれているポリゴン) の近似値を取得する余裕もあります。 ）。

しかし、アルゴリズムが単純 (テストが安価) で、できれば短い (コードが少ない) ものであることは、私にとって非常に重要です。

編集:交差点を表すポリゴンを取得したいことに注意してください。2 つのポリゴンが交差するかどうかという質問に対するブール値の答えだけが必要なわけではありません。

4

10 に答える 10

66

元の投稿者が簡単な解決策を探していたことは理解していますが、残念ながら実際には簡単な解決策はありません。

それにもかかわらず、私は最近、あらゆる種類のポリゴン (自己交差ポリゴンを含む) をクリップするオープンソースのフリーウェア クリッピング ライブラリ (Delphi、C++、および C# で記述) を作成しました。このライブラリの使い方は非常に簡単です: http://sourceforge.net/projects/polyclipping/ .

于 2010-06-06T11:28:06.440 に答える
18

ポリゴン クリッピングアルゴリズムを使用して、2 つのポリゴン間の交点を見つけることができます。ただし、すべてのエッジ ケースを考慮すると、これらは複雑なアルゴリズムになる傾向があります。

お気に入りの検索エンジンを使用して探すことができるポリゴン クリッピングの 1 つの実装は、Weiler-Athertonです。Weiler-Atherton に関するウィキペディアの記事

Alan Murta は、ポリゴン クリッパーGPCを完全に実装しています。

編集：

もう 1 つの方法は、最初に各ポリゴンを扱いやすい三角形のセットに分割することです。Gary H. Meisters によるTwo-Ears Theoremはそのトリックを行います。McGillのこのページでは、三角形の細分割について説明しています。

于 2010-02-16T13:05:37.140 に答える
15

C++ を使用していて、自分でアルゴリズムを作成したくない場合は、Boost.Geometryを使用できます。上記の Weiler-Atherton アルゴリズムの適応バージョンを使用します。

于 2010-02-21T10:15:14.610 に答える
6

あなたは私たちにポリゴンの表現を与えていません。だから私はあなたのために（提案するように）1つを選んでいます:)

各ポリゴンを1つの大きな凸多角形として表し、その大きな凸多角形から「減算」する必要がある小さな凸多角形のリストを表します。

その表現に2つのポリゴンが与えられた場合、交差を次のように計算できます。

大きな凸多角形の交点を計算して、交点の大きな多角形を形成します。次に、両方の小さい方のすべての交点を「減算」して、サブラクトされたポリゴンのリストを取得します。

同じ表現に従って新しいポリゴンを取得します。

凸多角形の交点は簡単なので、この交点の検索も簡単です。

これはうまくいくはずですが、正確さ/時間/空間の複雑さに関しては、これ以上深く考えていません。

于 2010-02-16T17:44:40.997 に答える
4

これは単純でばかげたアプローチです。入力時に、ポリゴンをビットマップに離散化します。交差するには、ビットマップを AND します。出力ポリゴンを生成するには、ビットマップのギザギザの境界線をトレースし、ポリゴン近似アルゴリズムを使用してギザギザを滑らかにします。（そのリンクが最も適切なアルゴリズムを提供するかどうかは覚えていません。これは Google の最初のヒットにすぎません。ビットマップ画像をベクトル表現に変換するツールの 1 つをチェックしてみてください。アルゴリズムを再実装せずにそれらを呼び出すことができるかもしれません。 ?)

最も複雑な部分は、境界をトレースすることだと思います。

ちなみに、90 年代の初めに、私は職場でこのような問題に直面しました。私はそれを黙らせました：実数座標で機能する（完全に異なる）アルゴリズムを思いつきましたが、浮動小数点（およびノイズの多い入力）の現実に直面して、完全に修正不可能な大量の退化ケースに遭遇したようです. おそらくインターネットの助けを借りて、私はもっとうまくやれたでしょう！

于 2010-02-16T23:04:23.137 に答える
0

非常に単純な解決策はありませんが、実際のアルゴリズムの主な手順は次のとおりです。

  1. ポリゴンの頂点とエッジに対してカスタムの二重リンク リストを作成します。ノードでの特別な操作のために、次と前のポインター/オフセットを自分で交換する必要があるため、使用std::listすることはできません。これは単純なコードを持つ唯一の方法であり、これにより優れたパフォーマンスが得られます。
  2. エッジの各ペアを比較して交点を見つけます。エッジの各ペアを比較すると O(N²) の時間がかかりますが、後でアルゴリズムを O(N・logN) に改善するのは簡単です。いくつかのエッジのペア (a→b と c→d など) では、交点は、tₐ=d0/(d0-d₁) で与えられるエッジ a→b のパラメーター (0 から 1) を使用して検出されます。ここで、d0 は (ca)×(ba)、d1 は (da)×(ba) です。× は、p×q=pₓ・qᵧ-pᵧ・qₓ などの 2D 外積です。tₐ を見つけた後、交点を見つけるには、それをセグメント a→b の線形補間パラメーターとして使用します: P=a+tₐ(ba)
  3. 各エッジを分割して、セグメントが交差する頂点 (およびリンク リスト内のノード) を追加します。
  4. 次に、交点でノードを交差する必要があります。これは、カスタムの二重リンク リストを実行するために必要な操作です。次のポインターのいくつかのペアを交換する必要があります (それに応じて前のポインターを更新し ます)。

次に、ポリゴン交差解決アルゴリズムの生の結果が得られます。通常、各リージョンの巻数に応じてリージョンを選択します。これに関する説明については、ポリゴンの巻き数を検索してください。

この O(N²) アルゴリズムから O(N·logN) アルゴリズムを作成する場合は、ライン スイープ アルゴリズム内で行うことを除いて、まったく同じことを行う必要があります。Bentley Ottman アルゴリズムを探します。内部アルゴリズムは同じですが、ループ内で比較するエッジの数が減るという唯一の違いがあります。

于 2015-05-26T13:43:26.797 に答える
0

ポリゴンが整列していない場合は、整列する必要があります。これを行うには、多角形の中心 (X の平均、Y の平均) を見つけてから、行列変換によって多角形を段階的に回転させ、点を軸の 1 つに投影し、最小 stdev の角度を使用して形状を揃えます (主成分を使用することもできます)。交点を見つけるための単純なアルゴリズムは、点のグリッドを定義することです。各ポイントについて、1 つのポリゴン、または他のポリゴン、またはその両方 (ユニオン) 内のポイントの数を維持します (これには、たとえばhttp://wiki.unity3d.com/index.php?title=PolyContainsPointなどのシンプルで高速なアルゴリズムがあります。）。ポリゴン 1 とポリゴン 2 のポイントをカウントし、ポリゴン 1 またはポリゴン 2 のポイントの量で割ると、(グリッド サンプリングに応じて) ポリゴンのオーバーラップの割合が概算されます。交差領域は、AND 演算に対応する点によって与えられます。

例えば。

function get_polygon_intersection($arr, $user_array)
{
    $maxx = -999;  // choose sensible limits for your application
    $maxy = -999;
    $minx = 999;
    $miny = 999;
    $intersection_count = 0;
    $not_intersected = 0;
    $sampling = 20;
    
    // find min, max values of polygon (min/max variables passed as reference)
    get_array_extent($arr, $maxx, $maxy, $minx, $miny);
    get_array_extent($user_array, $maxx, $maxy, $minx, $miny);
    
    $inc_x = $maxx-$minx/$sampling;
    $inc_y = $maxy-$miny/$sampling;
    
    // see if x,y is within poly1 and poly2 and count
    for($i=$minx; $i<=$maxx; $i+= $inc_x)
    {
        for($j=$miny; $j<=$maxy; $j+= $inc_y)
        {
            $in_arr = pt_in_poly_array($arr, $i, $j);
            $in_user_arr = pt_in_poly_array($user_array, $i, $j);
            
            if($in_arr && $in_user_arr)
            {
                $intersection_count++;
            }
            else
            {
                $not_intersected++;
            }
        }
    }
    
    // return score as percentage intersection
    return 100.0 * $intersection_count/($not_intersected+$intersection_count);
}
于 2021-05-05T15:37:42.100 に答える
-2

これは、ポリゴンによっては大まかな概算になる可能性がありますが、次のとおりです。

  • 各ポリゴンの重心を計算します。
  • 多角形の各点から重心までの最小距離、最大距離、または平均距離を計算します。
  • C1C2 (C1/2 は最初/2 番目のポリゴンの中心) >= D1 + D2 (D1/2 は最初/2 番目のポリゴンで計算した距離) の場合、2 つのポリゴンは「交差」します。

ただし、ポリゴンへの変換は重心にまったく同じ方法で適用され、中心ノードの距離は一度しか計算できないため、これは非常に効率的です。

于 2010-02-16T10:55:53.377 に答える