Data structure for rectangle overlapping

Question

I have a set of rectangles in specified space, and they can have different dimensions and positions.

I need to detect collision clusters, group of rectangles that intersect each others, like in the attached figure, in which I have two clusters (into red boxes).

The trivial way is to have a vector of these rectangles and, with a double for loop check intersections, like something

for (size_t i = 0; i < rectangles.size(); i++) {
  for (size_t j = i + 1; j < rectangles.size(); j++) {
    if (rectangles.at(i).intersect(rectangles.at(j)) {
      // Add rectangle[j] to cluster in which rectangle[i] is
    }
  }

I don't think that is the most efficient way in order to perform calculus.

How can I efficiently calculate these clusters? I've read something about plane partition using quad-tree, but I don't know how use them in this case. Is it the appropriate data structure or there's a more efficient way (I must handle it in soft real-time).

I have two clusters (grouped in red)

@VaughnCato R-Tree is the right choice for my problem, do you agree or I'm making a mistake? — Jepessen, Aug 27 '14 at 13:57
My intuition is that you are going to get better performance with a sweep-line approach. — Vaughn Cato, Aug 27 '14 at 13:59
Probably you're right. I'll study a bit these solutions. Thanks for your help. — Jepessen, Aug 27 '14 at 14:05

score 3 · Accepted Answer · edited Apr 13 '17 at 12:18

3

If the situation allows for it, using a quad tree is definately a good call, although make sure that you have enough objects for the overhead of the creation and maintenance of the structure worth it.

Aside from that, a simple check for the max X value of one rectangle vs the min X of the other and the same for Y should be okay if you're just using rectangles. If not, and you're not using concave objects, the separating axis theorem is a great method to do detection and will even stretch for 3d if you push it enough. One thing that I do really like about the separating axis theorem, is that it does collisions response too if you need it, as it can return the minimum vector to move the shapes out of one another.

Some of the people over on game-dev will have plenty of pointers on further collision detection and response if you get stuck.

edited Apr 13 '17 at 12:18

Community

1
1

answered Aug 27 '14 at 13:45

Yann

978
2
12
31

Thanks. I know how to perform rectangle collision, but I don't know what's the best data structure in order to minimize collision test. I've seen that @VaughnCato told me to use R-tree data structure and separating axis theorem I should obtain good performance. – Jepessen Aug 27 '14 at 14:00
Fair enough. Do bear in mind that it's fairly likely that separating axis theorem will only be better in the sense that you'll get greater accuracy of collision if your objects aren't easily bounded by a rectangle. While it is efficient, it's not as quick as a simple greater than/less than check. @Jepessen – Yann Aug 27 '14 at 14:03

Data structure for rectangle overlapping

1 Answers1