Engineering

Map search too square for you? Draw a polygon around your favorite neighborhood

Alex Hill Aug 10, 2018 • 3 min read

Here at ZapLabs, location and mapping data is central to much of our work within front- end, consumer-facing applications. Rich geographical data is not only helpful, but necessary, for providing the deep level of context needed to make a home buying decision. Anything which allows a potential home buyer to perform a more personal, customized home search will undoubtedly improve their experience. 

To this end, we’ve been making a multitude of improvements to our consumer map search experience. A recent update for our mobile website allows users to draw a custom polygon on their map search to match any arbitrary shape, allowing for highly specific, neighborhood-level home searches. Implementing this feature presented a few challenges; in this post, I’ll go over a few of the technologies we leveraged to make our lives easier.

In order to perform a home search, we must first convert a continuous, analog input of screen-drawn coordinates to a single enclosed polygon of latitude/longitude points which our back-end system can make sense of. The naive approach of simply aggregating all the points collected, and then drawing lines between them, would be far too unpredictable and inefficient given the possible range of user input. We needed a means of filtering out the “noise” and returning a minimum set of points which will create a complete polygon enclosing the drawn area.

First, we needed to collect a buffer of drawn points to analyze. However, simply accepting every input from a continuous stream would be far too burdensome for mobile device performance. So, as each “draw event” is fired, it gets filtered through a simple point-distance formula function (Fig. 1), which drops any points that were too close to the previous one by an arbitrary amount.

Once we have a manageable buffer of draw events (each with an associated screen-space XY value), the question is, how do we now build a polygon? The answer? Concave hulls!

A concave hull is a geometrical tool which simply determines the minimum set of points that enclose a given a set of points. This contrasts with a “convex” hull, which is simply the set of outermost points (Fig. 2).  Essentially, it is how we can find the “shrink-wrapped” outline of a set of points; just what we need to generate a manageable polygon.

Concaveman is an open source JavaScript library published by MapBox to do just this. The API is a single function, where we hand over an array of XY points and get back a concave hull of XY points. The library itself is based on a recent paper by Jin-Seo Park et. al., “A New Concave Hull Algorithm and Concaveness Measure for n-dimensional Datasets”, although it improves on their performance in a few areas.

So now that we have our filtered buffer of draw events with associated XY screen coordinates, we can feed those into Concaveman like such:

The result is our simplified polygon, perfectly inscribed within the user’s drawn points. From here, we convert these points from screen space XY coordinates, to latitude/longitude coordinates for display as a Google Maps polygon. Fortunately, the Google Maps API provides great utility functions to do just that. Once things are converted to latitude/longitude, it’s just a matter of adding a polygon layer based on those vectors to the map and sending the back-end service request.

 

In all, the process works really well for real-time usage, and the result is a snappy, fun search experience that allows users to make highly customized home searches that map to the neighborhood of their dreams.

Alex Hill

Alex is a Front End Engineer at ZapLabs. He has worked on software projects across a wide range of industries, from online dating to travel. You can generally find him spending way too much time on Hacker News, or attending a local JavaScript meetup.