CODEWITHSUNDEEP
c++collision-detectionrectangles
Jepessen
Jepessen

Reputation: 12415

Data structure for rectangle overlapping

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)

Upvotes: 3

Views: 1202

Answers (1)

Yann
Yann

Reputation: 988

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.

Upvotes: 3

Related Questions