Russian Qt Forum
Ноябрь 01, 2024, 08:23
Добро пожаловать,
Гость
. Пожалуйста,
войдите
или
зарегистрируйтесь
.
Вам не пришло
письмо с кодом активации?
1 час
1 день
1 неделя
1 месяц
Навсегда
Войти
Начало
Форум
WIKI (Вики)
FAQ
Помощь
Поиск
Войти
Регистрация
Russian Qt Forum
>
Forum
>
Qt
>
2D и 3D графика
>
Соединение двух точек "проводами"
Страниц:
1
[
2
]
Вниз
« предыдущая тема
следующая тема »
Печать
Автор
Тема: Соединение двух точек "проводами" (Прочитано 16735 раз)
kamre
Частый гость
Offline
Сообщений: 233
Re: Соединение двух точек "проводами"
«
Ответ #15 :
Март 04, 2015, 12:30 »
Цитата: Гурман от Март 04, 2015, 12:00
Делиться этим решением я никому не обещал и не планирую.
Жалко что ли, ведь всего "несколько дней" займет решние?
Ну хотя бы алгоритм и подход опишите, интересная же задача все-таки.
Записан
Гурман
Гуру общения
Offline
Сообщений: 1442
Qt 2.2, 3.3, 4.5, 4,7, 4.8, 5.3, 5.6, 5.9, 5.12
Re: Соединение двух точек "проводами"
«
Ответ #16 :
Март 04, 2015, 13:27 »
Без обхода "препятствий" и прочих заморочек с допустимостью прокладывания маршрута задача действительно тривиальная. Общее решение - это "черепашка", движущаяся по кратчайшему маршруту по сетке между двумя удаленными QPointF. Я решил хранить только QList<ConnectionSegment>, где ConnectionSegment это QGraphicsLineItem с будущими дополнительными возможностями (реакцией на события). Черепашка перед каждым шагом вычисляет наиболее выгодное направление следующего шага, одно из четырех возможных. Это просто - берем 4 соседние точки, и находим ту, расстояние от которой до целевой минимальное (таких 2, но одна найдется первой, и в моем случае это будет вариант по горизонтали). После чего рекурсивно делает шаг в этом направлении, то есть, переходит на соответствующую точку. При выполнении шага передается предыдущее направление (в виде целого числа от 0 до 3), и если при вычислении следующего шага оно не совпало с предыдущим - значит это поворот, его точка сохранятся в локальной переменной и взводится локальный флаг поворота. Если достигли конечной точки пути, то возврат из рекурсии и возвращаются координаты точки, от которой произошел возврат. Вызывающая функция получает их, и если у неё есть флаг поворота, то рисует отрезок от сохраненной точки поворота, до полученной, после чего возвращает свою точку поворота. Если флага поворота нет, то просто возвращает полученную из рекурсивного вызова точку (движение по прямой).
Таким образом, алгоритм рекурсивно проходит от начала к концу, находит точки поворота, и потом на возврате рисует отрезки. Поскольку у меня по задаче входы и выходы объектов всегда расположены слева и справа графических айтемов (никогда внизу или наверху), то без учета препятствий алгоритм будет рисовать линии только из 1-го, или 2-х отрезков. Но, как я уже сказал, это по задаче не нужно.
Гораздо сложнее, когда есть разнообразные препятствия. Характер этих препятствий разный, и отдельная проблема их правильно определять. Пока я учитываю только 2 типа препятствий - область на 1 шаг сетки больше границ каждого объекта, и недопустимость наложения линий на уже проложенные (допустимо только пересекать их под прямым углом). Основа алгоритма черепашки остается почти такой же, но в него вводится проверка допустимости шага и исключения недопустимых направлений. А также, если алгоритм заехал в тупик, то появляется дополнительный выход из рекурсии, с установкой флага запрещенного направления, и после каждого возврата алгоритм пытается заново определить выгодное направление, но то, в котором он побывал, становится запрещенным. Это всё значительно сложнее, поэтому я сейчас решаю именно эту задачу, и она не решается отдельно. Запрет пройденного направления "встроен" в простой алгоритм черепашки.
«
Последнее редактирование: Март 04, 2015, 13:29 от Гурман
»
Записан
2^7-1 == 127, задумайтесь...
Igors
Джедай : наставник для всех
Offline
Сообщений: 11445
Re: Соединение двух точек "проводами"
«
Ответ #17 :
Март 04, 2015, 13:51 »
Да, интересно. Я бы добавил "обрезку петель" (см малюнок)
Записан
Гурман
Гуру общения
Offline
Сообщений: 1442
Qt 2.2, 3.3, 4.5, 4,7, 4.8, 5.3, 5.6, 5.9, 5.12
Re: Соединение двух точек "проводами"
«
Ответ #18 :
Март 04, 2015, 15:07 »
Мой алгоритм в данном случае пойдет по синей линии. Хотя, конечно, могут быть случаи, когда оптимизация не повредила бы. Но за это заказчик должен будет дополнительно заплатить...
Записан
2^7-1 == 127, задумайтесь...
Igors
Джедай : наставник для всех
Offline
Сообщений: 11445
Re: Соединение двух точек "проводами"
«
Ответ #19 :
Март 04, 2015, 15:26 »
Ну то цветочки... А вот ягодки. Протянули красный, потом синий - все норм. Теперь надо тянуть зеленый, а как
Записан
Гурман
Гуру общения
Offline
Сообщений: 1442
Qt 2.2, 3.3, 4.5, 4,7, 4.8, 5.3, 5.6, 5.9, 5.12
Re: Соединение двух точек "проводами"
«
Ответ #20 :
Март 04, 2015, 16:22 »
Тут сетки нет, не видно, где можно пройти, где нет.
По идее, алгоритм "черепашки" с учетом препятствий - это почти тот же PacMan. В конце 90-х я его сам написал, у меня была своя версия PacMan для любого лабиринта, работал идеально, произвольные лабиринты можно было в текстовом редакторе рисовать. 4 "призрака" ловили ПакМана со 100% гарантией. То есть, алгоритм, который точно "найдет" целевую точку, я уже делал. Вот я по аналогии пытаюсь сейчас сделать, естественно, с использованием Qt. И рекурсивно, тот алгоритм был одноуровневым циклом.
Записан
2^7-1 == 127, задумайтесь...
Igors
Джедай : наставник для всех
Offline
Сообщений: 11445
Re: Соединение двух точек "проводами"
«
Ответ #21 :
Март 04, 2015, 17:53 »
Такая ситуевина возникает напр в некоторых алгоритмах триангуляции. На каждом шаге есть набор тр-ков который "оптимален". Приходит новая точка, попадает в 1 из тр-ков. Разбиваем его, но тогда набор тр-ков может стать неоптимален. Перестраиваем соседей, они становятся оптимальными, но могли зацепить своих соседей. Короче получается "волна", которая обычно быстро затухает. Ну в данном случае не знаю, с критерием оптимальности напряженка.
Записан
Гурман
Гуру общения
Offline
Сообщений: 1442
Qt 2.2, 3.3, 4.5, 4,7, 4.8, 5.3, 5.6, 5.9, 5.12
Re: Соединение двух точек "проводами"
«
Ответ #22 :
Март 04, 2015, 18:39 »
Я не видел ни одной 100% оптимальной реализации подобного роутинга в каком-либо софте, который его имеет. Хорошую детальную теорию по этому вопросу я не нашел даже на английском. Достаточно спросить у любого конструктора, которые пользуются Altium Designer (ex P-CAD), где это проработано лучше всего - все конструктора и радио-инженеры предпочитают рисовать схемы наполовину вручную, не говоря уже о разводке плат (я знаю их ответ, потому что работал с ними на соседнем этаже). Автоматические средства используют только для того, чтобы немного сэкономить время, не таскать все провода изначально. То есть, даже в этом дорогом коммерческом пакете автоматика не идеальна. Некая простая автоматическая оптимизация постфактум возможна, но наиболее эффективным будет возможностью пользователю редактировать сделанную автоматически разводку вручную. То есть, когда пользователь что-то соединяет, оно автоматом прокладывает линии, но если не понравилось, можно их поменять, создавая новые изгибы и двигая отрезки. Это тоже планируется. Увы, придётся еще колбасить сохранение и загрузку схем, чтобы детально все линии сохранялись.
«
Последнее редактирование: Март 04, 2015, 18:42 от Гурман
»
Записан
2^7-1 == 127, задумайтесь...
Igors
Джедай : наставник для всех
Offline
Сообщений: 11445
Re: Соединение двух точек "проводами"
«
Ответ #23 :
Март 04, 2015, 19:50 »
Цитата: Гурман от Март 04, 2015, 18:39
Я не видел ни одной 100% оптимальной...
Есть удобное стандартное объяснение
Цитировать
Well... nothing is perfect
Возражений нет, задача непростая. Но надо продумать "отходы" чтобы такой случай не стал фатальным. Напр ну не смог соединить одну. выдал месягу, зато остальные 100 все норм.
Да, и вот
Цитата: Гурман от Март 04, 2015, 12:00
И у меня нет дурацкой привычки пытаться перепрыгнуть овраг в два прыжка, если я знаю, что могу в один. Если кого-то сильно интересует - уже перелетел через середину оврага.
А овраг второй стороны может и не иметь
Записан
Гурман
Гуру общения
Offline
Сообщений: 1442
Qt 2.2, 3.3, 4.5, 4,7, 4.8, 5.3, 5.6, 5.9, 5.12
Re: Соединение двух точек "проводами"
«
Ответ #24 :
Март 04, 2015, 20:15 »
Цитата: Igors от Март 04, 2015, 19:50
надо продумать "отходы" чтобы такой случай не стал фатальным. Напр ну не смог соединить одну. выдал месягу, зато остальные 100 все норм.
Ну это банально. Разумеется, именно так и сделано. Если роутинг вернулся в начальную точку с ошибкой "тупик", ругается, что не смог провести линию, надо переместить объект. На будущее можно еще подумать над автоматическим перемещением объектов, если роутинг не выполнился.
Цитата: Igors от Март 04, 2015, 19:50
овраг второй стороны может и не иметь
я же сказал -
если я
знаю
, что могу в один
Записан
2^7-1 == 127, задумайтесь...
Igors
Джедай : наставник для всех
Offline
Сообщений: 11445
Re: Соединение двух точек "проводами"
«
Ответ #25 :
Март 05, 2015, 11:33 »
Ладно, по базовому алгоритму
Цитата: Гурман от Март 04, 2015, 13:27
Без обхода "препятствий" и прочих заморочек с допустимостью прокладывания маршрута задача действительно тривиальная. Общее решение - это "черепашка", движущаяся по кратчайшему маршруту по сетке между двумя удаленными QPointF.
...
Черепашка перед каждым шагом вычисляет наиболее выгодное направление следующего шага, одно из четырех возможных. Это просто - берем 4 соседние точки, и находим ту, расстояние от которой до целевой минимальное (таких 2, но одна найдется первой, и в моем случае это будет вариант по горизонтали). После чего
рекурсивно делает шаг в этом направлении,
то есть, переходит на соответствующую точку. При выполнении шага передается предыдущее направление (в виде целого числа от 0 до 3), и если при вычислении следующего шага оно не совпало с предыдущим - значит это поворот, его точка сохранятся в локальной переменной ...
...и дальше детали реализации.
Как-то "рыхло", не звучит какие же точки отбираются для рекурсии? Ну с тупиком ясно, но вот мы получили "какой-то путь", полный (от начала до конца), валидный, но необязательно лучший. Что дальше?
Записан
Гурман
Гуру общения
Offline
Сообщений: 1442
Qt 2.2, 3.3, 4.5, 4,7, 4.8, 5.3, 5.6, 5.9, 5.12
Re: Соединение двух точек "проводами"
«
Ответ #26 :
Март 05, 2015, 19:39 »
Всё там прозвучало, повторять не буду. Дальше на возврате из рекурсии он рисуется. И всё. Каждый сегмент будет ловить события мыши и путь будет позволять себя модифицировать. Больше пока ничего не надо.
Записан
2^7-1 == 127, задумайтесь...
Страниц:
1
[
2
]
Вверх
Печать
« предыдущая тема
следующая тема »
Перейти в:
Пожалуйста, выберите назначение:
-----------------------------
Qt
-----------------------------
=> Вопросы новичков
=> Уроки и статьи
=> Установка, сборка, отладка, тестирование
=> Общие вопросы
=> Пользовательский интерфейс (GUI)
=> Qt Quick
=> Model-View (MV)
=> Базы данных
=> Работа с сетью
=> Многопоточное программирование, процессы
=> Мультимедиа
=> 2D и 3D графика
=> OpenGL
=> Печать
=> Интернационализация, локализация
=> QSS
=> XML
=> Qt Script, QtWebKit
=> ActiveX
=> Qt Embedded
=> Дополнительные компоненты
=> Кладовая готовых решений
=> Вклад сообщества в Qt
=> Qt-инструментарий
-----------------------------
Программирование
-----------------------------
=> Общий
=> С/C++
=> Python
=> Алгоритмы
=> Базы данных
=> Разработка игр
-----------------------------
Компиляторы и платформы
-----------------------------
=> Linux
=> Windows
=> Mac OS X
=> Компиляторы
===> Visual C++
-----------------------------
Разное
-----------------------------
=> Новости
===> Новости Qt сообщества
===> Новости IT сферы
=> Говорилка
=> Юмор
=> Объявления
Загружается...