0

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.

Optimiz
  • 53
  • 7
  • Your question in not clear. What is the exact problem? – Saeid Nov 23 '15 at 00:35
  • The problem is that if rect1 and rect2 overlap, and rect2 and rect5 overlap, and rect3 and rect4 overlap, you'll store [1,2,5] as a group, and [3,4] as a group; if after that you find that 4 and 5 overlap, you need a way to join the two groups together. Or else you need to find all the overlaps first, and then create the groups. – m69's been on strike for years Nov 23 '15 at 00:41
  • 2
    Don't destroy your question. – deviantfan Nov 24 '15 at 00:17
  • deviantfan, please remove/delete this post. Thank you. – Optimiz Nov 24 '15 at 00:18
  • @Optimiz I can't, and neither can you. Getting help here includes that you leave everything so that it can help other people too. – deviantfan Nov 24 '15 at 00:19
  • Oh okay. Thanks anyhow! – Optimiz Nov 24 '15 at 00:19
  • @Optimiz You don't understand, do you? Don't destroy your question. If you don't agree with being a help for other people, you should've known that beforehand. The terms of use and rules of this site are visible for everyone. – deviantfan Nov 24 '15 at 00:19
  • This wont even be a help for other people. It wasn't even answered or figured out. It's just a waste of space tbh with my source on it. But you're the mod. You know what's best for this domain. Good day. – Optimiz Nov 24 '15 at 00:22
  • @Optimiz As said before, I'm not a mod. I can't delete your question. ... Yes, good day. – deviantfan Nov 24 '15 at 00:38
  • @Optimiz If you figured out a solution, please share it as an answer here. – m69's been on strike for years Nov 24 '15 at 01:20

1 Answers1

1

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.

Community
  • 1
  • 1
Saeid
  • 4,147
  • 7
  • 27
  • 43
  • there is an implementation in the link provided in my answer https://github.com/kartikkukreja/blog-codes/blob/master/src/Union%20Find%20%28Disjoint%20Set%29%20Data%20Structure.cpp – Saeid Nov 23 '15 at 00:51