2次元平面上にある、複数の座標をソートしたい

Question

2次元平面の上に、複数個の任意の座標を持った点があるものとします。
その座標は、何らかのデータ構造で保持します。
ある点が与えられた時、その点から一定の距離内にあるデータを取り出します。
この時、データを取り出す回数がなるべく抑えられるようにデータをソートしたいです。

例えば、人間が近い点を取り出す場合、データの座標が描かれたグラフがあれば、一定の距離内の点を検索する際、ある程度の目安がとれます。
しかし、配列等に格納し、x座標またはy座標でソートしてしまうと、配列内すべての要素との距離を測らなければなりません。

例えば点同士が近いほど値が近くなるような1つの値にまとめ、その大きさでソートするなどといった方法は存在しないのでしょうか？

Answer 1

二次元のデータである以上、インデクシングも二次元的に行うしかありません（地表面のように座標空間に限界があるのなら、適当な単位で区切ることで1つの値にまとめることはできますが、空間が無限に広がる場合はそうも行きません）。

データベースにも空間インデックスが用意されているケースがありますが、MicrosoftのSQL Serverでは何段階かのメッシュに区切って実装しているとのことです。

Answer 2

yの上位ビット、xの上位ビット、…の順で下位ビットへと交互に比較してソートします。
座標が近ければデータも近い、とか
データが近ければ座標も近い、という保証はありませんが、
座標が近いデータは近くに並びやすくなります。

あらかじめ、xとyの値をスケーリングしておく必要があります。
(または、下のコードでは、ビットマスク mask をy座標・x座標で別々にするなど)

C言語の例を示します。(xもyも0〜255の場合)
一般的なコンピュータでは、上から下、左から右の順に並びます。
(数学のxy座標では下から上、左から右の順になります)

#include <stdlib.h>
struct cood_s
    {
    int x;              /* x座標*/
    int y;              /* y座標*/
                        /* その他属性… */
    };
typedef struct cood_s   cood;
cood coods[100];
/* 値を設定… */

#define AX      (  ( (cood *)a )-> x  )
#define BX      (  ( (cood *)b )-> x  )
#define AY      (  ( (cood *)a )-> y  )
#define BY      (  ( (cood *)b )-> y  )
static  int     compare(const void *a, const void *b)
{
int mask;
int diff;

for ( mask=0x80; mask ; mask >>= 1 )
	{
	diff = (AY & mask) - (BY & mask);
	if (diff) return(diff);
	diff = (AX & mask) - (BX & mask);
	if (diff) return(diff);
	}
return(0);
}

static  void sort_coods(coods, coodcnt)
cood *coods;                    /* in   座標リスト */
int coodcnt;                    /* in   座標の組の数*/
{
qsort(coods, coodcnt, sizeof(cood), compare);
}

図にすると、x,y 各1ビットでは
┌─┬─┐
│０→１│
├─／─┤
│２→３│
└─┴─┘
x,y 各2ビットでは、これを再帰的に適用して
┌─┬─┬─┬─┐
│０→①│④→⑤│
├─／─／─／─┤
│②→③│⑥→⑦│
├─┼─┼─┼─┤
│⑧→⑨│⑫→⑬│
├─／─／─／─┤
│⑩→⑪│⑭→⑮│
└─┴─┴─┴─┘
のようになります。

座標の近傍をすべて探し出すには、
やはりcoco_bauerさんのようにインデックスを2本用意する必要があるかもしれません。

あまり厳密でない用途では、上記コードのxy混成ソートが役に立つかもしれません。
・地図アプリで近くの店を提案する
・戦略ゲームで近くの基地を提案する　など

座標にひもづけられた大きなデータを格納する場合に、
図のようなソート順にするとキャッシュのヒット率が上がるといった
メリットがあるかもしれません。

Answer 3

＜準備＞
x座標でソートした点のリスト(Xリスト)と、y座標でソートした点のリスト(Yリスト）を作成しておく。
リストは、[x座標、y座標、点の識別子(ユニークな名前)]の情報からなるデータで構成する。

＜点の抽出＞
ある点（x座標=A,y座標=B)と、一定の距離(C)が与えられたら、
・Xリストから、A-c <= x座標 <= A+C の点を抽出 (x座標でソートされているので、抽出する範囲はバイナリサーチで比較的容易に抽出できるはず）
・Yリストから、B-c <= y座標 <= C+C の点を抽出
・抽出された二組のデータに共通する点(両方の組に同じ識別子が出現する)について、一定の距離内にあるかどうかを確認(検算)する。

まぁ、単純に考えると、この辺りから考え始めるのが良いように思います。