2

私の問題を説明しましょう：

私は黒いベクトル形状を持っています（今のところ、一連の結合された直線であるとしましょうが、二次曲線もサポートできればいいと思います）。

また、定義済みの幅と高さの長方形もあります。黒い図形の上に配置して、2 つの結合を取ります。

私の最初の問題は、ベクトル共用体をすばやく抽出する方法がわからないことですが、自分で理解できる明確に定義された式があると思います。

私の 2 番目の、よりトリッキーな問題は、結合後に残る黒を最大化するために、四角形が必要な位置 (つまり、行列に必要な移動と回転) を効率的に検出する方法です (下の図を参照)。 ）。

以下の赤で輪郭を描かれた図形は、~33% の黒です。緑は 85% のようなものです。この形状と長方形には、いずれかが 100% の範囲をカバーする位置があります。

最適な長方形の配置

明らかに、四角形の少なくとも一部が黒い形状に接触しているすべてのポイントのすべての移動と回転の値を試してから、最も黒いカバレッジを持つポイントを追跡することで、これを強引に実行できます。問題は、限られた数のポジションしか試すことができないことです (したがって、最大数を見逃す可能性があります)。それとは別に、それは非常に非効率的です！

この問題に取り組むためのより効率的な方法を考えられますか?

大学時代に、フーリエ変換がここでの効率を改善する可能性があることを教えてくれましたが、ベクトル形状でそれを行う方法がわかりません!

4

3 に答える 3

2

ブルートフォース検索よりも高速および/または正確であることが約束されている3つのアイデア：

  1. 3D物理エンジンがあるとします。頂点がたとえば（0,0、-1）にある「円錐形」のサーフェス、原点に重心があるz = 0平面上の黒いポリゴン境界を定義し、円錐サーフェスは頂点を接続することによって形成されますポリゴンの境界を通る半無限の光線で。パーティーハットを逆さまにして、黒い多角形の形にしわくちゃにしたと考えてください。次に、長方形をz = 0平面に平行に、最初は円錐よりも非常に高い位置（z値が大きい）に制限して、確実に「内側」にある場所を簡単に見つけられるようにします。次に、長方形を重力の下で下向きに落下させ、zを中心にねじり、円錐に接触するときにのみxyに移動し、落ち着いてそれ以上移動できなくなるまで、完全に内側に留まります。物理エンジンの衝突検出と力の解決により、複雑さが処理されます。落ち着くと、ローカルな意味で黒いポリゴンを最大限にカバーできる位置になります。（z <0で落ち着く場合、カバレッジは100％です。）凸型の場合、おそらくグローバルな最大値です。非凸の場合（例のように）の結果を確率的に改善するには、開始位置をランダム化し、ポリゴンを何度もドロップして、最良の結果を取得します。本格的な物理エンジンは実際には必要ないことに注意してください（ただし 非凸の場合（例のように）の結果を確率的に改善するには、開始位置をランダム化し、ポリゴンを何度もドロップして、最良の結果を取得します。本格的な物理エンジンは実際には必要ないことに注意してください（ただし 非凸の場合（例のように）の結果を確率的に改善するには、開始位置をランダム化し、ポリゴンを何度もドロップして、最良の結果を取得します。本格的な物理エンジンは実際には必要ないことに注意してください（ただしそれらは確かにオープンソースに存在します）。衝突の解決を使用して、長方形がz軸を可能な限り均一にねじり、スライドするときに、疑似物理的な方法で長方形を回転および平行移動する方法を説明するだけで十分です。

  2. 異なる物理モデル。黒い領域が、重力や磁気などの通常の逆二乗の法則に従った2Dの魅力的なフィールドジェネレータであるとします。次に、このフィールドに応答する減衰媒体で長方形をドリフトさせます。それは、最大の領域が黒い領域と重なるように落ち着くはずです。ドーナツの中心のような「ヌル」には問題がありますが、これらが安定した平衡状態になることはないと思います。彼らはできますか？シミュレーションは、両方の形状を粒子群としてモデル化することで簡単に実行できます。または、長方形は単純な形状であり、あなたは物理学者であるため、点と長方形の間の引力を積分するための閉じた形を思い付くことができます。このように、黒い形状だけが粒子として表現する必要があります。良く考えると、正確な答え。残念ながら、この議論は分析的に行うことができないことを意味します。したがって、粒子雲が最終的な解決策になる可能性があります。幸いなことに、最新のプロセッサ、特にGPUは、非常に大きな粒子の計算を驚くべき速度で実行します。編集：私はこれを素早く汚いものに実装しました。凸形状には最適ですが、凹は必要なものではない安定したポイントを作成します。例を使用して：これがスクリーンショットです

  3. この問題は、ロボットの経路計画に関連しています。この文献を見ると、いくつかのアイデアが浮かぶかもしれません。RPPには障害物とロボットがあり、それらを避けたりスライドしたりしながらロボットが移動できる経路を見つけたいと考えています。ロボットが非対称で回転できる場合、2次元計画は3次元（トロイダル）構成空間（C空間）で実行されます。ここで、1つの次元は回転です（それ自体が閉じます）。アイデアは、ロボットをある点まで縮小しながら、Cスペースの障害物を「成長」させることです。障害物の拡大は、ミンコフスキー差を計算することによって達成されます。）すべてのポリゴンを凸型に分解する場合、MDを計算するための単純な「エッジマージ」アルゴリズムがあります。）C空間表現が完了すると、 「成長した」を突き刺さない 障害物は、元の障害物を回避する世界空間でのロボットの連続的な並進/回転に対応します。あなたの問題のために白い部分が障害物で、長方形がロボットです。オープンポイントを探しています。これは100％のカバレッジに相当します。100％未満の場合、C空間は、単なる2進値ではなく、ロボットと障害物との交差がどれほど「悪い」かを反映する3d上の関数である必要があります。あなたは最も悪い点を探しています。C空間表現はオープンリサーチのトピックです。ここでは八分木が機能する可能性があります。

どちらの場合も、検討すべき詳細がたくさんあり、まったくうまくいかない場合もありますが、少なくともこれらは、問題についてさらに考えるためのフレームワークです。物理学のアイデアは、シミュレートされたばねシステムを使用してグラフレイアウトを行うのと少し似ていますが、これは非常に成功しています。

于 2012-12-28T04:41:58.287 に答える
1

この問題の正確な最大値を見つけることが可能だとは思わないので、近似値で間に合わせる必要があります。

ベクトル画像をビットマップにレンダリングし、Haar 機能を使用する可能性があります。Haar 機能は、長方形領域の平均色を計算する非常に迅速な O(1) 方法を提供します。

さまざまな回転と位置に対してこれを複数回実行する必要がありますが、アルゴリズムの複雑さが単純な O(n^5) から O(n^3) に低下し、許容できるほど高速になる可能性があります。(ここで n は、スキャンしているさまざまな自由度のサイズです)

于 2012-12-28T01:14:09.330 に答える
-1

if whitespace !== 0 のようなものを使用して、ブロック内の残りの空白を追跡することを考えましたか?

于 2012-12-28T01:25:34.373 に答える