[amadey18]

Добрый день.

Задача состоит в том что бы найти оптимальный путь трассировки платы.
Прочитал кучу алгоритмов по трассировке, но как применить хотя бы один из них на ЛИСПе не понимаю...
например есть схема соединения элементов

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

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

может кто нибудь сталкивался с похожими задачами поиска оптимального пути. Помогите составить какой нибудь алгоритм, или код работы данной программки.

[Дима_]

Сообщение от amadey18 Прочитал кучу алгоритмов по трассировке, но как применить хотя бы один из них на ЛИСПе не понимаю...

Что вы понимаете под словом "прочитал" - посмотрел на код на елезнакомом диалекте или разобрался с принципом. Если второе - то что конкретно не получается реализовать в автолиспе, если первое - то вначале следует разобратся, что писать, а уж потом "браться за шашки".

[amadey18]

Сообщение от Дима_ Что вы понимаете под словом "прочитал" - посмотрел на код на елезнакомом диалекте или разобрался с принципом. Если второе - то что конкретно не получается реализовать в автолиспе, если первое - то вначале следует разобратся, что писать, а уж потом "браться за шашки".

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

при этом он должен проверять занята ли следующая ячейка или нет.
значит в автокаде ячейками будут являться точки привязки.

как организовать проверку на наличие чего либо на пути я примерно понял, используя функцию ssget загоняем в набор круги(контактные площадки) и полилинии(уже проведенные трассы), используя фильтр, затем вытаскиваем данные из набора в список, проверяем на пересечение, если есть, то значит на пути объект, который нужно обойти.
когда на пути больше нет объектов, то нарисовать поверх этих точек линию.
загвоздка возникла в организации рисования линии(т.е. волны), в каком направлении она пойдет(вверх, вниз, вправо, влево), при этом ее по идее не должно быть видно.

[Дима_]

Сообщение от amadey18 как организовать проверку на наличие чего либо на пути я примерно понял, используя функцию ssget загоняем в набор круги(контактные площадки) и полилинии(уже проведенные трассы), используя фильтр, затем вытаскиваем данные из набора в список, проверяем на пересечение, если есть, то значит на пути объект, который нужно обойти.

Я бы не стал проверять по "физическому" наличию линий и окружностей. Тут надо 1 раз прочитать данные, построить на ее основе мат. модель и прогнать выбранный алгоритм по ней, а по результату уже нарисовать трассы (1 раз)- т.к. как не оптимизируй, а перибирать тут придется не слабо, а если Вы этот "перебор" чертить будете, да еще и потом смотреть что начертили (програмно) - работать будет подобная программа до пенсии (если раньше fatal не словит).
з.ы. в вышеприведенном алгоритме, по моим прикидкам, при построении "волны" список будет "крайне неэффективен", а т.к. это единственный "родной" тип коллекций в АВТОлиспе, то стоит задуматся о смене либо алгоритма, либо языка.

[Елпанов Евгений]

по алгоритмам, я бы посоветовал не пытаться сразу создавать идеальную трассировку!
Думаю, наиболее простым решением будет первоначальная трассировка с плохим результатом.
Далее, написать несколько программ улучшайзеров, которые будут улучшать текущую трассировку по какому нибудь параметру, при этом, возможно ухудшать трассировку в целом.
Все эти программы можно будет запустить единой программе по принципам генетического алгоритма, те. поставить проверку лучше/хуже, запускать все программы по очереди и смотреть результат. Если программа делает хуже, отменяем действие...

Для создания простейшей трассировки, думаю достаточно все прорисовать вертикально - горизонтально и при получении пересечений сразу делать новый слой для удаления пересечения.
В качестве улучшайзеров, можно использовать переброску на один слой, когда задача сводится к удалению пересечения между двумя линиями. Укорачивание трассы - убрать лишние петли итд. В целом, не вижу огромных трудностей по реализации.

ps. Поддерживаю Дима_, не вижу смысла помогать в этой теме, если amadey18 сам не пишет кодов, только ждет результатов. Эта задача для меня понятна, но ее решение, лично мне, совершенно не нужно. Удачи!