15

I'm looking for an algorithm to solve this problem:

Given N rectangles on the Cartesian coordinate, find out if the intersection of those rectangles is empty or not. Each rectangle can lie in any direction (not necessary to have its edges parallel to Ox and Oy)

Do you have any suggestion to solve this problem? :) I can think of testing the intersection of each rectangle pair. However, it's O(N*N) and quite slow :(

Ismael
  • 2,995
  • 29
  • 45
Chan Le
  • 2,184
  • 3
  • 23
  • 33

6 Answers6

19

Abstract

Either use a sorting algorithm according to smallest X value of the rectangle, or store your rectangles in an R-tree and search it.

Straight-forward approach (with sorting)

Let us denote low_x() - the smallest (leftmost) X value of a rectangle, and high_x() - the highest (rightmost) X value of a rectangle.

Algorithm:

Sort the rectangles according to low_x().                   # O(n log n)

For each rectangle in sorted array:                         # O(n)
    Finds its highest X point.                              # O(1)
    Compare it with all rectangles whose low_x() is smaller # O(log n)
        than this.high(x)

Complexity analysis

This should work on O(n log n) on uniformly distributed rectangles.

The worst case would be O(n^2), for example when the rectangles don't overlap but are one above another. In this case, generalize the algorithm to have low_y() and high_y() too.

Data-structure approach: R-Trees

R-trees demonstration

R-trees (a spatial generalization of B-trees) are one of the best ways to store geospatial data, and can be useful in this problem. Simply store your rectangles in an R-tree, and you can spot intersections with a straightforward O(n log n) complexity. (n searches, log n time for each).

Adam Matan
  • 128,757
  • 147
  • 397
  • 562
  • It's O(n^2). The last step is not O(log n). Counter example: set of rectangles `{ [k, 2n-k]×[0, 1] | k ∈ {0, ..., n-1} }` – Yakov Galka May 04 '11 at 08:41
  • @ybungalobill: See addendum - the rectangles can be sorted according to their Y values too, so it remains `O(n log n)`. – Adam Matan May 04 '11 at 08:56
  • @Adam: Nope. Counter example 2: `{ [k, 2n-k]×[k, 2n-k] | k ∈ {0, ..., n-1} }` — sort however you want, use an R-tree... it's still O(n^2). – Yakov Galka May 04 '11 at 08:59
  • Adam, remember " Each rectangle can lie in any direction (not necessary to have its edges parallel to Ox and Oy)" – ariel May 04 '11 at 09:03
  • Please note that those rectangles's direction are arbitrary (i.e: its edges are not necessary parallel to the Ox and Oy). I think your solution only solve the cases when the edges are parallel to Ox and Oy? – Chan Le May 04 '11 at 09:05
  • I'm not sure - let me reason about it for a while. – Adam Matan May 04 '11 at 09:07
  • @ybungalobill - Are `[k, 2n-k]×[k, 2n-k]` merely point-rectangles? – Adam Matan May 04 '11 at 09:08
  • @Adam: what do you mean by 'point rectangles'? `[k, 2n-k]×[k, 2n-k]` is a rectangle with vertices `(k,k) (k,2n-k) (2n-k, 2n-k) (2n-, k)`, it's axis aligned and has area of 4(n-k)². – Yakov Galka May 04 '11 at 09:13
  • @ybungalobill Thanks, I thought the Cartesian product was just a separation mark between two points. – Adam Matan May 04 '11 at 09:31
  • 1
    Yeah, this is the answer to the wrong question. And accumulating the intersection of n axis-aligned boxes is trivial, you don't need any nontrivial data structures. Just whack away axis-aligned slices of the box. – Don Hatch Jul 01 '14 at 05:07
4

Observation 1: given a polygon A and a rectangle B, the intersection A ∩ B can be computed by 4 intersection with half-planes corresponding to each edge of B.

Observation 2: cutting a half plane from a convex polygon gives you a convex polygon. The first rectangle is a convex polygon. This operation increases the number of vertices at most per 1.

Observation 3: the signed distance of the vertices of a convex polygon to a straight line is a unimodal function.

Here is a sketch of the algorithm:

Maintain the current partial intersection D in a balanced binary tree in a CCW order.

When cutting a half-plane defined by a line L, find the two edges in D that intersect L. This can be done in logarithmic time through some clever binary or ternary search exploiting the unimodality of the signed distance to L. (This is the part I don't exactly remember.) Remove all the vertices on the one side of L from D, and insert the intersection points to D.

Repeat for all edges L of all rectangles.

Yakov Galka
  • 70,775
  • 16
  • 139
  • 220
2

This seems like a good application of Klee's measure. Basically, if you read http://en.wikipedia.org/wiki/Klee%27s_measure_problem there are lower bounds on the runtime of the best algorithms that can be found for rectilinear intersections at O(n log n).

user737606
  • 21
  • 2
  • thats correct, Klee's measure is pretty much the generalization of this question and covers it perfectly showing an optimal algorithm. – ldog May 04 '11 at 08:43
  • I'm finding the intersection. I think klee's measure is all about the union of those rectangles? – Chan Le May 04 '11 at 09:08
  • This answer is intriguing but it's not clear how it applies. Perhaps the question about intersections can be framed as a question about unions, by taking complements somehow? – Don Hatch Jul 01 '14 at 08:08
1

I think you should use something like the sweep line algorithm: finding intersections is one of its applications. Also, have a look at answers to this questions

Community
  • 1
  • 1
MarcoS
  • 13,386
  • 7
  • 42
  • 63
  • One problem I see here is that with n rectangles I can create n^2 boundary intersections... (think of a plus of a different thickness). – Yakov Galka May 04 '11 at 09:25
0

Since the rectangles must not be parallel to the axis, it is easier to transform the problem to an already solved one: compute the intersections of the borders of the rectangles.

  • build a set S which contains all borders, together with the rectangle they're belonging to; you get a set of tuples of the form ((x_start,y_start), (x_end,y_end), r_n), where r_n is of course the ID of the corresponding rectangle
  • now use a sweep line algorithm to find the intersections of those lines

The sweep line stops at every x-coordinate in S, i.e. all start values and all end values. For every new start coordinate, put the corresponding line in a temporary set I. For each new end-coordinate, remove the corresponding line from I.

Additionally to adding new lines to I, you can check for each new line whether it intersects with one of the lines currently in I. If they do, the corresponding rectangles do, too.

You can find a detailed explanation of this algorithm here.

The runtime is O(n*log(n) + c*log(n)), where c is the number of intersection points of the lines in I.

Philip
  • 5,795
  • 3
  • 33
  • 68
  • 1
    The problem is that c=n^2 is possible. See my comment on @MarcoS answer. – Yakov Galka May 04 '11 at 09:29
  • @ybunga: that's right, but that's the nature of the underlying problem. If the solution set has a maximum size of n^2, then the algorithm to find this set must also have a worst-case running time of O(n^2). The algorithm I suggested has the advantage that its runtime adapts to the complexity of the solution. – Philip May 04 '11 at 09:48
-1

Pick the smallest rectangle from the set (or any rectangle), and go over each point within it. If one of it's point also exists in all other rectangles, the intersection is not empty. If all points are free from ALL other rectangles, the intersection is empty.

Gaurav Dadhania
  • 5,167
  • 8
  • 42
  • 61
  • If R1 dont intersect with R2 and R3, this dont mean that R2 and R3 dont intersect each other – ariel May 04 '11 at 08:30
  • @ariel : but that means R1, R2 and R3 don't intersect. But this is still inefficient, we can say so just looking at the edges (either top/bottom or left/right) of the rectangles as mentioned by Adam. – Gaurav Dadhania May 04 '11 at 08:33
  • How do you determine "each point within it" ? :) since there are infinitely number of points inside an area. – Chan Le May 04 '11 at 09:12