動的長方形交差問題 - 動的長方形探索木 -
１．概要
ヒープ探索木(priority search trees)を同伴木とする動的区分木(dynamic segment trees)と、
同じくヒープ探索木を同伴木とする領域木(range trees)を使って、長方形の動的交差問題(Dynamic Rectangular Intersection)を解く。
◆主な機能
水平線分と垂直線分を辺とする長方形を対象とする。
長方形Ｒi=[x1:x2]×[y1:y2]の集合Ｒを蓄えて、質問長方形ｑと交差する長方形Ｒiを求める。
長方形[x1:x2]×[y1:y2]を動的に追加、削除できる。
本プログラムの最大の特徴は、動的区分木を用いたことです。
動的とは、追加、削除を効率良く実行できることです。
◆応用
・インターネット通信におけるルータ内でのアドレス検索
・VLSIレイアウトＣＡＤ
・地理情報システム
◆理論性能（動的長方形交差問題）
・メモリ ： Ｎ(logＮ)**2
・構 築 ： Ｎ(logＮ)**2
・探 索 ： (logＮ)**2＋Ｋ
・追 加 ： (logＮ)**2
・削 除 ： (logＮ)**2
Ｎ：長方形の数。Ｋ：探索で得られた長方形の数。
同じくヒープ探索木を同伴木とする領域木(range trees)を使って、長方形の動的交差問題(Dynamic Rectangular Intersection)を解く。
◆主な機能
水平線分と垂直線分を辺とする長方形を対象とする。
長方形Ｒi=[x1:x2]×[y1:y2]の集合Ｒを蓄えて、質問長方形ｑと交差する長方形Ｒiを求める。
長方形[x1:x2]×[y1:y2]を動的に追加、削除できる。
本プログラムの最大の特徴は、動的区分木を用いたことです。
動的とは、追加、削除を効率良く実行できることです。
◆応用
・インターネット通信におけるルータ内でのアドレス検索
・VLSIレイアウトＣＡＤ
・地理情報システム
◆理論性能（動的長方形交差問題）
・メモリ ： Ｎ(logＮ)**2
・構 築 ： Ｎ(logＮ)**2
・探 索 ： (logＮ)**2＋Ｋ
・追 加 ： (logＮ)**2
・削 除 ： (logＮ)**2
Ｎ：長方形の数。Ｋ：探索で得られた長方形の数。
２．長方形の重なり方の分類と探索アルゴリズム
長方形集合中の長方形Ｒiの左下座標を（ｘ1,ｙ1）、右上座標を（ｘ2,ｙ2）とする。
質問長方形ｑの左下座標を（ａ,ｂ）、右上座標を（ｃ,ｄ）とする。
長方形の重なり方を２つに分類する。これらは互いに排他的である。
（１）Ｒiの右下点のｘ座標ｘ2が[ａ,ｃ]内にあり、垂直の辺が交叉する。
重なり条件：ａ≦ｘ2≦ｃ かつ ｂ≦ｙ2 かつｙ1≦ｄ
（２）Ｒiの水平辺[ｘ1,ｘ2)（右が開）がｃを含み、垂直の辺が交叉する。
重なり条件：ｘ1≦ｃ＜ｘ2 かつ ｂ≦ｙ2 かつｙ1≦ｄ。
幅が０(ｘ1＝ｘ2)の長方形は（１）で調べる。
ｘ2＝ｃの場合は(1)で調べている。
（１）に対して、３次元領域ヒープ探索木を適用する。
主木をｘ2の領域木で、従木をｙ1,ｙ2のヒープ探索木で構成する。O(ＮlogＮ)のスペース
すなわち、Ｐi＝[x2,y1,y2]で３次元領域ヒープ探索木を構成しておき、
Ｌ＝[ａ,-∞,ｂ]、Ｕ＝[ｃ,ｄ,∞]としてＬ≦Ｐi≦Ｕである点Ｐiを探索すればよい。
（２）に対して、動的区分ヒープ探索木を適用する。
主木をｘ1,ｘ2の動的区分木で、従木をｙ1,ｙ2のヒープ探索木で構成する。O(ｎlogｎ)のスペース
すなわち、水平線分[x1:x2]で区分木を、垂直線分[y1:y2]で同伴木のヒープ探索木構成しておき、
質問長方形[ａ:ｂ]×[ｃ:ｄ]のｃで串刺しする線分[x1:x2)（右側が開）を調べ、
その中から垂直線分が交差する長方形Ｒiをヒープ探索木で選択する。
幅が０(ｘ1＝ｘ2)の長方形は(1)で調べるので、区分木は幅が０の線分を扱えなくて良い。
質問長方形ｑの左下座標を（ａ,ｂ）、右上座標を（ｃ,ｄ）とする。
長方形の重なり方を２つに分類する。これらは互いに排他的である。
（１）Ｒiの右下点のｘ座標ｘ2が[ａ,ｃ]内にあり、垂直の辺が交叉する。
重なり条件：ａ≦ｘ2≦ｃ かつ ｂ≦ｙ2 かつｙ1≦ｄ
（２）Ｒiの水平辺[ｘ1,ｘ2)（右が開）がｃを含み、垂直の辺が交叉する。
重なり条件：ｘ1≦ｃ＜ｘ2 かつ ｂ≦ｙ2 かつｙ1≦ｄ。
幅が０(ｘ1＝ｘ2)の長方形は（１）で調べる。
ｘ2＝ｃの場合は(1)で調べている。
（１）に対して、３次元領域ヒープ探索木を適用する。
主木をｘ2の領域木で、従木をｙ1,ｙ2のヒープ探索木で構成する。O(ＮlogＮ)のスペース
すなわち、Ｐi＝[x2,y1,y2]で３次元領域ヒープ探索木を構成しておき、
Ｌ＝[ａ,-∞,ｂ]、Ｕ＝[ｃ,ｄ,∞]としてＬ≦Ｐi≦Ｕである点Ｐiを探索すればよい。
（２）に対して、動的区分ヒープ探索木を適用する。
主木をｘ1,ｘ2の動的区分木で、従木をｙ1,ｙ2のヒープ探索木で構成する。O(ｎlogｎ)のスペース
すなわち、水平線分[x1:x2]で区分木を、垂直線分[y1:y2]で同伴木のヒープ探索木構成しておき、
質問長方形[ａ:ｂ]×[ｃ:ｄ]のｃで串刺しする線分[x1:x2)（右側が開）を調べ、
その中から垂直線分が交差する長方形Ｒiをヒープ探索木で選択する。
幅が０(ｘ1＝ｘ2)の長方形は(1)で調べるので、区分木は幅が０の線分を扱えなくて良い。
３．使用方法
◆ダウンロード（ダウンロードのページからもダウンロードできます）
sample01.zip 997 KB (1,021,930 バイト) ソース付き
３．１ インストール
ダウンロードしたファイルを、任意のディレクトリに解凍します。
ソースファイルとプロジェクトはインストールディレクトリ/RectTree_projにあります。
３．２ アンインストール
インストール時に作成したディレクトリごとファイルを削除します。
３．３ 使用方法
(1)ＤＯＳプロンプト画面を表示します。
(2)インストールディレクトリ/sample01に移動します。
(3)プログラム実行。
run_R.bat
３．４ 公開DLL関数
DLLの中に長方形の挿入、削除、探索、その他の関数が含まれています。
各関数の使用方法は、rectIntsectmain.c ファイル内のサンプルMainを参照して下さい。
本DLLは、メモリが確保出来る範囲と32Bit整数の範囲内で、データ数は無制限です。
以下、公開DLL関数の一覧です。
//管理用関数
void *rectAlloc();
void rectFree(void** rt);
void rectClear(void* rt);
//動的追加/削除用関数
int rectInsert(void* rt, int rectNo, int pnt[4]);
int rectDelete(void* rt, int rectNo, int pnt[4]);
//一括構築用関数
int rectPoint(void* rt, int rectNo, int pnt[4]);
int rectBuild(void* rt);
//質問用関数
int rectHowmany(void* rt, int pnt[4]);
int rectNumber(void* rt, int k);
sample01.zip 997 KB (1,021,930 バイト) ソース付き
３．１ インストール
ダウンロードしたファイルを、任意のディレクトリに解凍します。
ソースファイルとプロジェクトはインストールディレクトリ/RectTree_projにあります。
３．２ アンインストール
インストール時に作成したディレクトリごとファイルを削除します。
３．３ 使用方法
(1)ＤＯＳプロンプト画面を表示します。
(2)インストールディレクトリ/sample01に移動します。
(3)プログラム実行。
run_R.bat
３．４ 公開DLL関数
DLLの中に長方形の挿入、削除、探索、その他の関数が含まれています。
各関数の使用方法は、rectIntsectmain.c ファイル内のサンプルMainを参照して下さい。
本DLLは、メモリが確保出来る範囲と32Bit整数の範囲内で、データ数は無制限です。
以下、公開DLL関数の一覧です。
//管理用関数
void *rectAlloc();
void rectFree(void** rt);
void rectClear(void* rt);
//動的追加/削除用関数
int rectInsert(void* rt, int rectNo, int pnt[4]);
int rectDelete(void* rt, int rectNo, int pnt[4]);
//一括構築用関数
int rectPoint(void* rt, int rectNo, int pnt[4]);
int rectBuild(void* rt);
//質問用関数
int rectHowmany(void* rt, int pnt[4]);
int rectNumber(void* rt, int k);
４．測定性能
| 長方形数(N) | 主木(節点数) | 同伴木節点数 | 挿入時間 | 削除時間 | 探索時間 | 構築時間 |
| 10 | 51 | 35 | 0 | 16 | 0 | 0 |
| 32 | 161 | 206 | 0 | 0 | 0 | 0 |
| 100 | 499 | 974 | 0 | 16 | 0 | 0 |
| 316 | 1565 | 4067 | 0 | 0 | 0 | 0 |
| 1000 | 4869 | 15903 | 16 | 15 | 16 | 15 |
| 3162 | 14735 | 61515 | 63 | 62 | 62 | 16 |
| 10000 | 39971 | 223642 | 297 | 344 | 156 | 94 |
| 31623 | 87582 | 785074 | 1437 | 1625 | 625 | 375 |
| 100000 | 165391 | 2684360 | 6578 | 6922 | 3203 | 1532 |
挿入/削除時間は空の状態からN個挿入/削除したもので、∑(n=1:N)(log n)**2＝O(N(logN)**2)のはず。
実行時間の単位は1msでclock()関数の戻り値だが、分解能は1msの精度ではない。
探索時間は短すぎるので1000回繰返した時間。
探索時間は解の数(K)が関係するので(logN)**2に比例しているかよく見えない。
長方形集合、質問長方形は[0,99999]区間の一様乱数を用いて生成している。
◆実行環境
Endeavor MT8000
| OS | WindowsXP |
| CPU | Pentium4 650(3.4GHz) |
| メモリ | 3GB(PC3200) |
５．開発環境
Visual Studio 2005 C++