0

Railsアプリでそれを使用してルビーコードを書いています。そこでは、ユーザーからのExcelセルのような構造を受け入れる必要があり、それらのセル構造を検証する必要があります。

例えば：

ユーザーは、コロンで区切ることによってセルのブロックを指定できる必要があります。たとえば、A1:B2 は、フォーム内の A1、A2、B1、B2 セルをカバーする必要があります。

同様に、ユーザーは次のように多くの位置を入力できます

A1:B1 A2:C2 A1:F1

ただし、ユーザーが重複する位置に入ると問題が発生します。たとえば、次のようになります。

A1:D5 および A2:C3 また、D1:E1 および A1:F2。

この場合、A2:C3 は A1:D5 ブロック内にあるため、ユーザーはこれらが重複位置であることを示すエラー メッセージ (検証エラー) を受け取るはずです。

私が考えていた 1 つのロジックは、すべての位置を一意の整数値に変換し、それを使用して区別することですが、これまでのところ、この状態を追跡するロジックは得られていません。

これに対処する方法について何か考えがある人がいたら教えてください。

ありがとう、ディーン

4

1 に答える 1

0

あなたがしたいのは、単純なボックスまたは長方形の衝突検出です。これは、ゲームやグラフィックスのプログラミングで広く知られ、長い間解決されてきた問題です。

たとえば、次のブログ投稿を参照してください。

http://www.owenpellegrin.com/articles/vb-net/simple-collision-detection/

計算を容易にするために、英数字のセル名（列+行）を整数（x、y）座標に変換することをお勧めします。

したがって、からA1:D5、A2:C3それらは座標に変わります：(1,1):(4,5)、(1,2):(3,3)。

単純なボックス衝突検出アルゴリズムは、ポイント(1,2)と長方形の両方(3,3)が長方形内にあることを判別できる(1,1):(4,5)ため、2番目の長方形は最初の長方形内に完全に含まれます。つまり、オーバーラップがあります。

あなたの場合、アルゴリズムが「エッジ」衝突をオーバーラップとして処理することも確認する必要があります。つまり、同じ「エッジ」（つまり、2つのセル）を共有するため、A1:B2技術的にはと重複します。B1:C2B1:B2

注：各長方形を他の長方形と照合して交差するかどうかを確認する「ナイーブ」アルゴリズムの複雑さはO（n ^ 2）です。たとえば、数十個の長方形のみを扱っている場合は、問題ないはずです。ただし、数千の長方形を相互にチェックする必要がある場合は、軸ごとに1つずつ、2つの区間木を動的に構築することを検討する必要があります。

于 2012-10-22T06:58:08.583 に答える