Jarvis March

Recommended Posts

Steedie    122
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 on other sites
Replicon    306
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:

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).