大量の位置情報を地図上でうまく扱う為のデータ構造や描画方法の解説。
位置情報の格納がＤＢのレコードのような簡単な構造だと検索に時間がかかる。この時間を短縮する為に Quad Tree を採用している。
これは図のようにエリアを４分割して、それを再帰的に保持するデータ構造を持つ。構造体の定義はこう。
typedef struct TBQuadTreeNodeData {
double x;
double y;
void* data;
} TBQuadTreeNodeData;
TBQuadTreeNodeData TBQuadTreeNodeDataMake(double x, double y, void* data);
typedef struct TBBoundingBox {
double x0; double y0;
double xf; double yf;
} TBBoundingBox;
TBBoundingBox TBBoundingBoxMake(double x0, double y0, double xf, double yf);
typedef struct quadTreeNode {
struct quadTreeNode* northWest;
struct quadTreeNode* northEast;
struct quadTreeNode* southWest;
struct quadTreeNode* southEast;
TBBoundingBox boundingBox;
int bucketCapacity;
TBQuadTreeNodeData *points;
int count;
} TBQuadTreeNode;
TBQuadTreeNode* TBQuadTreeNodeMake(TBBoundingBox boundary, int bucketCapacity);最初が緯度・経度を持つ位置情報、２番めが境界、３番めがノード情報で自領域内の４つの子ノードを保持する。
１次元配列に比べて検索パスが激減するので効率よく目的の位置データを見つけ出せる。
その他、クラスタリングの方法（拡大レベルに応じて複数の位置情報を１つにまとめる）、アノテーション描画の最適化（１度置いたものを再利用）など、いろいろなテクニックについての解説がある。面白い。