5. Соединение свободных областей на соседних плоскостях

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

1) Рассмотрим строки матрицы ETFR_j j-ой плоскости и строки матрицы ETFR_j+1 j+1 плоскости, где j=1,…,m-1. Эти строки показывают объединенный маршрут на j-ой и j+1-ой плоскости, где значения обозначают номера строк путей матрицы LCR.

2) Сравним значения которые приведены в матрицах ETFR_j и ETFR_j+1 Для этого сравним значения таблиц TFR_j и TFR_j+1 сопоставляя свободные области в каждой ячейке:

2.1) Если найдены области свободные на двух плоскостях, тогда эти две плоскости считаются связанными через эти области, а именно:

2.1.1) Определим из матриц TFR для данных плоскостей координаты свободной области, через которую возможно объединение этих плоскостей путем сравнения свободных областей матриц TFR_j и TFR_j+1 по ячейкам. Могут возникнуть следующие условия:

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

- если свободная область (диапазон) в ячейках соответственно первой и второй плоскости не равны друг другу, то записываются координаты этой свободной области и меньший данный диапазон;

- если свободная область (диапазон) присутствует в ячейки одной из плоскостей, а в другой плоскости – отсутствует, то в матрицу ELCR в этом случае ничего не записывается;

2.1.2) Запишем в матрицу ELCR (Extension LCR) информацию в соответствующую строку (о 1-ой и 2-ой плоскости в 1-ую строку, о 2-ой и 3-ей плоскости во 2-ую строку и т.д.) об объединенных областях j и j+1 плоскости (номер строки, которые были определены в пункте 2.1.1) и координаты области соединения (которые были определены в пункте 2.1.3). А именно записывается:

- номер строки, в которую производится запись, говорит о том, что плоскость с этим номером связана с последующей плоскостью (1-ая и и 2-ая плоскость в первой строке, 2-ая и 3-я плоскость во второй строке и т.д.)

- в строку записываются координаты свободных областей, которые являются общими для i-ой и (i+1)-ой плоскости в формате (a,b)(c-d), где:

(a,b) – координаты свободной области;

a – номер ячейки (номер строки в матрице TFR);

b – номер пути (номер столбца в матрице TFR);

(с-d) – диапазон свободных узлов;

с – нижняя точка диапазона свободной области;

d – верхний точка диапазона свободной области;

2.1.3) Будем сравнивать все ячейки двух плоскостей между собой пока не будут проверены все соответствующие значения таблиц TFR_j и TFR_j+1 . В случае если не найдена ни одна общая свободная область между соседними плоскостями ни на одной ячейке, значит переход между этими плоскостями невозможен. В этом случае в матрицу ELCR записывается пустая строка.

Например, возьмем таблицы TFR_{1 ,} TFR₂ и TFR₃:

TFR1	TFR2	TFR3
1 2 1 1-2 2 1-1 3-3 3 1-1 3-3	1 2 1 1-3 2 1-1 3 1-1 3-3	1 2 1 1-3 2 1-1 3-3 3 1-3

Тогда матрица ELCR будет иметь вид:

2.2) Если проверены все значения таблиц TFR_j и TFR_j+1 ,то значение j увеличивается на единицу, пока не станет j=K-1, где K – количество плоскостей.

Рассмотрим пример матриц ELCR для трехмерного случая, который представлен на рисунке 4. Матрица TFR для этого случая приведена в Таблице 3. Соединение свободных областей на соседних плоскостях для каждой пары плоскостей представлено на рисунке 15.

Построим ELCR:

Рисунок 15 - Соединение свободных областей на соседних плоскостях