8

私は整数次元の長方形の平面を持っています。この平面の内側には、（整数次元で整数座標の）交差しない長方形のセットがあります。

私の質問は、このセットの逆を効率的に見つけるにはどうすればよいかということです。これは、サブ長方形に含まれていない平面の部分です。当然、この点の集まりは長方形のセットを形成します---そして私が興味を持っているのはこれらです。

私の現在の素朴な解決策は、ブール行列（平面のサイズ）を使用し、点i、jがサブ長方形内に含まれている場合は0に設定し、そうでない場合は1に設定することで機能します。次に、行列の各要素を反復処理し、それが1（無料）の場合は、ポイントから外側に向かって長方形を「成長」させます。一意性は問題ではありません（適切な長方形のセットであれば問題ありません）。

このような問題をより効果的に解決できるアルゴリズムはありますか？（つまり、ブール行列に頼る必要はありません。

4

5 に答える 5

7

はい、それはかなり簡単です。私は以前にSOについてほぼ同じ質問に答えましたが、まだそれを見つけることができませんでした。

とにかく、本質的にあなたはこれを行うことができます：

  • 対象領域に等しい単一の出力四角形を含む出力リストから開始します（対象領域を定義し、すべての入力四角形を含む任意のバウンディングボックス）
  • 各入力rectに対して
    • 入力rectが出力リストのいずれかのrectと交差する場合
      • 古い出力rectを削除し、交差点と元の出力rectの違いを表す最大4つの新しい出力rectを生成します。

オプションの最終ステップ：出力リストを反復処理して、単一のrectにマージできるrectのペアを探します（つまり、共通のエッジを共有するrectのペアを1つのrectに結合できます）。

于 2010-11-21T19:10:25.330 に答える
5

大丈夫！最初の実装！（java）、@ Paulの 回答に基づく：

List<Rectangle> slice(Rectangle r, Rectangle mask)
{
        List<Rectangle> rects = new ArrayList();

        mask = mask.intersection(r);

        if(!mask.isEmpty())
        {
                rects.add(new Rectangle(r.x, r.y, r.width, mask.y - r.y));
                rects.add(new Rectangle(r.x, mask.y + mask.height, r.width, (r.y + r.height) - (mask.y + mask.height)));
                rects.add(new Rectangle(r.x, mask.y, mask.x - r.x, mask.height));
                rects.add(new Rectangle(mask.x + mask.width, mask.y, (r.x + r.width) - (mask.x + mask.width), mask.height));

                for (Iterator<Rectangle> iter = rects.iterator(); iter.hasNext();)
                        if(iter.next().isEmpty())
                                iter.remove();
        }
        else rects.add(r);

        return rects;
}

List<Rectangle> inverse(Rectangle base, List<Rectangle> rects)
{
        List<Rectangle> outputs = new ArrayList();
        outputs.add(base);

        for(Rectangle r : rects)
        {
                List<Rectangle> newOutputs = new ArrayList();

                for(Rectangle output : outputs)
                {
                        newOutputs.addAll(slice(output, r));
                }

                outputs = newOutputs;
        }
        return outputs;
}

ここでおそらく実用的な例

于 2010-11-21T20:21:22.057 に答える
2

空間充填アルゴリズムを確認する必要があります。これらのアルゴリズムは、特定のスペースをいくつかの幾何学的図形で埋めるために疲れています。そのようなアルゴリズムをニーズに合わせて変更するのは難しいことではありません。

このようなアルゴリズムはゼロから開始するため（空のスペース）、最初に2D平面上に既にあるボックスで彼の内部データを入力します。次に、アルゴリズムに残りの作業を任せます。残りのスペースを別のボックスで埋めます。これらのボックスは、飛行機の反転したスペースチャンクのリストを作成しています。

これらのボックスをいくつかのリストに保持しておくと、ポイントが反転した平面上にあるかどうかを確認するのは非常に簡単です。リストをトラバースして、ポイントがボックス内にあるかどうかを確認します。

これは、役立つ可能性のあるアルゴリズムがたくさんあるサイトです。

于 2010-11-21T19:16:36.663 に答える
0

長方形をy座標で並べ替え、スキャンラインアプローチを採用することで、どこかに到達できると思います。私は実際に実装を構築する場合としない場合があります。

于 2010-11-21T19:09:23.947 に答える
0

長方形は交差していないため、これは比較的簡単です。目標は基本的に、平面を完全に覆う交差しない長方形のセットであり、一部はオリジナルとしてマークされ、一部は「逆」としてマークされます。

トップダウン（または左右など）のスキャンの観点から考えてください。あなたは現在の「タイドライン」ポジションを持っています。あなたが遭遇する次の水平線の位置が潮汐線上にないものであるかを決定します。これにより、次のタイドラインの高さがわかります。

これらの潮汐線の間に、各垂直線が1つの潮汐線から別の潮汐線に（そしておそらく両方向を超えて）到達するストリップがあります。これらの垂直線の水平位置を並べ替え、それを使用してストリップを長方形に分割し、元の長方形（の一部）または逆長方形（の一部）として識別できます。

最後まで進むと、（おそらく小さすぎる）長方形が表示され、必要な長方形を選択できます。また、現在のストリップの小さな長方形を、以前の拡張可能な長方形のセットと組み合わせるオプションもあります（各ステップで）。

元の長方形が交差する場合でも同じことができますが、少し面倒です。

読者のための演習として残された詳細;-)

于 2010-11-21T19:14:56.623 に答える