   Data Structure for a set of Rectangles
  Basically, I have a set of rectangles, denoted by S, and I want to store these in an efficient manner.The most common operations seem to be:Intersection Query - Given a rectangle r, find the subset i of S such that all rectangles in i intersect r.Subsumption Query - Given a rectangle r, find the subset i of S such that all rectangles in i are completely subsumed by r. E.g. if r is the rectangle (x1, y1, x2, y2), then i is the set of all rectangles (u1, v1, u2, v2) such that x1 < u1, y1 < u1, x2 > u2, and y2 > v2.Insert - Insert a rectangle r into S.Remove - Remove a rectangle r from S.Transform - For a given rectangle r and a transformation T, if r is a member of S, remove r from S and insert Tr into S.I'm a bit unsure about whether the Transform operation is required. I could just as well remove(x); insert(T(x));, but I know for a fact that that a very common operation will be to translate a particular member rectangle by a vector (basically, if we have the rectangle (0,0,1,1) and a vector (x,y), the translated rectangle would be (x, y, 1+x, 1+y). There are probably data structures in which this special case can be treated faster than by just using remove and insert, especially since most translations will be relatively local (x and the transformed x will typically be close to each other).So far I have looked at kd-trees. My current idea is to have a 4d-tree, where a rectangle (x1, y1, x2, y2) is just represented as a point in 4-space. I'm still pretty unfamiliar with kd-trees (well, I understand the basic algorithm, but I am sure there are some heuristics that can be considered for better performance). Really though, I would like to do a bit of a survey on data structures that are well suited to this kind of problem before I begin implementing.I'm sure there are plenty of people who have had similar requirements. I would be greatful for any advice or experiences you may have.   
  My simplistic algebresque 2D approach (since I work in 2D) with most of these, would be quadtree your environment. The smallest element being assembled as an object with coordinate information and any properties you need. Now you can easily pull up all the quadtree elements (smallest is say 25px by 25px) in a (relative) radius or within any (absolute) bounds or determine intersection, etc.The subsumption query is that old NP problem.Inserts and removes of multi-property abstracts are always most efficient when manipulated by reference :pI'm not quite sure why I would need to remove a rectangle, just to reinsert it again...unless it's no longer a rectangle! Pull by reference, change it there (it never leaves S).Personally, I use basic trig to move my elements in a 2D vector greekstyle (http://www.cs.unc.edu/~mcmillan/comp136/Lecture7/circle.html fun trig link, yes FUN)Of course anyone dealing in 4D space is probably talking over my head. Those are my experiences though :)   ;  I'm still trying to wrap my head around the full problem, but you might want to look into multi-resolution misaligned grids. There was an excellent talk on this structure at GDC '05 by a fellow from Ready at Dawn. The idea is to use uniform grid subdivision of your space, with multiple levels. And you jitter each layer by 1/2 the width of the next smallest layer, which guarantees that any 2D box can be placed into a layer within 2 levels of the optimal.   ;  The problem is that my game takes place in 2d, so I am representing game objects (and trigger areas such as traps, warps, etc) as rectangles. Given a rectangle I want to be able to find all the rectangles that intersect it (and in some circumstances, all the rectangles that are subsumed by it). Characters will be moving around on the map, so this means that the structure is not static -- imagine a character at (x,y) that moves to (a,b) ... the data structure will internally need to update itself because the character is no longer at (x,y); it is at (a,b) now. The only reason I seperate this from insertion and removal is that it is a special case of both -- imagine a monster roaming in a small area. It is moving but most of the time it is not moving far enough to break the kd-tree invariant, and so we can move it without rebuilding the kd-tree (or, just rebuilding a subtree). With a remove and insert, even if we did not need to rebuild the tree, we would still have to traverse all the way down to the leaf ... that's all. I could just as well use remove and insert, but I think there is probably some tricky algorithm out there which makes movement more efficient than just using remove and insert.Subsumption and intersection may be NP but we can still use a kd-tree (or other data structure) to reduce the number of rectangles that we must check ... that's the whole point. If I just use a flat list, then to find those rectangles that intersect a rectangle, I must check every single rectangle in the list. With a small rectangle and a a well-formed tree, only a logarithmic number of checks must be made.The 4D part was just an idea ... I know structures like kd-trees are designed to store points, my issues is that all of the objects I am storing are rectangles ... and I could end up having a rectangle cross a splitting line (the 2d analog of a splitting plane) if I am working in 2D. By representing a rectangle as a point in 4-space, I have the added complexity of partitioning a 4-dimensional space, but the advantage of working with only points. It's a trade off which I think might be beneficial, but I really don't know, so that's why I am checking in here ;)   ;  Yeah, the structure in the talk should definitely help. The actual talk was "Efficient Proximity Mapping in Highly Dynamic Environments". It seems like you can purchase the audio, but you'll really want the slides. I can't seem to find them anywhere. The structure is designed to be very fast for your set of operations... I wish I could find more info somewhere else. Let me poke around some more.   ;  IF your level is primarily horizontal, you could keep a list or vector of rectangles sorted by their x1 coordinate. If each rectangle keeps track of its position in the list, intersection testing is easy: Find position of rectangle A in the list and keep going right while doing vertical intersection checks until the other rectangles' x1 are greater than A's x2. If the objects only move around by small amounts, you could either move them around individually in the list or do an insertion sort on the list each update. Subsumption is then a special case. Adding lots of new objects individually might be costly, though.;  Hi... this might not help much but a few months ago i was doing someresearch on data structures for a particular geometric query and i remember this book i saw:Computational Geometry Algorithms and Applicationswritten by Berg, van Kreveld, Overmars and Schwarzkopffrom springer 2nd edition (2000)IIRC, it had at least a chapter on data-structures for the kind of querys you're after... if you have access to some library try searchingfor the book.Hope it helps.   ;  Why should the subsumption query be NP? All you need to do is test each rectangle in the set for subsumption, and return the set of individual rectangles that were subsumed, no? Even if you don't have any kind of intelligent sorting or partitioning of the collection, it's still O(n). Ditto the intersection query; it's the same thing with a slightly different predicate.And yes, (assuming C++) transformation is most easily accomplished by returning by reference; you can simply provide const-overloaded versions of the operator[]. Of course, this sort of depends on how you want to "identify" rectangles. Are two rectangles with the same coordinates "the same", or do they have some separate ID property?   