title: How to test if a given rectangle intersects with a list of excluded areas?
body: <p>I have implemented <code>SegmentBisect</code> for 1D segments. Given a list of 1D segments, it constructs a data-structure that defines the excluded regions on the x-axis. </p>
  
  <p>I have some difficulty to extend/use <code>SegmentBisect</code> to create a class that can fast find if a rectangle in the x-y space intersects an apriori list of rectangles.</p>
  
  <p>The 1D solution take <code>O(log(n))</code> I assume it's possible to get <code>O(log^2(n))</code></p>
  
  <pre><code>import bisect
  
  class SegmentBisect():
  
      def isCoordExcluded(self, coordinate):
          i = self.excludedIndex(coordinate)
          try:
              return self.isExcluded[i]
          except:
              return False
  
      def excludedIndex(self, coordinate):
          return bisect.bisect_right(self.segmentBisect, coordinate)
  
      def __init__(self, lineSegments):
  
          lineSegments.sort(key=lambda x:min(x))
          self.segmentBisect = []
          self.isExcluded    = []
          for segment in lineSegments:
              if type(segment) == range:
                  segment = range(min(segment), max(segment)+1) # to support input as range
              else: 
                  segment = range(min(segment), max(segment))
              low  = min(segment) 
              high = max(segment)+1 # to include b-1 for the excluded segment:(a,b)
              lowExcluded  = self.isCoordExcluded(low)
              highExcluded = self.isCoordExcluded(high)
  
              if lowExcluded and highExcluded:
                  continue
              elif not lowExcluded and not highExcluded:
                  self.segmentBisect.extend([low, high])
                  self.isExcluded.extend([False, True])
              elif lowExcluded and not highExcluded:
                  idx = self.excludedIndex(low)
                  self.segmentBisect[idx] = max(high,self.segmentBisect[idx])
              else:
                  raise('Error while adding the segment {0} to the bisect array.'.format(range(low,high)))
  
  import unittest
  class TestSegmentBisect(unittest.TestCase):
      def test_five_segments_three_intersections(self, sbs=None):
          if not sbs:
              sbs = SegmentBisect([(20,30), (10,3), (2,6), (8,12), (50,100)])
  
          for i in range(-2,2):
              self.assertFalse(sbs.isCoordExcluded(i))
  
          for i in range(2,12):
              self.assertTrue(sbs.isCoordExcluded(i))
  
          for i in range(20,30):
              self.assertTrue(sbs.isCoordExcluded(i))
  
          for i in range(30,50):
              self.assertFalse(sbs.isCoordExcluded(i))
  
          for i in range(50,100):
              self.assertTrue(sbs.isCoordExcluded(i))
  
          for i in range(100,102):
              self.assertFalse(sbs.isCoordExcluded(i))
  
      def test_five_segments_three_intersections_range(self):
          sbs = SegmentBisect([range(20,30), range(3,10), range(2,6), range(8,12), range(50,100)])
          self.test_five_segments_three_intersections(sbs)
  
  suite = unittest.TestLoader().loadTestsFromTestCase(TestSegmentBisect)
  unittest.TextTestRunner().run(suite)
  </code></pre>