Python3如何使用表示重叠坐标的元组键压缩字典

Question

我有一个字典，其中键是表示y线坐标（y0，y1）的元组，其中y0=线y坐标的底部，y1=y线顶部坐标

data = { (622, 633): 'text1', (604, 619) : 'text2', (596, 633) : 'text3', (577, 587) : 'text4', (551, 587) : 'text5'  }

我希望能够“压缩”字典，以便所有与元组相关且重叠的项都在tuple键下组合在一起，其范围最大为y0，y1。所以上面的字典应该是这样的：

^{pr2}$

我是python的新手，在这个问题上我有点头晕，希望能朝正确的方向点头。谢谢。

Answer 1

比如说：

# Returns True if point yt is in the range (y0, y1) inclusive
def _in(yt, y): return y[0] <= yt <= y[1]

# Returns True if either segment intersects (or is contained in the other), False otherwise
def intersects(s1, s2): return _in(s1[0], s2) or _in(s1[1], s2) or _in(s2[0], s1) or _in(s2[1], s1)

# Returns an (i,e) tuple for each element e of lst that "intersects" (see prev. function) list lst
#   i is index of element e in lst
def find_intersections(s, lst): return [(i,e) for (i,e) in enumerate(lst) if intersects(s,e)]

# Returns a 2-tuple containing the minimum and maximum of the input segments s1, s2
def merge(s1, s2): return (min(s1[0], s2[0]), max(s1[1], s2[1]))
# Note: The functions _in and merge assume that y0,y1 are sorted, ascending

data = { (622, 633): 'text1', (604, 619) : 'text2', (596, 633) : 'text3', (577, 587) : 'text4', (551, 587) : 'text5'  }
new_data = {}

lst = list(data.keys())
while len(lst):
    rng = lst.pop()

    keys = [rng,]
    while True:
        updated = False
        for (i,match) in find_intersections(rng, lst):
            updated = True
            keys.append(match)
            rng = merge(rng, match)
            lst.pop(i)
        if not updated: break

    new_data[rng] = ' '.join(sorted(data[k] for k in keys))

print(new_data)      # {(551, 587): 'text4 text5', (596, 633): 'text1 text2 text3'}

编辑：为Python3做了一些调整