I understand the concept of an R-Tree and how it is used to spatially index and store geometric objects such as polygons and points, but I am not sure how to construct it by choosing MBRs that group the actual objects.

What do I mean by "MBRs that group the actual objects"? For example, this image shows a set of MBRs as nodes (R1 through R7). Though I am not sure how one would have programmatically chosen those bounds to represent those regions?

The R-Tree is the ideal structure for my problem of locating intersecting polygon objects, but my current method is the brute force O(n^2) like so:

for p1 in polygons: # O(n)
    for p2 in polygons: # O(n)
        if p2 is not p1: # O(1)
            if p2.intersects(p1): # O(1); computed using DeMorgans law on vertices
                # do stuff

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.