Border points from point set

Question

I have an unordered set of two dimensional points, being the result of a image segmentation. The points when drawn together in a bitmap are a contigous region.

I'd like to know which points are in it's (region) border. The region might be concave, so this has ruled out Convex Hull to me. It also may have "holes" in it (ie. internal and external borders).

There's a good (> 10k) number of points. I tought about using a (non recursive) floodfill like search, adding the border points to a vector. This would also create me a problem to "separate" internal and external border points, if a internal border exists. Is there a better algorithm?

Answer 1

The problem is more complex than it seems. It is very nicely described in the link below, unfortunately without an algorithm. I hope this helps a little.
http://www.google.de/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0CEIQFjAB&url=http%3A%2F%2Fwww.geosensor.net%2Fpapers%2Fgalton06.GISCIENCE.ppt&ei=s4xdUf_BMqT-4QSmrICADw&usg=AFQjCNHKBdBDxQt9G29_l2QW2yd-AxRXXQ&bvm=bv.44770516,d.bGE