I have a large list of bounding boxes, how can I calculate duplicates?

Question

I have a list of bounding boxes, I was wondering how I could calculate which ones were redundant / duplicates.

The reason being is I have 2 million of these I send to a API and I want to know which are overlapping others so I can reduce them down so each box only covers a unique area of land, so no two bounding boxes cover the same piece of geo space.

How would I calculate it so that these bounding boxes were each covering their own unique space of geo land ?

I am writing this program in C++ btw.

Answer 1

I think that this task is more complex then you think.

You would have to split existing boxes, untill no overlapping exists, and then remove the boxes totally contained in another.

Instead giving you a solution to that, I recomend to check if you can live with:

1) remove the boxes that are totally contained in another box.
2) leave (partly-)overlapping boxes as they are.

For 2 millions you need a spatial index (QuadTree), to get a list of all boxes nearby one box.

If you have to avoid any overlappings, then you must continue to think what should be the result?
A) A union of overlapping rectangles that therfore is not an rectangle anymore, but a polygon.
or B) The result should be rectangles.

Answer 2

You could check if X% of a box's vertices are inside another box to find if it's overlapped but I suppose this isn't the optimal solution.