Jump to content
  • Advertisement
Sign in to follow this  

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.

If you intended to correct an error in the post then please contact us.

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


Err, reading over the pseudocode:

def jarvis(P)
i = 0
p[0] = leftmost point of P
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).

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

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

Sign me up!