Improving our contour algorithm

Last week we featured a tool for drawing contours which uses the Mapzen altitude API. We used a very simple algorithm called ‘Marching Squares’ that we found on Wikipedia. However, as GEB reader Боби Димитров pointed out in the comments, if you try to use too low a resolution altitude grid relative to the number of contours you want, you end up with something looking like abstract art:

The Marching Squares algorithm is remarkably simple. We just check every altitude from the grid obtained from the Mapzen API and colour it red or green based on whether it is above or below the altitude of the contour we wish to draw. Then we draw lines separating the two colours from the mid-points of the rectangles in the grid as shown below:

However, we realised that if between a red and green dot rather than using the mid-point, we check the altitudes of the points relative to our contour altitude and then use a point proportionally closer to the point closest to our contour altitude, we end up with a much better result:


All the settings were the same as the ‘abstract art’ sample above, except we used proportional ‘mid-points’ on our squares.

And best of all, it only required changing one line of code!

We have also tried smoothing out the contours using this open source code. It generally works well, but it tends to result in some unwanted loops, so we probably need to look for a different curve algorithm.

Our next step will be to use a different technique to access the elevation data from Mapzen, as suggested by them in the comments. If successful, it should allow much faster access to the elevation data – and thus higher resolutions will be possible.

The changes so far have been added as options in last week’s post.

About Timothy Whitehead

Timothy has been using Google Earth since 2004 when it was still called Keyhole before it was renamed Google Earth in 2005 and has been a huge fan ever since. He is a programmer working for Red Wing Aerobatx and lives in Cape Town, South Africa.






PLEASE NOTE: Google Earth Blog is no longer writing regular posts. As a result, we are not accepting new comments or questions about Google Earth. If you have a question, use the official Google Earth and Maps Forums or the Google Earth Community Forums.



PLEASE NOTE: Google Earth Blog is no longer writing regular posts. As a result, we are not accepting new comments or questions about Google Earth. If you have a question, use the official Google Earth and Maps Forums or the Google Earth Community Forums.