algorithm - 给定矩形的坐标，将它们连接起来形成从头到尾的路径

Question

有很多矩形；每个都有左下角和右上角坐标。它们要么重叠（完全或部分），要么至少与另一个边缘接触。

我正在寻找如何通过按顺序跟踪每个矩形来提出从开始到结束块的跟踪。让我们说它在开始块和结束块处都有一个标识符（坐标），它可以说跟踪已经开始和结束。

在下图中，我需要进行跟踪，以便依次获得编号为 1、2、3、4、5 的矩形。请让我知道解决此问题的最佳方法是什么？是否有任何适合此问题陈述的可用模块？

而且，接下来的事情是，如果有多个端点，如何提出从单个开始到多个结束块的所有路径？

Answer 1

您可以构建一个图表来模拟这个问题。对于每个矩形，考虑一个节点，如果这个矩形与任何其他矩形有连接，则它们的代表节点有一条连接它们的边。
然后你可以使用深度优先搜索来遍历这个图，看看是否有从开始三角形到结束三角形的路径。

triangles = [(2, 3, 5, 6), (5, 6, 10, 11)]
adj = []
for i in range(len(triangles)):
    adj.append([])
    triangle1 = triangles[i]
    for j in range(i):
        triangle2 = triangles[j]
        if overlap(triangle1, triangle2):
            adj[i].append(j)
            adj[j].append(i)
start = 0 # Any triangle that has overlap with starting point
end = 1 # Any triangle that has overlap with ending point
dfs(start, end): # A DFS function to check is there a path from start to end, and prints the path found.

该算法具有O(N^2) 复杂度。其中n是三角形的数量。