4th dimension with boost.geometry.index.rtree

Question

I need to optimize an edge case for my spatial index which can be described as follows:

• The spatial index contains a large set of 3D geometries (3D points and 2.5D extruded polygons) distributed all over the globe.
• There are some hot spots where at some locations on the globe a very large number of geometries collide with another and which leads to O² overlaps / collisions.
• At these hot spot locations it is therefore required to consider an additional type assigned to the geometry and reduce the number of spatial results.
• For example, one geometry may represent a car and another a geofence. At these hot spot locations (which are unknown beforehand and may dynamically change randomly) for example cars overlapping a geofence would be queried, while cars overlapping with other items should rather be ignored.

Is it possible to use boost r-tree for 4-dimensional data efficiently in this case?

UPDATE

I've created a small test program. The program fails to construct a 4d point with "No matching constructor for initialization of 'point' (aka 'point<float, 4, bg::cs::cartesian>')".

So it seems there is no support for 4d points with boost geometry.

Source code:

#include <iostream>
#include <vector>
#include <random>
#include <chrono>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/index/rtree.hpp>

namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;

typedef bg::model::point<float, 4, bg::cs::cartesian> point;
typedef bg::model::box<point> box;
typedef std::pair<point, unsigned> value;

int main(int argc, const char * argv[]) {
    bgi::rtree<value, bgi::quadratic<16>> rtree;

    const int NUM_ENTRIES = 10000000;
    const int NUM_QUERIES = 10000000;

    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_real_distribution<> disX(0, 1000);
    std::uniform_real_distribution<> disY(0, 1000);
    std::uniform_real_distribution<> disZ(0, 10);

    // Measure insertion time
    auto start_insert = std::chrono::high_resolution_clock::now();
    for (unsigned i = 0; i < NUM_ENTRIES; ++i) {
        float x = disX(gen);
        float y = disY(gen);
        float z = disZ(gen);
        float w = i % 2 == 0 ? 0.0f : 1.0f;
        point p(x, y, z, w);
        rtree.insert(std::make_pair(p, i));
    }
    auto end_insert = std::chrono::high_resolution_clock::now();
    auto insert_duration = std::chrono::duration<float>(end_insert - start_insert);
    float inserts_per_second = NUM_ENTRIES / insert_duration.count();
    std::cout << "Inserts per second: " << inserts_per_second << std::endl;

    // Measure query time
    auto start_query = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < NUM_QUERIES; ++i) {
        float x = disX(gen);
        float y = disY(gen);
        float z = disZ(gen);
        float w = i % 2 == 0 ? 0.0f : 1.0f;
        box query_box(point(x - 1, y - 1, z - 1, w), point(x + 1, y + 1, z + 1, w));
        std::vector<value> result;
        rtree.query(bgi::intersects(query_box), std::back_inserter(result));
    }
    auto end_query = std::chrono::high_resolution_clock::now();
    auto query_duration = std::chrono::duration<float>(end_query - start_query);
    float queries_per_second = NUM_QUERIES / query_duration.count();
    std::cout << "Queries per second: " << queries_per_second << std::endl;

    return 0;
}

Answer 1

Using a fourth dimension for type (car, building, etc.) should work fine for narrowing the search result. I assume the boost implementation supports four dimensions (I haven't used it myself).