0

解決しようとしているアルゴリズムに問題があります。衝突をチェックしようとしているポイントのリストがあります。おそらくいくつかのピタゴラスを使用する一般的な考えがありますが、私の主な問題はアルゴリズムの効率です。 1つの軸でのみ交差するかどうかを確認する必要があるため、ポイント（0,100）に長方形があり、ポイント（300、100）に長方形があるとしましょう。両方ともy = 100であるため、アプリではそれらを決定します衝突しますが、長方形のいずれかが残りの長方形と衝突するかどうかを確認するにはどうすればよいですか?

私の最初の試みは、新しい四角形が残りの四角形と衝突する場合に追加する各四角形のチェックをループすることでしたが、間違っていると思います.100個の四角形がある場合、最初の四角形が他の99個と衝突することを確認する必要があります、残りの部分と衝突する場合はそれぞれ。

ループが指数関数的に増加すると確信しているので、誰かがチェックする最善の効率的な方法を正しい方向に向けてください、ありがとう!

@John Phu Nguyen関数を使用して22-oct-13を編集

var events = [ {start: 30, end: 150}, {start: 540, end: 600}, {start: 560, end: 620}, {start: 610, end: 670} ];
//each start and end props are y coordinates, basically where the rect start and ends
function layOutDay(events) {
    //console.log(events);

    var events_container = document.querySelector('.events-col');
    var frag = document.createDocumentFragment();
    for(var i=0; i<events.length; i++){
        //console.log(events[i].start);
        var top = events[i].start;
        var bottom = events[i].end-events[i].start;

        var event = createEventDOM();
        var gutter = event.querySelector('.gutter');

        event.style.top = top + 'px';
        event.style.height = gutter.style.height = bottom + 'px';

        if(y_coords.indexOf(top) === -1 && y_coords.indexOf(bottom) === -1){
            y_coords.push(top);
            y_coords.push(bottom);

            y_coords.sort();

            event.style.left = '10px';
            console.log('NO collision', top, bottom);
        }else{
            console.log('collision', top, bottom);
            event.style.width = '250px';
            event.style.left = '220px';
        }

        frag.appendChild(event);
    }

    events_container.appendChild(frag);
}

関数を実行すると、2つの四角形が衝突しましたが、2つではなく3つあります。x軸で四角形を隣り合わせに移動するために、誰が誰と衝突しているかを知る必要があります!

ここに私がやろうとしていることのスクリーンショットがあります

おそらく微調整ですが、見つかりません。助けていただければ幸いです。ありがとう!!!

4

2 に答える 2

2

ループは指数関数的に増加するのではなく、二次関数的に増加しますが、これはまだ悪い場合があります。

たとえば、移動している長方形の数と固定されている長方形の数に応じて、いくつかの解決策があります。

コーディングが非常に簡単なソリューションは

  • 各セルがセルに接する長方形のリストを含むことができる NxN セルのグリッドを構築します
  • 長方形をループし、それらのそれぞれについて、接触するすべてのセルのリストに長方形を入れます。そうしている間に、長方形がセルの同じリストにある他の長方形と衝突しているかどうかを確認することもできます。

このグリッド データ構造は、四角形を移動するときに更新を維持するのが非常に簡単です。現在のリストから削除して、新しい位置のリストに挿入するだけです。

何が最適Nかは、アプリケーションによって異なります。

于 2013-10-21T17:50:45.533 に答える
1

軸に沿って個々のポイントを確認するだけの場合は、並べ替えられたリストがうまく機能します。

Javascript の場合:

//Existing points:
var x_coords = [0, 20, 310, 400];
var y_coords = [0, 50, 100, 500];

//New point
x_new = 300;
y_new = 100;

//Check for collision
if(x_cords.indexOf(300) == -1 && y_cords.indexOf(100) == -1) 
{
    //No collision, add to list
    //Add another point
    x_coords.push(300);
    x_coords.push(100);

    //Sort list, complexity should be low if sorted after every insert
    x_coords.sort();
    y_coords.sort();
}

範囲内の衝突を探している場合は、

x_cords.indexOf( 100 )
x_cords.indexOf( 200 )

値 100 と 200 のインデックスが得られます。その範囲内にあるものはすべて、並べ替えられたリストのこれら 2 つのインデックスの間に発生します。

追加情報：

「下」は現在、下ではなく要素の高さです。if ステートメントは次のようになります。

if(y_coords.indexOf(top) === -1 && y_coords.indexOf(end) === -1)

ただし、 indexOf() 関数は特定の値の間に値がある場合ではなく、特に値を探すため、これでも何も得られません。

これを行うには、リスト内包表記を使用できます。

elements_between_y100_and_y300 = [i for i in y_cords if (i >= 100 && i <=300)]

リストが空の場合、衝突はありません。

衝突した要素を見つけるには、次のような個別のリストを保持する必要があります。 element_at[200] = 2

于 2013-10-21T18:06:29.317 に答える