1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ How are the rectangles stored or represented? $\endgroup$
    – mathreadler
    Nov 18, 2020 at 11:10
  • $\begingroup$ @mathreadler: a flat list with centers, sizes and angles. $\endgroup$
    – user65203
    Nov 18, 2020 at 11:16
  • $\begingroup$ If n=10000 at most, then 'exhaustive' should certainly be doable if you are a bit careful with how you process them. At least save for each pair if they are compatible so you don't compute them twice. And if you process candidates in order of increasing distance, you will be able to stop early whenever you find a compatible one. $\endgroup$
    – Steven
    Nov 18, 2020 at 11:32

1 Answer 1

Reset to default
1
$\begingroup$

(If I understand the question correctly,) here is one approach.

  1. 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))$.

  2. 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.

  3. 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.

$\endgroup$
3
  • $\begingroup$ The angles differ for all rectangles, I am afraid the sorts would cost $O(N^2\log N)$. $\endgroup$
    – user65203
    Nov 18, 2020 at 11:37
  • $\begingroup$ @YvesDaoust I am not sure I understand the question. The angles I assumed were stored for each individual rectangle are in relation to some fixed ON frame. These were the ones I thought could be sorted. $\endgroup$
    – mathreadler
    Nov 18, 2020 at 11:53
  • 1
    $\begingroup$ Sorry, I misunderstood your explanation. Yes, we can restrict the search to nearby angles. $\endgroup$
    – user65203
    Nov 18, 2020 at 12:02

You must log in to answer this question.