# Thread: Finding the closest point in a list of points

1. Member 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> ();
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();
}
}

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);
}
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 08:28 AM.  Reply With Quote

2. Member Join Date
Nov 2009
Posts
18
Rep Power
0

## bump?
please this has been driving me crazy  Reply With Quote

3. Moderator   Join Date
Feb 2009
Location
New Zealand
Posts
4,716
Rep Power
18

## 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 08:58 AM.  Reply With Quote

4. Member 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  Reply With Quote

5. ## 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  Reply With Quote

6. Member 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  Reply With Quote

7. ##  Originally Posted by 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
Read the API documentation for the Comparator interface or the Comparable interface.

kind regards,

Jos  Reply With Quote

8. Member 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());;
}
});

}```
its giving me this error:
Cannot invoke compareTo(double) on the primitive type double
Last edited by sAntA199; 12-13-2009 at 03:06 AM.  Reply With Quote

9. ##  Originally Posted by 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

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  Reply With Quote

#### Posting Permissions

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