Блог

Существует много прямоугольников; каждый из них будет иметь нижние левые и верхние правые координаты. И они либо перекрываются (полностью или частично), либо касаются по крайней мере одного края с другим.

Я ищу, как создать трассировку от начальных до конечных блоков, последовательно отслеживая каждый прямоугольник. Допустим, есть идентификатор (координаты) как в начальном, так и в конечном блоках, который может указывать на то, что трассировка началась и закончилась.

На изображении ниже мне нужно проследить так, чтобы я получал прямоугольники, нумерация которых 1, 2, 3, 4, 5 последовательно. Пожалуйста, дайте мне знать, как лучше всего подойти к этому? и есть ли какие-либо уже доступные модули, которые вписываются в эту постановку задачи?

А также, следующее, если есть несколько конечных точек, как найти все пути, прослеженные от одного начального до нескольких конечных блоков?

Вы можете построить график, который моделирует эту проблему. для каждого прямоугольника рассмотрим узел, если этот прямоугольник имеет связь с любым другим прямоугольником, их представляющие узлы имеют ребро, соединяющее их.
Затем вы можете использовать поиск в глубину, чтобы пройти по этому графику и посмотреть, есть ли путь от начального треугольника до конечного треугольника.

 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 — количество треугольников.