Итак, у нас есть граф, ориентированный (но это не существенно), не обязательно планарный, который необходимо изобразить на плоскости (на чертеже, схеме). Граф задаётся пользователем, и положение вершин (узлов) графа задаёт пользователь, таким образом, положение вершин фиксировано. А вот соединить этот граф линиями-рёбрами — задача нашей программы.
«Ну и что тут такого?» — спросите вы, — «Рисуешь отрезок от одного узла до второго.» Так, вот, не пойдёт. Вершины графа изображаются не точками, а, к примеру, кружками или прямоугольниками. Поэтому, если просто соединять узлы прямыми стрелками, можно получить следующее:
- graph_direct_connection.png (6.65 Кб) Просмотров: 1501
(Что, конечно же, недопустимо)
Поэтому, первое требование: линии-рёбра должны огибать узлы, и ни в коем случае не пересекать их. При этом линии-рёбра не должны быть угловатыми. То есть делаем вывод, что линии-рёбра должны иметь форму кривых, если это необходимо.
Для вышеупомянутого случая это будет выглядеть, например, так:
- graph_curve_connection.png (4.19 Кб) Просмотров: 1502
Второе требование: линии-рёбра не должны сливаться в точке соединения с узлом в одну большую жирную кляксу. То есть, если из узла выходят (в узел входят) 5 линий, углы между ними должны стремиться стать одинаковыми, в то же время, не достигать крайности: 360o/5, потому что линии, выходящие совершенно в другую сторону от узла-назначения — тоже плохо.
«Ну и что сложного?» — скажете вы, — «Полно описанных для игроделов алгоритмов поиска свободного пути.» Не пойдёт. Дело в том, что такие алгоритмы просто ищут путь (обычно кратчайший), огибая препятствия. В них совершенно никак не предусмотрен учёт взаиморасположения искомого пути с уже найденными (и с теми, которые будут найдены после искомого). Поэтому, конечная картина будет полностью зависеть от порядка обхода узлов, то есть от порядка, в котором происходит трассировка линий-рёбер. Вот, например, для графа из 4 узлов и 2 рёбер, в зависимости от порядка может получиться две разные картины:
- graph_pathrouting_connection_undeterm.png (9.53 Кб) Просмотров: 1502
Это тоже крайне не приветствуется.
И вот почему это плохо: когда есть пара связанных узлов и ей соответствует другая симметричная (относительно некоторой прямой или точки) связанная пара узлов, то и связи (то есть линии-рёбра) должны быть симметричны. Почему? Потому что они совершенно равноценны. Невыполнение этого требования приводит к тому, что на подсознательном уровне одна линия-ребро воспринимается как более приоритетная, более сильная, более главная, в общем, по какому-то критерию более превосходящая другую. На левой половине верхнего рисунка одна стрелка идёт напрямую, а другая — в обход, так что, если и не на сознательном, то уж точно на подсознательном уровне возникнет заблуждение, что та стрелка, которая прямая, чем то более значима, чем та, которая идёт в обход (ведь именно она идёт напрямую, хотя могло быть наоборот?!).
А как я уже не раз говорил (один из моих девизов): дизайн пользовательского интерфейса — это не украшательство пользовательского интерфейса, это делание его практичным, удобным, понятным, не вводящим в заблуждение.
Кроме того, совершенно не исключено, что в будущем понадобится изображать линии-рёбра, которые не будут равноценными: например, если изображаемый граф будет взвешанным (то есть каждого ребра будет определён вес). В этом случае «кто кого» огибает будет зависеть уже от веса изображаемых рёбер. Но всё равно, при этом не исключены (не запрещены) рёбра с равным весом, для которых будет действительна та же проблема «визуальной неравноценности».
Так что, делаем вывод, типичные game-related алгоритмы поиска свободного пути не пригодны, потому что обрабатывают линии-рёбра последовательно, а не параллельно.
Итак, третье требование: не допускается изображать линии-рёбра так, чтобы их геометрия (форма, длина и пр. параметры) намекала на их неравноценность. В частности: если между узлами наблюдается какая-то симметрия, то и между соединяющими их линиями-рёбрами она должна наблюдаться (при условии что ей не мешают посторонние объекты).
Соответственно, верхний случай должен выглядеть так:
- graph_four_nodes_connection.png (4.51 Кб) Просмотров: 1500
Заметили кое-что? На этой картинке линии-рёбра не прямые, хотя могли бы быть.
Это потому, что существует четвёртое требование (а): когда линии-рёбра пересекаются, угол между касательными, проведёнными к каждой линии в точке пересечения должен стремиться быть побольше. В данном случае, так как прямых две, этот угол состовляет 90о, поэтому линии-рёбра изогнулись таким образом, чтобы в окрестности точки пересечения быть перпендикулярными.
Это необходимо, опять же, для того, чтобы не возникало клякс:
- graph_detraction_on_intersection.png (31.19 Кб) Просмотров: 1503
Ограничение (а): В то же время, линии-рёбра не должны изгибаться и вытягиваться сверх меры, то есть изгибаться так, чтобы обязательно соблюсти это условие максимальности всех углов. Например, на рисунке выше линии пересекаются под углами, меньшими, чем 60о.
Четвёртое требование (б): линии-рёбра должны изгибаться таким образом, чтобы точки пересечения распределялись по как можно большей площади, были как можно более удалены друг от друга. Это также необходимо, чтобы не возникало клякс:
- graph_detraction_hexagonal.png (16.58 Кб) Просмотров: 1502
Ограничение (б): аналогично.
Нулевое требование: линии-рёбра должны иметь минимальную длину, разумеется, не конфликтуя при этом со всеми вышеуказанными требованиями.
(Это требование нулевое, потому что оно всем очевидно и понятно, но, тем не менее, без него можно было бы просто увести все линии в бесконечность и заявить, что они где-то там пересекаются и огибают друг-друга правильным образом и в соответствии со всеми требованиями. Существование подобного требования-ограничения убирает все решения с уводом в бесконечность из множества допустимых решений)
Таким образом, линии-рёбра должны расположиться так, чтобы соблюдался баланс между нулевым требованием и всеми остальными вышеописанными.
В ограничениях требований 4а и 4б упоминается понятие некоторой меры, сверх которой не следует изгибаться линиям. Иными словами, сказано, что требование 4 не должно идти в ущерб нулевому требованию. Назовём число, показывающее, как соотносятся «силы» требования 0 и треования 4, коэффициентом детракции.
Аналогично, число, показывающее, как соотносятся «силы» требования 0 и треования 1, назовём коэффициентом огибания.
По сути, всё вышеописанное есть не что иное как сформулированные «критерии красивости», которые никак не мог сформулировать товарищ Debugger в своей задаче о сплайне Безье.
Зачем это всё надо?
Наверняка самые догадливые уже поняли, что надо это непосредственно для редактора графов, который необходим для работы (точнее для настройки правил работы) подсветки синтаксиса. Ну а вообще, это ведь полезно абсолютно всегда, когда необходимо изобразить граф и красиво соединить его узлы рёбрами. Например, я давно хочу написать замену Dependency-Walker-а, такую, чтобы она показывала граф зависимостей как настоящий граф, а не как дерево (так делает DW), потому что граф зависимостей модулей далеко не всегда является деревом (DW в этом случае меняет значок узла дерева на значёк со стрелочкой, намекая на ссылку на вышестоящий по иерархии зависимости модуль).
А теперь внимание вопрос:
У вас есть идеи, как, основываясь на всех вышеизложенных правилах, нарисовать линии-рёбра (для чего необходимо иметь возможность вычислить любую точку указанной линии-ребра)?
Если есть, тогда говорите, если нет, тогла слушайте меня, потому что у меня есть
.Вспомните-ка электростатику... Вспомните, как выглядят силовые линии и изолинии потенциала (эквипотенциальные линии):
- electrostatic.png (50.56 Кб) Просмотров: 1504
Ничего общего с нашей задачей не видите? А я вижу. Есть два важных факта о силовых линиях:
- Не существует силовой линии, соединяющей два одноимённых точечных заряда.
- Всегда* существуют силовые линии, соединяющие разноимённые точечные заряды
А теперь вспоминаем первое требование:
Линия, изображающая ребро, должна соединять две узла.
Силовая всегда соединяет два разноимённых точечных заряда.
Но при этом не должна пересекать другие узлы, а должна огибать их.
Силовая линия никогда не соединяет два одноимённых заряда.
Не должна быть угловатой (то есть должна быть гладкой)
Силовые линии, соединяющие два разноимённых точечных заряда, всегда гладкие.
Напрашивается вывод, что если рассмотреть изображения соединяемых узлов графа как разноимённые заряды, а всех остальных узлов как одноимённые, то множество линий, удовлетворяющих первому требованию совпадает с множеством силовых линий.
Но этого абсолютно недостаточно: нам нужна одна конкретная линия-ребро, а силовых линий — множество. Кроме того, этот подход не только не учитывает требования 2—4, он не учитывает главного ограничивающего требования — нулевого, которое запрещает решения, в которых все линии-рёбра уходят в бесконечность.
Поэтому, одной лишь математической модели, описывающей электростатическое взаимодействие, будет мало, и нужно что-то ещё.
А чем-то ещё будет модель, описывающая абсолютно тонкую упруго-деформирующуюся (растягивающуюся до бесконечности) нить, подчиняющуюся закону Гука. А объединим эти две модели просто: примем, что наша нить сделана из непроводящего материала и распределим по протяженности нити электрически заряд. Будем считать нить воплощением линии-ребра, а форму, которую в итоге примет нить — искомой формой линии-ребра.
А теперь посмотрим, почему такая модель соответствует всем нашим установленным требованиям:
Требование 1:
Линия будет огибать посторонние узлы, потому что и она, и узлы заряжены одноимённым зарядом, и между ними будет действовать отталкивающая сила. В то же время, линия от такого отталкивания не растянется в бесконечно длинную петлю, потому что по мере растягивая, сила (упругости), стремящаяся возвратить нить в исходное (не растянутое состояние) будет увеличиваться. Так что существует такое состояние нити, в котором эти силы уравновешены. Это состояние и будет искомым.
Упомянутый выше коэффициент огибания в нашей модели является ничем иным, как соотношение [коэффициента упругости нити] к произведению [заряд узла] × [линейная плотность заряда на нити].
Требование 2:
Линии не будут исходить/входить в узел в одной точке, а будут распределяться по окружности узла вследствие того, что по нитям распределён отрицательный заряд и они будут отталкиваться друг от друга. Так, например, если бы вторые концы нитей не были закреплены, и не было бы никаких внешний воздействий, нити бы вытянулись в стороны от узла в радиальных направлениях так, чтобы между ними был одинаковый угол. Но в данном случае будет выполняться и оговорка данного требования: нити всё же не расположатся под равными углами в следствие того, что будут натянуты. Сила действия оговорки опять же определена коэффициентом огибания
Требование 3:
Линии не будут выглядеть неравноценными, потому что в отличие от описанного случая, они не высчитываются по очереди и не страдают от того, что обсчитанные в последнюю очередь знают о и огибают обсчитанные в первую очередь линии. В данном случае все линии-нити испытывают одинаковые взаимодействия с узлами и другими линиями-нитями.
Тем не менее, ничто не мешает добавить поддержку отображения неравноценных линий-рёбер (помните это замечание? о взвешанных графах). Делается это просто: коэффициент жесткости нити устанавливается в соответствии с весом ребра. Более «сильное» ребро на рисунке будет в меньшей степени выгибаться и в большей идти напрямик.
Требование 4а:
Нити будут стараться избегать образования острых углов в местах пересечения, поскольку между пересекающимися нитями действует сила отталкивания. Так, если бы две нити с незакреплёнными концами пересекались, они бы развернулись друг относительно друга так, чтобы угол между ними стал равен 90о (в этом случае потенциальная энергия системы минимальна). В нашем же случае угол хоть и будет стремиться к увеличению, но не будет становиться максимальным в силу упругости нитей.
Упомянутый в ограничении коэффициент детракции в нашей модели определяется просто: как отношение [коэффициента жесткости нити] к [линейной плотности заряда нити].
Требование 4б:
Центры пересечений нитей не будут скапливаться в одной точке, потому что поле в этой точке обладало бы предельно высокой напряженностью. И, так как нити заряжены одноимённым зарядом, они бы все с одинаковой силы отталкивались от такой точки.
Оговорки, допущения и проблемы
- Открыт вопрос о том, какую брать изначальную длину для нерастянутых линий-нитей. Если брать её одинаковой, то линии-нити, соединяющие более удалённые узлы, будут казаться более жесткими, что недопустимо,
- Считается, что нить не проводит ток, что
, и что
. Однако, элементарные отрезки нити будут взаимодейстсовать друг с другом (отталкиваться) и растягивать нить, причём растяжение будут неравномерным (концы растянутся больше, середина не растянется). Это, в свою очередь, в силу непроводимости нити, приведёт к тому, что распределение заряда на единицу связанной с пространством (а не с нитью) длины будет больше в середине нити, чем на краях, а кажущаяся жесткость наоборот возрастёт на краях. Пока я не могу сказать, полезен ли этот побочный эффект, но если нет, возможно, придётся снабдить нить крайне необычным свойством: хоть нить и непроводящая, при ей растяжении заряд каким-то чудесным образом всё-равно перераспределяется, чтобы распределение заряда на единицу связанной с пространством длины оставалось постоянным по всему контуру нити. Правда, кажется, это сильно усложнит расчёты.
- Проблема ещё в том, что все нити взаимодействуют друг с другом, но в отличие от зафиксированных вершин графа, они могут гнуться произвольным образом.
- Соответственно, вы чувствуете, сколько матана (в прямом смысле, в данном случае) скрывается под всем этим?
- Проблему представляют множественные решения. Например, если у вас на одной прямой лежат три узла графа, и надо соединить первый с третьим, возникает вопрос: как должна обогнуть линия-ребро второй узел (слева или справа)? Уже два варианта. А теперь представьте, что у вас 6 узлов, лежащих на одной прямой, и надо соединить 1-ый с 3-им и 4-ый с 6-ым. Теперь уже две линии-ребра, каждая из которых может обогнуть промежуточный узел либо слева, либо справа. Думаете, теперь уже 4 варианта (слева-слева, слева-справа, справа-слева, справа-справа) решения? Не угадали: их по прежнему два (либо слева-справа, либ справа-слева) — два ребра не станут огибать лишний узел с одинаковой стороны, поскольку отталкиваются друг от друга. А если таких триплета три, и они расположены на сторонах треугольника, то решений не 8, не 4, не два, а вообще одно: линии-рёбра обогнут лишний узел с той стороны, которая является внешней, по отношению к треугольнику. Так что не всё так просто, как кажется
Перерыв. Попытка описать всё это уравнениями в следующий раз.
Высказываемся.
