Построение планарного графа.

google it.

волновой алгоритм

Он же жадный как свин

сабж

ну ты надеюсь его не попиксельно рисовал?

Я не понимаю при чём здесь это, я ищу алгоритм которому не нравятся косые линии и чтобы путь ступеньками получал меньший приоритет, чем более прямой

Задача: есть объекты набросанные на плоскость. Есть две точки на одно объекте и на другом, построить связь состоящую из ортогональных линий, не пересекающую другие объекты. Я в пространство дискретизирую до точек с разностью координат 10, получается сетка. Вот по ней надо найти кратчайший красивый путь.
Задача решена в некоторых свободных UML редакторах, но в том коде хер что найдёшь

Планарные графы тут причём... Но в конкретном случае...

Самое просто, что приходит в голову... Иди с концов. Т.е. строй ломаную с двух строн, анализируя, куда она может двигаться(учитываешь направление где вторая точка, соседние объекты и т.п.). Получаешь новые точки — потом запускаешь алгоритм для соединения этих точек... и т.п. Не?

>Задача: есть объекты набросанные на плоскость. Есть две точки на одно объекте и на другом, построить связь состоящую из ортогональных линий, не пересекающую другие объекты. Я в пространство дискретизирую до точек с разностью координат 10, получается сетка. Вот по ней надо найти кратчайший красивый путь.

Это нетривиально в общем случае. Особенно кравиво, с учётом выравнивания объектов и равномерного распределения связий. Может так случиться, что при большом кол-ве объектов для кравивых линий нужно двигать объекты.

для начала задачу можно решить на целочисленной сетке, без возможности двигать объекты — и меня, кстати, задача заинтересовала, так что я не поленился ее порешать — у меня получилось (если не ошибаюсь) О(m*n) операций, где m и n это размеры прямоугольника в котором ищутся пути, а штраф за каждый излом линии принят равным 1

однако... как бы повежливее выразиться... никоим образом не пытаясь здесь обсуждать модератора этого раздела Pi и его действия (это разрешено только в разделе http://www.linux.org.ru/forum/linux-org-ru/), замечу, что *мне* совершенно не ясно, как модератор Pi отнесется к постам с моим решением и его обсуждением; поэтому я воздержусь от излишних постов в этот раздел сайта

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

Волновой алгоритм с приоритетами.

>где m и n это размеры прямоугольника в котором ищутся пути, а штраф за каждый излом линии принят равным 1

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

соглашусь (хотя расстояние я учитывал); но я думал, что топикстартеру нужно понимание алгорима, а не конкретная реализация, т.к. ее можно спокойно скопипастить из имеющихся UML редакторов (если, конечно, его редактор свободный)

У меня проект-курсовая, на гуглокоде, gpl v3. Линк не дам, боюсь срача
А вот понимание алгоритма, можно на псевдокоде, было бы не плохо.
У меня есть свои задумки, но хотелось бы из чего-то выбирать

Ах да, объекты двигать ненужно, сетка целочисленная. Просто найти красивый путь.

Ну... как вариант:

1)Строишь граф. Каждая вершина графа - пара (точка, направление)

2) между вершинами (point1, dir1) и (point2, dir2) есть ребро только, если point1 и point2 соседние и dir2 = point2 - point1. И вес этого ребра 1 + alpha*(dir1!=dir2).

3) Далее находишь кратчайший путь из вершин (point1, *) в вершины (point2, *) алгоритмом Дейкстры.

Смысл параметра alpha. Чем больше alpha, тем меньше изгибов в ущерб длинне пути.

Maze Router: Lee Algorithm

Lee, “An algorithm for path connection and its application,” IRE Trans. Electronic Computer, EC-10, 1961.

Собственно то, что Вам нужно:

Hightower’s Algorithm

Hightower, “A solution to line-routing problem on the continuous plane,” DAC-69.

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

Спасибо большое. Разберусь, авось реализую. Дейкстра не совсем годен, точек много и кол-во узлов надо минимальное и не в ущерб длине

А расскажите, как статью достать ? Все источники ааагорожены

>Спасибо большое. Разберусь, авось реализую. Дейкстра не совсем годен, точек много и кол-во узлов надо минимальное и не в ущерб длине

делаешь alpha = 0.01 и алгоритм выбирает среди минимальных путей путь с найменьшим количеством узлов.

Да и дейкстра для разряженных графов не сильно хуже поиска в ширину.

Волновой алгоритм с приоритетами.

Где про него хорошо написано?! А то мне ничего путнего не попалось

>Где про него хорошо написано?!

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

спб.

>Да также, как и в обычной обратной волне (примеров миллион), только при просмотре соседних нод добавлять не единичку, а весовой коэффициент сложности перехода. Потом - пройти от конца к началу по наименьшим значением.

Или я чего-то не понял, или это будет та же Дейкстра, или неправильно работать.