Search code examples
image-processinggraphics2dpolygonpoint

Best polygon fitting into points

I'm looking for an algorithm to find a polygon that can represent a set of points in 2D space. Specifically, if given a set of points like this

enter image description here

It should ideally produce something similar to this:

enter image description here

(The arrows are segments)

Basically, the output would be a set of segments that "best" address the features of the points. The algorithms possibly take some parameters to control the numbers of output segments.

I currently do not have any ideas on what algorithms I'm looking for. Any papers or advice are appreciated.

Solution

  • This is a possible algorithm.

    For every point, look at the 2 points closest to it, they become connected. Then use Douglas Peucker to refine the edges.

    Essentially you will create a first polygon containing all the points, and the try to eliminate points whose elimination doesn't change the shape too much.