4. Объединение свободных соединенных областей
Объединение соединенных областей происходит на основе матриц TFR и LCR для соединения свободных областей на каждой плоскости между собой. В результате на каждой плоскости будут получены одна или несколько объединенных областей, изолированных друг от друга. Внутри каждой из этих областей можно будет перемещаться от любой точки A к любой точке B, двигаясь пошагово на один дискрет (т.е. каждая область является связанной) (можно свободно перемещаться в пределах области). А переходить из одной изолированной объединенной области в другую на j-ой плоскости будет нельзя.
1) Создадим на основе матриц LCR новую матрицу – ETFR (Extension TFR) матрицу объединенных свободных областей для каждой плоскости.
2) Для этого поместим в матрицу ETFR номер первой строки матрицы LCR. Если в матрице LCR существуют другие пути (количество строк больше 1), то произведем сравнение путей в матрице LCR по значениям в столбцах.
2.1) Если в хотя бы одном i-ом столбце значения в j-ой и j+k строке совпадают, где j – это уникальный обнаруженный путь (первый считается уникальным по умолчанию), k=1, …, j-1, то в матрицу ETFR на j-ой строке следует добавить текущий номер пути (строки) матрицы LCR. Рассмотрим все i столбцов для всех пар j и j+k по ходу исключая из дальнейшего рассмотрения те области j+k, которые совпали с j-ой.
Например:
если матрица LCR
имеет вид
,
то матрица ETFR
будет иметь
вид
,
так как для путей представленных в
первой и второй строке матрицы LCR
первая ячейка этой плоскости общая т.к.
и строка 1, и строка 2 содержат общий
элемент в своем первом столбце, поэтому
мы можем первый и второй путь матрицы
LCR
объединить в общую область и записать
номера этих строк в одной строке матрицы
ETFR.
Третья строка матрицы LCR
уникальна, так как элементы этой строки
не совпадают с остальными строками по
столбцам. Поэтому сформируем новую
строку матрицы ETFR
и запишем в неё 3 - номер строки уникального
пути LCR.
Количество строк в матрице ETFR говорит о числе изолированных свободных областей.
2.2) Если обнаружен полностью уникальный путь, не совпадающий с предыдущим, то номер этой строки заносится в следующую строку матрицы ETFR. Заканчивается поиск общих областей для первого уникального пути, а затем начинается поиск совпадений для следующего уникального пути, исключая из рассмотрения те области, которые уже были найдены как совпадение раньше.
2.3) Если были найдены все уникальные пути и рассмотрены все возможные совпадения путей в матрице LCR, то переходим к построению ETFR для следующей матрицы LCR начиняя с шаг 1.
Матрица ETFR для примера (рис. 5, таблица 2) приведенного в предыдущих пунктах будет образована следующим образом:
Возьмем первую строку матрицы LCR2,I, как уникальный путь и запишем её номер в первую строку матрицы ETFR. Рассмотрим вторую строку. Сравним её с первой, сравнивая их значения по столбцам.
,
Уже в первом столбце их значения совпадают. Поэтому запишем в первую строку матрицы ETFR и номер второй строки матрицы LCR2,I Полученная матрица ETFR будет иметь вид:
,
что означает существует одно объединение свободных областей в котором есть два пути, которые представлены в 1-ой и 2-ой строке матрицы LCR.
Рассмотрим пример матриц ETFR для трехмерного случая, который представлен на рисунке 4. Матрица TFR для этого случая приведена в Таблице 3. Объединение свободных областей для каждой плоскости представлено на рисунке 14.
Построим матрицы ETFR для каждой плоскости:
|
|
|
Рисунок 14 - Объединение свободных областей