トップページ > ダウンロード > 不良ビット救済

動的長方形探索木 - 長方形の動的交差問題 -

1.概要

ヒープ探索木(priority search trees)を同伴木とする動的区分木(dynamic segment trees)と、
同じくヒープ探索木を同伴木とする領域木(range trees)を使って、長方形の動的交差問題(Dynamic Rectangular Intersection)を解く。 

◆主な機能
 水平線分と垂直線分を辺とする長方形を対象とする。
 長方形Ri=[x1:x2]×[y1:y2]の集合Rを蓄えて、質問長方形qと交差する長方形Riを求める。
 長方形[x1:x2]×[y1:y2]を動的に追加、削除できる。
 本プログラムの最大の特徴は、動的区分木を用いたことです。
 動的とは、追加、削除を効率良く実行できることです。
 
◆応用
 ・インターネット通信におけるルータ内でのアドレス検索
 ・VLSIレイアウトCAD
 ・地理情報システム
 
◆理論性能(動的長方形探索木)
 ・メモリ : NlogN
 ・構 築 : N(logN)**2
 ・探 索 : (logN)**2+K
 ・追 加 : (logN)**2
 ・削 除 : (logN)**2
 N:長方形の数。K:探索で得られた長方形の数。
 

2.長方形の重なり方の分類と探索アルゴリズム

長方形集合中の長方形Riの左下座標を(x1,y1)、右上座標を(x2,y2)とする。
 
 質問長方形qの左下座標を(a,b)、右上座標を(c,d)とする。
 
 長方形の重なり方を2つに分類する。これらは互いに排他的である。
 
(1)Riの右下点のx座標x2が[a,c]内にあり、垂直の辺が交叉する。
   重なり条件:a≦x2≦c かつ b≦y2 かつy1≦d
 
(2)Riの水平辺[x1,x2)(右が開)がcを含み、垂直の辺が交叉する。
   重なり条件:x1≦c<x2 かつ b≦y2 かつy1≦d。
   幅が0(x1=x2)の長方形は(1)で調べる。
   x2=cの場合は(1)で調べている。
 
 (1)に対して、3次元領域ヒープ探索木を適用する。
  主木をx2の領域木で、従木をy1,y2のヒープ探索木で構成する。O(NlogN)のスペース
  すなわち、Pi=[x2,y1,y2]で3次元領域ヒープ探索木を構成しておき、
  L=[a,-∞,b]、U=[c,d,∞]としてL≦Pi≦Uである点Piを探索すればよい。
 
 (2)に対して、動的区分ヒープ探索木を適用する。
  主木をx1,x2の動的区分木で、従木をy1,y2のヒープ探索木で構成する。O(nlogn)のスペース
  すなわち、水平線分[x1:x2]で区分木を、垂直線分[y1:y2]で同伴木のヒープ探索木構成しておき、
  質問長方形[a:b]×[c:d]のcで串刺しする線分[x1:x2)(右側が開)を調べ、
  その中から垂直線分が交差する長方形Riをヒープ探索木で選択する。
  幅が0(x1=x2)の長方形は(1)で調べるので、区分木は幅が0の線分を扱えなくて良い。

3.使用方法

◆ダウンロード(ダウンロードのページからもダウンロードできます)
  
   sample01.zip   134 KB (137,652 バイト)
   sample01.lzh   136 KB (140,127 バイト)

3.1 インストール 
 
 ダウンロードしたファイルを、任意のディレクトリに解凍します。
 
3.2 アンインストール
 
 インストール時に作成したディレクトリごとファイルを削除します。

3.3 使用方法
 
 (1)DOSプロンプト画面を表示します。
 
 (2)インストールディレクトリに移動します。
 
 (3)プログラム実行。
   run_R.bat
 
3.4 公開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_20161231(void* rt, int pnt[4]); //2016/12/31まで使えます
   int rectNumber(void* rt, int k);

4.測定性能


 
長方形数(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)

5.開発環境

Visual Studio 2008 C++
Copyright 2011 Sogen System Co.,Ltd. All Rights Reserved.