Соединение двух точек "проводами"

[kamre]

Делиться этим решением я никому не обещал и не планирую.

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

[Гурман]

Без обхода "препятствий" и прочих заморочек с допустимостью прокладывания маршрута задача действительно тривиальная. Общее решение - это "черепашка", движущаяся по кратчайшему маршруту по сетке между двумя удаленными QPointF. Я решил хранить только QList<ConnectionSegment>, где ConnectionSegment это QGraphicsLineItem с будущими дополнительными возможностями (реакцией на события). Черепашка перед каждым шагом вычисляет наиболее выгодное направление следующего шага, одно из четырех возможных. Это просто - берем 4 соседние точки, и находим ту, расстояние от которой до целевой минимальное (таких 2, но одна найдется первой, и в моем случае это будет вариант по горизонтали). После чего рекурсивно делает шаг в этом направлении, то есть, переходит на соответствующую точку. При выполнении шага передается предыдущее направление (в виде целого числа от 0 до 3), и если при вычислении следующего шага оно не совпало с предыдущим - значит это поворот, его точка сохранятся в локальной переменной и взводится локальный флаг поворота. Если достигли конечной точки пути, то возврат из рекурсии и возвращаются координаты точки, от которой произошел возврат. Вызывающая функция получает их, и если у неё есть флаг поворота, то рисует отрезок от сохраненной точки поворота, до полученной, после чего возвращает свою точку поворота. Если флага поворота нет, то просто возвращает полученную из рекурсивного вызова точку (движение по прямой).

Таким образом, алгоритм рекурсивно проходит от начала к концу, находит точки поворота, и потом на возврате рисует отрезки. Поскольку у меня по задаче входы и выходы объектов всегда расположены слева и справа графических айтемов (никогда внизу или наверху), то без учета препятствий алгоритм будет рисовать линии только из 1-го, или 2-х отрезков. Но, как я уже сказал, это по задаче не нужно.

Гораздо сложнее, когда есть разнообразные препятствия. Характер этих препятствий разный, и отдельная проблема их правильно определять. Пока я учитываю только 2 типа препятствий - область на 1 шаг сетки больше границ каждого объекта, и недопустимость наложения линий на уже проложенные (допустимо только пересекать их под прямым углом). Основа алгоритма черепашки остается почти такой же, но в него вводится проверка допустимости шага и исключения недопустимых направлений. А также, если алгоритм заехал в тупик, то появляется дополнительный выход из рекурсии, с установкой флага запрещенного направления, и после каждого возврата алгоритм пытается заново определить выгодное направление, но то, в котором он побывал, становится запрещенным. Это всё значительно сложнее, поэтому я сейчас решаю именно эту задачу, и она не решается отдельно. Запрет пройденного направления "встроен" в простой алгоритм черепашки.

[Igors]

Да, интересно. Я бы добавил "обрезку петель" (см малюнок)

[Гурман]

Мой алгоритм в данном случае пойдет по синей линии. Хотя, конечно, могут быть случаи, когда оптимизация не повредила бы. Но за это заказчик должен будет дополнительно заплатить... 

[Igors]

Ну то цветочки... А вот ягодки. Протянули красный, потом синий - все норм. Теперь надо тянуть зеленый, а как

[Гурман]

Тут сетки нет, не видно, где можно пройти, где нет.

По идее, алгоритм "черепашки" с учетом препятствий - это почти тот же PacMan. В конце 90-х я его сам написал, у меня была своя версия PacMan для любого лабиринта, работал идеально, произвольные лабиринты можно было в текстовом редакторе рисовать. 4 "призрака" ловили ПакМана со 100% гарантией. То есть, алгоритм, который точно "найдет" целевую точку, я уже делал. Вот я по аналогии пытаюсь сейчас сделать, естественно, с использованием Qt. И рекурсивно, тот алгоритм был одноуровневым циклом.

[Igors]

Такая ситуевина возникает напр в некоторых алгоритмах триангуляции. На каждом шаге есть набор тр-ков который "оптимален". Приходит новая точка, попадает в 1 из тр-ков. Разбиваем его, но тогда набор тр-ков может стать неоптимален. Перестраиваем соседей, они становятся оптимальными, но могли зацепить своих соседей. Короче получается "волна", которая обычно быстро затухает. Ну в данном случае не знаю, с критерием оптимальности напряженка.

[Гурман]

Я не видел ни одной 100% оптимальной реализации подобного роутинга в каком-либо софте, который его имеет. Хорошую детальную теорию по этому вопросу я не нашел даже на английском. Достаточно спросить у любого конструктора, которые пользуются Altium Designer (ex P-CAD), где это проработано лучше всего - все конструктора и радио-инженеры предпочитают рисовать схемы наполовину вручную, не говоря уже о разводке плат (я знаю их ответ, потому что работал с ними на соседнем этаже). Автоматические средства используют только для того, чтобы немного сэкономить время, не таскать все провода изначально. То есть, даже в этом дорогом коммерческом пакете автоматика не идеальна. Некая простая автоматическая оптимизация постфактум возможна, но наиболее эффективным будет возможностью пользователю редактировать сделанную автоматически разводку вручную. То есть, когда пользователь что-то соединяет, оно автоматом прокладывает линии, но если не понравилось, можно их поменять, создавая новые изгибы и двигая отрезки. Это тоже планируется. Увы, придётся еще колбасить сохранение и загрузку схем, чтобы детально все линии сохранялись.

[Igors]

Я не видел ни одной 100% оптимальной...

Есть удобное стандартное объяснение

Well... nothing is perfect

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

Да, и вот

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

А овраг второй стороны может и не иметь 

[Гурман]

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

Ну это банально. Разумеется, именно так и сделано. Если роутинг вернулся в начальную точку с ошибкой "тупик", ругается, что не смог провести линию, надо переместить объект. На будущее можно еще подумать над автоматическим перемещением объектов, если роутинг не выполнился.

овраг второй стороны может и не иметь 

я же сказал  - если я знаю, что могу в один

[Igors]

Ладно, по базовому алгоритму

Без обхода "препятствий" и прочих заморочек с допустимостью прокладывания маршрута задача действительно тривиальная. Общее решение - это "черепашка", движущаяся по кратчайшему маршруту по сетке между двумя удаленными QPointF.
...
Черепашка перед каждым шагом вычисляет наиболее выгодное направление следующего шага, одно из четырех возможных. Это просто - берем 4 соседние точки, и находим ту, расстояние от которой до целевой минимальное (таких 2, но одна найдется первой, и в моем случае это будет вариант по горизонтали). После чего рекурсивно делает шаг в этом направлении, то есть, переходит на соответствующую точку. При выполнении шага передается предыдущее направление (в виде целого числа от 0 до 3), и если при вычислении следующего шага оно не совпало с предыдущим - значит это поворот, его точка сохранятся в локальной переменной ...

...и дальше детали реализации.

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

[Гурман]

Всё там прозвучало, повторять не буду. Дальше на возврате из рекурсии он рисуется. И всё. Каждый сегмент будет ловить события мыши и путь будет позволять себя модифицировать. Больше пока ничего не надо.