Given the cordinates of rectangles, connect them to make path from start to end

Question

There are lot of rectangles ; each one will have lower left and upper right co-ordinates. And they are either overlapping (fully or partially ) or touching at-least one edge with other one.

Am looking for how to come up with a trace from start to end blocks by tracing each rectangles in sequence. Lets say there it an identifier (co-ordinates) both at start and end blocks, which can say that trace has started and ended.

In the image below, I need to trace such that i get rectangles numbering 1 , 2, 3, 4, 5 in sequence. Please let me know what is the best way to approach this ? and are there any already available modules which fits into this problem statement?

And also, next thing is , if there are multiple end points, how to come up with all the paths traced from single start to multiple end blocks ?

Answer 1

You can build a graph that models this problem. for every rectangle, consider a node, if this rectangle has connection with any other rectangle, their representing nodes have an edge connecting them.
Then you can use Depth First Search to traverse this graph and see if there is a path from start triangle to the end triangle.

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.

This Algorithm has O(N^2) Complexity. which n is the number of triangles.