python - 从线中找到矩形的高效算法？

Question

给定一个仅水平和垂直的路径列表(具有开始和结束坐标)，我如何找到它们形成的所有矩形？

详细信息:

• 矩形的端点必须是其组成边的端点。即不需要由线的交叉点形成的矩形。
• 给出开始和结束的 x,y，表示为每行的复数。
• 输出应该是代表矩形每条边的四行

这是我天真的实现，太慢了。还有其他方法吗？

def find_rectangles(paths):
    vertical_paths = filter(lambda path: is_vertical(path), paths)
    horizontal_paths = filter(lambda path: is_horizontal(path), paths)

    vertical_paths.sort(key=lambda path: path.start.imag, reverse=True)
    horizontal_paths.sort(key=lambda path: path.start.real)

    h_pairs = []
    for i in range(0, len(horizontal_paths) - 1):
        for j in range(1, len(horizontal_paths)):
            if horizontal_paths[i].start.real == horizontal_paths[j].start.real and horizontal_paths[i].end.real == horizontal_paths[j].end.real:
                h_pairs.append((horizontal_paths[i], horizontal_paths[j]))

    v_pairs = []
    for i in range(0, len(vertical_paths) - 1):
        for j in range(1, len(vertical_paths)):
            if vertical_paths[i].start.imag == vertical_paths[j].start.imag and vertical_paths[i].end.imag == vertical_paths[j].end.imag:
                v_pairs.append((vertical_paths[i], vertical_paths[j]))


    rects = []
    for h1, h2 in h_pairs:
        for v1, v2 in v_pairs:
            if h1.start == v1.start and v1.end == h2.start and h1.end == v2.start and h2.end == v2.end:
                rects.append(Rect(h1.start, h1.end, h2.end, h2.start))

    return rects

编辑:(所有建议的改进)

主要区别在于我将所有水平边的端点存储在一个集合中，因此查找它们的时间复杂度为 O(1):

def find_rectangles(paths):
    vertical_paths = [path for path in paths if is_vertical(path)]
    horizontal_paths_set = set([(path.start, path.end) for path in paths if is_horizontal(path)])

    vertical_paths.sort(key=lambda pair: path.start.imag, reverse=True)

    v_pairs = [pair for pair in list(itertools.combinations(vertical_paths, 2)) if pair[0].start.imag == pair[1].start.imag and pair[0].end.imag == pair[1].end.imag]

    rects = []
    for v1,v2 in v_pairs:
        h1 = (v1.start, v2.start)
        h2 = (v1.end, v2.end)

        if(h1 in horizontal_paths_set and h2 in horizontal_paths_set):
            rects.append(Rect(h1[0], h1[1], h2[1], h2[0 ]))

    return rects

我的新代码运行速度快得多，但仍处于 O(n2) 的数量级。欢迎提出任何改进建议。

Answer 1

您可以先放弃对 v_pairs 的搜索。你只需要知道潜在的矩形(水平对)是否可以闭合。

def find_rectangles(paths):
    vertical_paths = filter(lambda path: is_vertical(path), paths)
    horizontal_paths = filter(lambda path: is_horizontal(path), paths)

    vertical_paths.sort(key=lambda path: path.start.imag, reverse=True)
    horizontal_paths.sort(key=lambda path: path.start.real)

    potential_rectangles = []
    for i,h1 in enumerate(horizontal_paths[:-1]):
        for h2 in horizontal_paths[i+1:]:
            if ((h1.start.real == h2.start.real) 
                    and (h1.end.real == h2.end.real)):
                potential_rectangles.append((h1,h2,None,None))

    rectangles = []
    for v in vertical_paths:
        for i,(h1,h2,v1,v2) in enumerate(potential_rectangles):
            if v1 is None and v.start == h1.start and v.end == h2.start:
                potential_rectangles[i][2] = v
                if v2 is not None:
                    rectangles.append(potential_rectangles.pop(i))
                break
            if v2 is None and v.start == h1.end and v.end == h2.end:
                potential_rectangles[i][3] = v
                if v1 is not None:
                    rectangles.append(potential_rectangles.pop(i))
                break

    return rectangles

当然有很大的潜力可以加快选择速度，具体取决于收到的数据。例如，按长度对路径进行排序。你能提供更多细节吗？

编辑后Bisect 比“is in”快很多，但它需要一个有序的标量值列表。