Detecting "concave hull" on map image – Photoshop

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?