7

この問題では、速度が非常に重要です。問題をよりよく説明するために、素敵な画像を描きました。アルゴリズムは、長方形のエッジがキャンバスの範囲内に続くかどうかを計算する必要があります。エッジは別の長方形と交差しますか?

私たちは知っています：

  1. キャンバスのサイズ
  2. 各長方形のサイズ
  3. 各長方形の位置

解決が早ければ早いほど良いです！私はこれにかなり行き詰まっており、どこから始めればよいか本当にわかりません。

代替テキスト http://www.freeimagehosting.net/uploads/8a457f2925.gif

乾杯

4

6 に答える 6

6

X 軸と Y 軸のそれぞれに一連の間隔を作成するだけです。次に、新しい長方形ごとに、X 軸または Y 軸に交差する間隔があるかどうかを確認します。間隔セットを実装する 1 つの方法については、こちらを参照してください。

最初の例では、横軸に設定された間隔は 、縦軸には次のよう{ [0-8], [0-8], [9-10] }になります。{ [0-3], [4-6], [0-4] }

これは単なるスケッチです。ここでは多くの詳細を抽象化しました (たとえば、通常、間隔セット/ツリーに対して、「これと交差する」のではなく「どの間隔がこれと重なるか」と尋ねますが、実行できないことは何もありません)。

編集

この関連する MIT レクチャーをご覧ください(少し長いですが、絶対に価値があります)。(拡張赤黒木を実装するよりも) 単純な解決策を見つけたとしても、これらの背後にある考え方を知っておくとよいでしょう。

于 2010-07-08T12:36:17.387 に答える
2

互いに平行でない直線は、ある時点で交差します。各線の傾きを計算し、交差しない線を決定します。

それから始めて、それを最適化する方法を見てみましょう。あなたのデータがどのように表現されているかわかりませんし、あなたの画像も見えません。

勾配の使用は単純な等値チェックであり、おそらくデータの並べ替えを利用できることを意味します。実際、一連の個別の傾斜を作成することもできます。同じ長方形の 2 つの勾配が交差しているとは見なされないように、データを表す方法を理解する必要があります。

編集:待って.. 辺が無限遠になる 2 つの長方形が交差しないのはどうしてですか? 長方形は、基本的に互いに垂直な 2 本の線です。それらの線が無限に伸びている場合、それは常に別の線と交差することを意味するべきではありませんか?

于 2010-07-08T12:35:08.920 に答える
1

ここにアイデアがあります。で各長方形を作成する代わりに(x, y, width, height)、でインスタンス化する(x1, y1, x2, y2)か、少なくとも幅と高さを指定してこれらの値を解釈させます。

このようにして、どの長方形が類似xまたはy値を持っているかをチェックし、対応する長方形が同じ2次値を持っていることを確認できます。

例：

指定した長方形の値は次のとおりです。

  • 正方形1：[0、0、8、3]
  • 正方形3：[0、4、8、6]
  • 正方形4：[9、0、10、4]

まず、（衝突なし）と比較Square 1します。Square 3

  • x値を比較する
    • [0、8]から[0、8]これらはまったく同じであるため、クロスオーバーはありません。
  • y値を比較する
    • [0、4]から[3、6]これらの数値はどれも類似していないため、要因ではありません

次に、 （衝突）と比較Square 3します。Square 4

  • x値を比較する
    • [0、8]から[9、10]これらの数値はどれも類似していないため、要因ではありません
  • y値を比較する
    • [4、6]から[0、4]長方形の数は共通して4ですが、0！= 6であるため、衝突が発生します。

衝突が発生することがわかっているので、メソッドは終了しますが、評価Square 1をSquare 4行い、さらに明確にするために使用します。

  • x値を比較する
    • [0、8]から[9、10]これらの数値はどれも類似していないため、要因ではありません
  • y値を比較する
    • [0、3]から[0、4]長方形の数は共通して0ですが、3！= 4であるため、衝突が発生します。

追加の詳細が必要な場合はお知らせください:)

于 2010-07-08T13:08:06.913 に答える
1

私はこの質問が好きです。これが私の試みです：

可能な場合: 各長方形から多角形を作成します。各エッジは、クリップする必要がある最大長の線として扱います。クリッピング アルゴリズムを使用して、天気をチェックしたり、ラインが別のラインと交差していないかどうかを確認したりします。たとえば、これは次のとおりです。ラインクリッピング

ただし、心に留めておいてください。頂点位置にある交点が見つかった場合、それは有効なものです。

于 2010-07-08T13:01:22.407 に答える
1

問題を解決するために選択した言語について言及していない限り、何らかの疑似コードを使用します

すべてが問題なければ、1 つの軸に沿った四角形のエッジの並べ替えられたコレクションは、重複しない間隔のシーケンスになるはずです。

  1. すべての長方形に番号を付け、個々の ID を割り当てます
  2. 空のバイナリ ツリー コレクション (btc) を作成します。このコレクションには、情報 btc::insert(key, value) を持つ整数ノードを挿入するメソッドが必要です
  3. すべての長方形に対して、次のようにします。

foreach rect in rects do
    btc.insert(rect.top, rect.id)
    btc.insert(rect.bottom, rect.id)
  1. 今、btc を反復します (これにより、並べ替えられた順序が得られます)

btc_item = btc.first()
do
    id = btc_item.id
    btc_item = btc.next()
    if(id != btc_item.id)
    then report_invalid_placement(id, btc_item.id)
    btc_item = btc.next()
while btc_item is valid

5,7,8 - rect.left および rect.right の座標について、手順 2、3、4 を繰り返します。

于 2010-07-08T12:49:19.453 に答える
0

ええと、重なり合う間隔の答えを極端にとると、x軸とy軸に沿ったすべての異なる間隔を単純に決定します。切断線ごとに、間隔の開始値に基づいて切断する軸に沿って上限検索を実行します。間隔が見つからない場合、または間隔が線と交差していない場合、それは有効な線です。

少し注意が必要なのは、有効な切断線が軸に沿って長方形の境界と交差しないことを理解することです。そのため、重なり合う間隔を1つの間隔に組み合わせることができます。最終的に、単純な並べ替えられた配列（O（n）時間を入力）と各切断線のO（log n）検索が行われます。

于 2010-07-09T06:53:40.813 に答える