Doing Map Selections Using a Quadtree

     

My methodology to building products is:

I find the faster you can get feedback the faster you can figure out if your hypothesis is correct. The hypothesis being, “my solution solves the problem, and it’s worth building”.

It’s often better not to work on a doomed idea for years and years. Even if the MVP idea doesn’t work out, there will always be some lessons you can learn from them. This post is about one of those cool tricks that worked out well, but the idea surrounding it might take too long to be profitable (for us).

Without giving away the idea too much we were building a product that would let the Australian Government pick a set of properties in a particular area, and then communicate with the owners of those properties.

For the demo we wanted the user to be able to select an area on a map and list the properties within that selection. After a bit of searching, we found some data sets that had the geospatial data we needed. We just needed a way to select and filter. We found a number of tools that let you draw a region on a map, (we used leaflet.js); however, we couldn’t find anything simple that let you query a map layer (for lack of a better term).

The end result, and what we were going for, is shown in this video:

Using Leaflet we could get the selection coordinates, but we still needed a way to use those values to filter to the properties within that region. We had the coordinates of all the properties we wanted to be able to select from, but we needed a way to retrieve them.

Our little MVP was using an sqlite database since we didn’t want to build out a whole supporting infrastructure for a demo. And while sqlite had geospatial capabilities, you have to compile it into sqlite yourself, and we didn’t want to bother with a custom build just for a demo.

📓 Side Note: If you are doing this for a production app, you might want to look into something like PostGIS.

To get our demo ready, I put on my video-game hat, and made a simple QuadTree that used the properties coordinates to split up the space with the property Id as a payload. Then, it was just a matter of taking the leaflet selection coordinates and using that as a query rectangle in the quad tree. Anything with in that region should be close to the selection. It over selects because it’s using an axis aligned bounding box - akin to the broad phase of a collision detection system - but it can easily be improved… but this is just an MVP so let’s not go crazy.

I am not going into the code too much here, as it’s really is just a basic quad tree with a rectangular selection. The only bit that tripped us up was that it was much easier to visualise and conceptualise the quad tree by normalising the latitude and longitude coordinates into 0-360 and 0-180. Like in the following picture:

lat/long to quad tree

We’ve done the demo, and the people we were showing it to quite liked it. However, it turns out trying to get a product into a government takes a long time and requires a lot of effort - who knew? So we’ve pivoted to another idea entirely, but this was just so much fun to build I just had to write about it.

Also, if you are looking for something that selects properties on a map, or you work for the Australian Government and can fast track things, drop me a line 🕶️.