1

長方形のグループの周りに境界を作成する必要があるプロジェクトに取り組んでいます。

私が達成したいことの例として、この写真を使用しましょう。

編集: 画像タグを適切に機能させることができなかったので、ここに完全なリンクがあります: http://www.flickr.com/photos/21093416@N04/3029621742/

特別なリンク長方形 B によってリンクされた長方形 A と C があります。これは、グラフ内の 2 つのノード (A、C) とそれらの間のエッジ (B) と考えることができます。つまり、長方形は次の方法で相互にポインターを持っています: A->B、A<-B->C、C->B

各長方形には、インデックス 0 が左下、インデックス 3 が右下である配列に格納された 4 つの頂点があります。

このリンクされた構造を「トラバース」して、その周囲の境界 (赤い線) を構成する頂点を計算します。私はすでにこれを達成する方法についていくつかの小さなアイデアを持っていますが、数学に傾倒している人の中には、巧妙なトリックが用意されているかどうかを知りたい.

これをここに投稿する理由は、誰かが以前に同様の問題を解決し、私が使用できるいくつかのアイデアを持っている可能性があるためです. 誰もが座って、これを長く懸命に考えるとは思いません。回答を待っている間、並行して解決策に取り組みます。

どんな入力でも大歓迎です。

4

6 に答える 6

6

長方形が互いに垂直であるため、4 つの値 (2 つの x 座標と 2 つの y 座標) で表すことができる例を使用します。

   1 2 3 4 5 6

1 +---+---+
   | | | |   
2 + A +---+---+
   | | | | ビ |
3 + + +---+---+
   | | | | | | | | | |
4 +---+---+---+---+ +
               | | | |
5 + C +
               | | | |
6 +---+---+

1) すべての x 座標 (左と右の両方) をリストに収集し、並べ替えて重複を削除します

1 3 4 5 6

2) すべての y 座標 (上と下の両方) をリストに収集し、並べ替えて重複を削除します。

1 2 3 4 6

3) 一意の x 座標間のギャップ数 * 一意の y 座標間のギャップ数で 2D 配列を作成します。セルごとに 1 ビットしか必要ないため、c++ では vector<bool> を使用すると、これの非常にメモリ効率の高いバージョンが得られる可能性があります。

4*4

4）すべての長方形をこのグリッドにペイントします

   1 3 4 5 6

1 +---+
   | | 1 | 0 0 0
2 +---+---+---+
   | | 1 | 1 | 1 | 0
3 +---+---+---+---+
   | | 1 | 1 | 1 | 1 |
4 +---+---+---+---+
     0 0 | 1 | 1 |
6 +---+---+

5) グリッド内の各セル、各エッジについて、その基本方向のセルの横にあるセルがペイントされていない場合は、そのエッジの境界線を描画します

問題では、長方形は、それぞれが角を表す 4 つのベクトルとして記述されています。各長方形が任意で、他の長方形とは異なる回転である場合、上で概説したアプローチは機能しません。複雑なポリゴンの周りのパスを見つける問題は、通常、ベクター グラフィックス ラスタライザーによって解決されます。この問題を解決するための良いアプローチは、Cairo などのライブラリを使用して作業を行うことです!

于 2008-11-16T23:22:34.937 に答える
2

この問題に対する一般化された解決策は、スキャンラインに関してブール演算を実装することです。開始するための簡単なディスカッションをここで見つけることができます。テキストから：

「ブールアルゴリズムの基礎はスキャンラインです。基本的な原則については、Franco P. Preparata と Michael Ian Shamos によるComputational Geometry an Introductionが非常に優れています。」

私はこの本を持っていますが、今はオフィスにあるので、読むべきページ番号を調べることはできませんが、長方形の幾何学に関する第 8 章がおそらく最良の出発点です。

于 2008-11-16T04:35:50.233 に答える
1
  1. 3 つの長方形すべての境界の合計を個別に計算する
  2. A と B の重なり合う四角形を計算し、合計から減算します。
  3. B と C の重なっている四角形についても同じことを行います。

(A と B から重複する長方形を取得するには、中央の 2 つの X 位置と、中央の 2 つの Y 位置を取得します)

例 (x1,y1) - (x2,y2):

  • 長方形 A: (1,1) - (3,4)
  • 長方形 B: (3,2) - (5,4)
  • 長方形 C: (4,3) - (6,6)

計算：

  1. 10 + 8 + 10 = 28
  2. 順序付けられた X 座標 = 1,3,3,5 中央の 2 つは 3 と 3
    順序付けられた Y 座標 = 1,2,4,4 中央の 2 つは 2 と 4
    なので: (3,2) - (3,4) : 境界 = 4
  3. 順序付けられた X 座標 = 3,4,5,6 中央の 2 つは 4 と 5
    順序付けられた Y 座標 = 2,3,4,6 中央の 2 つは 3 と 4
    なので: (4,3) - (5,4) : 境界 = 4
  4. 28 - 4 - 4 = 20

これは視覚化された私の例です:

   1   2   3   4   5   6

1  +---+---+
   |       |   
2  +   A   +---+---+
   |       | B     |
3  +       +   +---+---+
   |       |   |   |   |
4  +---+---+---+---+   +
               |       | 
5              +   C   +
               |       |
6              +---+---+
于 2008-11-14T16:20:10.843 に答える
0

簡単なトリックは次のとおりです。

  1. 最初の長方形から領域を作成する
  2. 他の長方形を領域に追加します
  3. 領域の境界を取得します (何とか? :P)
于 2008-11-14T11:04:57.360 に答える
0

少し考えた後、私は次のようなことをするかもしれません：

擬似コード:

 LinkRectsConnectedTo(Rectangle rectangle,Edge startEdge) // Edge can be West,North,East,South 
    for each edge in rectangle starting with the edge facing last rectangle
       add vertices in the edge to the final boundary polygon
       if edge is connected to another rectangle
          if edge not equals startEdge
             recursively call LinkRectsConnectedTo(rectangle,startEdge)

明らかに、この疑似コードは少し改良する必要があり、すべてのケースをカバーしていない可能性がありますが、私は自分の問題を解決したかもしれないと思います.

于 2008-11-14T11:25:57.957 に答える
0

私はこれを完全に考えていませんが、次のようなことができないのだろうか：

  • すべてのエッジのリストを作成します。
  • P1.X = P2.X であるすべてのエッジを取得します。
  • そのリストで、X が等しいペアを取得します
  • ペアごとに、重ならない部分の 1 つまたは 2 つのエッジに置き換えます
  • エッジを正しい順序で取得するために巧妙なことを行います

あなたの四角形は常に水平に配置されますか? そうでない場合は、同じことを行う必要がありますが、Y についても同様ですか? そして、彼らは常に触れていることが保証されていますか? そうでない場合、アルゴリズムは壊れませんが、「正しい順序」は定義できません。

于 2008-11-14T12:17:02.190 に答える