Быстрый способ проверить, перекрывает ли область другую (одномерную) область

#python

Вопрос:

У меня есть огромный набор регионов, буквально тысячи точек с началом и концом. Т.е.:

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

У меня также есть другой набор точек (как начальный, так и конечный), где я хочу быстрый способ проверить, перекрывает ли область в этом наборе область в другом наборе. Есть ли быстрый способ сделать это?

Спасибо!

—РЕДАКТИРОВАТЬ—

@Spike Gronim ответил на мой вопрос деревом интервалов.

Спасибо, Спайк!

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

1. en.wikipedia.org/wiki/Interval_tree

2. насколько большими могут стать эти точки? Я имею в виду диапазон начала и конца?

3. В десятках тысяч. Это геномные координаты.

4. перекрывают ли когда-либо диапазоны в каждом списке другие диапазоны в том же списке?

5. Упорядочены ли два списка по начальной координате?

Ответ №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

Ответ №2:

Найдите минимальные / максимальные конечные точки обеих областей, затем посмотрите, перекрываются ли они.