CODEWITHSUNDEEP
c++algorithmequivalence
Optimiz
Optimiz

Reputation: 53

Grouping Overlapping Shapes (x,y)

My algorithms to find overlapping rectangles (regions) with the use of x-y coordinates (bottom left corner, top right corner) works fine. But my algorithm for grouping the overlapped ones together doesn't appear to be working. Can someone please tell me what I am doing wrong?

My program reads in x-y coordinates from a .txt file such as this...

0 5 3 6 (0,5 is bottom left corner and 3,6 is top right corner)

2 7 8 9 (2,7 is bottom left corner and 8,9 is top right corner)

and then figures out what all of the groups are over overlapping rectangles and prints out the groups.

i.e. Rectangle 0 overlaps 2, 2 overlaps 1, and 1 overlaps 5. That means rectangles 0, 2, 1, and 5 are all in 1 group so that I can print out that group #1.

i.e. Rectangle 4 and 3 overlap, so that means that rectangles 4 and 3 are in group #2.

i.e. Rectangle 10 overlaps 11, and rectangle 11 overlaps rectangle 12. So that means rectangles 10, 11, and 12 are all in group #3 so that I can neatly print that out.

Upvotes: 0

Views: 292

Answers (1)

Saeid
Saeid

Reputation: 4265

From what I understand what you need to do is implement a union-find data structure to store the connected components. It does exactly what you intend. For more explanation you should read this question: Union-find data structure

Using the code mentioned what you need to do is this:

UF uf( n ); // create and initialize a UF. n is the number of rectangles you have
if ( two rectangles overlap ){ 
     if ( ! connected( rectangleId1, rectangleId2 ) ){ // if they aren't already in the same component
           merge( find(rectangleId1), find(rectangleId2) ); // put them in the same component
     }
}

After that every rectangle with same value for find( rectangleId ) belong to the same component.

Upvotes: 1

Related Questions