Помогите, о всезнающий all

Пишу одну программку

Автор: Grog13
Дата: 06.06.05

, и столкнулся с совсем не понятной для меня проблемой.
Мне нужно красиво рисовать соединения между ножками различных микросхем.
Т.е. к примеру как тут схематично нарисовано:



Т.е. смысл такой — я нажимаю мышкой на одной ножке и веду соединение к другой ножке — и должен получить примерно такой результат.
Какие данные мне даны: — координаты и размеры соединяемых чипов и их ножек.
А дальше программулька должна каким-то образом вычислить оставшиеся промежуточные точки.
Как такие вещи делаются?

Спасибо.

Здравствуйте, Grog13, Вы писали:

G>Мне нужно красиво рисовать соединения между ножками различных микросхем.
G>Т.е. к примеру как тут схематично нарисовано:

G>

G>Т.е. смысл такой — я нажимаю мышкой на одной ножке и веду соединение к другой ножке — и должен получить примерно такой результат.
G>Какие данные мне даны: — координаты и размеры соединяемых чипов и их ножек.
G>А дальше программулька должна каким-то образом вычислить оставшиеся промежуточные точки.

G>Как такие вещи делаются?

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

Сходи в библиотеку, почитай про поиск пути в лабиринте, алгоритм Ли, алгоритм А*, лучевой алгоритм, канальную трассировку.
Посмотри на Protel (www.altium.com), Pulsonix (www.pulsonix.com), TopoR (www.freestyleteam.com/ru). Демки доступны.

Насчет твоего вопроса в .NET_GUI ("Реакция своего контрола на мышку")...
Не надо никаких UserControl'ов.
Пробежал по массиву, по всем объектам, проверил попадание.
Чем проще, тем лучше. Работало быстро даже на 286-х в стародавние времена.
Начинаешь проверять попадание сперва в самые мелкие объекты, затем в те, что покрупнее. В твоем случае (я не телепат, могу только догадываться), наверное стоит начинать с проводников, затем проверять контакты, затем компоненты.

Да, проводники это не прямоугольники, а отрезки линий!!! Вот и используй соответствующие алгоритмы. "Расстояние от точки до отрезка(прямой)" разжевывался здесь многократно.

SVZ>Сходи в библиотеку, почитай про поиск пути в лабиринте, алгоритм Ли, алгоритм А*, лучевой алгоритм, канальную трассировку.
SVZ>Посмотри на Protel (www.altium.com), Pulsonix (www.pulsonix.com), TopoR (www.freestyleteam.com/ru). Демки доступны.

Да, похоже что волновой алгоритм это для меня http://doc.mpv.ru/steps/theory/volna.html
Только как я понял там нужно бегать по массиву.

Что-то не очень пока понятно как это сделать.

Т.е. у меня есть регион (.NET Region) — который представляет собой расположение объектов на рабочей области.
Далее есть координаты начала пути и координаты конца пути.
Мне что разбивать всю рабочую область на квадратики размер которого равен одному шагу пути?
Ну если у меня рабочее поле 1024x768, а квадратик например 3x3 пискеля — это мне создавать массив из [1024/3, 768/3]?

Здравствуйте, Grog13, Вы писали:

SVZ>>Сходи в библиотеку, почитай про поиск пути в лабиринте, алгоритм Ли, алгоритм А*, лучевой алгоритм, канальную трассировку.
SVZ>>Посмотри на Protel (www.altium.com), Pulsonix (www.pulsonix.com), TopoR (www.freestyleteam.com/ru). Демки доступны.

G>Да, похоже что волновой алгоритм это для меня http://doc.mpv.ru/steps/theory/volna.html
G>Только как я понял там нужно бегать по массиву.

Ну, скажем точнее, по дискретному монтажному полю.

G>Т.е. у меня есть регион (.NET Region) — который представляет собой расположение объектов на рабочей области.
G>Далее есть координаты начала пути и координаты конца пути.
G>Мне что разбивать всю рабочую область на квадратики размер которого равен одному шагу пути?
G>Ну если у меня рабочее поле 1024x768, а квадратик например 3x3 пискеля — это мне создавать массив из [1024/3, 768/3]?

Пиксели тут ни при чем. Равно, как и НЕТовские регионы. Пиксели приходящи (зависят от текущего масштаба изображения), а DBU (твои внутренние ед. изм-я) вечны.
Размер дискрета твоего коммутационного поля зависит от размеров объектов. К примеру, ширина проводника 0.5мм, расстояние между контактами м/сх 2.5мм,
диаметр контактной площадки 1.2 мм. Если проводник пойдет между площадками, то с каждой стороны будет зазор по 0.4мм.
Выбираем НОК — 0.1мм. Вот размер дискрета.
Тогда ширина проводника получается 5 дискрет, зазора — 4 дискрета, диаметр КП — 12 дискрет.
Так что если захочешь развести плату размером 20х12 см, тебе понадобится коммутационное поле 2000х1200 дискрет.
Дальше надо думать, сколько памяти тебе понадобится на один дискрет. Если использовать простой волновой алгоритм (описание которого ты нашел),то байта 3, как минимум, чтобы не произошло переполнение. Это для вышеупомянутого примера 20х12.
Есть модификация этого алгоритма. Волна записывается не как последовательность чисел, а чередующиеся 0 и 1. Тогда на дискрет достаточно двух бит. Минус — сложнее этап построения трассы. Нужно учитывать расстояние до источника. Подробностей не помню, давно дело было.

Взгляни еще Генетический алгоритм для трассировки двухслойных каналов. Применение здесь ГА попахивает шарлатанством, но есть хоть какое-то описание канальной трассировки и есть хороший список литературы.
Здесь описан лучевой алгоритм, опять же есть список литературы.

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>Здравствуйте, Grog13, Вы писали:

SVZ>>>Сходи в библиотеку, почитай про поиск пути в лабиринте, алгоритм Ли, алгоритм А*, лучевой алгоритм, канальную трассировку.
SVZ>>>Посмотри на Protel (www.altium.com), Pulsonix (www.pulsonix.com), TopoR (www.freestyleteam.com/ru). Демки доступны.

G>>Да, похоже что волновой алгоритм это для меня http://doc.mpv.ru/steps/theory/volna.html
G>>Только как я понял там нужно бегать по массиву.

SVZ>Ну, скажем точнее, по дискретному монтажному полю.

Ну да =)

И тут я столкнулся со следующей проблемкой:



Допустим я "запустил" волну от светло-зеленой точки (0) до темно зеленой точки следующей реализацией волнового алгоритма (первое что пришло в голову):

public void GenField(ArrayList wave)
{
            ArrayList wave2 = new ArrayList();
                        // size_x, size_y - максимальные размеры поля
            for (int i = 0; i < wave.Count; i++)
            {
                Point xy = (Point)wave[i]; // Берем очередную точку волны

                // Ходим наверх
                if (xy.Y - 1 >= 0 && m_massiv[xy.X, xy.Y - 1] == EMPTY)
                {
                    // ставим туда значение на 1 больше чем наше
                    m_massiv[xy.X, xy.Y - 1] = m_massiv[xy.X, xy.Y] + 1;
                    wave2.Add(new Point(xy.X, xy.Y - 1));
                }
                // Ходим вправо
                if (xy.X + 1 < size_x && m_massiv[xy.X+1, xy.Y] == EMPTY)
                {
                    m_massiv[xy.X + 1, xy.Y] = m_massiv[xy.X, xy.Y] + 1;
                    wave2.Add(new Point(xy.X + 1, xy.Y));
                }
                // Ходим вниз
                if (xy.Y + 1 < size_y && m_massiv[xy.X, xy.Y + 1] == EMPTY)
                {
                    m_massiv[xy.X, xy.Y + 1] = m_massiv[xy.X, xy.Y] +1;
                    wave2.Add(new Point(xy.X, xy.Y + 1));
                }
                //Ходим влево
                if (xy.X - 1 >= 0 && m_massiv[xy.X - 1, xy.Y] == EMPTY)
                {
                    m_massiv[xy.X - 1, xy.Y] = m_massiv[xy.X, xy.Y] + 1;
                    wave2.Add(new Point(xy.X-1, xy.Y));
                }
            }
            if(wave2.Count > 0) GenField(wave2); // продолжаем со следующего фронта
}

и вызываем ее следующим образом

    ArrayList wave = new ArrayList();
    wave.Add(new Point(2,2));
    m_massiv[2,2] = 0;
    GenField(wave);

в конечной точке (темно-зеленой) получаем 6, а не 8 (если идти слева).
Вообщем, вопрос, как правильно такие ситуации обратабывать, ибо в моей реализации там ничего такого нет.
И еще вопрос — как его можно "убыстрить"? =)

И еще собственно — как находить по этому полю сам путь. То что каждый следующий шаг должен быть на 1 больше предыдущего понятно.
Но вот тут вот собственно два пути. Как найти наикратчайший?

Здравствуйте, Grog13, Вы писали:

G>Здравствуйте, Stanislav V. Zudin, Вы писали:

G>И тут я столкнулся со следующей проблемкой:

G>

G>Допустим я "запустил" волну от светло-зеленой точки (0) до темно зеленой точки следующей реализацией волнового алгоритма (первое что пришло в голову):

<skipped>

G>в конечной точке (темно-зеленой) получаем 6, а не 8 (если идти слева).
G>Вообщем, вопрос, как правильно такие ситуации обратабывать, ибо в моей реализации там ничего такого нет.
Как только ты достиг цели — конец, алгоритм закончил работу, соответственно на цифре 6 ты должен остановиться.

G>И еще собственно — как находить по этому полю сам путь. То что каждый следующий шаг должен быть на 1 больше предыдущего понятно.

Идти от конца к началу, как сказано в найденой тобой статье, т.е. от 6 к 0.

G>И еще вопрос — как его можно "убыстрить"? =)
Использовать эвристики.
Например, пустил волну из исходной точки, из полученных точек посчитал расстояние (манхеттеновское сойдет) до цели, выбрал ту, что ближе. Пустил из нее волну. И так до тех пор, пока либо не достигнешь цели, либо куда-нибудь не упрешься. Во втором случае вернулся на предыдущий шаг и ищешь другой путь. Поиск в глубину, в общем.

И почитай таки про А*.