Points reconstruction

Question

I would like to ask about one idea that I had and I haven't figured out the solution, my idea is about:

Having a set of GPS coordinates point, which are covered by a rectangle, how to connect those points according to its shape, as I tried Quick Hull to connect those points, it formed a convex and it was not my expected result, my expectation is such as we have a set of points that follow a 'L' letter shape, so that if we connect them, we can have a 'L' shape.

I tried the voronoi and delaunay but still haven't got a good result!!

Thank you for helping me to figure a good solution for this.

Really appriciated!

Thanks everyone

Answer 1

I think the 2D "Alpha shapes" algorithm would the right choice for you.

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Alpha_shapes_2/Chapter_main.html

Alpha shapes can be considered as a generalization for the "convex Hull" algorithm that allows for generation of more general shapes.

By using alpha shapes you will be having control over the level of details to be captured by the resultant shape by changing the alpha parameter value.

You can try the java applet here : http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html

to have better understanding about does this algorithm do.