How should I index for a simple world of rectangles?

The world consists of many (1k-10k) rectangles of similar sizes, and I need to be able to quickly determine potential overlaps when trying to add a new rectangle. Rectangles will be added and removed dynamically. Are 开发者_开发技巧R-Trees appropriate here? If so, are there any good libraries I should consider? (I'm open to suggestions in any language).

R-Trees would be suitable, yes.

quad trees are also a good data structure for quickly finding objects in a region of 2D space. They are really a more uniform version of r-trees. Using these structures you can quickly zero in on a small region of space, with very few tests, even with massive data sets.

There is a c# implementation here, though I have not looked at it.

This kind of data structure (and it's 3D version called Octrees) are often used in games to manage the large data sets of objects that need to know if they are near any other objects for collision testing, and all kinds of other fun reasons.

You should be able to find lots of articles and examples of these kinds of data structures in the games industry sites, like gamasutra and opengl.org

You can also look up to kd-trees.

I don't know of any implementation but in 3D at least they are usually considered more performant than Octrees. For example, here is a return of experience I just googled it.

You may want to consider alternative to quad trees if you ever have a problem of performance.

However it should be noted that kd-trees are hard to rebalance...