title: Data Structure For Determining Intersection of Rectangle with a Larger Set of Rectangles
body: <p>My data set is made of many rectangles that lie on an x,y plane (represented by a set of quad points). 99.9% of the time these rectangles will not overlap, but very rarely they will. I'm trying to find an optimal data structure for storing the rectangles so that I can find instances of intersection. </p>
  
  <p>By the way, the rectangles contain text, so I'm doing this in order to find occurrences of the same text overlapping. This is because occurrences like this should be treated as one rectangle of text instead of two.</p>
  
  <p>For example: 
  let's say I'm searching for the text "123".
  There are two rectangles. The first rectangle contains "TEST 123" and the second contains "123". If "123" overlaps with the "123" within the first rectangle (within a given threshold) then my search result should return only one occurrence of the text "123".  </p>
  
  <p>So far I have briefly taken a look at quadtrees, r-trees, k-d trees, and range trees. I do not know much about these trees, nor do I know if any would work for this problem.
  I feel like an r-tree would not be optimal in this case because the the chance of overlap is very small.    </p>