長方形交差問題

長方形交差問題(Rectangular Intersection)

１．概要

平面走査法とヒープ探索木(priority search trees)を組み合わせて、交差する長方形のペアを列挙する。

◆機能
　水平線分と垂直線分を辺とする長方形を対象とする。
　長方形Ｒi=[x1:x2]×[y1:y2]の集合Ｒを蓄えて、交差する長方形のペア(Ｒi,Ｒj)を全て求める。
　ついでに、交差する長方形のグループを求める。
　長方形Ｒ1,Ｒ2が同じグループであるのは、交差ペア(Ｒi,Ｒj)を枝とする無向グラフで
　Ｒ1からＲ2に至るパスが存在することである。

◆理論性能（交差長方形のペアを列挙）
　・メモリ　：　Ｎ
　・時　間　：　Ｎ(logＮ)＋Ｋ

　　　　Ｎ：長方形の数。Ｋ：交差する長方形のペア数。

２．長方形のペアを列挙するアルゴリズム（Algorithm of rectangular intersection）

入力：長方形Ｒi=[x1:x2]×[y1:y2]の集合Ｒとする。

　全ての長方形の左辺のＸ座標x1を昇順に並べた列をＳとする。
　垂直線分[y1:y2]の集合Ｄを空にする。（走査線上の長方形の垂直線分の集合）
　右のＸ座標x2のヒープＨを空にする。（走査線上の長方形の右辺の集合）
　Ｓ内の最小のＸ座標ａを垂直な走査線とする。

ヒープＨからx2＜ａの長方形Ｒiを削除すると共に、集合Ｄからも削除する。
列Ｓを参照してａを左座標とする全ての長方形Ｒiに対して、
　　Ｒiの垂直線分[y1,y2]と交差するＤ内の線分[y3,y4]に対して、
　　　　線分[y3,y4]に対応する長方形Ｒjとのペア(Ｒi,Ｒj)を交差ペアとする。
　　Ｒiの垂直線分[y1,y2]をＤに追加する。
　　Ｒiの右辺の座標x2をＨに追加する
ａより次に大きいＳ内のＸ座標を新たにａとして、上記を繰り返す。
Ｓが空になったら終了する。

集合Ｄをヒープ探索木で構成することで、線分の追加/削除をＯ(logＭ)の手間で、
質問線分と交差する線分をＯ(logＭ＋Ｋ)の手間で計算できる。
ＭはＤ内の線分数、Ｋは交差する線分数である。

３．交差する長方形のグループを求めるアルゴリズム

　ペアを列挙するアルゴリズムにおいて、交差する長方形のペア(Ｒi,Ｒj)が得られたところで、
Ｒi,Ｒjが属するグループをユニオンファインド木を用いてマージする。
マージの手間は、グループの大きさにほぼ無関係で定数時間である。

長方形番号の小さい順に調べて、ユニオンファインド木にグループ番号を設定する。
　　単独のユニオンファインド木には、グループ番号０を設定する。
　　単独でないユニオンファインド木には、１から始まる連番をグループ番号として設定する。
すべての長方形に、それが属するユニオンファインド木の番号を設定する。

なお、交差ペア(Ｒi,Ｒj)を得る必要が無く、グループ化するだけならば、Ｏ(ＮlogＮ)の
アルゴリズムが報告されている。

４．測定性能

長方形数 (N)	グループ	ペア数 (K)	計算時間 N(logN) + K
10	0	0	0.00
32	1	60	0.00
100	3	166	0.16
316	163	1797	0.47
1000	142	224	1.40
3162	168	200	4.17
10000	203	208	14.10
31623	201	201	52.00
100000	202	202	172.00

実行時間の単位は1msでclock()関数の戻り値だが、分解能は1msの精度ではない。
長方形集合は左下座標を[0, 2**31)、辺の長さを[0, 20*(2**31-1)/N)区間の一様乱数で生成している。

◆測定環境
　 Endeavor MT8000

OS	WindowsXP
CPU	Pentium4 650(3.4GHz)
メモリ	3GB(PC3200)
測定日	2012年 7月

５．使用例

◆ダウンロード（ダウンロードのページからもダウンロードできます）
　　
   sample03.zip 　　421 KB (432,085 バイト) ソース付き

５．１　インストール
　ダウンロードしたファイルを、任意のディレクトリに解凍します。

５．２　アンインストール
　インストール時に作成したディレクトリごとファイルを削除します。

５．３　使用例

   #include 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
   #include "rectPairDLL.h"

   Rect ri[] = { //x1, x2, y1, y2 サンプル長方形
       { 12, 21, 55, 60, 0},
       { 15, 26, 17, 18, 0},
       { 9, 22, 11, 13, 0},
       { 10, 23, 14, 42, 0},
       { 8, 35, 17, 30, 0},
       { 31, 39, 16, 19, 0},
       { 12, 19, 15, 25, 0},
       { 24, 41, 6, 9, 0},
       { 16, 29, 59, 70, 0},
       {-20, -6,-30,-10, 0},
       {-15, 10,-20, 0, 0}
   };
   void sample1()
   {
       int g_num, a_num, p_num, i, n, list[ sizeof(ri)/sizeof(ri[0]) ];

       n = sizeof(ri)/sizeof(ri[0]);
       //交差する長方形のペアとグループ数を求める
       g_num = rectPairs_20161231(ri, n, 0); //2016/12/31まで使用可能です。
       printf("グループ数 = %d（孤立の長方形はグループから除外）\n", g_num);
       // i 番目（０始まり）の長方形と交差する長方形の個数と番号を取得する
       i = 1;
       a_num = rectAdjacentLlist(list, i, 0);
       printf(" %d 番目の長方形と交差する長方形の数 = %d\n", i, a_num);
       if( a_num > 0 ) {
       printf(" %d 番目の長方形と交差する長方形の番号\n", i);
       for( i = 0; i < a_num; ++i ) printf(" %d\n", list[i]);
       }
       //交差した長方形のペア数を取得する
       p_num = rectOvlpNum();
       printf("長方形のペア数 = %d\n", p_num);
       //使用した領域を開放する
       rectPairFree ();
       return;
   }

５．４　実行結果

   グループ数 = 3（孤立の長方形はグループから除外）
    1 番目の長方形と交差する長方形の数 = 3
    1 番目の長方形と交差する長方形の番号
    4
    6
    3
   長方形のペア数 = 9

６．開発環境

Visual Studio 2005 C++