Retrieve outer most points on a 2d graph

Question

G'day everyone,

I have a 2d graph which has some points plotted on it. What I need to do is get only the outer most points so that I can connect them up (isn't really relevant).

What I can't seem to wrap my head around is the algorithm that I need to use in order to do this?

---

I think this might help you understand what I want to achieve:

o o o
o x o
o o o

All the o's I want to get and the x I want to ignore. Also, the points can be in any position and any shape but I still want to only grab the outer most points.

Any ideas? Thanks.

Answer 1

You're probably looking for the Graham scan algorithm, a method for finding a convex hull of a set of points.