For the past few months the Homeflow development team has been spring cleaning the mapping system to provide our clients with blisteringly quick and highly customisable maps with a brand new feature, Draw a Map!
You can read about it (and watch a video) on how it works here (and you might want to start with that article first) as this article is really about the underlying technology behind it.
Until recently, we’ve been using the Google Maps API; which, while functional, contains a lot of overhead and is difficult to extend and customise. We instead decided to go the open source route and embrace leaflet.js as our mapping system alongside OSM tiling for the visuals (MapBox custom tiling coming soon!).
On websites that have this software activated, it is possible to freehand draw a shape around any area in the UK, edit it to perfection and search for properties that match your requirements in your desired area. The figure below illustrates this on Radarhomes, a Homeflow powered portal. As you can see, I quite like the East of Brighton.
The ease of use and speed of the tool shrouds the complexity under the hood. Our new developer, former physicist and numerical algorithm enthusiast, Jack Roberts, developed a concave hull algorithm for the software. For those who aren’t maths inclined, here’s a quick outline of what goes on.
1) Using the HTML5 canvas element, we allow the user to draw any set of points they wish. These points, which are taken from the mouse event registers, are then passed into the main point crunching algorithm, known affectionately as Hull.
2) Using the Ramer-Douglas-Peucker algorithm, we then strip the points down. This removes a lot of computational overhead in the later calculation while still preserving the drawn shape and runs in O(n ln n) time.
3) This filtered set of points then gets thrown into our Delaunay Triangulator. This sub-algorithm produces a set of non-intersecting triangles that connect all points in the set. Most of the computational overhead comes from this step, which is worst case O(n2) but for most use cases is nearer O(n ln n).
4) Now we have what’s known as a ‘Convex Hull’, a blob that contains all our points that loses all our interior detail. We then go about the shape, edge, by edge, working out which lines are longer than a variable we determine from the length of all the edges. This then returns the alpha shape, which looks like the shape we started with but it’s not quite! The interior edges will be double counted, so we once more do a sweep through the lattice and remove the duplicates and return the final set of points. This our concave hull. The processing time for this is somewhere between O(n ln n) and O(n2) depending on the point set.
5) The final step, which can’t be illustrated, is the server call to Ctesius, who is the greek God of property and also our property handling application. By feeding the boundaries of these drawn areas to Ctesius, we can return custom pins on the location of all properties that match your search.
I imagine that if you’re still reading at this point, you’re wondering why, for the example given, would we need such an overkill algorithm to reproduce a C shape? Surely, we could just thin out the points and return them in step two?
You’re officially Not Wrong™ and for a lot of use cases, this algorithm is overkill. But we like a good bit of maths and we like to try and cover all possible use cases. Since our software is facing outwards to the web, we want to cater for all people irrespective of what shape they wish to draw. So if someone draws this:
Our algorithm gets rid of all the rubbish on the inside and produces this:
For those stats inclined, the execution time for the concave hull algorithm, drawing a simple shape over Brighton, on my 11″ Macbook Air running the latest Chrome build is 27.5ms.