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

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

P>Помогите найти алгоритм! Есть некоторое поле, внутри которого находятся прямоугольники. НЕкоторые прямоугольники соединены между собой. Надо эти соединительные линии нарисовать так, чтобы они огибали другие прямоугольники. Координаты начальной и конечной точки и всех прямоуг. соотв. известны. Волновой поиск пути не подходит, так как размеры поля большие, перебирать матрицу такого размера не получается. Линии должны быть ортогональными. Путь между прямоугольниками — не обязательно кратчайший. Помогите пожлст!

Препарата, Шеймос, "Вычислительная геометрия: введение", М. Мир 1989
Глава 8. ГЕОМЕТРИЯ ПРЯМОУГОЛЬНИКОВ
Конкретно, см. следующие параграфы

8.4. Мера и периметр объединения прямоугольников
8.5. Контур объединения прямоугольников
8.6. Замыкание объединения прямоугольников
8.7. Внешний контур объединения прямоугольников
8.8. Пересечения прямоугольников и связанные с этим задачи

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

P>Помогите найти алгоритм! Есть некоторое поле, внутри которого находятся прямоугольники. НЕкоторые прямоугольники соединены между собой. Надо эти соединительные линии нарисовать так, чтобы они огибали другие прямоугольники. Координаты начальной и конечной точки и всех прямоуг. соотв. известны. Волновой поиск пути не подходит, так как размеры поля большие, перебирать матрицу такого размера не получается. Линии должны быть ортогональными. Путь между прямоугольниками — не обязательно кратчайший. Помогите пожлст!

Алгоритмы разводки печатной платы, судя по всему.

Если нужно только ортогонально, но нет сетки, то делаешь очень просто.
Пусть через прямоугольник проходят линии a,b,c,... Они не пересекаются между собой (граф разводки планарный), но пересекаются с прямоугольником. Упорядочим их, скажем, слева направо и сверху вниз. Возьмём первую линию и выведем её за прямоугольник. Затем вторую, с некоторым отступом от первой. И так далее.

К>Алгоритмы разводки печатной платы, судя по всему.

К>Если нужно только ортогонально, но нет сетки, то делаешь очень просто.
К>Пусть через прямоугольник проходят линии a,b,c,... Они не пересекаются между собой (граф разводки планарный), но пересекаются с прямоугольником. Упорядочим их, скажем, слева направо и сверху вниз. Возьмём первую линию и выведем её за прямоугольник. Затем вторую, с некоторым отступом от первой. И так далее.

Ну в общем похоже на разводку, но не разводка =)) А поподробнее можно про алгоритмы разводки? Может ссылки какие есть. И я честно говоря не очень понял предложенный алгоритм.

Здравствуйте, FreshMeat, Вы писали:
FM>Препарата, Шеймос, "Вычислительная геометрия: введение", М. Мир 1989
FM>Глава 8. ГЕОМЕТРИЯ ПРЯМОУГОЛЬНИКОВ
FM>Конкретно, см. следующие параграфы
FM>

FM> 8.4. Мера и периметр объединения прямоугольников
FM> 8.5. Контур объединения прямоугольников
FM> 8.6. Замыкание объединения прямоугольников
FM> 8.7. Внешний контур объединения прямоугольников
FM> 8.8. Пересечения прямоугольников и связанные с этим задачи

Книжка стоящая. Спасибо за ссылку.