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

Question

我有一个巨大的区域，有数千个点，有起点和终点。一、 电子邮箱：

[（30153701），（40115890），…]

我还有另一组点（起点和终点），我想用一种快速的方法来测试这组中的某个区域是否与另一组中的某个区域重叠。有没有快速的方法？在

谢谢！在

--编辑--

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

谢谢，斯派克！在

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

Answer 1

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

Answer 2

找到两个区域的最小/最大端点，然后查看这些端点是否重叠。在