How do I calculate a bounding polygon?

Question

I have a cloud of 2D points and I would like to calculate the perimeter of a polygon which encompasses all of them.

Is there a name for this mathematical process which I can Google or can someone tell me how to start thinking about the problem, please?

Answer 1

You're probably looking for the convex hull and for convex hull algorithms.

One of the simplest 2D algorithms is the Gift wrapping algorithm. To quote Wikipedia:

It has O(nh) time complexity, where n is the number of points and h is the number of points on the convex hull. Its real-life performance compared with other convex hull algorithms is favorable when n is small or h is expected to be very small with respect to n. In general cases the algorithm is outperformed by many others.

So depending on the size of your problem, you might need to take a look on the algorithms page linked above in order to find more advanced approaches.

Answer 2

One well-defined such polygon is the convex hull. There are several well-studied algorithms for finding convex hulls.