快速检查一个区域是否与另一个区域重叠的方法

Question

我有一大堆地区，一个开始和结束的数千个点。即：

[（3015，3701），（4011，5890），...]

我也有另一组点（开始和结束），我希望有一个快速的方法来测试是否或者该组中的区域与另一组中的区域重叠。有没有快速的方法来做到这一点？

谢谢！

- 编辑 -

@Spike Gronim回答我的问题与间隔树。

谢谢，斯派克！

http://en.wikipedia.org/wiki/Interval_tree

Answer 1

然后找到这两个区域的最小/最大端点如果这些重叠看到。

Answer 2

def test(lista, listb): 
    a = 0 
    b = 0 
    found = False 
    while a<len(lista) and b<len(listb): 
     result = check(lista[a] , listb[b]) 
     if result < 0: 
      a += 1 
      continue 
     if result > 0: 
      b += 1 
      continue 
     # we found overlapping intervals 
     found = True 
     return (found, a, lista[a], b, listb[b]) 
    return found 

def check((astart, aend) , (bstart, bend)): 
    if aend < bstart: 
     return -1 
    if bend < astart: 
     return 1 
    return 0 


lista = [(3015, 3701), (4011, 5890)] 
listb = [(1,2), (100,200), (4500,6000)] 
result = test(lista, listb) 
print result