Finding the closest point in a list of points

[sAntA199]

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?

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;
	   }

[sAntA199]

bump?
please this has been driving me crazy

[pbrockway2]

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.

[sAntA199]

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

[JosAH]

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

[sAntA199]

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

[JosAH]

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

[sAntA199]

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

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

[JosAH]

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

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:

double y1= ((City)o1).getY();
double y2= ((City)o2).getY();

return (y1 < y2)?-1:(y1 > y2)?1:0;

kind regards,

Jos