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.

I know it's not the answer you are looking for, but this might interest you : http://en.wikipedia.org/wiki/Sweep_and_prune — Pol0nium, Oct 09 '13 at 12:37
I want it so if the area of a bounding box is covered by the others by more than 50% (Although this percentage could be altered), then it should prune it. and Sure I'll draw an image :) on paint for you — James Campbell, Oct 09 '13 at 12:37
Something like this? http://stackoverflow.com/a/6634668/752320 — Geobits, Oct 09 '13 at 13:15
@JamesCampbell In this context, does "prune" mean "make smaller" or "get rid of"? — Bernhard Barker, Oct 09 '13 at 14:16

score 1 · Accepted Answer · answered Oct 10 '13 at 16:34

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.

answered Oct 10 '13 at 16:34

AlexWien

28,470
6
53
83

Yes it is very complex, one solution I came up with is these bounding boxes are actually calculated from a geolocation point which is at the centre of them. So I could workout a radius from that centre point that fills as much of the box as possible. If any other centre points are in that radius then I remove them and their associated box, I would then just rely on the potential small amount of overlap to not matter or effect results adversely, which is sort of what you've already mentioned doing above :) – James Campbell Oct 10 '13 at 23:01
That sounds fine, you can often save much money if you go a simple but sufficient way. – AlexWien Oct 11 '13 at 12:32

score 0 · Answer 2 · answered Oct 10 '13 at 08:37

0

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.

answered Oct 10 '13 at 08:37

stan0

11,549
6
42
59

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

2 Answers2