0

I have put myself in a conundrum here, where I have 50 rects in one array and 50 rects in another. I need to find the two rects that are the closest to each other.

So I use this code:

for(int i=0;i<49;i++)
{
 for(int j=0;j<49;j++)
 {
  double distance = Math.sqrt(Math.pow(rectF1.get(i).centerX() - rectF2.get(j).centerX(), 2) 
                               + Math.pow(rectF1.get(i).centerY() - rectF2.get(j).centerY(), 2));
 }
}

It works but I have to check through 2500 times! And if the rects move (they do) then it's possible I won't catch the closest rects at the right moment! X.X

stegrd
  • 25
  • 6

1 Answers1

1

You seem to look base your search on the center of the rectangle. Thus you problem becomes a Nearest neighbour problem. To solve this, I would use a KD-Tree:

http://en.wikipedia.org/wiki/K-d_tree

For a java library look at KDTree Implementation in Java

Community
  • 1
  • 1
ruediste
  • 2,434
  • 1
  • 21
  • 30
  • Yes! Thank you! Is there somewhere I can learn all these datastructure types for java? I love learning :) – stegrd Jun 21 '14 at 09:05
  • The keyword here is "Datastructures and Algorithms". It is a fairly general subject, independent of the programming language. I had a lecture on it at university. But do some googling, you'll find a lot of material. – ruediste Jun 21 '14 at 09:08
  • I wonder if there is a faster algorithm to do this. Using this approach, we need index the second rectangle set using kdtree, which takes `O(m log m)`, where `m` is the size of the second set. Then, for each rectangle in the first set, find the nearest neighbor in the second set, which, in overall, takes `O(n log m)`, where `n` is the size of the first set. In total, this takes `O((n+m) log m)`. – fajarkoe Jun 21 '14 at 09:24
  • If the points are evenly spread, one could fill them into a grid (taking O(m)) and then doing the nearest neighbor search in O(n), totalling to O*n+m). But if the points cluster in a small area, but some points are scattered over a large area, this approach breaks down. – ruediste Jun 21 '14 at 09:45