I have implemented `SegmentBisect`

for 1D segments. Given a list of 1D segments, it constructs a data-structure that defines the excluded regions on the x-axis.

I have some difficulty to extend/use `SegmentBisect`

to create a class that can fast find if a rectangle in the x-y space intersects an apriori list of rectangles.

The 1D solution take `O(log(n))`

I assume it’s possible to get `O(log^2(n))`

```
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)
```