二次元平面の入れ子領域を表現するデータ構造2009/04/14今ごにょごにょと調べつつ考えているんですけれど,二次元平面に特定の領域を入れ子で作ったときの,適当なデータ構造はないもんだろうか。※本文は関係ありません)を,考えてもらえればいいと思います。データ構造として必要な要件は,こんなもの。領域の入れ子関係を自然に表現できること(単純なアルゴリズムで扱えること)。任意の領域へのアクセスが速いこと。領域の分割,併合といったデータ間の操作が容易で速いこと。入れ子というと真っ先に思いつくデータ構造は二分木(B木)で,その二次元版の有名どころに,四分木ってのがあります。画像の象限で4つに分けたもの。シューティングゲームとか作ってるとこでは,おなじみの構造かもしれません。これならそれっぽく作れそうな感じ。要件の前2者も満たします。このやり方は,単純に4分割するだけなので,任意の領域を収める構造にするには,もちっと工夫が必要です。残る最後の操作なんだけれども,これはどうなんだろう。四分木は,計算幾何にいわゆる領域探索問題を解くのに使われるようなので,領域相互の分割・併合(特に併合)は想定していないはず。併合しちゃったら木構造が崩れるので,そゆ操作はないはず。これも,「任意の領域を収める構造」に対応することで解消できるんだろうか。まともな結論が出てないのでごにょごにょなんですけど,もちっと考えるしかないな。