I have a list of coordinates, I need to find the bounds of the points as in a shape where all the points fit into, this shape can be any type of 2D shape (I only have (x, y) no z), as in lets say I have these points:
1, 1
2, 2
5, 7
5, 5
3, 2
10, 2
1, 3
8, 1
It would create the shape:
Sorry about the fuzzy picture. Was drawn on an html canvas.
The bounds of this would be:
1, 1
8, 1
10, 2
5, 7
1, 3
What would be an algorithm to get this list and then sort it in a way where I can draw it, for example, how it is above, it is sorted so I can go clockwise around the shape.
I eventually used this code to figure it out (C#)
public static Vertex[] ConvexHull(Vertex[] points)
{
Vertex[] clean = RemoveDuplicates(points);
if (clean .Length < 3)
throw new ArgumentException("At least 3 dissimilar points reqired", "points");
if (clean .Length == 3)
{
//This is the hull
return clean;
}
List<Vertex> hull = new List<Vertex>();
// get leftmost point
Vertex P = clean.Where(p => p.X == clean.Min(min => min.X)).First();
Vertex E;
do
{
hull.Add(P);
E = clean[0];
for (int i = 1; i < clean.Length; i++)
{
//Going around anti-clockwise get everything that points left
if ((P == E) || (Orientation(P, E, clean[i]) == -1))
{
E = clean[i];
}
}
P = E;
}
while (E != hull[0]);
return hull.ToArray();
}
The problem you describe is that of finding the convex hull of a set of points. There are a number of well-known algorithms for this problem, differing in their time complexity, their numeric stability and their flexibility with respect to input shapes other than points, as well as their implementation complexity.
The printed version of the Algorithm Design Manual by Skiena has a list as well as hints to help you choose. Unfortunately this is not included in the online version. Nevertheless, here is an (incomplete) list of possible algorithms: