Detecting "concave hull" on map image

Question

I'm developing the open-source JavaScript plugin for Waze -- well-known free GPS navigator -- specifically for online editor. The idea of this userscript is to make it possible to quickly select large uniform colored map areas to convert them to landmarks.

So far I've successfully implemented the tool you would call "Magic Wand" in graphic editors like Photoshop: user clicks somewhere on the map (say, on the lake or forest) and script selects whole area covered by same color and creates a polygon for landmark.

Everything works great except that I am using convex hull algorithm to obtain the... well... convex hull :) That is: the polygon connecting the most outer points of the found points cloud.

But as everyone understand only few landmarks have a convex shape while most of real world objects have a polyline shape with concave areas. On the picture above you can see that the area has few sharp edges and a farmfield in the right bottom corner covered by convex hull -- that's wrong.

I was Googling for suitable algorithm and digging through math papers but still have no luck finding one. The most popular question about concave hulls here on Stackoverflow refers to Alpha-shapes along with Delaunay triangles. Though I don't understand how to use it in case: all points are connected to each other forming a continuous polyline thus it seems that I cannot find suitable alpha-radius as even circle with radius equal to 1 pixel with be alpha-exposed.

Any ideas how to archive the goal of building a concave hull will be much appreciated! May be I am moving in a wrong direction and need to look at bitmap vectorization algorithms?

Answer 1

You can read how to implement concave hull algorithm in this paper. The basic idea is to build the convex hull and flex (concave) edges inward. There is JavaScript implementation of this algorithm: hull.js.

Answer 2

Alpha shapes is defined by finding the delaunay triangulation of a set of points and then delete edges that exceed alpha. You need the delaunay triangulation but not the circles. It's also works with lines. To calculate the shape with JS you can use TopoJSON or try this answer:Calculate bounding polygon of alpha shape from the Delaunay triangulation. You can also try my php package http://concavehull.codeplex.com/.