Dynamic closest elements

Question

Hi,

I have a 2D surface ( Grid ) with 50 elements at different locations. I need to decide which are the 10 closest elements to a given point.

In addition, the given point is constantly moving and i need to do the calculation on each movement.

I know I can calculate the Euclidean distance to each point on each movement, but I want a faster way.

Thanks.

Answer 1

So, I am going to put all the attempts that I went over to figure out my implementation and hopefully you will be able to figure out the best approach for you project.

I am working on somewhat similar project to what you have mentioned. But in my case I need to do extra cycles once I found the points within a given distance threshold. I have tried few iterations, first I started by creating a distance grid. Keep in mind, I am not working on 2D surface but I don't think changing this to 2D will take much work.

Here is how I developed my distance grid (its so simple even a cave man can do it, I making fun of myself) , Also keep in mind I didn't continue using the grid to finish up my implementation.

public double[][] distanceGrid() {
 double[] gridSize = combineArrays(generateClusters(1, 3), generateClusters(12, 15));
 double [][] pointsDistanceGrid = new double[gridSize.length][gridSize.length];
 for (int i = 0; i < pointsDistanceGrid.length; i++) {
  for (int j = 0; j < pointsDistanceGrid[i].length; j++) {
   pointsDistanceGrid[i][j] = Math.abs(gridSize[i] - gridSize[j] );
   System.out.print(" " + pointsDistanceGrid[i][j]);
  }
  System.out.println("");
 }

 return pointsDistanceGrid;
}

As I mentioned I didn't use it.

Since I had to deal with a distance threshold, and I decided before finding "The Nearest" i wanted to see all the points that are closer to the particular point that I am looking at, so I implemented this method.

/**
 * Given a point method returns an array with point that are within the limit of threshold.
 * @param point
 * @return
 */
public double[] pointsWithinThreshold(double point) {
 double[] neighbors = new double[bigCluster.length];
 for (int i = 0; i < bigCluster.length; i++) {
  if (bigCluster[i] != point) {
   double distance = 0;
   distance = Math.abs(point - bigCluster[i]);
   if (distance <= getDistanceThreshold()) {
    neighbors[i] = bigCluster[i];
   }
  }
 }
 return neighbors;
}

After this I realize I don't really care what are all the closest points so I end up not using this and refractor some of this functionalities to a method where I get the closest member and do recursive DFS.

Let me know if you would like to see that, I didn't put it here coz I thought you only need to know the closest 10 member.

Hope this helps and good luck.

Answer 2

It sounds like you're trying to come up with a way where you can take the 10 closest points at time t and use those to help you figure out the 10 closest at time t+1. Here's an idea to consider.

When you calculate the 10 closest points, also store the angular direction of where they are relative to your current location. Then, when you move you can calculate the direction in which you moved. Focus your search on the space that's opened up to you (think of a circle around point A and another around point B. The space in B but not in A is where you want to focus your search).

Of course, to do this you need to have some way of searching in a particular area of the grid instead of doing a linear search through an array of points to find those close to you. I'd recommend looking into BSP trees for that. If you're not doing it already, using BSP trees instead of linear search might alone be the performance boost you're looking for.