Проектирование печатных плат. Овчинников В.А - 20 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

20
если перекрываются соответствующие им прямоугольники.
При представлении цепи минимальным покрывающим деревом не-
обходимо определять, пересекается ли каждая пара ветвей этих деревьев.
Для пары ветвей при известных координатах вершин составляются урав-
нения прямых линий. Исследуя эти уравнения методами аналитической
геометрии, определяют возможность пересечения соответствующих со-
единений.
Вершины графа пересечений сопоставляются с соединениями
, ребра
устанавливают возможность их пересечения. Раскраска вершин графа бу-
дет правильной, если никакие смежные вершины не окрашены одним цве-
том. Минимальное количество цветов, которое необходимо для правиль-
ной раскраски, определяет число слоев МПП.
Перекрытие прямоугольников, построенных на вершинах цепей, или
пересечение минимальных покрывающих деревьев еще не означает, что
соответствующие цепи
нельзя протрассировать на одном слое без пересе-
чений.
При учете возможности проведения “конфликтующих” проводников
без пересечения за счет огибания распределение соединений по слоям мо-
жет быть сделано путем объединения проводников, идущих под некото-
рым углом друг к другу, в группы. Каждая такая группа затем трассируется
в своем слое.
Трассировка цепей выполняется
последовательно, и каждая проло-
женная трасса является препятствием для всех непроведенных. В связи с
этим большое значение приобретает задача нахождения последовательно-
сти проведения соединений в каждом слое. Сформулируем условия отсут-
ствия пересечений двух ребер и методику определения последовательно-
сти их проведения.
Рассмотрим два ребра u(i,j) и u(k,p). Их уравнения в параметрической
форме
для ребер u(i,j) и u(k,p) соответственно имеют вид
t = λ·t(i) + (1- λ)·t(j) t = μ·t(k) + (1 – μ)·t(p)
S = λ·S(i) + (1 – λ)·S(j) S = μ·S(k) + (1 – μ)·S(p)
где
λ=((t(k)-t(p))·(S(j)-S(p))–(S(k)-S(p))·(t(j)-t(p))/((t(k)-t(p))х
х(S(j)-S(i))–(S(k)-S(p)) (t(j)-t(i));
μ=((t(j)-t(p))·(S(j)-S(i))–(S(j)-S(p))·(t(j)-t(i))/((t(k)-t(p))х
х(S(j)-S(i))–(S(k)-S(p))·(t(j)-t(i)).
Ребра пересекаются, если 0 <= λ <= 1, 0 <= μ <=1.
На основании этого условия определяется список пересекающихся

Страницы