РАЗЛОЖЕНИЕ ПРЯМОУГОЛЬНОГО ЛАБИРИНТА БЕЗ ДЫР В СИСТЕМУ ПРЯМОУГОЛЬНИКОВ

Автор: Белоус Ю.А., Грунский И.С.
Источник: «Проблемы информатики и моделирования» - 2012 / Тезисы XII международной научно – технической конференции. — Харьков, НТУ «ХПИ — 2011», С. 3.

Предложен новый алгоритм решения следующей задачи: пусть задано слово обхода v по внешнему контуру прямоугольного выпуклого лабиринта в коде Фримена n, s, o,w. Требуется построить систему прямоугольников, покрывающих этот лабиринт без их пересечения.

Алгоритм заключается в пошаговом выделении из v максимального по размеру прямоугольника, в который входит верхняя горизонтальная граница лабиринта, содержащая рабочую точку, и формировании нового обхода оставшейся части лабиринта и новой рабочей точки. Это выполняется до тех пор, пока v не станет пустым.

Шаги работы алгоритма:

1) Из начала слова v выделяем o^k до смены буквы, и из конца слова – n^l до смены буквы, т.е. получим слово v = o^k v' n^l, из которого выделяем s^t. Рабочая точка равна (0,0).

2) Если l < t, то переходим к 3 пункту. Если l > t, то переходим к пункту 4.

3) l < t. Формируем прямоугольник П(k, l), который описывается количеством k ребер по оси x и количеством l ребер по оси y. Проверяем угол на выпуклость/вогнутость. Если угол вогнутый – переходим к пункту 3.1, иначе к пункту 3.2.

3.1) Угол вогнутый. Формируем новый обход: имеющееся слово v = o^k s^t v'' o^r n^l заменяем новым словом v = o^k+r s^t-l v" и формируем координаты новой рабочей точки (– r, l).

3.2) Угол выпуклый. Формируем новый обход: исходное слово v = o^k s^t v'' w^r n^l заменяем новым словом v = o^k-r s^t-l v" и формируем координаты новой рабочей точки (r, l).

4) l > t. Формируем прямоугольник П(k,t). Проверяем угол на выпуклость/вогнутость. Если угол выпуклый – переходим к пункту 4.1, а иначе к пункту 4.2.

4.1) Угол выпуклый. Формируем новый обход: имеющееся слово v = o^k s^t w^r v'' n^l заменяем новым словом v = o^k-r v" n^l-t и формируем координаты новой рабочей точки (0, t).

4.2) Угол вогнутый. Формируем новый обход: имеющееся слово v = o^k s^t o^r v'' n^l заменяем новым словом v = o^k+r v" n^l-t и формируем координаты новой рабочей точки (0,t).

5) Если длина слова v равна 0, то алгоритм заканчивает работу, иначе – переходим к пункту 1.