Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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
add comment

1 Answer

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
add comment

Your Answer

 
discard

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.