12 Replies Latest reply: Dec 5, 2009 4:55 AM by 843853 RSS

    jarvis march with ArrayList

    843853
      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
        • 1. Re: jarvis march with ArrayList
          796262
          konos5 wrote:
          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
          When do you need it by? What have you tried? How much are you willing to pay?
          • 2. Re: jarvis march with ArrayList
            800282
            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
              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
                konos5 wrote:
                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...
                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.
                • 5. Re: jarvis march with ArrayList
                  843853
                  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
                    konos5 wrote:
                    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...
                    Sure, but if you don't understand how the wheel works, doesn't that defeat the purpose of the homework assignment?
                    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....
                    My advice stands. Break what you're trying to do into steps, written down in your own words. What's your question?
                    • 7. Re: jarvis march with ArrayList
                      843853
                      Allright...
                      the main problem is:

                      How do I compare the polar angle that the lowest y Point
                      yPoint.get(0);
                      forms with every candidate point in the hull?

                      that's actually my main problem...can't get any clearer than that....
                      • 8. Re: jarvis march with ArrayList
                        796262
                        konos5 wrote:
                        Allright...
                        the main problem is:

                        How do I compare the polar angle that the lowest y Point
                        yPoint.get(0);
                        forms with every candidate point in the hull?

                        that's actually my main problem...can't get any clearer than that....
                        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?

                        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
                          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
                            konos5 wrote:
                            Point taken...
                            BUT
                            I have the value of the point with the lowest y value...right?
                            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.
                            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.
                            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?
                            Just for the record:
                            1)This is not some kind of coursework but rather a passion for knowledge...
                            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.
                            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
                              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
                                problem solved using graham scan instead...