Storing and filtering spatial data within RAM

Question

I'm trying to figure out what's the proper way of storing and filtering spatial data inside a running program.

I have a 2D map of theoretically infinite size. Users generate objects which are placed on the map, so infinite objects, theoretically.

I'm storing all this data inside an SQL database.

Whenever a user opens the map I fetch all of the objects within the rectangle they are viewing. When they move the map I subtract the already loaded rectangle from the new view box rectangle and fetch only the missing objects.

This is all fine until it gets to a point where there are a couple thousand objects cached in memory and I navigate the map to a place where I have all the objects loaded, but it takes a bunch of seconds to only go through the entire array of objects and determine which ones I need to draw - i.e. the ones within the current view box.

I'm pretty certain this problem has a name and is well known and solved, so as much as I loved to do that before I'd like to save some time and not reinvent the wheel, however I lack the terminology to help myself.

Answer 1

I see you found a library that seems to meet your needs but there are multiple options here.

The general structure here is called a spatial index. One the simplest and easiest to understand is called a quad-tree. You divide your space into 4 equal size sub-spaces and add those to the root. Then if any of the nodes contains more than some limit per node, that node is divided into 4 equal spaces and added to the parent node and so on and so forth.

This structure then allows much faster searching than iterating over list of points. There are other approaches and generalizations to this problem. The library you have chosen uses an R-Tree. This structure differs from a quad tree in a few ways. Significantly, for lookups, it allows overlapping nodes. This means you may have to search the space of more than one node whereas in the quad-tree, a given point will be in one and only one node.

The choice between different approaches in structure comes down to the way the data will be accessed. In your case, if you are always retrieving the data for constant size areas and objects are evenly distributed across the space, you might even want to just divide into tiles as described in the answer linked to in the first comment.