Алгоритм построения линий графа на плоскости с автоматическим обходом препятствий

Пример прикреплён. В нём линии связей пересекают таблицы, хотелось бы, чтобы автоматически обходили. Куда глянуть? Или как формулировать вопрос яндексу?

Миниатюры

 

0

Рисунок похож на graphviz. https://graphviz.org/docs/layouts/dot/ (есть исходники)

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

0

Сообщение от Massaraksh7 Вот что я пока придумал. Но тут надо ещё проверять.

Может стоит подумать над структурой данных "линия"

0

Сообщение от Igor3D Может стоит подумать над структурой данных "линия"

Да с ней я, как раз, определился - либо кубический параметрический сплайн дефекта 1, либо сплайн Акимы.

0

Сообщение от Massaraksh7 Да с ней я, как раз, определился - либо кубический параметрический сплайн дефекта 1, либо сплайн Акимы.

Возможно Вы смотрели какую-то статью со списком сплайнов. В приложениях/редакторах что изучал я реально используется один: кубический сплайн Безье. Остальные так, для комплекта или дань истории. Практически все они достижимы тем же Безье, а главное - он имеет прекрасный интерактивный контроль, начиная с "авто", т.е. по минимуму, нужно только добавить точки, остальное на автомате. А можно и "раздуть" управление (кривизной) как душе угодно. В общем, как говорят, "рекомендую"

Ну и займитесь кривыми/сплайном, это по-любому надо делать, а там, глядишь, и какие-то идейки с "авто-обходом" созреют

0

Есть какое-то ограничение на таблицы? На картинке 2 ряда таблиц. Может быть 5 рядов ("строк") таблиц?

0

Сообщение от Igor3D Ну и займитесь кривыми/сплайном, это по-любому надо делать

Они у меня сделаны, я давно ими пользуюсь для своих задач.

Сообщение от Shamil1 Есть какое-то ограничение на таблицы? На картинке 2 ряда таблиц. Может быть 5 рядов ("строк") таблиц?

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

Миниатюры

 

0

Сообщение от Massaraksh7 Они у меня сделаны,

***

Миниатюры

 

0

Сообщение от Massaraksh7 Они у меня сделаны, я давно ими пользуюсь для своих задач.

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

Метод "сделать и посмотреть" (да, без всякого плана, мат моделей и.т.п.) отнюдь не плох, тем более здесь это не накладно по реализации

0

Сообщение от Igor3D Тогда почему не реализовать что Вы предложили в #17?

Это задача перспективная, не первоочередная. Пока здесь собираю разные варианты.

0

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

0

Да, тоже думал об этом.

0

Что с ответом на вопрос в сообщении #9?

И еще: придумайте несильно перегруженный хороший примерчик. Нарисуйте нам.

Добавлено через 38 минут
Теорема: для любой топологии можно всегда провести любые две пары линий связи так, чтобы они пересекались не более 1 раза.
Доказательство: если две линии пересекаются два раза, то участок от пересечения до пересечения можно исправить так, чтобы они шли параллельно, не пересекаясь, при этом пересечения устранятся. При этом очевидно, преимущество такой параллельной прокладки: если одна линия проходит "красиво", то и вторая будет тоже "красивой".

Пользуясь этой теоремой, можно строить менее запутанные связи.

0

Сообщение от Mikhaylo прямоугольники будут сверху над связью B-E, а какие - снизу.

Что значит "сверху" и "снизу"? Связи могут идти и вертикально.

0

Линию связи можно рассматривать как дорогу, по которой едешь из дома А в дом Б, а слева или справа находятся другие дома. Это то же самое, что если нарисовать квадратики и линии связи и тогда "лево-право" превращается "вверх-вниз".

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

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

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

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

0

Всё равно не очень понятно.
То есть, всё что вы пишете, оно, вроде бы, логично, но алгоритма в этом не просматривается.

0

Я примерно понимаю, что за ПО вы создаёте. Я бы на вашем месте сделал интерактивный режим отрисовки: пользователь сам определяет, как идут линии, либо просит оптимизировать автоматически. Сплайны - это отстой, лучше квадратно-гнездовой способ реализовать, когда линии связи строго горизонтально или вертикально, с поворотами на 90 градусов.

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

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

Вторая часть.
1. У нас фиксированы начало и конец дуги. Используем квадратно-гнездовой способ. Определяем, в какую сторону надо двигаться, исходя из того, откуда выходит дуга (обычно влево или вправо). Шаг сетки 5 мм, поэтому первый кусочек 5 мм готов.
2. Определяем, какая сторона у дуги внутренняя, какая наружная в составе петли или же дуга без петли, у нее нет сторон.
3. Если дуга в составе петли, то перебираем все вершины и смотрим по координатам, требуется ли разворот и обход этой вершины, если же таких вершин нет, то мы просто двигаемся в направлении конечной вершины, предпочитая движение в том же направлении как и в предыдущем шаге.
4. Дуги беспетельные могут обходить вершины как угодно, с любой стороны.

0

Сообщение от Mikhaylo Сплайны - это отстой, лучше квадратно-гнездовой способ реализовать

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

0

Сплайны не проблема. Проблема в другом: этот алгоритм вполне рабочий, но может не устроить решение. А еще вы можете внести 1000 усовершенствований. То есть описал некое направление, а не конкретный алгоритм.
Эх, и зря же вы сказали, что "не горит".)))

0