8

例 http://xthlegion.co.uk/images/dividerectangle.png 例 http://xthlegion.co.uk/images/dividerectangle2.png

上の画像を検討すると、ユーザー定義の座標のペアによって小さな四角形に分割された単一の大きな四角形で構成されていることがわかります (例の画像の各ペアは、異なる色で識別されます)。

私がやろうとしているのは、結合を定義するだけで、これらの長方形の座標を取得することです。エッジは明示的な結合として扱われます。順番は関係ありません。

これを行うアルゴリズムの名前を知っている人はいますか (派手な名前のアルゴリズムがあると確信しています!)、または C# コードの例がありますか? 私はしばらくの間、これを自分でやろうとして苦労してきましたが、ほとんど成功していません。さらに別の完全な数学の失敗!

更新:
受け取ったコメントに基づいて、この質問をすぐに更新すると思いました。

  1. 線は直線でなければならないため、座標の各ペアは 1 つの軸上に配置されます
  2. 座標は、エッジまたは別のペアの交点から開始する必要があります。2 番目の座標も同様に終了する必要があります。相互に開始/終了しない「孤立した」座標は違法であり、今のところ無視する必要があります。最終的に頭が整ったら、スナップが可能になるはずです。
  3. この例では、すべてのペアが多かれ少なかれきれいに四角形を分割していますが、実際にはそうではなく、さまざまなサイズの四角形を作成する多くの線が存在する可能性があります。

2 回目の更新 - 動作します :)
例 http://xthlegion.co.uk/images/dividerectangle3.png

4

3 に答える 3

5

あなたが計算しようとしているのは、線分の配置です。(特に良い名前ではありませんが、私たちが行き詰っている名前のようです!) それを計算するには:

  1. 交点のセット (2 つの線分が交わる、または交差するすべての点) を見つけます。これは、Bentley–Ottmann アルゴリズムで計算できます。n 個の線分とk 個の交差がある場合、これには O(( n + k ) log n ) かかります。(ただし、線分が少ない場合は、単純な O( n 2 ) アルゴリズムを使用する方がよいでしょう。)

  2. 少し追加の簿記を使用すると、各交点でどのエッジが発生したかを記録できるため、線分のセットに対応する平面直線グラフ(PSLG) を計算できます。

  3. PSLG をクワッドエッジ データ構造に変換します。これには 2 つの手順が必要です。最初に、各頂点に付随するエッジを角度で順序付けることにより、データ構造内のエッジ (エッジ接続) を見つけます。

  4. 2 つの面にまだ接続されていないエッジを選択し、接続されていない側に面を作成し、その面の境界を歩き回り、それを各エッジに順番に接続します。すべてのエッジが 2 つの面に接続されるまで繰り返します。

一般に、これにより長方形以外の面が生成されます (すべての線分が軸に沿って配置され、すべての交点が整数の座標を持っている場合でも)、アプリケーションではこれが発生しないか、長方形以外の面を破棄できます。

于 2012-12-17T22:15:41.227 に答える
2

答えは、次のルールを前提としています。これは、いずれにしても必要であると私は信じています。

ユーザーは、水平線または垂直線を使用して既存の四角形を再分割することしかできません。

これは、最初の例では、サブディビジョンの順序は、ブラウン、イエロー、ブルー グリーンでなければならないことを意味します。

使用している四角形クラスに関係なく、2 つの拡張メソッドを定義します:SubdivideHorizontalとSubdivideVerticalは、サブディビジョンの座標を受け入れ、サブディビジョンの結果として得られる 2 つの四角形を返します。
再分割する各四角形を、結果として得られる 2 つの再分割四角形に置き換え、すべての再分割に対して再帰的に繰り返します。

于 2012-12-17T19:55:41.870 に答える
-1

私は次のことをします。

  1. 外側の 4 つのコーナーのそれぞれにポイントを作成します。
  2. 各ユーザー定義ポイントにポイントを作成します。
  3. ラインが空のポイントを横切るたびにポイントを作成します。
  4. 各正方形を実行し、4 つの角すべてに点があるかどうかを確認します。
于 2012-12-17T19:41:57.177 に答える