Easily storing and retrieving objects based on coordinates requires a geometry spatial-capable storage solution. But what do we do when our storage solution doesn't support spatial index?
In this post I describe one possible solution that permits developers to store and retrieve geo-data information in a table (like Azure table) or in memory (hash/dictionary or any key/value data structure).
This approach divides our area, world, or canvas to grids (or buckets) such that each bucket gets a unique key that can be used as the grid ID indexed in our storage.
For example let us imagine that we divide a space into buckets each of which is 30 meters long and 30 meters wide. All objects in this space are mapped to a bucket Id. The exact coordinates of each object should also be stored as part of the object’s properties. These precise coordinates can later be used to determine the object’s exact location and, second, to filter objects when querying all objects within a specific rectangular or circular area.
One of the benefits of using this approach is that solutions such as Azure Table cost less than spatial-capable storage solution like SQL and MySQL. Of course this approach comes with a "cost" that filtering and additional computation is needed on the client side.
If you're using Node.js, the spatial-mapping module used in this post can help you map objects to buckets very easily. Otherwise, implementing this mapping logic in other languages should still be fairly straightforward.
For example, let’s consider Azure table storage. In Azure table all rows require a cluster key and row key. Accordingly if you assign the bucket ID as the cluster key and the object ID as the row key it’s therefore possible to query all objects with a specific cluster key and receive all objects within a bucket. An additional advantage of this setup is that all objects within the same bucket will also be stored in the same storage node. By default Azure stores all objects with same cluster ID within the same storage node.
Getting all users in a specific area (rectangle or a circle) should be done by finding the bucket ids of all buckets inside this area (whole grid or part of it). Then, on the client side, we can apply a filter function to filter objects that are not in the specific area we're interested in by using a simple mathematical condition.