Outline plotting algorithm

Formulation of candidate polygons

It seems like what you're looking for a polygon such that

  • all of its vertices are in your point set
  • it contains every point in your point set

This defines a feasible set of candidate polygons with respect to your point set.

Convex Hull?

One objective function could be "Among these polygons, choose the one with the minimum number of vertices." That would be the convex hull of your point set. Other answers address that approach, so I won't say anything more about it.

Something more...

But that is not the only objective function you could choose. For example, you could instead have a trade-off between having fewer vertices, having less total area, and having less-sharp angles at vertices. I don't know of any existing named algorithms for that problem, but it's definitely an interesting one.

One approach could be to start by finding the convex hull, then "pull in" edges to interior vertices in the locations where the cost of the extra vertex is outweighed by the benefit of having less total area.

For example, this:

enter image description here

Would become this, by pulling in the edge along the top:

enter image description here

This second polygon might be a more "natural" fit for the point set, even though it is not the convex hull of the point set.


You're probably looking for the Convex Hull of the points; there are a variety of algorithms for finding that.