Public Group

Jarvis March

This topic is 4064 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

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

• 17
• 11
• 12
• 9
• 49
• Forum Statistics

• Total Topics
631395
• Total Posts
2999758
×

Important Information

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!