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

Question

我有一大堆区域，里面有成千上万的点，每个区域都有一个开始点和一个结束点。比如说：

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

我还有另一组点（同样有开始和结束），我想找个快速的方法来检查这两组区域是否有重叠的地方。有没有什么快速的方法可以做到这一点呢？

谢谢！

--编辑--

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

谢谢你，Spike！

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

Answer 1

先找出两个区域的最小和最大边界点，然后看看这些边界点是否有重叠的部分。

Answer 2

在编程中，有时候我们会遇到一些问题，尤其是在使用特定的工具或库时。比如，有人可能在使用某个库的时候，发现它的某个功能没有按照预期工作。这种情况下，通常我们会去查找相关的文档或者在网上搜索解决方案。

如果在网上找不到答案，很多人会选择在像StackOverflow这样的平台上提问。在提问时，提供清晰的信息是非常重要的。比如，描述你遇到的问题，提供相关的代码片段，以及你尝试过的解决方法，这样其他人才能更好地理解你的问题，并给出有效的建议。

总之，遇到问题时，不要着急，先自己查找一下资料，如果还是解决不了，再去请教别人。记得把问题描述清楚，这样才能更快找到解决办法。

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