0
$\begingroup$

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:

enter image description here

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();
}
$\endgroup$
3
  • $\begingroup$ You're looking for the 2D Convex hull algorithm. $\endgroup$
    – Ed Pegg
    Apr 22, 2013 at 23:29
  • $\begingroup$ Would you be able to give some example math? $\endgroup$
    – FabianCook
    Apr 22, 2013 at 23:54
  • $\begingroup$ Try the Graham scan algorithm. You can find code for it all over the web (and via that Wikipedia link). $\endgroup$ Apr 23, 2013 at 0:34

1 Answer 1

1
$\begingroup$

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:

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .