統計情報(30日間)


最新情報をツイート

人気の投稿

数万の位置情報を高速に地図へプロットする方法

このエントリーをはてなブックマークに追加

大量の位置情報を地図上でうまく扱う為のデータ構造や描画方法の解説。



位置情報の格納がDBのレコードのような簡単な構造だと検索に時間がかかる。この時間を短縮する為に Quad Tree を採用している。

これは図のようにエリアを4分割して、それを再帰的に保持するデータ構造を持つ。構造体の定義はこう。
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);

最初が緯度・経度を持つ位置情報、2番めが境界、3番めがノード情報で自領域内の4つの子ノードを保持する。
1次元配列に比べて検索パスが激減するので効率よく目的の位置データを見つけ出せる。

その他、クラスタリングの方法(拡大レベルに応じて複数の位置情報を1つにまとめる)、アノテーション描画の最適化(1度置いたものを再利用)など、いろいろなテクニックについての解説がある。面白い。


Leave a Reply