Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
up vote 2 down vote accepted

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

share|improve this answer
Thanks, that looks like it could be the solution! – Flyphe Jan 16 '13 at 9:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.