Пишу программу типа электроникс воркбенч (для моделирования электронных схем). Нужен алгоритм трассировки полилиний между элементами. Так чтоб было правдоподобно, и чтоб полилинии не налезали на элементы. И чтоб петлей разных тоже не было.
_basmp_ Не кратчайшего, а наиболее прямого. Т.е. путь должен содержать минимум изгибов, причём изгибы по 90 градусов.
Причем изгибы должны располагаться так, чтобы полилиния не налезала на элементы, а обходила их стороной.
murder это и есть кратчайший God_Father такая мысль. разбить рабочее поле сеткой с шагом равным минимальному расстоянию между проводниками/проводником-корпусом. каждая из получившихся ячеек будет соответствовать некому минимальному зерну площади пространства чертежа. Ячейка может иметь несколько состояний с разными свойствами. Например 0 - пустое пространство (возможна любая трассировка) 1 - гор проводник (можно пересечь 2) 2 - верт проводник (можно пересечь 1) 3 - пересечение проводников (пересекать нельзя) 4 - изгиб проводника (пересекать нельзя) 5 - корпус или вывод (пересекать нельзя, перемещать нельзя) итд ячейки такой сетки со своими свойствами и будут создавать тот лабиринт в котором вы будете искать кратчайший путь (алгоритмы в сети должны быть)
возможно пригодятся.. http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_A* или http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B внизу статей есть ссылки на туторы/реализации да. само собой все напрямую для данного соединения доступные ячейки одной линии сетки соединены прямыми перходами. те соединение <начальная точка>-<поворот>-<поворот>- ... -<поворот>-<конечная точка>
God_Father Тут несуществует универсального решения. Поэтому применяют эврестические алгоритмы. ясно что путь должен быть минимальным. Но и также содержать малое число изгибов. Можно использовать обычный поиск минимального пути. Только ввести вес пути от числа изгибов. Если хочешь более точно, то тогда вначале ищем все пути до точки выбираем с наименьшим числом изгибов и после среди таких с наименьшей дленой. Тут понадобиться перебор всех вариантов с отсечением, но это очень долго.
Pavia По-моему брутфорс тут очень даже приемлем, т.к. путь будет находится всего 1 раз при клике мышью. Тормоза в несколько секунд будут только на очень больших схемах.
