雑食性雑感雑記

知識の整理場。ため込んだ知識をブログ記事として再構築します。

C++ Boost ライブラリで RTree

Linux C C++ Boost RTree

概要

  • C++ Boost ライブラリの RTree 機能を使ってみた。

RTree って？？

  • 空間インデックス。地図上の何かを検索したりするのに使う。
  • 例えば「現在位置から 1km 以内にある牛丼屋さんを探せ」とか。
  • 詳しいことは Wikipedia とか参照。

背景

  • 仕事で作成している検索システム、DB の RTree 機能を利用したものだった。
  • 『DB を利用しない and C++ 実装』の改修の話になった。
  • Boost に RTree 機能があることを知り、使ってみることに。

使ってみる

  • 基本は Boost に使い方が載っている。
  • 「rtree boost」でググると結構サンプル出てくる。

実装例

  • 下記の 2種類を作成し、RTree で検索かけてみる。
    • targets : RTree の検索対象となる 2次元座標のセット
    • centers : RTree の検索中心となる 2次元座標のセット
  • 10 x 10 の範囲に targets をばらまき、centers から 6 x 6 の矩形作って検索。
  • C++ の記述として怪しいところがあったらゴメンナサイ。。
#include <iostream>
#include <string>
#include <vector>

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/index/rtree.hpp>

typedef double              distance_t;
typedef std::vector<size_t> indexes_t;

// Coordinates
typedef std::vector<double>          coordinates_t;
typedef std::vector< coordinates_t > coordinates_set_t;

// Geometry
namespace geometry = boost::geometry;
typedef geometry::model::point<distance_t, 2, geometry::cs::cartesian> point_t;
typedef geometry::model::box<point_t> box_t;
typedef std::pair<box_t, size_t> box_value_t;
typedef geometry::index::rtree< box_value_t, geometry::index::quadratic<16> > rtree_t;

// OFFSET
#define BOX_OFFSET (0.05)

// Prototype
coordinates_set_t createCenters();
coordinates_set_t createTargets();
rtree_t createRtree( coordinates_set_t targets );
indexes_t getNeighborIndexes( coordinates_t center, rtree_t targets, distance_t filter );


/*
 * Main
 */
int main()
{
    // 3.0 の大きさの矩形で取得したい
    distance_t filter = 3.0;

    // (1) Create coordinates set
    coordinates_set_t centers = createCenters();
    coordinates_set_t targets = createTargets();

    // (2) Create RTree
    rtree_t target_rtree = createRtree( targets );

    // (3) Get neighbor index
    coordinates_t center;
    for ( size_t i = 0; i < centers.size(); i++ ) {
	center = centers[i];
	std::cout << "Center " << (i+1) << ": ("
                  << center[0] << ", " << center[1] << ")" << std::endl;

	indexes_t indexes = getNeighborIndexes( center, target_rtree, filter );
	std::cout << "Index : ";
	for ( size_t j = 0; j < indexes.size(); j++ ) {
	    std::cout << indexes[j] << " ";
	}
	std::cout << std::endl << std::endl;
    }

    return 0;
}



/*
 * Centers 作成
 */
coordinates_set_t createCenters()
{
    coordinates_set_t centers;

    coordinates_t tmp;
    for ( size_t i = 0; i < 3; i++ ) {

	tmp.clear();
	tmp.push_back( 5.0 * ( i + 1 ) );
	tmp.push_back( 5.0 * ( i + 1 ) );

	centers.push_back( tmp );
    }

    return centers;
}

/*
 * Targets 作成
 */
coordinates_set_t createTargets()
{
    coordinates_set_t targets;

    coordinates_t tmp;
    for ( size_t i = 0; i < 10; i++ ) {
	for ( size_t j = 0; j < 10; j++ ) {

	    tmp.clear();
	    tmp.push_back( 1.0 * i );
	    tmp.push_back( 1.0 * j );

	    targets.push_back( tmp );
	}
    }

    return targets;
}

/*
 * RTree 作成
 */
rtree_t createRtree( coordinates_set_t targets )
{
    rtree_t target_rtree;

    coordinates_t tmp;
    for ( size_t i = 0; i < targets.size(); i++ ) {
	tmp = targets[i];

	box_t b( point_t( tmp[0] - BOX_OFFSET, tmp[1] - BOX_OFFSET ),
		 point_t( tmp[0] + BOX_OFFSET, tmp[1] + BOX_OFFSET ) );

	target_rtree.insert( std::make_pair( b, i ) );
    }

    return target_rtree;
}


/*
 * Get neighbor index
 */
indexes_t getNeighborIndexes( coordinates_t center, rtree_t targets, distance_t filter )
{
    std::vector<box_value_t> result;
    box_t query_box( point_t( center[0] - filter, center[1] - filter ),
                     point_t( center[0] + filter, center[1] + filter ) );
    targets.query( geometry::index::intersects( query_box ), std::back_inserter( result ) );

    indexes_t indexes;
    std::vector<box_value_t>::iterator itr;
    for ( itr = result.begin(); itr != result.end(); ++itr ) {
	box_value_t value = *itr;
	indexes.push_back( value.second );
    }

    return indexes;
}
  • 実行結果 ( CentOS + g++ で実行、適当に改行入れてます。)
$ g++ ./rtree.cpp
$ ./a.out
Center 1: (5, 5)
Index : 28 27 26 25 24 23 22 38 37 36 
35 34 33 32 48 47 46 45 44 43 42 58 57 
56 55 54 53 52 68 67 66 65 64 63 62 78 
77 76 75 74 73 72 88 87 86 85 84 83 82

Center 2: (10, 10)
Index : 79 78 77 89 88 87 97 98 99

Center 3: (15, 15)
Index :

使用例

  • 仕事では大量のデータを処理する必要があったので、次のような使い方。
    • まず、RTree で対象データの近傍にあるデータを取得。
    • 近傍にあるデータの中から、更に複雑な図形で絞り込み。
  • 始めから複雑な図形の絞り込みを行うと、恐ろしいレベルの時間を消費してしまうので…。

備考

  • 時間があったら、DB の RTree との実行時間比較とかやってみたい。
    • データのアクセス速度とか、色々ありそうだけど。。
  • 多次元の場合はどうするの？？
    • (お仕事のソースでは) 上記2次元の比較を組み合わせて使いました。
      • 3次元だったら、『(1+2)・(2+3)・(3+1) の 3パターンで近傍取る』みたいな。