Jarvis March
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 :)
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:
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).
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 pp[i+1] i = i + 1 while p != 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).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement