Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Intersection of N rectangles

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 :(

like image 271
Chan Le Avatar asked May 04 '11 08:05

Chan Le


People also ask

How do you find the intersection of a rectangle?

The coordinates for some intersection will just be the point where "edge a" of "rectangle 1" intersects "edge x" of "rectangle 2." That is, the intersection point will have the x value of (edge a or x), and the y value of the other edge (since these rectangles are parallel to the axis the x or y value of an edge will ...

How do you find the intersection of two rectangles in Java?

Rectangle rect1 = new Rectangle(100, 100, 200, 240); Rectangle rect2 = new Rectangle(120, 80, 80, 120); Rectangle intersection = rect1. intersection(rect2);

How do you find the intersection of two rectangles in Python?

If we have two (axis-aligned) rectangles, we have to check whether they overlap or not. So, if the input is like R1 = [0,0,2,2], R2 = [1,1,3,3], then the output will be True. otherwise, return True.


2 Answers

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

like image 58
Adam Matan Avatar answered Nov 10 '22 10:11

Adam Matan


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.

like image 21
Yakov Galka Avatar answered Nov 10 '22 11:11

Yakov Galka