7. Построение маршрута

Если в результате работы алгоритма получено, что q^т достижима, тогда применяем единую область (строку) из матрицы TUR для построения маршрута.

1) Возьмем путь достижимости из матрицы TUR и на его основе будем двигаться от свободной области (строки) матрицы ETFR, которая включает в себя q⁰, к свободной области (строки) матрицы ETFR, которая включает в себя q^т, т.е. движение в матрице TUR будет происходить с права налево или слева направо. Чтобы определить это, надо найти каким элементам матрицы TUR (строкам матрицы ETFR) принадлежат q⁰ и q^T. Для этого выполним следующие шаги:

1.1) Определим, какой матрице TFR и LCR принадлежат точки.

1.2) Исходя из этой информации, и номеров плоскостей, в которых находятся эти точки, можно определить какой строке матрице ETFR они принадлежат.

1.3) Благодаря полученным данным найдем элемент матрицы TUR и определим направление, в котором они (объединенные свободны области) будут последовательно рассматриваться.

2) Рассмотрим все возможные области соединения в этих соседних областях (из матрицы ELCR). Из матрицы ELCR определим до каких областей из которых возможен переход в другую плоскость (если это необходимо для достижения q^т) можно совершить меньше всего шагов в соответствии с путем LCR, используя методом уменьшения разницы координат. Для этого сделаем следующие шаги:

2.1) Определим какой матрице TFR и LCR принадлежит текущая точка.

2.2) Определим какой строке матрицы LCR принадлежит точка перехода на другую плоскость.

2.3) Определим количество шагов которые необходимо сделать, чтобы достичь из текущей точкой областей перехода между плоскостями из матрицы ELCR или q^т (если эта последняя плоскость), двигаясь по соединенным областям в одной плоскости (из матрицы LCR) путем смещения по свободной области в ячейке (которые можно получить из TFR) пока не достигнем свободной области в соседней ячейке, затем переходим на следующую ячейку и смещаемся по ней и т.д.

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

Изменяем разницу координат так, чтобы свести её к нулю по каждой координате в соответствии со следующими приоритетами шага:

2.3.1) Изменить (+/-) три координаты xyz за один шаг

2.3.2) Изменить две координаты за шаг xy || xz || yz за шаг

2.3.3) Изменить одну координату x || y || z за шаг

2.4) Проверяем условие: Если по одной или двум из координат разница сведена к нулю, то соответственно приоритеты 2.3.1 и 2.3.2 не рассматриваются. Если все разницы сведены к нулю, то

- соседняя ячейка достигнута. Если есть еще ячейки, согласно матрице LCR, в которые необходимо сделать переход, чтобы достигнуть области перехода в другую плоскость, то стремимся к новой разнице между ячейками, переходим к шагу 2.3;

- область перехода в другую плоскость достигнута, переходим к шагу 2.5;

- q^т (в случае если q^т лежит в рассматриваемой плоскости, последнем элементе строки достижимости в матрице TUR) достигнута, переходим к шагу 2.6;

2.5) Перейдем на шаг 2.2 и рассмотрим следующую свободную область, из которой возможен переход в другую плоскость, пока не будут рассмотрены все свободные области.

2.6) Сравним полученные значения и выберем минимальное количество шагов необходимое для достижения области перехода на другую плоскость.

3) Сделаем шаг(и) и сместим текущую точку к области перехода на другую плоскость. Перейдем на другую плоскость.

4) Повторим шаги начиная с первого пока не будет достигнута последняя объединенная область матрицы TUR в которой находится точка q^т. Если она достигнута, то перейдем к шагу 2.1, чтобы придти в q^т.

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

Построим маршрут:

№ шага	Координата: плоскость, строка TFR, столбец TFR, номер узла (снизу вверх)	Количество шагов
1	1, 1, 1, 3 1, 3, 2, 3 Так как эти шаги равнозначны, то выберем первый	1 1
2	2, 1,1, 2	1
3	3, 2,1, 1 qT достигнута	1

Рисунок 18 – Построение маршрута