2

私のアプリケーションでは、2 つ以上のポリゴンがあり、ポリゴンは他のポリゴンの内側または外側にある可能性があります (すべて内側または外側すべて)。私はこれをしなければなりません：

  1. ポリゴンが他のポリゴンの内側にあるかどうかを確認します（交差なしですべて内側にあります）。
  2. ポイント1がtrueの場合、「ポリゴンをマージ」;

私の「ポリゴンのマージ」を理解するには、次の画像を参照してください。

ここに画像の説明を入力

ご覧のように、ABCDA と 1-2-3-1 の 2 つのポリゴンがあります。2 つのポイント (ABCDA の 1 つのポイントと 1-2-3-1 の 1 つのポイント) を見つけてから、新しいラインである 2 つのラインで接続する必要があります。ポリゴンの線と交差してはなりません。

この種の問題について、最善の解決策をより速く見つけるための理論はありますか?

4

3 に答える 3

1

他のポリゴンの横にあるポリゴン

ポリゴンはすべて内側または外側のいずれかであるため、これは単純に、ポリゴンが他のポリゴンの内側にあるか外側にあるかをテストすることになります。これは、さまざまなソリューションでよく知られている問題です。ポリゴン内のポイント

ポリゴンのマージ

あなたの問題に対する唯一の解決策はありません。私にとって最も明白なアプローチは、2 つのコーナーを見つけることです。各ポリゴンの 1 つのコーナーは、他のどのコーナーのペアよりも接近しています。

于 2013-02-22T11:54:44.100 に答える
0

最高のパフォーマンスに近づくには、独自のデータでさまざまなアルゴリズムを比較する必要があります。Point-In-Polygon アルゴリズムのいくつかを比較したところ、レイキャスティングが最高のパフォーマンスを提供することがわかりました。比較は次のとおりです。よく書かれたレイキャスティング アルゴリズムの実装については、こちらを参照してください。

これは高速で単純な部分でした。次のステップでは、2 つのポリゴンをマージします。ポリゴンが凸状の場合、より近い2つの頂点を接続できますが、それらが凹状である可能性があると言っているため（または、エッジに余分な頂点がある凸状のポリゴンでさえ）、より近いコーナーは機能しません. 例えば： ここに画像の説明を入力

接続線がポリゴンのエッジと交差しない各ポリゴンから 1 つの頂点を選択する必要があります。2 つの線の交点を見つけるには、次のようにします。

function Zero(const Value: Double): Boolean;
const
  Epsilon = 1E-10;
begin
  Result := Abs(Value) < Epsilon;
end;

function IntersectLines(const X11, Y11, X12, Y12, X21, Y21, X22, Y22: Double;
  out X, Y: Double): Boolean;
var
  A1, B1, C1, A2, B2, C2, D: Double;
begin
  A1 := Y12 - Y11;
  B1 := X11 - X12;
  C1 := A1 * X11 + B1 * Y11;

  A2 := Y22 - Y21;
  B2 := X21 - X22;
  C2 := A2 * X21 + B2 * Y21;

  D := A1 * B2 - A2 * B1;
  if Zero(D) then
    Result := False // Lines are parallel
  else
  begin
    X = (B2 * C1 - B1 * C2) / D;
    Y = (A1 * C2 - A2 * C1) / D;
  end;
end;

ただし、交点を見つけただけでは、選択した頂点が適切ではないということにはならないことに注意してください。これは、線分を扱っているため、交点は線分内にある必要があるためです。それを見つけるには、ポイントがセグメントの境界ボックス内にあるかどうかを確認できます。たとえば、この図では、1 と 2 が選択された頂点であり、3 がエッジと交差する線の交点ですが、3 は 1 と 2 を覆うバウンディング ボックスの内側にはありません。

ここに画像の説明を入力

選択した頂点の各カップルの交差線は、バウンディング ボックス内の各ポリゴンの少なくとも 2 つのエッジ (選択した頂点で交わるエッジ) と交差することに注意してください。

その後、選択した頂点から外側のポリゴンを分割し、それらの間に内側のポリゴンのリダイレクトされた頂点を挿入する必要があります。

最後の言葉として、私は言うべきです：はい！これらすべてについて多くの理論がありますが、独自の理論を見つける必要があります。あなたが言ったように、1 つのポリゴンはすべて他のポリゴンの内側にあるということは、それらが体系的に生成されるか、文字境界のように事前に定義されていることを意味します。次に、説明したすべてのアルゴリズムを変更して、独自のケースでより良いパフォーマンスを達成できる場合があります。

于 2013-02-22T23:36:26.560 に答える