Sign in to follow this  
Steedie

Jarvis March

Recommended Posts

Hey guys Does anyone know any good tutorials online or code samples for a Jarvis March algorithm? Need to start looking at how to use it but dont know where to start, I understand the basic idea of it, but turning it into code is where I struggle Cheers EDIT - In C++ is possible :)

Share this post


Link to post
Share on other sites
The wikipedia entry has pseudocode and an explanation. If you're studying convex hull algorithms, you should be able to churn c++ (or whatever you're using) code from pseudocode :-).

EDIT:

Err, reading over the pseudocode:

def jarvis(P)
i = 0
p[0] = leftmost point of P
do
p[i+1] = point such that all other points in P are to the
right of the line p[i]p[i+1]
i = i + 1
while p[i] != p[0]
return p


I guess the hard part is kind of lumped into one line hehe. To determine whether point C is "to the right" of the line formed by points A and B, I think you can just compute the cross product AB x BC and check if it's positive (you'll have to read up on it, I might have it backwards - and it depends on your coordinate system as well).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this