{"id":185,"date":"2008-10-04T00:57:16","date_gmt":"2008-10-04T04:57:16","guid":{"rendered":"http:\/\/www.virtualroadside.com\/blog\/?p=185"},"modified":"2016-07-03T10:56:33","modified_gmt":"2016-07-03T15:56:33","slug":"r-tree-implementation-for-cpp","status":"publish","type":"post","link":"http:\/\/www.virtualroadside.com\/blog\/index.php\/2008\/10\/04\/r-tree-implementation-for-cpp\/","title":{"rendered":"R* Tree Implementation for C++"},"content":{"rendered":"<p>So a few weeks ago I finished preliminary work on an <a href=\"http:\/\/en.wikipedia.org\/wiki\/R*_tree\">R* Tree<\/a> implementation in C++. My goal for this implementation is as follows:<\/p>\n<ul>\n<li>Simple API &#8211; Most existing implementations I&#8217;ve seen are far from simple<\/li>\n<li>Generic enough to use with most types, with low overhead<\/li>\n<li>N dimensions for bounding boxes<\/li>\n<li>Easy to integrate and use for <a href=\"http:\/\/roadnav.sourceforge.net\">Roadnav<\/a><\/li>\n<li>Take advantage of modern C++ features to get decent performance<\/li>\n<\/ul>\n<p>This is a header-only implementation of an R tree with an R* index, and makes heavy use of templates, STL, and STL-style functors; but it should work in any relatively modern C++ compiler. To do searching for nodes, this implementation uses the Visitor pattern via functors &#8212; there are examples and documentation in RStarVisitor.h.<\/p>\n<p>If you use this, <em>*please*<\/em> let me know, I&#8217;m very interested to see what bugs may come up, and possible performance problems. Unfortunately, I haven&#8217;t gotten around to writing any comprehensive tests for it (but given the tests I&#8217;ve run so far, I&#8217;m reasonably sure the implementation is mostly correct), but I expect that once I get it integrated into Roadnav that this will follow shortly after. Also, integration of the R* tree into Roadnav will make a lot of potential errors pop out. Look for this in the near future.<\/p>\n<p>Additionally, I am thinking about some of the following ideas too:<\/p>\n<ul>\n<li>Adding the ability to work with extra-large datasets by saving\/loading to\/from disk (after all, that is the point of R trees&#8230;)<\/li>\n<li>Adding a bulk insert function &#8212; there is pseudocode already for this, but I haven&#8217;t actually written an implementation for this yet. Also, a more efficient bulk delete function<\/li>\n<li>Trying to implement it as a <a href=\"http:\/\/www.boost.org\/\">Boost <\/a><a href=\"http:\/\/www.boost.org\/doc\/libs\/1_36_0\/doc\/html\/intrusive.html\">intrusive <\/a>container. I&#8217;ve been playing with some Boost stuff lately at work, and theres a lot of neat things there.<\/li>\n<\/ul>\n<p>I&#8217;ll also use this opportunity to put in a plug for Roadnav &#8212; if you&#8217;re looking to work on an open source project, theres a bunch of (mostly) interesting stuff that I&#8217;m working on\/planning for Roadnav. What I&#8217;m working on right now is totally removing US-specific stuff from Roadnav, and moving to an OpenStreetMap-only implementation. Theres a number of features that are getting thrown away, but I think that the dynamic community that OSM opens up to Roadnav will be well worth it.<\/p>\n<p><strong>Note:<\/strong> I&#8217;ve updated this quite a bit (though, remove functionality has been removed and it no longer uses the visitor pattern for data access), and its currently a part of libsdbx. Libsdbx can be found in Roadnav SVN at <a href=\"https:\/\/roadnav.svn.sourceforge.net\/svnroot\/roadnav\/libsdbx\/trunk\/\">https:\/\/roadnav.svn.sourceforge.net\/svnroot\/roadnav\/libsdbx\/trunk\/<\/a>. I&#8217;ll write about this soon.. but its pretty neat. It supports R* and modified B+ trees, in memory or on disk. Check it out.<\/p>\n<p><strong>Note II<\/strong>: I&#8217;ve pushed the source code to github at <a href=\"https:\/\/github.com\/virtuald\/r-star-tree\">https:\/\/github.com\/virtuald\/r-star-tree<\/a><\/p>\n<p><a href=\"http:\/\/www.virtualroadside.com\/software\/#RStarTree\">Download the sourcecode here<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>So a few weeks ago I finished preliminary work on an R* Tree implementation in C++. My goal for this implementation is as follows: Simple API &#8211; Most existing implementations I&#8217;ve seen are far from simple Generic enough to use with most types, with low overhead N dimensions for bounding boxes Easy to integrate and [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[38],"tags":[],"_links":{"self":[{"href":"http:\/\/www.virtualroadside.com\/blog\/index.php\/wp-json\/wp\/v2\/posts\/185"}],"collection":[{"href":"http:\/\/www.virtualroadside.com\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.virtualroadside.com\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.virtualroadside.com\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.virtualroadside.com\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=185"}],"version-history":[{"count":6,"href":"http:\/\/www.virtualroadside.com\/blog\/index.php\/wp-json\/wp\/v2\/posts\/185\/revisions"}],"predecessor-version":[{"id":531,"href":"http:\/\/www.virtualroadside.com\/blog\/index.php\/wp-json\/wp\/v2\/posts\/185\/revisions\/531"}],"wp:attachment":[{"href":"http:\/\/www.virtualroadside.com\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=185"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.virtualroadside.com\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=185"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.virtualroadside.com\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=185"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}