I have a large set of rectangles with random orientation and size. Say up to $10000$ rectangles, which are non-overlapping.
For every rectangle, I need to find the nearest compatible neighbor. Two rectangles are said to be compatible when the angle they both form with the line that joins their center is below a fixed tolerance. The distance is computed between the rectangle centers. Note that every rectangle has two orthogonal directions. (In a more advanced version of the problem, the tolerance can also depend on the sizes.)
I can obviously solve this by exhaustive search, trying all pairs of rectangles, but this is an $O(N^2)$ process. I am looking for algorithmic ways to accelerate (parallelization is not an option). I know about efficient solutions for the all-nearest-neighbors search based on the Voronoi diagram, kD-trees and similar techniques, but in my case the compatibility condition makes them unsuitable.
Any suggestion ? A speedup factor of $10$ would already be very welcome.
(If I understand the question correctly,) here is one approach.
Sort for angle of rotation first. Keep offset in the list of +90 degree modulos. Use your favorite sorting algorithm here. Several of the classical ones shall perform $\mathcal O(n\log(n))$.
Now all compatible ones will lie locally close to each other with exception of the edges of the list. This is nice both for cache hits and for ease of writing algorithm.
We can build a double loop with the inner loop breaking as soon as we go outside of threshold. This shall greatly reduce the number of comparisons required if the threshold is small. No unnecessary comparisons will need to be done.