点集合から矩形に含まれる点部分集合を抽出する（象限分割法）

始めに

前置き

　このアルゴリズムは、１９８９～１９９１年に受注したシステムのためにわたしが独自に構築したものですが、現在では一般的な４分木の１種と認識しています。
　また、本ブログのメインテーマは巡回セールスマン問題となりますが、本記事の象限分割法と巡回セールスマン問題を比較したときの計算量の違いや解法の難度の要因を模索していました。
　その要因は、一目瞭然とも言えるのですが、逆にその要因を厳密に特定できれば、巡回セールスマン問題の解法に役立つのではないかと考えたのです。
　結論は未だにでていませんが、キーワードは「関係」と「組み合わせ」ではないかと思っています。

概要

　対象座標系は２次元直角座標系とします。
　点集合P=｛p1.p2.p3...,pn｝としたとき、検索条件を｛ｘ1、ｘ2、ｙ1、ｙ2｝で示される矩形情報とします。
　出力は、検索矩形内に内包される点集合Pの部分集合PPとなります。

応用例

　①　検索条件矩形を画面または、Windowとします。それぞれの検索条件矩形の座標は、点集合Pの座標系に変換します。
　②　マウスなどでクリックしたとき、そのクリックした点に一定の幅を持たせ検索条件矩形とします。①と同様に座標変換が必要です。これにより、クリックした点に近い点がいくつか得られます。

計算量

１点の抽出（クリック点に最も近い点など）

　点集合の要素数をNとしたとき、１点を抽出（検索）する場合を考えます。
１点を抽出（検索）する場合の検索条件は、できるだけ狭い矩形となります。
　但し、矩形が狭すぎると０点の抽出となる場合もあります（抽出できないケース）。
　m点を抽出したとき、検索点とm点の距離を計算し最も近い点を検索結果とします。

AVL木

　２分探索木のAVL木の考え方が４分探索木にも適用されます。
底となるノードとルートとの距離が平均的であることが求められます。
これを平衡木と呼びます。
２分探索木の場合、距離の差を１以内とすることが可能ですが、4分探索木の場合、それは難しいように思われます。
筆者は4分探索木の平衡木化の考察を行っていないので、この考察を行うことも面白いかもしれません。

計算量

　４分探索木が平衡木であると仮定すると、検索回数（計算量）F=LogN（低は４）に近くなります。
但し、ベースとなる点集合の配置座標などにより、厳密な計算量は現在計算できません。

アルゴリズム

アルゴリズムの概要

　①　点集合Pから４分木を生成
　②　検索条件矩形に内包される点集合を抽出

「４分木を生成」のアルゴリズム

図を参照ください。

　①　点集合Pからｘとｙの最小値と最大値を取得
　②　①で取得した値に僅かな幅を持たせ、点集合世界を設定
　　　（点集合Pの全ての要素が点集合世界に内包されることになります）
図のボタン［アルゴリズム　ステップ１］をクリックしてください。
　　　上図の点LBとRTが点集合Pのｘとｙの最小値と最大値となります。
　　　幅Wを加算ないしは減算した点RminとRmaxが点集合世界となります。
　　　尚、それぞれの点は左下隅、右上隅となります。
　③－１　点集合から任意の点を点集合世界に投入します。
　　　随時、ｎ点まで投入を繰り返します。
　　　つまり、逐次投入となります。
　　　尚、ここでは２点までを例として示します。
図のボタン［アルゴリズム　ステップ２、３］をクリックしてください。
　　　P１を投入したとき、点集合世界はⅰ～ⅳの領域に分割されます。

　　　Rminの座標を（Rminx,Rminy）
　　　Rmaxの座標を（Rmaxx,Rmaxy）
　　　P1の座標を（P1x,P1y）
　　　としたとき、

　　　ⅰ～ⅳの領域は次の座標域で表現できます。
　　　ⅰ：P1x-Rmaxx,P1y-Rmaxy
　　　ⅱ：Rminx-P1x,P1y-Rmaxy
　　　ⅲ：Rminx-P1x,Rminy-P1y
　　　ⅳ：P1x-Rmaxx,Rminy-P1y

　　　これを４分木で表現します。
　　　木構造のルートは、P1（第１の投入点）となります。
　　　そして、P1はノードとなり点集合世界の域座標を所有します。
　　　また、P1はⅰ～ⅳの座標域を持つ４つの分枝を所有します。
　③－２　２点目（P2）を投入します。
　　　P2はP１で構築された領域のⅳに存在するものとします。
　　　P2はP1の領域ⅳを４つの領域に分割します。
　　　　これを４分木で表現します。
　　　P2は木構造のルートP1の領域ⅳの分枝に所属します。
　　　このとき、領ⅰ～ⅲの分枝は要素を持ちません。
　　　また、P２はⅰ～ⅳの座標域を持つ４つの分枝を所有します。
　④　注意点
　　　逐次投入していく点が座標域の境界上（軸上）に存在するとき、どちらの座標域に属するかという問題については、ルールを決めておきます。
　　　このルールが検索時と合致していれば問題は起こりません。

検索のアルゴリズム

　①　検索条件は矩形の左下隅と右上隅の座標になります。
　②　検索する順番は木構造の上位レベルから行います。
　③　検索条件矩形が木構造のノードの分枝のいくつかにまたがるときは、その全ての分枝を捜査します。
　④　座標域の境界上（軸上）に検索条件矩形が接するときは、木構造で設定したルールに従います。全てを捜査しても問題ありませんが、検索速度が少し遅くなります。