Results 1 to 9 of 9
  1. #1
    sAntA199 is offline Member
    Join Date
    Nov 2009
    Posts
    18
    Rep Power
    0

    Default Finding the closest point in a list of points

    so i have an arraylist of several different points on a hashmap. I want to find the closest point, and then the next closest, and so on, drawing a line between each one. Basically the traveling salesperson problem.

    Ive set this up but i cant really figure out what to do in getNextPoint()

    any help?

    Java Code:
    public static ArrayList<City> algo1 (ArrayList<City> cityList)
    	   {
    	       ArrayList<City> thisList = new ArrayList<City> ();
    	       thisList.addAll((ArrayList<City>)cityList);
    	       City tempPoint = null;
    	       double firstXValue = 600;
    	       
    	       
    	       for (int i = 0; i < cityList.size(); i++)
    	       {
    	           if (i < cityList.size()-1)
    	        	   tempPoint = new City(thisList.get(i).getX(), thisList.get(i).getY(), true);
    
    	           if (tempPoint.getX() < firstXValue)              // finds farthest left city
    	           {
    	               thePoint = thisList.get(i);
    	               firstXValue = thePoint.getX();
    	               thisList.get(i).removeCity();
    	           }
    	       }     
    
    	       goodList.add(thePoint);
    	       
    	       int limit = thisList.size() - 1;
    	       for (int i = 0; i < thisList.size(); i++)
    	       {
    	    	   thisList = onlyTrue(thisList);
    	    	   thePoint = thisList.get(0);
    	           City nextCity = getNextPoint(goodList.get(i), thisList);
    	           goodList.add(nextCity);
    	       }
    	       return goodList;
    	    }
    	
    	   private static ArrayList<City> onlyTrue(ArrayList<City> trueList)
    	   {
    		    for (int i = 0; i < trueList.size(); i++)
    		    {
    			    if (trueList.get(i).checkIt() == false)
    			    	trueList.remove(i);
    		    }
    		    return trueList;
    	   }
    
    	   private static City getNextPoint (City tempPoint, ArrayList<City> thisList)
    	   {
    	       double minDist = 1000000;
    	       Point2D firstCity = tempPoint;
    	       Point2D secondCity = null;
    	       for (int i = 0; i < thisList.size(); i++)
    	       {
    	                if (firstCity.distance(thisList.get(i)) < minDist)
    	                {
    	                    minDist = firstCity.distance(thisList.get(i));
    	                    secondCity = thisList.get(i);
    	                    thisList.get(i).removeCity();
    	                }
    	       }
    	       //totalWeight = totalWeight + minDist;    ////////////////////////////////////
    	       return (City)secondCity;
    	   }
    Last edited by sAntA199; 12-12-2009 at 07:28 AM.

  2. #2
    sAntA199 is offline Member
    Join Date
    Nov 2009
    Posts
    18
    Rep Power
    0

    Default

    bump?
    please this has been driving me crazy

  3. #3
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    i cant really figure out what to do in getNextPoint()

    You are trying to return the City in thisList which is closest to tempPoint, right? If so the general idea looks OK: check each city and if they are closer than anything seen so far make that city the "candidate" and, when all the cities have been checked return the candidate. This may not be the most efficient strategy, but it'll do.

    If you have a specific problem with the method, say what that is. You'll need to post code that compiles and runs. Say what behaviour you were expecting, and what behaviour you actually get. (Or if there is a compiler message, say what that is.)

    A few things stand out

    "static". Don't make it static. In fact don't make anything static, save a few lines in a main() method somewhere.

    100000000. Integer defines a MAX_VALUE whose use makes both the code clearer and more precise. Alternatively you could make the distance to the first city in the list the minDist.

    get(i). You call this three times - perhaps you could use a variable. Again, it might aid clarity.

    thisList.get(i).removeCity() Do you mean this? Does a City have really a removeCity() method? (sounds seditious). Or are you trying to remove the city from the list? If the latter, use the list's remove() method. But, better (I think), don't. Let the caller remove the city from the list if they want and let getNextPoint() just do one thing: find the nearest city.

    (City)secondCity;/secondCity = thisList.get(i); Really? secondCity is a Point2D. Maybe I'm missing something, but this looks like "faith based casting" - things which act as a point or a City as the spirit moves them.
    Last edited by pbrockway2; 12-12-2009 at 07:58 AM.

  4. #4
    sAntA199 is offline Member
    Join Date
    Nov 2009
    Posts
    18
    Rep Power
    0

    Default

    Ok well first of all City extends Point. the method removeCity sets a boolean value on the city object to false so it is removed in the onlyTrue() method.

    also, im trying to find the point closest to thePoint; tempPoint is just for finding the farthest left city


    right now the whole thing returns
    78, 326 as the first point, which is found when looking for the farthest left point, 156, 257 and 207, 306.
    there should be 7 points returned in this order:
    0 78, 326
    1 156, 257
    2 207, 306
    3 285, 365
    4 399, 194
    5 280, 143
    6 557, 132

    i can post more parts of the code if needed but im pretty sure that all my problems are coming from that part

  5. #5
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,386
    Blog Entries
    7
    Rep Power
    20

    Default

    If you're dealing with a lot of points there's a better method (it works for a few points as well but the computational overhead may be to large).

    Sort your points (I assume they're two dimensional points) according to their y-coordinate in ascending order. Given a point x,y you can quickly find to y-coordinates Ymin <= y <= Ymax. Find the minimum distance between those two points and your sample point (x, y), say the distance is M.

    if M <= min(|Ymin-y|, |Ymax-y|) you have found a point nearest to your sample point (x, y). Otherwise take two points, one next to the point (Xmax, Ymax) and one previous to (Xmin, Ymin) and repeat the step above. (finding those two points is just an index increment and decrement because of the sorted order of the y-coordinate.

    kind regards,

    Jos

  6. #6
    sAntA199 is offline Member
    Join Date
    Nov 2009
    Posts
    18
    Rep Power
    0

    Default

    im running into the same problem for sorting the points by there y coordinates as i was before in sorting the points in that I really just dont know how to do it

  7. #7
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,386
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by sAntA199 View Post
    im running into the same problem for sorting the points by there y coordinates as i was before in sorting the points in that I really just dont know how to do it
    Read the API documentation for the Comparator interface or the Comparable interface.

    kind regards,

    Jos

  8. #8
    sAntA199 is offline Member
    Join Date
    Nov 2009
    Posts
    18
    Rep Power
    0

    Default

    is this anywhere near correct?


    I was sick the week I would have learned sorting algorithms in class and it really shows. im trying to override the compare method so it works with the Citys

    Java Code:
    private static ArrayList<City> onlyTrueInOrder(ArrayList<City> trueList)
    	   {
    		    ArrayList<City> finalList = new ArrayList<City> ();
    		    for (int i = 0; i < trueList.size(); i++)
    			    if (trueList.get(i).checkIt() == false)
    			    	trueList.remove(i);
    //S		    int[] yS;
    //		    for (int i = 0; i < trueList.size(); i++)
    //		    	yS[i] = (int)trueList.get(i).getY();
    //		    Vector Y = new Vector();
    		    Collections.sort(trueList, new Comparator()
    		    {
    	            public int compare(Object o1, Object o2)
    	            {
    	            	City c1 = (City)o1;
    	            	City c2 = (City)o2;
    	            	return (int)c1.getY().compareTo(c2.getY());;
    	            }
    	            });
    		    
    	   }
    its giving me this error:
    Cannot invoke compareTo(double) on the primitive type double
    Last edited by sAntA199; 12-13-2009 at 02:06 AM.

  9. #9
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,386
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by sAntA199 View Post
    is this anywhere near correct?


    I was sick the week I would have learned sorting algorithms in class and it really shows. im trying to override the compare method so it works with the Citys

    Java Code:
    private static ArrayList<City> onlyTrueInOrder(ArrayList<City> trueList)
    	   {
    		    ArrayList<City> finalList = new ArrayList<City> ();
    		    for (int i = 0; i < trueList.size(); i++)
    			    if (trueList.get(i).checkIt() == false)
    			    	trueList.remove(i);
    //S		    int[] yS;
    //		    for (int i = 0; i < trueList.size(); i++)
    //		    	yS[i] = (int)trueList.get(i).getY();
    //		    Vector Y = new Vector();
    		    Collections.sort(trueList, new Comparator()
    		    {
    	            public int compare(Object o1, Object o2)
    	            {
    	            	City c1 = (City)o1;
    	            	City c2 = (City)o2;
    	            	return (int)c1.getY().compareTo(c2.getY());;
    	            }
    	            });
    		    
    	   }
    its giving me this error:
    Cannot invoke compareTo(double) on the primitive type double
    The method getY() returns a double; a double is a primitive type and primitives don't have methods; if you retrieve both the Y values from the two cities, you have to compare them using the ordinary comparison operators:

    Java Code:
    double y1= ((City)o1).getY();
    double y2= ((City)o2).getY();
    
    return (y1 < y2)?-1:(y1 > y2)?1:0;
    kind regards,

    Jos

Similar Threads

  1. Finding the most repeated names in a list
    By jboy in forum New To Java
    Replies: 2
    Last Post: 09-17-2009, 03:08 PM
  2. Finding objects in a list
    By starwars in forum AWT / Swing
    Replies: 5
    Last Post: 09-11-2009, 03:42 PM
  3. Replies: 0
    Last Post: 04-02-2009, 09:00 PM
  4. Replies: 0
    Last Post: 11-25-2008, 09:24 AM
  5. Replies: 2
    Last Post: 08-24-2008, 12:30 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •