Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Ломаная линия с обходом препятствий

Автор: Reaver 7.7.2009, 18:36

Добрый день.
Разрабатываю небольшой редактор схем. Столкнулся со следующей проблемой.
Есть 2 прямоугольных объекта, на гранях объектов находятся точки.
Необходимо между этими точками провести ломаную кривую с наименьшим числом отрезков. Отрезки ломаной должны распологаться под прямым углом, а также не пересекать прямоугольники и не лежать на их гранях.
Все это выглядит приблизительно так:
user posted image

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

Автор: maxdiver 7.7.2009, 21:09

А точки по одной штуке на каждом объекте что ли?

Вообще, простое и надежное решение видится всё-таки через графы. Сначала найдём те точки-кандидаты, через которые может проходить путь. Достаточно взять, во-первых, от точки на объекте отступить на 1 от объекта, а во-вторых, провести вокруг каждого прямоугольника 4 прямых, отстоящих от него на расстоянии 1, и взять всевозможные пересечения всех таких прямых. В результате получим набор точек (их будет не очень много, ну прямых будет 4+4, соответственно точек пересечения 4*4), которых достаточно для проведения искомого пути. Нам нужен кратчайший путь, поэтому строим из этих точек граф (планарный), соединяя каждую найденную точку с <=4 соседями (вверх,вниз,вправо,влево), в полученном графе находим кратчайший путь.

Автор: Reaver 8.7.2009, 03:10

Спасибо большое, это то что надо.

Автор: pompei 8.7.2009, 06:12

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

На данный момент задача прокладки соединительных проводов в электронных схемах и микросхемах общего и удовлетворительного решения НЕ ИМЕЕТ. Такие крутые компании как Intel, AMD, и пр. используют для решения этой задачи в своих процессорах и пр. микросхемах исскуственный интеллект (ИИ), который "работает" в суперкомпьютерах. (Даже есть патенты зарегистрированные на эти ИИ, до которых человек не смог додуматься, а ИИ смог). И даже в этих системах имеется ручная корректировка маршрутов, и она используется очень интенсивно.

Автор: Reaver 8.7.2009, 09:31

Суть задачи как раз в том, чтобы изначально создать ломаную, не пересекающую эти 2 объекта. Остальное уже лежит на совести пользователя.