Outline plotting algorithm

Question

I've been given this task by my wife, so it's top priority :-)

I have a collection of points (actually Northings & Eastings, but it doesn't really matter). I want to take those points and create a set of vectors that represent the outline, so I can plot on Google earth.

So, something like:

  #                       #
           #             #       #
#             #    #
      #   #

            #

Would give:

  #-----------------------#--
 /                            \ --#
#                  #------------/
 \-----#         /
         \     /
            #

A possible solution I came up with, is to compute vectors between every point, and discard every vector that is overlapped by another vector. I haven't implemented this yet (not really sure how), but I wondered if there are other ways.

The algorithm only has to run a couple of times, so if it takes an hour per run and gigs of RAM it's not an issue.

Answer 1

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:

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

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.