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

長方形交差問題(Rectangular Intersection)

1.概要

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

◆機能
 水平線分と垂直線分を辺とする長方形を対象とする。
 長方形Ri=[x1:x2]×[y1:y2]の集合Rを蓄えて、交差する長方形のペア(Ri,Rj)を全て求める。
 ついでに、交差する長方形のグループを求める。
 長方形R1,R2が同じグループであるのは、交差ペア(Ri,Rj)を枝とする無向グラフで
 R1からR2に至るパスが存在することである。
 
◆理論性能(交差長方形のペアを列挙)
 ・メモリ : N
 ・時 間 : N(logN)+K

    N:長方形の数。K:交差する長方形のペア数。
 

2.長方形のペアを列挙するアルゴリズム(Algorithm of rectangular intersection)

入力:長方形Ri=[x1:x2]×[y1:y2]の集合Rとする。
 
 全ての長方形の左辺のX座標x1を昇順に並べた列をSとする。
 垂直線分[y1:y2]の集合Dを空にする。(走査線上の長方形の垂直線分の集合)
 右のX座標x2のヒープHを空にする。(走査線上の長方形の右辺の集合)
 S内の最小のX座標aを垂直な走査線とする。
 
ヒープHからx2<aの長方形Riを削除すると共に、集合Dからも削除する。
列Sを参照してaを左座標とする全ての長方形Riに対して、
  Riの垂直線分[y1,y2]と交差するD内の線分[y3,y4]に対して、
    線分[y3,y4]に対応する長方形Rjとのペア(Ri,Rj)を交差ペアとする。
  Riの垂直線分[y1,y2]をDに追加する。
  Riの右辺の座標x2をHに追加する
aより次に大きいS内のX座標を新たにaとして、上記を繰り返す。
Sが空になったら終了する。
 
集合Dをヒープ探索木で構成することで、線分の追加/削除をO(logM)の手間で、
質問線分と交差する線分をO(logM+K)の手間で計算できる。
MはD内の線分数、Kは交差する線分数である。

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

 ペアを列挙するアルゴリズムにおいて、交差する長方形のペア(Ri,Rj)が得られたところで、
Ri,Rjが属するグループをユニオンファインド木を用いてマージする。
マージの手間は、グループの大きさにほぼ無関係で定数時間である。
 
長方形番号の小さい順に調べて、ユニオンファインド木にグループ番号を設定する。
  単独のユニオンファインド木には、グループ番号0を設定する。
  単独でないユニオンファインド木には、1から始まる連番をグループ番号として設定する。
すべての長方形に、それが属するユニオンファインド木の番号を設定する。
 
なお、交差ペア(Ri,Rj)を得る必要が無く、グループ化するだけならば、O(NlogN)の
アルゴリズムが報告されている。

4.測定性能

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

5.使用例

◆ダウンロード(ダウンロードのページからもダウンロードできます)
  
   sample03.zip   75.9 KB (77,749 バイト)
   sample03.lzh   75.6 KB (77,438 バイト)

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

5.3 使用例
 
   #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 番目(0始まり)の長方形と交差する長方形の個数と番号を取得する
       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;
   }
   
5.4 実行結果
   
   グループ数 = 3(孤立の長方形はグループから除外)
    1 番目の長方形と交差する長方形の数 = 3
    1 番目の長方形と交差する長方形の番号
    4
    6
    3
   長方形のペア数 = 9
   
   

6.開発環境

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