I have 2D point sets that surround a shape which is convex or close to convex. The picture below shows you two examples.
I am looking for a simple procedure to construct a polygon that fills the inside.
I know about Alpha shapes, but I am looking for something simpler as I have to fully implement from scratch.
Any suggestion ?
]1
In answer to question meowgoesthedog mentioned I suggested Delaunay triangulation. I still think it can work :-) For triangle that doesn't have sides of similar length, triangulation guaranties empty space on the other side of longer sides. For triangle with sides a << b ~ c, there is an empty space on sides b and c with radius ~b/2. For triangle a + b ~ c, there is an empty space on side c of radius ~c/2. Triangles of first type will connect opposite points of your shape, and triangles of second type will connect corner points of your shape.
Similar approach, but with smaller degree of certainty, can be to choose some 'small' length, create planar graph of input nodes where edges are between nodes that are closer than given length, and find longest closed cycle traversing edges in positive direction and that cycle is positively oriented (not outer shape). Graph can be constructed parallel by constructing space partition for input nodes. Node to start traversing is for sure one with large angle. Probably few nodes has to be checked.
One problem in this approach is construction of planar graph, edge intersections has to be checked. That can be done cheap since partition is used. Other is that tolerance defines result shape. Smaller tolerance will produce smaller features or maybe some points that are in shape will be omitted. Larger tolerance makes graph larger and filters smaller features.
Both of these problems are 'solved' with Delaunay triangulation.
