Stack Overflow
Stack Overflow

Questions tagged [r-tree]

R-Tree is a popular index structure for spatial data, stored as Minimum Bounding Rectangles (MBRs).

R-Trees were invented by Antonin Guttman in his 1984 seminal paper R-trees: a dynamic index structure for spatial searching. The extended usability of this data structured is presented in the survey R-trees Have Grown Everywhere and popular implementations include the boost::geometry::index library.

263 questions
98
votes
3 answers

What is the difference between a KD-tree and a R-tree?

I looked at the definition of KD-tree and R-tree. It seems to me that they are almost the same. What's the difference between a KD-tree and an R-tree?
zjffdu
  • 25,496
  • 45
  • 109
  • 159
43
votes
2 answers

R-Tree and Quadtree Comparison

I want to compare the R-Tree and the Quadtree for geospatial data. While there is literature out there I struggle to find documents that cover real basic comparison. So I decided to ask this question. In my opinion, the R-Tree has the advantage of…
Andre
  • 1,249
  • 1
  • 15
  • 38
27
votes
4 answers

C++ R - tree implementation wanted

Does anyone know a good and simple to use in production code R-tree implementation? (actually, any implementations - R*, R+ or PR-tree would be great) It doesn't matter if it is a template or library implementation, but some implementations that…
M. Williams
  • 4,945
  • 2
  • 26
  • 27
21
votes
3 answers

Is there any documented free R-Tree implementation for .NET?

I found some open source R-Tree implementations in C#, but none with documentation nor signs of being used by someone else than the developer.
Jader Dias
  • 88,211
  • 155
  • 421
  • 625
16
votes
5 answers

R-Tree Implementation Java

I was searching the last few days for a stable implementation of the R-Tree with support of unlimited dimensions (20 or so would be enough). I only found this http://sourceforge.net/projects/jsi/ but they only support 2 dimensions. Another Option…
drame
  • 435
  • 1
  • 4
  • 14
15
votes
2 answers

libspatialindex and Rtree on python

Okay, so I am trying to install libspatialspatialindex to my Ubuntu machine python. I did follow all the instructions and downloaded libspatialindex1_1.4.0-1.1_amd64.deb from http://packages.ubuntu.com/lucid/libspatialindex1 and downloaded the amd64…
Neelabh Pant
  • 807
  • 2
  • 7
  • 12
14
votes
3 answers

Java commercial-friendly R-tree implementation?

I need a commercial-friendly (Apache Licence, LGPL, Mozilla Public License etc) R-tree implementation in Java, in order to substitute the geonames Web Service for timezones, as suggested in the question "Determine timezone from latitude/longitude…
Markos Fragkakis
  • 7,499
  • 18
  • 65
  • 103
13
votes
3 answers

Fast method to find distance from point to closest edge of polygon

Setup Function will need to provide the distance from a point to the closest edge of a polygon Point is known to be inside of the polygon Polygon can be convex or concave Many points (millions) will need to be tested Many separate polygons (dozens)…
thaspius
  • 1,135
  • 3
  • 17
  • 33
10
votes
0 answers

What is the R*-Tree algorithm?

Where can I find enough documentation to implement an R*-Tree? Specifically, I need to be able to: Insert nodes Remove nodes Search for K nearest neighbours Find all nearest neighbours within distance x. Is there a single place where this…
fmark
  • 57,259
  • 27
  • 100
  • 107
10
votes
1 answer

Why boost.geometry.index.rtree is slower than superliminal.RTree

I test boost.geometry.index.rtree (boost 1.59 www.boost.org) and superliminal.RTree (http://superliminal.com/sources/sources.htm#C_Code). To my surprise, superliminal.RTree is more quickly than boost.geometry.index.rtree. Environment settings add…
zadecn
  • 169
  • 1
  • 8
9
votes
1 answer

Any R-Tree implementation in F# (or C#)?

Possible Duplicate: Is there any documented free R-Tree implementation for .NET? Are there any R-Tree implementations in F#? Assumptions are: no need for insertion or deletion, fixed set of Geo-Fences (regions). Needs are: very fast search…
Kaveh Shahbazian
  • 13,088
  • 13
  • 80
  • 139
9
votes
3 answers

efficient way to handle 2d line segments

I am having huge set of 2D line segments. So, I know; Line number, Begin (X,Y,Z) and End (x,Y,Z) of each line segment. I want to get proximity line segments for a given line segment. Likewise for all. To find the proximity I can apply this If I…
gnp
  • 257
  • 3
  • 8
8
votes
3 answers

how to construct a RTree using given data points

I need to construct a R tree using given data points.I have searched for implementation of R tree.All the implementation i found construct r tree when given coordinates of rectangle as input.I need to construct r tree when given data points…
rajsekhar
  • 403
  • 1
  • 5
  • 14
8
votes
5 answers

Efficient nearest neighbour search in Scala

Let this coordinates class with the Euclidean distance, case class coord(x: Double, y: Double) { def dist(c: coord) = Math.sqrt( Math.pow(x-c.x, 2) + Math.pow(y-c.y, 2) ) } and let a grid of coordinates, for instance val grid = (1 to 25).map {_…
elm
  • 20,117
  • 14
  • 67
  • 113
7
votes
2 answers

TopologicalError: The operation 'GEOSIntersection_r' could not be performed

Hi Guys, I am trying to map the district shapefile into assembly constituencies. I have shape files for Both.Basically I have to map all the variables given at district level in census data to assembly constituency level. So I am following a pycon…
jatin rajani
  • 495
  • 1
  • 6
  • 15
1
2 3
…
17 18