6. Создание объединенных областей и проверка достижимости

Проверим достижимость q⁰ и q^T на основе связанных укрупненных областей (ETFR) в соседних плоскостях из матрицы ELCR. Целью этого является соединить все области находящиеся в различных плоскостях в единую область (рис. 16а) или несколько единых областей (рис. 16б) и установить, принадлежат ли точки q⁰ и q^T хотя бы одной единой области (только в этом случае они достижимы), или они принадлежат различным областям (в этом случае они недостижимы и дальнейшее построение маршрута не имеет смысла).

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

а) б)

Рисунок 16 (а) – единая область, (б) – две единых области в пространстве

Единые области будем помещать в матрицу TUR (Table of United Region – Таблицу Единых Областей), каждую новую единую область в новую строку матрицы.

1) Исходя из координат, узнаем в какой плоскости находятся q⁰ и q^T , а также какой строке матрицы ETFR принадлежат эти точки.

2) Определим области, в которой находятся точки.

2.1) Начнем с поиска в таблицах свободных областей TFR_i и TFR_j где i и j – номера плоскостей в которой находятся соответственно точки q⁰ и q^T. В TFR_i ищем, на пересечении какой строки и какого столбца находится область, содержащая q⁰. В TFR_j ищем, на пересечении какой строки и какого столбца находится область, содержащая q^T.

2.2) Затем ищем какой строке матрицы LCR_i принадлежит q⁰, какой матрице LCR_j принадлежит q⁰ основе полученных данных из TFR_i и TFR_j .

2.3) Найдем из матрицы ETFR те объединения свободных областей, которым принадлежат точки, на основе полученных данных из LCR. Другими словами, определим в какой строке ETFR_i находится укрупненная область, содержащая q⁰ , в какой строке ETFR_j находится укрупненная область содержащая q^T.

2.4) На основе данных матрицы ELCR будем соединять ETFR_i и ETFR_j:

2.4.1) Проверим, с какими соседними областями из (k+1)-ой плоскости имеют соединение укрупненные области из k-ой плоскости, где k=1,…,K-1 – номер плоскости на основе данных из матрицы ELCR. Объединим их в одну или несколько единых областей по следующим критериям:

2.4.1.1) Если хотя бы в одном узле свободные области этих плоскостей можно соединить между собой, то укрупненные области можно объединить в одну единую область и тогда из укрупненной области на k-ой плоскости можно перейти в область на (k+1)-ой плоскости. В этом случае в текущую объединенную область (строку матрицы TUR) запишем номера объединяемых плоскостей и номер объединяемых областей, как элементы матрицы одной строки TUR в следующем формате:

- номер строки – номер единой области;

- № плоскости k (№ строки ETFR_k, № строки ETFR_k,…) – элементы матрицы;

2.4.1.2) Если существует такая укрупненная свободная область (одна из строк матрицы ETFR_k), которая не может быть соединена или соединяется с другой свободной областью, которая не включена в текущую (формирующуюся в данный момент) единую область, то образуется другая (пока временная) единая область (новая строка матрицы TUR)

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

2.4.2) Внесем изменения в матрицу TUR и рассмотрим следующие плоскости (строку матрицы ELCR) и т.д. пока не будут рассмотрены все плоскости (все строки матрицы ELCR);

Например, для матриц ETFR:

И матрицы ELCR:

матрица TUR будет иметь вид:

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

4) В случае если совпадающие пути не найдены, значит точки принадлежат различным единым областям. Поэтому точки считаются недостижимыми и следующий этап алгоритма, поиск маршрута, не проводится.

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

Построим матрицу TUR и проверим достижимость q⁰ и q^T:

Так как точки q⁰ и q^T принадлежат одной единой области, то они достижимы.

Рисунок 17 - Создание объединенных областей