Results 1 to 9 of 9
 12092009, 08:21 PM #1Member
 Join Date
 Nov 2009
 Posts
 18
 Rep Power
 0
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; 12122009 at 08:28 AM.
 12122009, 08:29 AM #2Member
 Join Date
 Nov 2009
 Posts
 18
 Rep Power
 0
bump?
please this has been driving me crazy
 12122009, 08:55 AM #3Moderator
 Join Date
 Feb 2009
 Location
 New Zealand
 Posts
 4,585
 Rep Power
 12
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; 12122009 at 08:58 AM.
 12122009, 09:40 AM #4Member
 Join Date
 Nov 2009
 Posts
 18
 Rep Power
 0
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
 12122009, 12:04 PM #5
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,776
 Blog Entries
 7
 Rep Power
 21
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 ycoordinate in ascending order. Given a point x,y you can quickly find to ycoordinates 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(Yminy, Ymaxy) 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 ycoordinate.
kind regards,
Jos
 12122009, 09:27 PM #6Member
 Join Date
 Nov 2009
 Posts
 18
 Rep Power
 0
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
 12122009, 09:30 PM #7
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,776
 Blog Entries
 7
 Rep Power
 21
 12132009, 12:43 AM #8Member
 Join Date
 Nov 2009
 Posts
 18
 Rep Power
 0
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());; } }); }
Cannot invoke compareTo(double) on the primitive type doubleLast edited by sAntA199; 12132009 at 03:06 AM.
 12132009, 09:41 AM #9
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,776
 Blog Entries
 7
 Rep Power
 21
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;
Jos
Similar Threads

Finding the most repeated names in a list
By jboy in forum New To JavaReplies: 2Last Post: 09172009, 04:08 PM 
Finding objects in a list
By starwars in forum AWT / SwingReplies: 5Last Post: 09112009, 04:42 PM 
Finding distance from a point to a Rectangle2D.objecy
By busdude in forum New To JavaReplies: 0Last Post: 04022009, 10:00 PM 
help me in finding the entry points in the source code of java.....
By aks.nitw in forum Advanced JavaReplies: 0Last Post: 11252008, 10:24 AM 
given number of points(cordinates) , find max points lie on the same line ?
By Hayzam in forum New To JavaReplies: 2Last Post: 08242008, 01:30 AM
Bookmarks