Алгоритм трассировки соединений по магистралям

В данном алгоритме можно отказаться от использования дискретного представления поля.
Из двух контактов выпускаются два луча, которые будем называть магистралями. Эти магистрали - M₁^A и M₁^B - магистрали первого уровня. Если они пересекаются, то трасса найдена. Если нет, то на данных магистралях находятся базовые точки и уже из них выпускаются магистрали второго уровня и так далее, пока не будет найдено пересечение либо не будет превышен предел на уровень магистрали.
После нахождения пересечения магистралей выбирается пересечение по отрезку наименьшей длины до точки испускания. Так, если в точке P пересекаются магистрали 1-го и 2-го уровней, а в точке Q - пересекаются две магистрали второго уровня, то для проведения трассы следует выбрать точку P.

	1	2	3	4	5	6	7	8
1				А
2
3
4							В
5
6
7
8

Пример:

Из пересечений выбираем то, которое соединяет А и В (полное наименьшее по длине).

Лучевой алгоритм трассировки соединений.

1) Из каждого из двух контактов, подлежащих соединению, формируются по два луча во взаимно перпендикулярных направлениях. Для каждого из четырех лучей задается приоритетное направление распространения. Если лучи, испускаемые из разных контактов, пересекаются, то трасса найдена.

2) Если пересечение не найдено, лучи испускаются из клеток, пересечённых лучами из первого контакта.

2) Если пересечение опять не найдено, лучи испускаются из клеток, пересечённых лучами из второго контакта.

3) Продолжаются повторения пунктов 2 и 3, пока не будет найдено пересечение.

Пример:

Приоритеты:

1) Из А выпускаются лучи вправо и вниз.

2) Из В выпускается луч вверх и влево.

1) Из А выпускаются лучи вниз и вправо.

2) Из В выпускаются лучи влево и вверх.

С помощью такого подхода разводится 80% трассы.

Когда размещено мало элементов, затраты данного алгоритма много меньше затрат волнового алгоритма.

			канал