Распространение числовой волны

Образование очередного фронта волны начинается с присво-ения всем свободным, ранее не помеченным ячейкам, соседним с ячейками предыдущего фронта , веса .

Соседними с данной ячейкой могут быть ячейки двух видов:

1) Ячейки ДРП, которые имеют с ней общее ребро (рис.7.3):

; ; ; . Очередной фронт волны распространяется по четырем направлениям.

Рис.7.3.

2) Ячейки ДРП, которые имеют с ней хотя бы одну общую точку (рис.7.4) ; ; ; ; ; ; ; . Очередной фронт волны распространяется в свободные ячейки по восьми направлениям.

Рис. 7.4

Рассмотрим вначале 1-й случай.

Результат распространения волны от источника A представлен на рис.7.2. Между ячейками A и B существует путь длиной 13. Трасса пути показана на рис.7.5. В этом случае трассы прокладываются только под углами в 90^о.

Для сокращения числа поворотов пути на этапе проведения может быть принято следующее правило приоритета. При переходе от ячейки фронта к ячейке фронта следует, по возможности, сохранять направление, опреде-ляемое переходом от ячейки к ячейке .

Рис.7.5.

В данном случае вес, присваиваемый ячейке фронта , равен расстоянию этой ячейки от источника в ортогональной метрике.

Во втором случае результат распространения волны от того же источника A представлен на рис.7.6. Но здесь длина пути между ячейками AиB равна 8. Трасса пути показана на рис.7.7. Видим, что во втором случае трассы могут проводиться под любыми углами.

Чтобы исключить неопределенность при проведении пути для случая, когда несколько ячеек имеют одинаковый минимальный вес, вводят понятие путевых координат, задающих предпочтительность проведения трассы. Каждое направление кодируют двоичным числом по , где q – число просматриваемых соседних ячеек. При этом чем более предпочтительно то или иное направление, тем меньший числовой код оно имеет. Например, если задаться приоритетным порядком проведения пути сверху, справа, снизу и слева, то коды соответствующих путевых координат будут 00, 01, 10 и 11. Присвоение путевых координат производят на этапе распространения волны. При проведении пути движение от ячейки к ячейке осуществляют по путевым координатам.

В первом случае (рис.7.5) приоритетный порядок проведения пути задан: сверху, справа, снизу и слева. Во втором случае (рис.7.7) – сверху, с правого верхнего угла, справа, с правого нижнего угла, снизу, с левого нижнего угла, слева и с левого верхнего угла.

Рис.7.6. Рис.7.7.