Jan 17, 2010

Imagine a grid of 16x16. All points are integers, there will be no partial points.I have a list of points that fall somewhere on that grid. Since each point is has an integer x,y coordinate, there can be a maximum of 256 points, but normally there will be considerably less than that.What I am trying to do is take a new point N and find the closest point to it in my list of points. The brute force approach is to use the Pythagorean theorem to find the absolute distance from each point on the list to N, and the minimum of all those distances would give me the closest point. However, since there could easily be 100 points, or so, and there is a real advantage to speed in this case, I am looking for a faster way to do this.

The first thing I thought of would be to divide the grid into four quadrants of 8x8. I could then quickly determine which quadrant N was in, and I was able to pre-compute which quadrant each of the points on the list was in. Therefore, I could easily narrow the search down to the points in the same quadrant as N, but that is invalid. If N lies near the boundary of a quadrant, the closest point might not actually be in the same quadrant as N.So what I am looking for is a way to search a list of X,Y points to quickly find the point closest to some other point N. The fact that the search area is 16x16 might help. A certain amount of pre-computation can be done on the points in the list if it helps, but N can fall anywhere in the grid.

View 28 Replies
View Related