# Creating bounds of a shape

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
{
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();
}

• You're looking for the 2D Convex hull algorithm. Apr 22, 2013 at 23:29
• Would you be able to give some example math? Apr 22, 2013 at 23:54
• Try the Graham scan algorithm. You can find code for it all over the web (and via that Wikipedia link). Apr 23, 2013 at 0:34