mieki256's diary

とにかくあれこれ眺めているのだけど、難しすぎてちんぷんかんぷん。そもそも自分、二分木とやらもちゃんと勉強したことがないわけで。

が、調べてるうちに、地形を等間隔に分割して、1つ1つのグリッドにどのポリゴンが関係してるかを情報として持てばどうにかなるのではと思い至る。弾等の点座標が入ってるグリッドについては、等間隔で分割されているからすぐに場所を取得することができるだろうし。後はそこに関係してるであろうポリゴン数枚とだけ、厳密に判定していけば、みたいな。

と思ったけどこれじゃダメだな…。弾は点じゃなくて直線になるだろうから、点がどのポリゴンに内包されてるかを調べるのではなくて、直線がどのポリゴンと交差しているのかを調べないといけない予感。つまり直線と関係しそうなポリゴンをどれだけ早く絞り込めるか、という話になりそうな。