python之检查一个区域是否与另一个 (1-d) 区域重叠的快速方法

我有一个巨大的区域集合——有数千个点，有起点和终点。即:

[(3015, 3701), (4011, 5890), ....]

我还有另一组点(包括开始点和结束点)，我想要一种快速方法来测试该组中的区域是否与另一组中的区域重叠。有没有快速的方法来做到这一点？

谢谢!

--编辑--

@Spike Gronim 用区间树回答了我的问题。

谢谢，斯派克!

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

请您参考如下方法:

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