CODEWITHSUNDEEP
c++calgorithmcomputational-geometry
user2609926
user2609926

Reputation:

how to determine whether a set of rectangles contain two who have overlapped area?

struct Rect
{
double left, right, top, bottom;
};

std::vector<Rect> vec;

now we have N(N > 1000) rectangles, what's an efficient algorithm to determine whether any two of them are overlapped?

updates: all these rectangles are parallel to coordinate system.

Upvotes: 5

Views: 947

Answers (4)

greybeard
greybeard

Reputation: 2432

I feel olidged to mention RH Güting and W Schilling, "A Practical Divide-and-Conquer Algorithm for the Rectangle Intersection Problem", Information Sciences 42 (1987).
The strategy followed in Pham Trung's answer (plane sweep) is more likely to have a faster implementation for set problems, divide-and-conquer is closely related to data structures suitable for "online queries", e.g., "For the given set of axis-aligned rectangles, what is the subset intersecting this one?"

Upvotes: 0

Pham Trung
Pham Trung

Reputation: 11284

You can represent a rectangle by two segments: open segment (x1,y1) to (x1,y2) and close segment (x2,y1) to (x2,y2) with x1 < x2 and y1 < y2.

First, we can sort all these segments in O(nlogn) time by its x coordinate.

Second, we process each segment one by one, if we encounter an open segment, we add the interval (y1, y2) from that segment into an interval tree, if we encounter an close segment, remove that from the tree. For each segment we added, we can query the tree to see how many segments in the tree, are overlapping with this segment, which is also the number of rectangles that are overlaping with this rectangle's open segment. Time complexity for each query O(logn).

So, we will have a O(nlogn) algorithm.

Upvotes: 7

Tony Delroy
Tony Delroy

Reputation: 106068

One crude approach is to divide the coordinate space into a D * D grid, then create a two-dimensional array of vectors of rectangles that overlap each area:

std::vector<Rect*> grid[D][D];

For example, you might have a 20x20 grid, with some of your 1000+ rectangles internal to a single grid coordinate and others overlapping many grid elements. Still, by a little trial and error tuning of D you can probably get an average of maybe 5-50 rectangles in each vector (depending on how drastically they vary in size), which you can then brute-force search for overlaps.

If you want to optimise this further:

  • you could keep a single nullptr in the vector if any rectangle completely covers the grid region, short-circuiting per-rectangle comparisons
  • you could experiemnt with separate grids for different sized rectangles - a larger rectangle that fully covers a grid coordinate would know there's an overlap if the vector wasn't empty()

(It's noteworthy that the amount of effort worth putting in to sorting, merging/simplifying overlapping rectangles, indexing etc. is vastly different if you have a body of rectangles to which you repeatedly add new rectangles, wanting to test each for overlaps with any prior rectangles. Wanting to know exactly which rectangles overlap is another complexity (one which the brute-force step above happens to satisfy). I take the question to mean that there's a group of unsorted rectangles for which a one-off true/false is-there-any-overlap answer is needed.)

Upvotes: 0

Cheers and hth. - Alf
Cheers and hth. - Alf

Reputation: 145194

one idea is to maintain one collection of horizontal in-use ranges, and one collection of vertical in-use ranges. adding a new rectangle, call the rectangles that it overlaps with horizontally H, and ditto V for vertical. if the intersection of sets H and V is non-empty, those are the rectangles it overlaps in 2D with.

up till the first 2D overlap I think this would perform in O(n log n), provided the ranges are suitably represented, some kind of sorted structure.

Upvotes: 0

Related Questions