Russian Qt Forum

Стандартная задача - соединять две точки (QPointF в нашем случае) "проводами", которые проходят только по вертикали и горизонтали, и поворачивают только под прямым углом. При этом не накладываются на прочие элементы изображения, а другие подобные линии могут пересекать тоже только под прямым углом. Линии должны сами выбирать где им "ломаться" и сами должны располагаться на оптимальном расстоянии от других айтемов сцены. С возможностью изменять их положение драгом. Такие линии есть в Visio, OpenOffice Draw и других пакетах. Делалось многими и много раз. В самом Qt такой штуки, увы нет. Разумеется, и я сам могу сделать за несколько дней. Но может уже есть такое готовое для QGraphicsScene, типа набора QWT? Может не надо изобретать велосипед? Может есть сторонняя готовая библиотека? Или хотя бы, как называется такой тип объектов, но так чтобы при поиске не путаться в бесчисленных описаниях connection сигналов-слотов, QGraphicsLine и QRubberBand.

Пример документации из одной Java библиотеки (http://docs.yworks.com/yfiles/doc/developers-guide/orthogonal_edge_router.html).

up

С теорией более-менее ясно, что надо делать в общем, тоже более-менее ясно. Провести линии и вычислить обходы можно, подобное раньше делать приходилось. Разумеется, "провода" - это набор отрезков, концы которых соединены. Вот тут не вполне ясно, как это лучше делать на Qt. Точнее - какой вариант реализации самих проводов лучше:

- Хранить и отрисовывать QList<QGraphicsLine>
- Хранить QPainterPath, а на сцене рисовать QGraphicsPathItem( QPainterPath ), причем QPainterPath всегда будет разомкнут
- теоретически можно еще хранить QList<QPointF>, и рисовать на сцене QGraphicsLine между этими точками - почти тоже самое, что в первом случае, но удалять линии со сцены муторно

Не ясно, будет ли нормально второй вариант работать с разомкнутым QPainterPath. Не видно - можно ли выделить отдельный участок QGraphicsPathItem другим цветом. Надо при наведении курсора на отрезок "провода" выделить этот отрезок цветом и определить его ориентацию, чтобы можно было его двигать только перпендикулярно отрезку. Как я вижу, QPainterPath предназначен больше для создания сложных закрытых объектов, которые оперируют, как единое целое. Поэтому склоняюсь к варианту с QList<QGraphicsLine>. В нем и выделение, и определение ориентации без особых проблем просматривается.

Кто-то делал что-то подобное? Каким путём?

Провода обычно делают наследниками QGraphicsItem прямо или косвенно. провод знает к кому он подключен и при удалении провода сам отключается.

Базовую идею смотри в примере DiagramScene, подробности реальной реализации, например, во Fritzing (https://github.com/fritzing/fritzing-app) и QElectrotech (http://svnweb.tuxfamily.org/listing.php?repname=qet/qet)

Спасибо, конечно, но это тот случай, когда советующий не вполне понял суть вопроса...

Если ты про автоматическое расположение отрезков, то в QElectrotech именно так и сделано. При перемещении компонентов провода сами перестраиваются.

class Conductor : public QObject, public QGraphicsPathItem  (http://svnweb.tuxfamily.org/filedetails.php?repname=qet%2Fqet&path=%2Ftrunk%2Fsources%2Fqetgraphicsitem%2Fconductor.h)
Проводник содержит внутри себя
class ConductorSegment (http://svnweb.tuxfamily.org/filedetails.php?repname=qet%2Fqet&path=%2Ftrunk%2Fsources%2Fconductorsegment.h)

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

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

Вот это уже интересно - как они на QGraphicsPathItem это сделали. Спс, посмотрю.

ЗЫ: глянул, чё-то как-то муторно там сделано, кроме самого QGraphicsPathItem им пришлось хранить и фактически работать с двунаправленным списком сегментов. Почему-то не стали использовать QList. И если хранятся отрезки, то почему нельзя было их и нарисовать? Такое впечатление, будто авторы сначала сделали всё на QGraphicsPathItem, потом стало его не хватать, прилепили отрезки.

Я подробностей не знаю, но знаю что было так:
Был один программер, потом пришёл ещё один, видимо по опытнее, т.к. дело пошло быстрее, хотелки реализовывались. Сейчас развитие затормозилось, в истории хранилища, комитов от второго программера не видно, да и в "О программе" он пропал.

Т.е. первый, видимо, начал делать на QGraphicsPathItem, потом второй подключился стал перелапачивать код, а когда ушёл, всё осталось не доделанным.
может что-то не поделили.

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

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

Ну вот, сейчас мурло опять выдаст типа "это ерунда!" - и разговор закончится  :)

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

Поддержу вопрос Igors :)
Думал, уже скоро топик стартер поделится своим решением этой не тривиальной, сделанным "за несколько дней". А пока что-то все чужое ищет...

1. Напрасно думал. Делиться этим решением я никому не обещал и не планирую. ;D Может быть, буду продавать по LGPL, если хорошо получится. 8)
2. Чужого не ищу. lit-uriy показал ответ на мой вопрос про варианты использования классов Qt, и он совпал с моими выводами. Задачу решаю абсолютно по-своему и всю сразу - с обходом препятствий, с исключением наложения соединителей, с соблюдением правил "отхода" от "разъемов". Это не тривиально, но без этого всего решение никому тут не нужно. И у меня нет дурацкой привычки пытаться перепрыгнуть овраг в два прыжка, если я знаю, что могу в один. Если кого-то сильно интересует - уже перелетел через середину оврага. :)

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

Ладно, по базовому алгоритму
...и дальше детали реализации.

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

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