title: Data structure to hold list of rectangles?
body: <p>I was wondering if there is a good data structure to hold a list of axis-aligned non overlapping discrete space rectangles. Thus each rectangle could be stored as the integers x, y, width, and height. It would be easy to just store such a list but I also want to be able to query if a given x,y coordinate is inside any other rectangle.</p>
  
  <p>One easy solution would be to create a hash and fill it with the hashed lower left coordinates of the start of each rectangle. This would not allow me to test a given x,y coordinate because it would hit an empty space in the middle. Another answer is to create a bunch of edges into the hash table that cover the entire rectangle with unit squares. This would create too many needless entries for a rectangle of say 100 by 100.</p>