Алгоритмы трассировки (стр. 2 из 2)
b) В каждом элементе излома проверяем значение двоичного кода ak и направление построения пути в наилучшем направлении. Если ak³0 и направление обхода препятствий совпадает с наилучшим направлением построения пути, то элемент dk будет элементом спуска. В противном случае dk не является элементом спуска.
Этап 3. Минимизация длинны пути сводится к построению выпуклого контура, описанного вокруг первоначального пути. Если нет возможности получить выпуклый контур из-за наличия препятствий, то строится сглаженный контур, т.е. контур, имеющий меньшую длину, чем первоначальный.
Находим все элементы спуска первоначального пути и разбиваем его на отдельные участки, разграниченные элементами спуска. Последовательно минимизируем все участки пути.
1) Находим все элементы излома соответствующего участка пути, и если имеется не более одного излома, то он не подлежит минимизации если элементов излома два и более, то минимизация заключается в том, что строится новый путь Lн(da, dj) пути L(da, dj), где dj- элемент излома пути, самый близкий к конечному элементу.
2) Построенный вновь подпуть Lн(da, dj) сравнивается по длине с путем L(da, dj), и если новый путь меньше, то L(da, dj) заменяется на Lн(da, dj).
3) Минимизация повторяется для следующего элемента излома, самого близкого к dj, и до тех пор, пока на Lн(da, dj) или L(da, dj) останется один элемент излома.
Осуществляется минимизация обоих первоначально построенных путей, полученных при положительном (левом) и отрицательном (правом) обходе группы препятствий, из которых выбирается минимальный
(рисунок 3).
2. Волновой алгоритм трассировки.
Дискретное поле платы разбивают на три множества, описываемых с помощью булевых матриц:
С – множество элементов поля, требующих соединения между собой (на рисунке 4 множество
, где i=0, 1, 2, 3);Р – множество элементов поля, запрещенных для трассировки (на рисунке 4,а(б) это множество закрашено черным);
S – множество свободных элементов поля платы.
Требуется, используя элементы множества S, соединить элементы множества С в одну цепь, не пересекающую Р.
Процесс нахождения минимального пути состоит из двух этапов:
- Распространение волны от источника до встречи с одним из приемников;
- Определение пути от источника к приемнику.
В качестве источника выбирается один из элементов множества С, все остальные элементы являются приемниками. Обозначим через Rk множество элементов волны на шаге k и назовем его k-фронтом волны, тогда Rk+1 принадлежит Н-окрестности Rk.
На каждом шаге расширения делается проверка пересечения фонта волны с приемником. Как только какой-либо элемент приемника будет включен в волну, процесс распространения волны завершается, и от ближайшего к источнику элемента приемника начинается построение пути.
Для построения волны используются матрицы распространения волн в горизонтальном (Rk’), и вертикальном (Rk) направлении и матрицы точек поворота с вертикального направления на горизонтальное (Mk) и с горизонтального направления на вертикальное (Mk’), где
; 
; 
.На рисунке 5, а - г приведены соответственно матрицы Rk, Rk’, Mk, Mk’, построенные для k=12. Источником является фрагмент С0. Для наглядности в клетках, занятых волной, указывается номер шага, на котором достигнута эта точка.
На этапе построения пути определяется, каким фронтом достигнут приемник: горизонтальным или вертикальным. От элемента пересечения волны с приемником в направлении, соответствующему последнему фронту волны, определяем элементы, не принадлежащие множеству Р. При встрече с первым же элементом множества точек поворота рассмотренного направления движение прекращается. Все пройденные элементы включаются в искомый путь. Элемент встречи принимается за исходный для движения по другому фронту волны.
Направление чередуется таким образом до тех пор, пока не будет достигнут элемент источника.
На рисунке 5, д показан пример построения пути от приемника С1 к источнику С0. Стрелками показано направление движения. В дальнейшем процесс распространения волны повторяется с учетом построенного пути. Такой выбор источника обеспечивает ветвление цепи в любой ее точке.
Процесс заканчивается, когда все элементы С будут связаны в единую цепь (рисунок 5, е), либо когда оставшиеся элементы этого множества уже не могут быть присоединены к источнику.