2次元平面の上に、複数個の任意の座標を持った点があるものとします。
その座標は、何らかのデータ構造で保持します。
ある点が与えられた時、その点から一定の距離内にあるデータを取り出します。
この時、データを取り出す回数がなるべく抑えられるようにデータをソートしたいです。
例えば、人間が近い点を取り出す場合、データの座標が描かれたグラフがあれば、一定の距離内の点を検索する際、ある程度の目安がとれます。
しかし、配列等に格納し、x座標またはy座標でソートしてしまうと、配列内すべての要素との距離を測らなければなりません。
例えば点同士が近いほど値が近くなるような1つの値にまとめ、その大きさでソートするなどといった方法は存在しないのでしょうか?
気になる質問をクリップする
クリップした質問は、後からいつでもMYページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
回答3件
0
ベストアンサー
二次元のデータである以上、インデクシングも二次元的に行うしかありません(地表面のように座標空間に限界があるのなら、適当な単位で区切ることで1つの値にまとめることはできますが、空間が無限に広がる場合はそうも行きません)。
データベースにも空間インデックスが用意されているケースがありますが、MicrosoftのSQL Serverでは何段階かのメッシュに区切って実装しているとのことです。
投稿2017/05/09 05:31
総合スコア145183
0
yの上位ビット、xの上位ビット、…の順で下位ビットへと交互に比較してソートします。
座標が近ければデータも近い、とか
データが近ければ座標も近い、という保証はありませんが、
座標が近いデータは近くに並びやすくなります。
あらかじめ、xとyの値をスケーリングしておく必要があります。
(または、下のコードでは、ビットマスク mask をy座標・x座標で別々にするなど)
C言語の例を示します。(xもyも0〜255の場合)
一般的なコンピュータでは、上から下、左から右の順に並びます。
(数学のxy座標では下から上、左から右の順になります)
C言語
1#include <stdlib.h> 2struct cood_s 3 { 4 int x; /* x座標*/ 5 int y; /* y座標*/ 6 /* その他属性… */ 7 }; 8typedef struct cood_s cood; 9cood coods[100]; 10/* 値を設定… */ 11 12#define AX ( ( (cood *)a )-> x ) 13#define BX ( ( (cood *)b )-> x ) 14#define AY ( ( (cood *)a )-> y ) 15#define BY ( ( (cood *)b )-> y ) 16static int compare(const void *a, const void *b) 17{ 18int mask; 19int diff; 20 21for ( mask=0x80; mask ; mask >>= 1 ) 22 { 23 diff = (AY & mask) - (BY & mask); 24 if (diff) return(diff); 25 diff = (AX & mask) - (BX & mask); 26 if (diff) return(diff); 27 } 28return(0); 29} 30 31static void sort_coods(coods, coodcnt) 32cood *coods; /* in 座標リスト */ 33int coodcnt; /* in 座標の組の数*/ 34{ 35qsort(coods, coodcnt, sizeof(cood), compare); 36} 37
図にすると、x,y 各1ビットでは
┌─┬─┐
│0→1│
├─/─┤
│2→3│
└─┴─┘
x,y 各2ビットでは、これを再帰的に適用して
┌─┬─┬─┬─┐
│0→①│④→⑤│
├─/─/─/─┤
│②→③│⑥→⑦│
├─┼─┼─┼─┤
│⑧→⑨│⑫→⑬│
├─/─/─/─┤
│⑩→⑪│⑭→⑮│
└─┴─┴─┴─┘
のようになります。
座標の近傍をすべて探し出すには、
やはりcoco_bauerさんのようにインデックスを2本用意する必要があるかもしれません。
あまり厳密でない用途では、上記コードのxy混成ソートが役に立つかもしれません。
・地図アプリで近くの店を提案する
・戦略ゲームで近くの基地を提案する など
座標にひもづけられた大きなデータを格納する場合に、
図のようなソート順にするとキャッシュのヒット率が上がるといった
メリットがあるかもしれません。
投稿2023/11/03 03:11
編集2023/11/03 12:41総合スコア2
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
<準備>
x座標でソートした点のリスト(Xリスト)と、y座標でソートした点のリスト(Yリスト)を作成しておく。
リストは、[x座標、y座標、点の識別子(ユニークな名前)]の情報からなるデータで構成する。
<点の抽出>
ある点(x座標=A,y座標=B)と、一定の距離(C)が与えられたら、
・Xリストから、A-c <= x座標 <= A+C の点を抽出 (x座標でソートされているので、抽出する範囲はバイナリサーチで比較的容易に抽出できるはず)
・Yリストから、B-c <= y座標 <= C+C の点を抽出
・抽出された二組のデータに共通する点(両方の組に同じ識別子が出現する)について、一定の距離内にあるかどうかを確認(検算)する。
まぁ、単純に考えると、この辺りから考え始めるのが良いように思います。
投稿2017/05/09 06:36
総合スコア6915
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
あなたの回答
tips
太字
斜体
打ち消し線
見出し
引用テキストの挿入
コードの挿入
リンクの挿入
リストの挿入
番号リストの挿入
表の挿入
水平線の挿入
プレビュー
質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。