주어진 데이터 포인트를 사용하여 RTree를 구성하는 방법

Question

R 트리 주어진 데이터 포인트를 사용하여 구성해야합니다 .R tree.All 구현의 구현을 검색했습니다. . 나는 주어진 데이터 포인트 자체 (1 차원 일 수있다)가있을 때 r 트리를 만들 필요가있다.이 코드는이 데이터 포인트를 둘러싸고 직사각형을 만들어 트리를 만들어야한다.

Answer 1

최소 = 최대 = 좌표의 MBR (Minimum bounding rectangle)을 사용하십시오. 그들은 모두 이렇게합니다. 그러나 좋은 구현은 잎 노드의 용량이 디렉토리 노드보다 약 2 배 큰 포인트 데이터를 저장합니다.

Answer 2

포인트를 저장하기 위해 Rtree를 사용하는 것은 오용처럼 보입니다. 이런 종류의 구조가 공간 데이터를 저장하기 위해 표시되었지만 일부 연구 후에 방금 찾은 공간이 영 (0)이 아닌 영역을 저장하는 데 가장 적합하다는 것을 알았습니다 (이름의 R은 Region 또는 Rectangle 용이므로). 멋진 인덱스가있는 간단한 테이블을 작성하면 데이터를 업데이트하고 검색하는 데 더 우수한 성능을 제공해야합니다. 아래에있는 내 예를 고려해

CREATE TABLE locations (id, latitude, longitude); 
CREATE INDEX idx_locations ON locations (latitude, longitude); 

바람직하다 그냥 지점이 아닌 사각형을 대표하는 것처럼 모든 행에 대해 maxLongitude 이상 maxLatitude 및 minLongitude 이상 minLatitude을 반복하려는 경우

CREATE VIRTUAL TABLE locations USING rtree(id, minLatitude, maxLatitude, minLongitude, maxLongitude); 

이상. 후자의 접근 방식은 예상대로 작동하지만 Rtrees는 사각형 영역을 인덱싱하는 데 적합하며 점을 저장하는 데 사용하면 최악의 성능으로 오용됩니다. 위와 같이 복합 색인을 선호하십시오.

추가 읽기 : http://www.deepdyve.com/lp/acm/r-trees-a-dynamic-index-structure-for-spatial-searching-ZH0iLI4kb0?key=acm

Answer 3

당신이 C++ 구현을 찾고 있다면, 하나는 현재 Boost.Geometry에 포함 (. 부스트 1.57) 점, 박스 및 세그먼트를 저장할 수있다.

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

#include <vector> 

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

int main() 
{ 
    typedef bg::model::point<float, 2, bg::cs::cartesian> point; 
    typedef bg::model::box<point> box; 

    // a container of points 
    std::vector<point> points; 

    // create the rtree 
    bgi::rtree< point, bgi::linear<16> > rtree(points.begin(), points.end()); 

    // insert some additional points 
    rtree.insert(point(/*...*/)); 
    rtree.insert(point(/*...*/)); 

    // find points intersecting a box 
    std::vector<point> query_result; 
    rtree.query(bgi::intersects(box(/*...*/)), std::back_inserter(query_result)); 

    // do something with the result 
}