This content has been marked as final.
Show 12 replies

1. Re: jarvis march with ArrayList
796262 Dec 3, 2009 7:49 AM (in response to 843853)konos5 wrote:
When do you need it by? What have you tried? How much are you willing to pay?
Hi everyone,
I am looking for a java implementation of the jarvis march algorithm a.k.a "gift  wrapping algorithm".
I 've searched the web but a couple implementations I found, are just too complicated for my level.
I just need the simplest implementation available where I will be giving an input of an ArrayList of Points and
I'll be getting an ArrayList back with the points ordered in proper sequence.
Thank you for your time.
Edited by: konos5 on Dec 2, 2009 10:34 PM 
2. Re: jarvis march with ArrayList
800282 Dec 3, 2009 7:51 AM (in response to 796262)Paying someone a whole 10 dukes to make it for him or her, that's what the OP tried. 
3. Re: jarvis march with ArrayList
843853 Dec 3, 2009 8:49 AM (in response to 800282)That't what I've managed to do so far...
I am actually trying to "translate" wikipedia's pseucode but with no luck so far...
Any help would be really appreciated...
import java.awt.*; import java.util.*; public class pureJarvis { public static void jarvisPolygon(ArrayList<Point> input) { int endPoint, pointOnHull; ArrayList<Integer> xPoints = new ArrayList<Integer>(); //2 new arrayLists that contain the x and y coordinates of ArrayList<Integer> yPoints = new ArrayList<Integer>(); //the input points seperately for (int i=0; i<sorted.size(); i++) //assigning the values... { xPoints.add(input.get(i).x); yPoints.add(input.get(i).y); } Collections.sort(yPoints); //Sorting so that I can get the lowest y Point at index 0 of the arrayList pointOnHull = (int)yPoints.get(0); //which I assign to the variable pointOnHull (but I am not sure) for (int i=1; i<yPoints.size(); i++) {} }

4. Re: jarvis march with ArrayList
796262 Dec 3, 2009 8:56 AM (in response to 843853)konos5 wrote:
If I were you, I wouldn't bother trying to translate anybody else's pseudocode (or real code, for that matter). Write down, in your own words, what you want to do. Split it up into steps, and then focus on translating those small steps into java. Ask specific questions when you get stuck.
That't what I've managed to do so far...
I am actually trying to "translate" wikipedia's pseucode but with no luck so far...
Any help would be really appreciated... 
5. Re: jarvis march with ArrayList
843853 Dec 3, 2009 9:07 AM (in response to 796262)I am trying to translate the pseudocode because the solution is based on a known algorithm and
I don't believe I need to "reinvent the wheel" for that matter...
Anyway, my problem lies in the second "for loop" (2 posts above) where I have to compare the lowest point(lowest y value or index 0 of the yPoints ArrayList)
with all the others. I am not sure how I should go about it.... 
6. Re: jarvis march with ArrayList
796262 Dec 3, 2009 9:24 AM (in response to 843853)konos5 wrote:
Sure, but if you don't understand how the wheel works, doesn't that defeat the purpose of the homework assignment?
I am trying to translate the pseudocode because the solution is based on a known algorithm and
I don't believe I need to "reinvent the wheel" for that matter...
Anyway, my problem lies in the second "for loop" (2 posts above) where I have to compare the lowest point(lowest y value or index 0 of the yPoints ArrayList)
My advice stands. Break what you're trying to do into steps, written down in your own words. What's your question?
with all the others. I am not sure how I should go about it.... 
7. Re: jarvis march with ArrayList
843853 Dec 3, 2009 10:23 AM (in response to 796262)Allright...
the main problem is:
How do I compare the polar angle that the lowest y Point
forms with every candidate point in the hull?yPoint.get(0);
that's actually my main problem...can't get any clearer than that.... 
8. Re: jarvis march with ArrayList
796262 Dec 3, 2009 10:29 AM (in response to 843853)konos5 wrote:
Well you could loop through them (which is what I think your intent is), but I suppose it depends on what exactly you want to learn from the comparisons. You've already found the lowest value, why do you need to compare that to every other value?
Allright...
the main problem is:
How do I compare the polar angle that the lowest y Point
forms with every candidate point in the hull?yPoint.get(0);
that's actually my main problem...can't get any clearer than that....
PS Not sure if it matters, but when you sort your List of Y values, that means they no longer pair with the List of X values. If you wanted to keep the coordinate pairs together, you might want to use a custom comparator with a List of Points. 
9. Re: jarvis march with ArrayList
843853 Dec 3, 2009 11:15 AM (in response to 796262)Point taken...
BUT
I have the value of the point with the lowest y value...right?
if I start comparing the polar angle it forms with every other Point in my hull with respect to x axis,
then by looping through my points I can get back the points that compose the convex hull, which is my main goal.
*Just for the record:
1)This is not some kind of coursework but rather a passion for knowledge...
2)I believe I already know how the wheel works and what it's used for ...I just don't know which components to use in order to build one...
P.S You must be right about the Y and X points splitting them up...but for now I just need their y ordering...
Can I use a tangent to calculate angles? And if yes, how? 
10. Re: jarvis march with ArrayList
796262 Dec 3, 2009 11:47 AM (in response to 843853)konos5 wrote:
Technically, you have the value of the lowest Y value. You have no way of knowing where that point is because you lost the corresponding X value.
Point taken...
BUT
I have the value of the point with the lowest y value...right?
if I start comparing the polar angle it forms with every other Point in my hull with respect to x axis,
How do you plan to do that with only one value? Don't you need both an X and a Y to find an angle?
then by looping through my points I can get back the points that compose the convex hull, which is my main goal.
Just for the record:
Well that's good, but trying to learn won't get you far if you bite off more than you can chew. It's better to start small and work your way up than to start large and become frustrated.
1)This is not some kind of coursework but rather a passion for knowledge...
2)I believe I already know how the wheel works and what it's used for ...I just don't know which components to use in order to build one...
Haha fair enough. But if your goal is to learn which components to use, I'd suggest building your own wheel at least once :)
P.S You must be right about the Y and X points splitting them up...but for now I just need their y ordering...
You have their Y ordering. But for the next step, don't you need both values?
Can I use a tangent to calculate angles? And if yes, how?
You can use trig to calculate angles, but not without having an X and a Y value. 
11. Re: jarvis march with ArrayList
843853 Dec 5, 2009 4:53 AM (in response to 796262)Problem solved I think...
Used Graham scan instead...
even though a bit more complicated...its implementation was much easier...
An excellent implementation can be found here:
http://www.thinkatorium.com/index.php?n=Main.AlgorithmsAssignment4
Thanks everyone for your time 
12. Re: jarvis march with ArrayList
843853 Dec 5, 2009 4:55 AM (in response to 843853)problem solved using graham scan instead...