如何使用給定的數據點構建一個RTree

我需要構造一個R樹使用給定的數據點。我已經搜索了R樹的實現。所有的實現我發現構造r樹時矩形的座標作爲輸入。當給定數據點本身（它可以是1維）時，我需要構造r樹。代碼應該考慮創建包含這些數據點的矩形並構造r樹。如何使用給定的數據點構建一個RTree

來源

2011-04-30 rajsekhar

使用min = max =座標的MBR（Minimum bounding rectangle）。他們都這樣做。但是，好的實現會在目錄節點中存儲容量大約是容量的兩倍的點數據。

來源

2011-12-22 21:18:51

可以詳細說明一下嗎？在大多數R-tree代碼中，您將創建一個矩形（右下角和右上角的點），並將該矩形添加到R樹。你是說如果我們想存儲一個點，那麼這兩個點（右下和右上）應該是同一個點？ – stackoverflowuser2010 2013-09-25 17:39:41

單點的MBR當然有'min = max = coordinate'。通過在葉級別存儲點而不是MBR，我們可以獲得大約兩倍的對象，這將磁盤空間減少了將近2倍。 – 2013-09-25 17:43:42

謝謝。因此，通過解讀你的答案，我假定你的意思是「是的，如果我們想存儲一個點，那麼兩個點（右下和右上）應該是同一個點」。與其他數據結構（如點區四叉樹）相比，R-tree是否更適合存儲點？ – stackoverflowuser2010 2013-09-25 17:56:54

-1

我想用Rtree來存儲點似乎是一種誤用。雖然這種結構被用來存儲空間數據，但經過一番研究後，我發現它最適合存儲非零區域（因爲名稱中的R是Region或Rectangle）。創建一個具有良好索引的簡單表應該爲更新和搜索數據提供更好的性能。考慮下面我舉的例子：

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

最好在

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

，如果你只是打算在maxLongitude重複minLatitude超過maxLatitude和minLongitude的每一行，以代表點，而不是矩形。雖然後一種方法將按預期工作，但Rtrees適合索引矩形區域，並且使用它們來存儲點是一種誤用，表現最差。喜歡上面的複合索引。

延伸閱讀：http://www.deepdyve.com/lp/acm/r-trees-a-dynamic-index-structure-for-spatial-searching-ZH0iLI4kb0?key=acm

來源

2012-12-26 03:51:43

不能同意。我需要僅限點的索引，並且R-tree查詢比複合索引（SQLite）快。空間不僅僅關於數據，而且關於查詢：如果你想知道矩形（查詢）中包含的所有點（數據），請嘗試使用R樹。 – pwes 2013-05-30 21:15:35

如果你正在尋找一個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 
}

來源

2015-01-09 01:30:42

下面是使用斷言一些數值例子：https://github.com/cirosantilli/cpp-cheat/blob/160e96ec04df93c4ad227d63af5e651498bca834/boost/rtree.cpp – 2017-01-13 23:45:58

如何使用給定的數據點構建一個RTree

回答

相關問題