2006年08月05日
カテゴリ： カテゴリ未分類
7.5 Sort and Sweep Methods
ソートとスウィープの方法。固定の分割空間にオブジェクトを挿入するのは複数の分割空間にまたがっているオブジェクトによって格子と8分木の記述方法に加わる複雑さに対処しなければならないことです。代わりに何らかのソートされた空間を考えることができます。ソートとスウィープと呼ばれる方法があります。(sort and sweep)
最初に1次元から考えるとソートされているリストに登録する場合はリストをスウィープすることでアクティブな間隔を記録することができます。
リストがソートされた後にオブジェクトが一般的にフレームとフレームの間でかなり離れたところまで動くことはないためリストはあるフレームから次のフレームまでソートされているままで残ります。この性質を利用して単純な挿入ソートを用いて順番を管理します。
ソートの高速化のために双方向のリストを用意する必要があります。
オブジェクトが集合してしまいやすい一般的な状況における解決方法の1つとしてｙ軸はｘｚのみリストに保存する方法があります。ゲームなどではｙは比較的近い値で密集するからです。
ソートとスウィープの方法。固定の分割空間にオブジェクトを挿入するのは複数の分割空間にまたがっているオブジェクトによって格子と8分木の記述方法に加わる複雑さに対処しなければならないことです。代わりに何らかのソートされた空間を考えることができます。ソートとスウィープと呼ばれる方法があります。(sort and sweep)
最初に1次元から考えるとソートされているリストに登録する場合はリストをスウィープすることでアクティブな間隔を記録することができます。
リストがソートされた後にオブジェクトが一般的にフレームとフレームの間でかなり離れたところまで動くことはないためリストはあるフレームから次のフレームまでソートされているままで残ります。この性質を利用して単純な挿入ソートを用いて順番を管理します。
ソートの高速化のために双方向のリストを用意する必要があります。
オブジェクトが集合してしまいやすい一般的な状況における解決方法の1つとしてｙ軸はｘｚのみリストに保存する方法があります。ゲームなどではｙは比較的近い値で密集するからです。
お気に入りの記事を「いいね！」で応援しよう
【毎日開催】
15記事にいいね！で1ポイント
PR
キーワードサーチ
▼キーワード検索
大鳥居.
人生ゲーム
コメント新着
© Rakuten Group, Inc.
