Convex Hulls…No, Not Sailing
KODA had some fun this week playing around with Convex Hulls. It’s not a new idea for the spatial sciences, but it’s a new idea for KODA. It’s something that started as a quick and dirty way to find a 2-dimensional boundary around a cloud of points. It works great and is fast and stable.
In my opinion, it’s an awesome project for any budding programmer – especially those interested in spatial data. It involves some important fundamentals including floating point calculations, loops, array item swaps and sort algorithms. If you get something going don’t hesitate to send it through.
Who is Graham?
I’m not lucky enough to have anything named after me…yet. The Graham Scan however is named after Ronald Graham who worked for Bell Laboratories at the time (around 1972).
The algorithm finds the convex polygon around a set of points. Convex polygons are defined in a number of ways, but are often noted as shapes which have no internal angles greater than 180 degrees. For the mechanically minded - think of a rubber band stretched around a cluster of nails half-way hammered into a table.
The algorithm has been implemented by a number of programmers already, but it was nice to do it for ourselves. It’s a far better to understand the nuts and bolts of your code – rather than relying on an off the shelf DLL or something.
What’s the catch...? No, Not Fishing
The Graham Scan is very good at finding an overall convex polygon to summarize a cloud of points, but not so good when dealing with something that has concave detail. If you think about summarizing the coastline of Australia, the Graham Scan will draw a line directly from the south-western tip of Western Australia all the way to the southern tip of Tasmania – compare the red and green lines below.
Courtesy of Google Maps
A few cool ideas have started to seem more tangible since we started playing around with hulls. So, one of the next steps for KODA is to develop some enhanced versions of the scan that will intelligently transform the convex hull from the Graham Scan into a more meaningful concave hull. Maybe we’ll work out how to find a good concave hull directly…
Finally, next week’s blog post will have some exciting news. Can’t wait to share it with you – so stay tuned.
Please like, share, follow and we look forward to comments.
Until next time, KODA