Автоматическая трассировка по существующему скелету для Autocad (оптимизируем код общими усилиями)

NEDIS · 13.09.2010, 13:10

Доброго времени суток коллеги.
Хочу поделиться наработками по программке.
Сразу хочу попросить сильно меня не пинать в плане грамотности написания кода, начал изучать LISP только с весны этого года, благодаря dwg.ru. Наверняка я наделал неподъемную кучу косяков, поэтому очень рад буду выслушать рекомендации по оптимизации и рад буду любой оказываемой помощи.
Хочу выразить благодарность всем чьи наработки я использовал в частности: Кулику Алексею (aka kpblc), VVA и hwd (и остальных участников форума, кого я забыл упомянуть в силу своей некомпетентности).

Алгоритм Флойда (Проба пера).
Немного о содержимом:
1. Два файла Lisp Команды и Функции
2. DWG файл с планировками и тестовыми закладными устройствами «скелетами» по которым выполняется трассировка полилиниями.
3. Команды:
a. NEDIS-input-system-for-tracing – Команда создает набор примитивов по которым будет выполняться трассировка, обрабатывает эти примитивы и выдает конечные матрицы для трассировки.
b. NEDIS-tracing-point-to-point - Трассировка точка-точка (выбор пользователя).
4. Функции:
a. NDS-start-finish-for-Floyd - Находит ближайший примитив, точку пересечения с ним и узлы для трассировки
b. NDS-manipulation-for-Floyd - Создает определенного вида списки для дальнейшей обработки функцией NDS-solution-matrix-Floyd (Работает только с LWPOLYLINE и LINE)
c. NDS-solution-matrix-Floyd - Создает и решает матрицу Флойда и матрицу маршрутов (алгоритм взят от сюда http://khpi-iip.mipk.kharkiv.edu/lib.../din_0124.html )
d. NDS-tracing - Выполняем трассировку (т.е. находим кротчайший путь по matrica-route-end, проверяя возможность такого пути по matrica-floyda-end (не должен рассматриваемый элемент быть равен "NO") получаем список узлов оптимального маршрута)
e. dwgru-geom-point-on-line - Проверяет принадлежность точки отрезку
f. pln - Создает полилинию по списку вершин lst, c - nil/T - разомкн/замкнт или '(с слой цвет)
5. Логику работы программ объяснять не буду, старался внутри все пояснять. По мере обсуждения буду «повествовать» почему делал так.
6. Основная проблема кроется в функции NDS-solution-matrix-Floyd шибко долго она решает Вариант 1 планировки. Вообщем-то это и понятно, так как чем больше точек для построения матрицы Флойда тем больше циклов оня будет проделовать (а их три и они все внутри друг друга). Над оптимизацией сам не работал, сильно загружен по работе.

Алгоритм Дейкстры (Проба пера-2).
Оказался наиболее шустрым.
Некоторые нюансы:
1. Иногда вылетает ошибка типа переменной (непосредственно уже при трассировке) – думаю где-то намутил с обработкой списков (не разбирался), надеюсь с помощью однофорумчан ее решить.
2. Полилиния не должна сама себя пересекать, функция не увидит такую точку пересечения и, как следствие, не будет создано корректное разрешение для этой точки
Отличая от предшественника:
1. Взамен NDS-manipulation-for-Floyd пришел NDS-manipulation-for-Dijkstra с соответствующими доработками, сильно его не менял – времени нету, но укоротить код можно прилично для быстродействия.
2. По замечаниям более опытных коллег убрал лишние setq.
3. NDS-solution-Dijkstra – создает разрешения для точек (от куда куда можно) все загоняет в одномерный массив (список).
4. NDS-tracing-all-in-one – функция определяет из 4-х вариантов трасс (1 – стартовая точка, ближайший узел справа от стартовой точки, … , ближайший узел справа от финишной точки, финишная точка; 2 - стартовая точка, ближайший узел слева от стартовой точки, … , ближайший узел справа от финишной точки, финишная точка; и т.д) наиболее короткую.

Ну вот такой винегрет получился

.

Vov.Ka · 13.09.2010, 22:50

Offtop: я бы посоветовал использовать Autodesk Map

zamtmn · 14.09.2010, 07:30

Vov.Ka
Хороший совет... я бы понял если Map был бы бесплатен. а так он вообщето совсем не про то.

NEDIS · 14.09.2010, 09:42

Цитата:

Сообщение от Vov.Ka

Offtop: я бы посоветовал использовать Autodesk Map

Offtop: MAP не знаю и времени особо тоже нет его осваивать, есть какие-нибудь руководства толковые?

Vov.Ka · 14.09.2010, 19:43

zamtmn, разница в цене между чистым акадом и мапом 10%, и почти все прибамбасы мапа пригодятся любому чертежнику

NEDIS, если есть возможность установить мап, то посмотри здесь http://www.theswamp.org/index.php?to...6521#msg366521
функция SolveLabyrinth ищет кратчайший маршрут по выбранным линиям

NEDIS · 15.09.2010, 14:59

Так ... 13 просмтров архива и ниодного отголоска чего и как, у всех то работают команды? И как быстро?

Цитата:

Сообщение от Vov.Ka

NEDIS, если есть возможность установить мап, то посмотри здесь http://www.theswamp.org/index.php?to...6521#msg366521
функция SolveLabyrinth ищет кратчайший маршрут по выбранным линиям

Интересная ссылочка, а вообще есть какой-нибудь user guide (желательно на русском)?

zamtmn · 15.09.2010, 20:22

>>Так ... 13 просмтров архива и ниодного отголоска чего и как, у всех то работают команды? И как быстро?

Работают. NEDIS-input-system-for-tracing - как я понял строит граф? почему так медленно?

ShaggyDoc · 16.09.2010, 07:18

Цитата:

13 просмтров архива и ниодного отголоска чего и как

Так там всякие матрицы-шматрицы, да еще какого-то бродяги Флойда.

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

Чисто по коду, не вникая в алгоритмы.

1. В целом написано грамотно, работа большая проделана, интересная. Разделены функции и команды. Но:

2. Режут глаз многочисленные последовательные setq. "Хочется рвать и метать, рвать и метать!" (С). Это делает код плохочитаемым (на глаз "лиспера", а не "сиониста" или "басикиста"). Кроме того, последовательный вызов setq замедляет работу. Это каждый раз загрузка, разбор аргументов и прочее. В обычных программах это некритично, а в такой, да еще с многочисленными вложенными циклами, значительно влияет на скорость.

Сравним

Код:

[Выделить все]

(while
				(> (length spisok-all-vershin) 0)
				(progn
					(setq vershina-N (car spisok-all-vershin))
					(setq spisok-all-vershin (vl-remove vershina-N spisok-all-vershin))
					(setq spisok-vershin (vl-list* vershina-N spisok-vershin))
				)
			)

с вариантом:

Код:

[Выделить все]

(while
  (> (length spisok-all-vershin) 0)
	(setq vershina-N (car spisok-all-vershin)
	        spisok-all-vershin (vl-remove vershina-N spisok-all-vershin)
                spisok-vershin (vl-list* vershina-N spisok-vershin)
       )
)

Избавились от вызова progn и двух вызовов setq. И от связанных с этим "накладных расходов". А таких мест в программе множество.

3. Запросы с помощью get-функций надо защищать от прерывания или неправильного ввода. Если пользователь введет что-то не то, не так или не введет - будут ошибки и всё псу под хвост. Или коту.

Дима_ · 16.09.2010, 08:38

Цитата:

Сообщение от NEDIS

Так ... 13 просмтров архива и ниодного отголоска чего и как, у всех то работают команды? И как быстро?

А что ты хочешь, чтоб тебе написали о программе которая не понятно чего делает? Хочешь совет поставь грамотно вопрос. По коду - оптимизация бывает двух типов на уровне кода и алгоритма - вторая ГОРАЗДО важней - а по ней-то как раз и сказать нечего - т.к. - конечная задача не ясна. По коду - там полно "детских болезней" (без обид), но в целом в правильном направлении - например - в том-же куске кода, который приводит ShaggyDoc есть комбинация:

Код:

[Выделить все]

(while (> (length spisok-all-vershin) 0)...

здесь идет явное не понимание сути списка - список это не массив - чтоб посчитать его длинну надо пройтись по всем его элементам (то есть по сути выполнить количество cdr'ов равных длинне списка), а все, что с ним делается - это сравнивается равна ли его длинна нулю (примерно то же самое, что Вы бы проверяли "больше-ли одного шага шагать до Камчатки все время перешагивая все расстояние"). И делается это на каждом шагу.
Эта конструкция "без потерь" меняется на

Код:

[Выделить все]

(while spisok-all-vershin ...

так как nil и '() в лиспе - синонимы.
p.s. дальше рассказывать не буду т.к. тут затрагиваються гораздо более "глубокие вещи" в целом, повторюсь, совсем не плохо.
p.p.s У тебя прослеживаеться "неправильный" для лиспа императивный подход - работать с ПЕРЕМЕННОЙ в ЦИКЛЕ, оба понятия "аттавизм" в лиспе почитай что такое функциональное программирование, аргументы и рекурсия.

ShaggyDoc · 16.09.2010, 10:02

Цитата:

Эта конструкция "без потерь" меняется на

Совершенно верно. Тоже хотел написать, но отвлекся и не выкинул из своего примера

Жалко, куда то sir Alaspher пропал. Вот уж он любит код оптимизировать!

И по алгоритму. Не вникал. Но матрицы у меня вызывают подозрение. Это "вузовский" подход. Но в практике часто оказывается, что и без них гораздо проще обойтись, особенно если обработку приходится самому писать. Особенно на LISP

Вот мой любимый пример шедевра Лиспа:

Цитата:

(defun ru-list-Douglas-Wilson-transpose (lst)
;|
Здесь мы используем функцию транспонирования списка
по алгоритму Дугласа Вильсона (Douglas Wilson)
http://xarch.tu-graz.ac.at/autocad/lisp/
|;

(apply 'mapcar (cons 'list lst))
)

Всего одна строчка, но трансформирует список. Грубо говоря колонки и строки "матрицы" местами меняет.

NEDIS · 16.09.2010, 12:51

Цитата:

Сообщение от ShaggyDoc

Так там всякие матрицы-шматрицы, да еще какого-то бродяги Флойда. Мало кому интересна такая частная, редкая задача. По которой только сам автор знает, чего он хочет.

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

Цитата:

Сообщение от ShaggyDoc

3. Запросы с помощью get-функций надо защищать от прерывания или неправильного ввода. Если пользователь введет что-то не то, не так или не введет - будут ошибки и всё псу под хвост. Или коту.

Приведи пример если не трудно

.

Цитата:

Сообщение от Дима_

А что ты хочешь, чтоб тебе написали о программе которая не понятно чего делает? Хочешь совет поставь грамотно вопрос. По коду - оптимизация бывает двух типов на уровне кода и алгоритма - вторая ГОРАЗДО важней - а по ней-то как раз и сказать нечего - т.к. - конечная задача не ясна. По коду - там полно "детских болезней" (без обид), но в целом в правильном направлении - например - в том-же куске кода, который приводит ShaggyDoc есть комбинация:

Я понимаю, что косяков кучу наделал и алгоритм взял не оптимальный (или реализовал не оптимально).
Суть идеи следующая:
Создается набор примитивов, этот набор обрабатывается и создается несколько списков 1- всех вершин и 2 – «разрешения» узлов, где можно «сворачивать», далее все это компонуется в матрицу Флойда (сам его случайно в инете нашел), эта матрица решается и выдает результат из какой точки в какую можно попасть по кротчайшему пути если не возможно то элементу присваивается «NO» если возможно то присваивается длина трассы между этими точками.

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

Do$ · 16.09.2010, 13:35

Даже с представленным чертежом не могу понять, что делают программы NEDIS-input-system-for-tracing и NEDIS-tracing-point-to-point

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

NEDIS · 16.09.2010, 13:38

Цитата:

Сообщение от Do$

Даже с представленным чертежом не могу понять, что делают программы NEDIS-input-system-for-tracing и NEDIS-tracing-point-to-point

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

Вечером сделаю видео

.

P.S. NEDIS-input-system-for-tracing - рамка, необходимо выделить этаж после расчета выполняется трассировка командой NEDIS-tracing-point-to-point ввод 1 или 2 взависимости от предлогаемого условия трассировки.
P.S.S. А с анализаторами ошибок я вообще не работал еще, мне бы вычисления ускорить.

ShaggyDoc · 16.09.2010, 14:37

Цитата:

Приведи пример если не трудно

А что если, в момент запроса точки пользователь нажмет ESC? Нажмет Enter? Напишет нехорошее слово?

Все примеры я привел в книге САПР на базе AutoCAD - как это делается. Для любого ввода делается специальная функция, которая работает абсолютно надежно.

Например, если требуется ввод обязательной точки используется функция

Код:

[Выделить все]

(defun ru-get-point-reguired (message base_point)

                             ;|
Запрос ввода точки с обязательным указанием

(ru-get-point-reguired "Вторая точка" (trans (getpoint "\nПервая точка: ") 1 0))
(ru-get-point-reguired "Вторая точка"  nil)

|;

  (trans (_ru-get-with-default
           message
           nil
           'getpoint
           1
           nil
           (if (ru-is-point base_point)
             ;; base_point всегда в WCS переводим
             ;; в ПСК для getpoint
             (trans base_point 0 1)
             base_point
           ) ;_ end of if
           nil
         ) ;_ end of _ru-get-with-default
         1
         0
  ) ;_ end of trans
) ;_ end of defun

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

Код:

[Выделить все]

(defun ru-get-point-or-exit (message keywords / result)
                            ;|
(ru-get-point-or-exit "Первая точка" "Начало Образец" (list)
(ru-get-point-or-exit "Первая точка" nil)
|;

  (if (ru-is-point
        (setq result (_ru-get-with-default
                       message "Выход" 'getpoint nil keywords nil T) ;_ end of _ru-get-with-default
        ) ;_ end of setq
      ) ;_ end of ru-is-point
    (trans (ru-conv-point-to-3d-point result) 1 0)
    result
  ) ;_ end of if
) ;_ end of defun

И еще несколько десятков подобных. И все они используют низкоуровневую функцию

Код:

[Выделить все]

(defun _ru-get-with-default (message
                             default_str
                             quoted_get_func
                             initget_param
                             keywords
                             base_point
                             esc_enabled
                             /
                             result
                             question
                             lst_params
                             key_str
                             alt_key_str
                             alt_word
                             lst_alt_words
                             lst_words
                            )
                            ;|

Выполняет функцию quoted_get_func с возможностью получения значения
по умолчанию
Параметры:
message - строка запроса
default_str - строка, выводящаяся в <default_str>
quoted_get_func - имя getxxx-функции с апострофом
initget_param - биты для initget или nil
keywords - ключевые слова для initget или nil
base_point - базовая точка или nil в ПСК!!!

Возвращает значение, ключевое слово или nil

|;
 (setq key_str ""
       alt_key_str
       " _"
       lst_alt_words
       '()
 ) ;_ end of setq

 

 (if keywords
  (progn
   (setq lst_words (ru-string-to-list keywords " "))
   (foreach word lst_words
    (setq key_str       (strcat key_str
                                word
                                (if (/= word (last lst_words))
                                 "/"
                                 ""
                                ) ;_ end of if
                        ) ;_ end of strcat
          alt_word      (ru-conv-string-win-translit word)
          lst_alt_words (cons alt_word lst_alt_words)
          alt_key_str   (strcat alt_key_str
                                alt_word
                                (if (/= word (last lst_words))
                                 " "
                                 ""
                                ) ;_ end of if
                                " "
                        ) ;_ end of strcat
    ) ;_ end of setq
   ) ;_ end of foreach
   (setq key_str       (ru-string-format "[%1]" key_str)
         lst_alt_words (reverse lst_alt_words)
   ) ;_ end of setq
  ) ;_ end of progn
 ) ;_ end of if
 (if default_str
  (setq question (ru-string-format
                  "\n%1  %2<%3>:"
                  (list message key_str default_str)
                 ) ;_ end of ru-string-format
  ) ;_ end of setq
  (setq question
        (ru-string-format "\n%1  %2:" (list message key_str))
  ) ;_ end of setq
 ) ;_ end of if
 (if base_point
  (setq lst_params (list base_point question))
  (setq lst_params (list question))
 ) ;_ end of if
 ;;------------- Новый цикл с возможностью esc ------------
 (setq end nil)
 (while
   (not end)
   (ru-error-catch
    (function (lambda ()
        (cond ((and initget_param keywords)
               (initget initget_param (strcat keywords alt_key_str))
              )
              ((not (null initget_param))
               (initget initget_param)
              )
              ((not (null keywords))
               (initget (strcat keywords alt_key_str))
              )
        ) ;_ end of cond

        (setq result (vl-catch-all-apply quoted_get_func lst_params)
              end T)
          result      
                      
              ) ;_ end of lambda
    ) ;_ end of function
    ;;Это выполняется при ошибке
      (function
       (lambda (msg)
        (if esc_enabled
         (setq result nil
               end t
         ) ;_ end of setq
         (progn 
         (princ "\nЗдесь прерывание по ESC недопустимо!")
          (setq ;;result nil
               end NIL
         )
         )
        ) ;_ end of if
        (princ)
       ) ;_ end of lambda
      ) ;_ end of function
 
   ) ;_ end of ru-error-catch
 ;;------------- Новый цикл с возможностью esc ------------

 ) ;_ end of while
 ;; а здесь бы и вернуть "настоящее" ключевое слово. Чтобы не в каждой программе анализировать
 ;; Но обратный транслит не сделать, надо сопоставлять списки
 ;; есть lst_words  
 ;; (vl-position "A" (list "A" "B" "F"))
 (if
  (ru-is-string result)
  (setq result (nth (vl-position result lst_alt_words) lst_words))
 ) ;_ end of if
 (if (ru-is-point result)
  (setq result (ru-conv-point-to-3d-point result))
 ) ;_ end of if
 result
) ;_ end of defun

Она выполняет любую get* в возможностями задавать ключевые слова, значения по умолчанию и прочее нужное.

Но, для начала, при использовании get-функций необходимо приучиться использовать initget.

zamtmn · 16.09.2010, 15:01

>>Автоматическая трассировка по существующему скелету для Autocad (оптимизируем код общими усилиями)

оптимизировать тут нужно не код, а алгоритм. что NEDIS-input-system-for-tracing делает такого, что результата ее работы невозможно дождаться на исходных данных чуть сложнее чем в примере?

NEDIS · 16.09.2010, 15:37

Цитата:

Сообщение от zamtmn

>>
оптимизировать тут нужно не код, а алгоритм. что NEDIS-input-system-for-tracing делает такого, что результата ее работы невозможно дождаться на исходных данных чуть сложнее чем в примере?

Матрицу маршрутов решает, а решает очень медленно. Нужно скорее всего подход к решению марицы поменять, как честно не знаю

(алгоритм).

ShaggyDoc

Цитата:

Сообщение от zamtmn

А что если, в момент запроса точки пользователь нажмет ESC? Нажмет Enter? Напишет нехорошее слово?

В будующем учту, сейчас все таки больше меня мучает скорость решения матрицы.

zamtmn · 17.09.2010, 09:40

>>Матрицу маршрутов решает, а решает очень медленно. Нужно скорее всего подход к решению марицы

я с методом флойда не знаком, что значит решает? заранее ищет все возможные маршруты?

NEDIS · 17.09.2010, 09:57

Цитата:

Сообщение от zamtmn

>>я с методом флойда не знаком, что значит решает? заранее ищет все возможные маршруты?

Обсалютно точно - создает матрицу которая содержит информацию из какой точки (любой) в какую (любую) и через какие можно быстро попасть.

ShaggyDoc · 17.09.2010, 11:27

Цитата:

Сообщение от NEDIS

Обсалютно точно - создает матрицу которая содержит информацию из какой точки (любой) в какую (любую) и через какие можно быстро попасть.

Вот в этом и "корень зла". Матрица ведь не сама "знает". Её надо заполнить - по большей части заведомо ненужными данными. А потом их анализировать. И всё это в многочисленных циклах...

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

Менять надо алгоритм. Забыть вообще про матрицу и действовать простыми методами. Вообще про "математические методы" забыть.

PS. Несколько лет назад форумчанин Lexa разработал программу автоматической трассировки кабелей в 3D. Задавались фиксированные точки в пространстве ("хомуты") в виде окружностей, через центр которых должна была оптимально пройти трасса. И не просто точки отбирались, а трасса вычерчивалась, да еще с учетом радиуса гнутья кабеля и "запретных" мест. Всё работало достаточно точно и быстро. Никакой "высшей математики", только "арихметика Магницкого". Так как подобные задачи могут не иметь оптимального решения (просто длина маршрута не всегда главный показатель), во время работы её можно было "направить". Чтоб не искала путь из Иркутска на Камчатку через Бердичев. К сожалению, Lexa теперь Автокадом не занимается...

zamtmn · 17.09.2010, 12:27

>>Обсалютно точно - создает матрицу которая содержит информацию из какой точки (любой) в какую (любую) и через какие можно быстро попасть.

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

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

Дима_ · 17.09.2010, 12:31

Цитата:

Сообщение от ShaggyDoc

Вообще про "математические методы" забыть.

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

ShaggyDoc · 17.09.2010, 14:29

Цитата:

Сообщение от Дима_

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

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

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

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

Поиск кратчайшего пути разными способами выполняется. Есть много отработанных алгоритмов. В том числе не "математических".

NEDIS · 17.09.2010, 14:29

Цитата:

Сообщение от ShaggyDoc

Вот в этом и "корень зла". Матрица ведь не сама "знает". Её надо заполнить - по большей части заведомо ненужными данными. А потом их анализировать. И всё это в многочисленных циклах...

На выходных постараюсь реализовать следующий метод http://inf.1september.ru/2000/7/art/danil.htm "3. Бектрекинг на графе, заданном перечислением вершин и ребер". Никаких вложенных циклов и матриц тем более, вроли комнат буду выступать имена примитивов вида <Имя объекта: 7ef54b70>. Надеюсь все будет шустро

методом "Проб и ошибок", так сказать погуляем по "скелету". Единственное - это надо будет делать на каждой итерации трассировки.

P.S. Не помню ... есть какая-нибудь LISP-функция, которая находит все примитивы пересекаемые с заданным ?

Дима_ · 17.09.2010, 15:12

Цитата:

Сообщение от NEDIS

P.S. Не помню ... есть какая-нибудь LISP-команда, которая находит все примитивы пересекаемые с заданным ?

в прямую нет, но можно взять границы примитива (vla-getboundingbox...) и по этим точкам отсечь рамкой, далее отфильтровать набор через (vla-intersectwidth...) но это только при условии нечастого использования - ибо если в цикле - каждая такая итерация - достоточна ресурсоемка.

ShaggyDoc · 17.09.2010, 19:39

NEDIS, в дополнение к алгоритму стоит подумать о порядке ввода точек (комнат). Это математически они могут быть как угодно перемешаны, а в реальном объекте они группируются. Например, ответвление "коридора", или "этаж".

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

И конкретную задачу лучше бы уточнить. Все-таки "две больших разницы" поиск кратчайших маршрутов и

Цитата:

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

Здесь все проще. Трасса каналов задана. Её автоматически не проложишь - масса "непрограммируемых" условий. А вот нарисовать каждую линию от шкафа до каждого порта гораздо легче. Заодно длины рассчитать и прочее.

Я сам такое делал.

NEDIS · 18.09.2010, 14:15

Цитата:

Сообщение от ShaggyDoc

Трасса каналов задана. Её автоматически не проложишь - масса "непрограммируемых" условий.

Именно так трасса каналов задана и только после этого выполняется автоматическая трассировка "порт - шкаф"

ShaggyDoc · 18.09.2010, 18:23

Цитата:

Сообщение от NEDIS

Именно так трасса каналов задана и только после этого выполняется автоматическая трассировка "порт - шкаф"

Тогда зачем вся эта математика? Описываете геометрию трассы, как это принято во всяких гидравлических расчетах:

1. Обозначаете как-то все порты и точки "перекрестков" (можно, для простоты, целыми числами, хотя удобнее "по-человечески", прямо обозначениями портов).

2. Описываете топологию сети - какая точка с какой соединяется. Вот здесь простор для фантазии. Хотя, с учетом того, что в СКС не разветвлений, это легче - можно легко описать маршруты.

3. Вычисление координат каждого маршрута. Сначала, для простоты, берете осевую линию трассы. А потом для каждого кабеля с учетом смещения на некоторое расстояние, лучше на реальное - порядка 5 мм. Можно с учетом габарита канала, в несколько ярусов. Здесь можно и постараться избежать повторных расчетов участков с несколькими кабелями.

4. Рисование каждого кабеля полилинией. Если надо - присоединение информации (окуда, куда и прочее) в виде расширенных данных для каких-то других расчетов.

zamtmn · 18.09.2010, 19:38

>>Тогда зачем вся эта математика? Описываете геометрию трассы, как это принято во всяких гидравлических расчетах:

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

NEDIS · 18.09.2010, 21:27

Цитата:

Сообщение от zamtmn

единственное место для полета фантазии - как представить граф средствами лиспа и нарисовать примитивами автокада.

Абсолютно согласен. Без построения графа (двумерной матрицы) и ее решения в поиске оптимального (наикротчайшего) пути не обойтись.

Цитата:

Сообщение от ShaggyDoc

Тогда зачем вся эта математика? Описываете геометрию трассы, как это принято во всяких гидравлических расчетах:

Так я ее и описываю - графом которой потом решаю.

zamtmn · 19.09.2010, 03:34

>>Без построения графа (двумерной матрицы) и ее решения в поиске оптимального (наикротчайшего) пути не обойтись.

если я правильно понял двумерная матрица получится размера кол-во узлов X кол-во узлов? это очень неэкономично - связей мало, соответственно матрица почти вся заполнена нулями. лучше 2 одномерных массива, один узлы (+возможно примыкающие связи), другой связи с примыкающими узлами и весами

NEDIS · 19.09.2010, 11:42

Цитата:

Сообщение от zamtmn

>>Без построения графа (двумерной матрицы) и ее решения в поиске оптимального (наикротчайшего) пути не обойтись.

если я правильно понял двумерная матрица получится размера кол-во узлов X кол-во узлов? это очень неэкономично - связей мало, соответственно матрица почти вся заполнена нулями. лучше 2 одномерных массива, один узлы (+возможно примыкающие связи), другой связи с примыкающими узлами и весами

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

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

Дима_ · 19.09.2010, 12:38

Цитата:

Сообщение от NEDIS

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

Можно - по хорошему переменных быть не должно вообще - в твоем коде прослеживаеться "не правильный" подход - изменение переменной внутри цикла - по хорошему функция не должна обращаться ни к каким "внешним" переменным - тем более для их установки - есть аргументы, есть возврат. В автолиспе с рекурсией надо быть внимательным - т.к. не поддерживаеться т.н. "хвостовая рекурсия"; при начальном уровне для "многовложенных" функций, как правило, проще mapcar, хотя рекурсия безусловно более функциональна. Если есть сложность с построением - напиши разберем.

Sleekka · 19.09.2010, 13:41

трассировка http://ru.wikipedia.org/wiki/%D0%A2%...D0%B8%D1%8F%29
достаточно общее понятие, можно вкратце объяснить, что в этой программе трассируется, для какой отрасли?

zamtmn · 19.09.2010, 16:51

>>И как найти оптимальную (самую короткую)
>>трассу без связей i-узла с j-узлом по двум одномерным массивам?

это алгоритм Дейкстры - http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры. реализация данного алгоритма на паскале работает без видимых задержек на сложных трассах (в разумных пределах - проверено на разделах ОПС довольно сложных зданий).

NEDIS · 19.09.2010, 22:30

Цитата:

Сообщение от Дима_

Если есть сложность с построением - напиши разберем.

Вот с чем основная загвостка:

Код:

[Выделить все]

(setq num1 0 num2 0 num3 0)
	(setq matrica-floyda-end matrica-floyda-start matrica-route-end matrica-route-start)
	; num1 - k, num2 - i, num3 - j 
	(while
		(<= num1 (- (length spisok-vershin+X) 1))
		(setq num2 0)
		(while
			(<= num2 (- (length spisok-vershin+X) 1))
			(setq num3 0)
			(while
				(<= num3 (- (length spisok-vershin+X) 1))
				(if
					(and (/= num1 num2) (/= num2 num3) (/= num1 num3))
					(if
						(or
							(and
								(/= (cadr (assoc (strcat (itoa num2) "-" (itoa num1)) matrica-floyda-end)) "NO")
								(/= (cadr (assoc (strcat (itoa num1) "-" (itoa num3)) matrica-floyda-end)) "NO")
								(/= (cadr (assoc (strcat (itoa num2) "-" (itoa num3)) matrica-floyda-end)) "NO")
								(>
									(cadr (assoc (strcat (itoa num2) "-" (itoa num3)) matrica-floyda-end))
									(+
										(cadr (assoc (strcat (itoa num2) "-" (itoa num1)) matrica-floyda-end))
										(cadr (assoc (strcat (itoa num1) "-" (itoa num3)) matrica-floyda-end))
									)
								)
							)
							(and
								(/= (cadr (assoc (strcat (itoa num2) "-" (itoa num1)) matrica-floyda-end)) "NO")
								(/= (cadr (assoc (strcat (itoa num1) "-" (itoa num3)) matrica-floyda-end)) "NO")
								(= (cadr (assoc (strcat (itoa num2) "-" (itoa num3)) matrica-floyda-end)) "NO")
							)
						)
						(setq
							matrica-floyda-end
							(subst
								(list
									(strcat (itoa num2) "-" (itoa num3))
									(+
										(cadr (assoc (strcat (itoa num2) "-" (itoa num1)) matrica-floyda-end))
										(cadr (assoc (strcat (itoa num1) "-" (itoa num3)) matrica-floyda-end))
									)
								)
								(assoc (strcat (itoa num2) "-" (itoa num3)) matrica-floyda-end)
								matrica-floyda-end
							)
							matrica-route-end
							(subst
								(list
									(strcat (itoa num2) "-" (itoa num3))
									(itoa num1)
								)
								(assoc (strcat (itoa num2) "-" (itoa num3)) matrica-route-end)
								matrica-route-end
							)
						)
					)
				)
				(setq num3 (+ num3 1))
			)
			(setq num2 (+ num2 1))
		)
		(setq num1 (+ num1 1))
		(princ (strcat "\nПриступил к решению матриц Флойда и Маршрутов. Решено --> " (itoa (/ (* 100 (+ num1)) (- (length spisok-vershin+X) 1))) " %\n"))
	)

Вот что я набросал для внутреннего цикла num3 (типо рекурсивная функция) - естественно не работает

:

Код:

[Выделить все]

(defun NDS-recursion-num3 (num1 num2 num3 spisok-vershin+X matrica-floyda-end)
	(if
		(= num3 0)
		matrica-floyda-end
		(if
			(or
				(and
					(/= (cadr (assoc (strcat (itoa num2) "-" (itoa num1)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end))) "NO")
					(/= (cadr (assoc (strcat (itoa num1) "-" (itoa num3)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end))) "NO")
					(/= (cadr (assoc (strcat (itoa num2) "-" (itoa num3)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end))) "NO")
					(>
						(cadr (assoc (strcat (itoa num2) "-" (itoa num3)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end)))
						(+
							(cadr (assoc (strcat (itoa num2) "-" (itoa num1)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end)))
							(cadr (assoc (strcat (itoa num1) "-" (itoa num3)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end)))
						)
					)
				)
				(and
					(/= (cadr (assoc (strcat (itoa num2) "-" (itoa num1)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end))) "NO")
					(/= (cadr (assoc (strcat (itoa num1) "-" (itoa num3)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end))) "NO")
					(= (cadr (assoc (strcat (itoa num2) "-" (itoa num3)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end))) "NO")
				)
			)
			(subst
				(list
					(strcat (itoa num2) "-" (itoa num3))
					(+
						(cadr (assoc (strcat (itoa num2) "-" (itoa num1)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end)))
						(cadr (assoc (strcat (itoa num1) "-" (itoa num3)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end)))
					)
				)
				(assoc (strcat (itoa num2) "-" (itoa num3)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end))
				NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end)
			)
		)
	)
 )

Дима_ · 20.09.2010, 00:43

Не вникая что такое матрица флойда - смотрю твой рекурсивный пример:
1. (= num3 0) -> (zerop num3);
2. (if (or (and много вычислений)
(and мало вычислений)
); конец or
я не вникал, но вначале надо проверять то, что более вероятно является условием выхода и если равновероятно - то начинать надо с меньшего кол-ва вычислений (быстрее).
3. NDS-recursion-num3 ..... -> забыт запуск функции - нет "(" она видимо перед num1
4. у функции 5 аргументов а вызываешь ты ее с 4 (даже если ошибку с "фуyкцией" num1 убрать - а вобще сейчас 1 получаеться).
5. если у тебя num1 и num2 внутри этой функции не меняются, то зачем на них все время одинаковые вычисления (itoa) делать одного раза будет достаточно.
6. зачем ты передаешь рекурсивно первичную матрицу - наверное там должен быть результат assoc.

NEDIS · 22.09.2010, 16:12

Цитата:

Сообщение от zamtmn

это алгоритм Дейкстры - http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры. реализация данного алгоритма на паскале работает без видимых задержек на сложных трассах (в разумных пределах - проверено на разделах ОПС довольно сложных зданий).

Честно говоря когда выбирал алгоритм, то как раз и рассматривал алгоритмы Флойда и Дейкстры

. Выбрал Флойда (сработало Русское "Все и сразу"

). Сейчас поменял алгоритм трассировки с Флойда на Дейкстры.

Вывод: все считает шустро - таких проблем как с Флойдом, используя даже "неправильный" для LISP-а императивный подход, замечено не было. Спасибо Sleekka за наставление.

Обновил топик. Добавил новые функции.

В ближайшие дни скомпоную все в отдельные функции (для удобства), ну и соответственно переделаю команду NEDIS-tracing-point-to-point под новые функции.

Eddicordo · 10.11.2010, 12:32

Прикольно. Авто трассировка Алгоритм Дейкстры мне напомнила Карту Украины или Киева.
Где указываешь точку А и точку В. (Указать кратчайший путь для проезда автомобилем по дороге от точки А до точки В. Плюс показать длину этого пути.)
Но с запуском вашей программы ничего не понятно.
Да еще Кад висит

NEDIS · 10.11.2010, 14:36

Цитата:

Сообщение от Eddicordo

Прикольно. Авто трассировка Алгоритм Дейкстры мне напомнила Карту Украины или Киева.
Где указываешь точку А и точку В. (Указать кратчайший путь для проезда автомобилем по дороге от точки А до точки В. Плюс показать длину этого пути.)
Но с запуском вашей программы ничего не понятно.
Да еще Кад висит

Что именно не понятно?

P.S. На трех машинах разной кофигурации запускал - все считает шустро, проблем не замеченно.

Eddicordo · 11.11.2010, 11:05

NEDIS, Все разобрался. Это я загрузил сразу 2 алгоритма. Вот и подвисло.
Но чет странно при команде NEDIS-tracing-point-to-point путь находит вроде бы правильно. А вот поллинию налаживает со сдвигом. То есть не точно по указанному скелету.
Это у тебя как пример показаны отрезки ну очень огромные. Ты начерти отрезки по 10-100 мм. и увидишь не точности.

Да и при команде NEDIS-input-system-for-tracing наши отрезки должны быть именно в том слое !!SS_zakl_gofra_25.
Неудобство в том что при указании наших отрезков они уже должны быть в нужном слое.
Был бы неплохо что бы при указании нашего скелета из отрезков все что мы выделяем само переносилось в нужный нам слой.
И выделение рамкой скелета ну очень не удобно. А выделить ВСЕ, по моему никому и не нужно.
Выделение должно быть указание конкретного отрезка клац, дольше клац., если надо, выделение стандартным методом рамкой справа на лево выделяется все что вошло в рамку ну и слево на права как у Вас сейчас.

Создал свои отрезки присвоил им твой слой !!SS_zakl_gofra_25.
Указываю NEDIS-input-system-for-tracing

Код:

[Выделить все]

Команда:
Активируйте способ выбора закладных устройств:
      1. Выбор всех устройств на активном листе Модель
      2. Выбор рамкой необходимых мне устройств
2
Выделите фрагмент в рамках которого будет выполняться трассировка
Restoring System variables
Application aborted: неверный тип аргумента: numberp: nil

Для выделение корректней использовать вот такой код

Код:

[Выделить все]

            ;(setq    pt1 (getpoint "\nВыделите фрагмент в рамках которого будет выполняться трассировка")
                ; getcorner - рисует "резиновую" рамку (стр. 89);


(if (null (setq pt1 (ssget '((0 . "INSERT") (66 . 1)))))
    (setq
      pt1 (ssget
           "_X"
           (list '(0 . "INSERT") '(66 . 1) (cons 410 (getvar "CTAB")))
         ) ;_ end of ssget
    ) ;_ end of setq
  ) ;_ end of if



                pt2 (getcorner pt1)
            ;)

Но почему то, так не находит наш скелет

Frigate · 11.11.2010, 20:23

Eddicordo,

если надо только линии (LINE) на определенном слое "!!SS_zakl_gofra_25" выделить рамкой, то вставь такой код:

Код:

[Выделить все]

(ssget "_:L" (list '(0 . "LINE")  '(8 . "!!SS_zakl_gofra_25")))

если и линии, и полилинии, то такой:

Код:

[Выделить все]

(ssget "_:L" (list '(-4 . "<OR") '(0 . "LINE") '(0 . "LWPOLYLINE") '(-4 . "OR>")  '(8 . "!!SS_zakl_gofra_25")))

NEDIS · 13.11.2010, 14:19

Цитата:

Сообщение от Eddicordo

Но чет странно при команде NEDIS-tracing-point-to-point путь находит вроде бы правильно. А вот поллинию налаживает со сдвигом. То есть не точно по указанному скелету.
Это у тебя как пример показаны отрезки ну очень огромные. Ты начерти отрезки по 10-100 мм. и увидишь не точности.

Это связано с округлением координат до 10E-6, при дальнейших монипуляциях конечная трасса будет отклоняться от скелета max +/- 0,5 ед. автокада. Дело в том, что когда писал все это одновременно и изкчал LISP и столкнулся с тем, что один и тот же список координат может прочитать по разному: т.е. х=0.12345679 а при следующей обработке я получал 0.12345680 т.е. появлялась ошибка, которую я решил округлением. Вообще я все функции и команды на НГ перебиру и постараюсь решить эту проблему.

Цитата:

Сообщение от Eddicordo

Да и при команде NEDIS-input-system-for-tracing наши отрезки должны быть именно в том слое !!SS_zakl_gofra_25.
Неудобство в том что при указании наших отрезков они уже должны быть в нужном слое.

Я создал свою панель закладных устройств гофра, лоток, уголки и т.д. при нажатии соответсвующей кнопки у меня создается/активируется необходимый слой, тип линии. Т.е. уже при начерталке у меня все в нужных слоях.

Цитата:

Сообщение от Eddicordo

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

Тут уже все зависит от потребностей каждого

мне шаговое выделение неудобно. Но и предусмотреть еще один цикл набора примитивов тоже не проблема ... да и перенести выбранные примитивы на другой слой тоже не составляет труда. Вообщем если надо то сделаем

Цитата:

Сообщение от Eddicordo

Выделение рамкой скелета ну очень не удобно. А выделить ВСЕ, по моему никому и не нужно.

Тут не согласен: я связист (по сути) мне из точки А в точки в кучу точек надо кучу кабелей протащить (отчертить трассы), и если я буду каждый раз делать набор опорных примитивов для трассировки я с ума сойду

. Про выделение ВСЕ: у меня есть блоки слаботочные розетки в них есть атрибуты (в том числе координата расположения) есть шкафы (тоже блоки с атрибутами). Настроив розетки (к какому шкафу принадлежит) и дав имена шкафам я выбираю все закладные, а дальше запускаю мою команду по трассировке розеток, т.е. идет считывание ее координаты, далее куда трассируем и вперед - для всех в цикле. Кучу времени экономлю (хотя откровенно бывают глюки, но это исправлю со временем).

P.S. Пока я пробую свою недоделку в проектах (выявляю зихеры), дальше: дороботка, изменения и отладка.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Создание форм и шрифтов для AutoCAD	Shoorup	AutoCAD	6	25.01.2013 17:43
Информация по идентификационным кодам программ в сетевых лицензиях Autodesk	KSI	AutoCAD	1	14.09.2009 15:59