Entry

プログラミングメモ - 二次元平面の入れ子領域を表現するデータ構造

2009年04月14日

今ごにょごにょと調べつつ考えているんですけれど,二次元平面に特定の領域を入れ子で作ったときの,適当なデータ構造はないもんだろうか。入れ子の領域構造というのは,例えば,HTML の構造を説明するときに使われる入れ子の図(参照:tDiary.org - テーマ向けHTMLの構造図解 ※本文は関係ありません)を,考えてもらえればいいと思います。

データ構造として必要な要件は,こんなもの。

  • 領域の入れ子関係を自然に表現できること(単純なアルゴリズムで扱えること)。
  • 任意の領域へのアクセスが速いこと。
  • 領域の分割,併合といったデータ間の操作が容易で速いこと。

入れ子というと真っ先に思いつくデータ構造は二分木(B木)で,その二次元版の有名どころに,四分木ってのがあります。画像の象限で4つに分けたもの。シューティングゲームとか作ってるとこでは,おなじみの構造かもしれません。

これならそれっぽく作れそうな感じ。要件の前2者も満たします。もっとも,このやり方は,単純に4分割するだけなので,任意の領域を収める構造にするには,もちっと工夫が必要です。

また,残る最後の操作なんだけれども,これはどうなんだろう。四分木は,計算幾何にいわゆる領域探索問題を解くのに使われるようなので,領域相互の分割・併合(特に併合)は想定していないはず。つか,併合しちゃったら木構造が崩れるので,そゆ操作はないはず。これも,「任意の領域を収める構造」に対応することで解消できるんだろうか。

あまりまともな結論が出てないのでごにょごにょなんですけど,もちっと考えるしかないな。こりゃ。

Trackback
Trackback URL:
Ads
About
Search This Site
Ads
Categories
Recent Entries
Log Archive
Syndicate This Site
Info.
クリエイティブ・コモンズ・ライセンス
Movable Type 3.36
Valid XHTML 1.1!
Valid CSS!
ブログタイムズ

© 2003-2012 AIAN