Волновой алгоритм трассировки

Дискретное поле платы разбивают на три множества, описываемых с помощью булевых матриц:

С – множество элементов поля, требующих соединения между собой (на рисунке 4 множество , где i=0, 1, 2, 3);

Р – множество элементов поля, запрещенных для трассировки (на рисунке 4,а(б) это множество закрашено черным);

S – множество свободных элементов поля платы.

Требуется, используя элементы множества S, соединить элементы множества С в одну цепь, не пересекающую Р.

Процесс нахождения минимального пути состоит из двух этапов:

- Распространение волны от источника до встречи с одним из приемников;

- Определение пути от источника к приемнику.

В качестве источника выбирается один из элементов множества С, все остальные элементы являются приемниками. Обозначим через R_k множество элементов волны на шаге k и назовем его k-фронтом волны, тогда R_k+1 принадлежит Н-окрестности R_k.

На каждом шаге расширения делается проверка пересечения фонта волны с приемником. Как только какой-либо элемент приемника будет включен в волну, процесс распространения волны завершается, и от ближайшего к источнику элемента приемника начинается построение пути.

Для построения волны используются матрицы распространения волн в горизонтальном (R_k’), и вертикальном (R_k) направлении и матрицы точек поворота с вертикального направления на горизонтальное (M_k) и с горизонтального направления на вертикальное (M_k’), где

;

;

.

На рисунке 5, а - г приведены соответственно матрицы R_k, R_k’, M_k, M_k’, построенные для k=12. Источником является фрагмент С₀. Для наглядности в клетках, занятых волной, указывается номер шага, на котором достигнута эта точка.

На этапе построения пути определяется, каким фронтом достигнут приемник: горизонтальным или вертикальным. От элемента пересечения волны с приемником в направлении, соответствующему последнему фронту волны, определяем элементы, не принадлежащие множеству Р. При встрече с первым же элементом множества точек поворота рассмотренного направления движение прекращается. Все пройденные элементы включаются в искомый путь. Элемент встречи принимается за исходный для движения по другому фронту волны.

Направление чередуется таким образом до тех пор, пока не будет достигнут элемент источника.

На рисунке 5, д показан пример построения пути от приемника С₁ к источнику С₀. Стрелками показано направление движения. В дальнейшем процесс распространения волны повторяется с учетом построенного пути. Такой выбор источника обеспечивает ветвление цепи в любой ее точке.

Процесс заканчивается, когда все элементы С будут связаны в единую цепь (рисунок 5, е), либо когда оставшиеся элементы этого множества уже не могут быть присоединены к источнику.