| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Отрисовка линии с обтеканием рандомных шейпов |
| Автор: mgarin 6.8.2010, 17:36 |
| Заголовок, однозначно, требует пояснение. Думаю, многие работали с тем же Visio или подобными приложениями - там есть возможность линковать различные фигуры линиями или стрелками. Так вот меня интересует подобный функционал... 1. Предположим есть некая абстрактная область на которой лежит 10 прямоуголников (в случайных местах, могут пересекаться или полностью перекрываться друг другом) 2. Есть точка A(x,y) и точка B(x2,y2) Необходимо отрисовать линию из A в B избегая вех прямоугольников но при этом кратчайшим путем. Также необходим некий настраиваемый отступ от прямоугольников. Думаю, тема изъезженная, но найти что-либо сложно ибо поисковики пока не умеют искать по описанию-трактату =/ Интересует - есть ли какая готовая библиотека или готовый алгоритм на данную тему? |
| Автор: Amp 6.8.2010, 17:57 |
| Первое, что пришло на ум - волновой алгоритм. |
| Автор: kamre 7.8.2010, 16:50 | ||
Готовая библотека: http://www.yworks.com/en/products_yfiles_about.html Из open source есть библиотека http://www.eclipse.org/gef/zest/, в которой реализованы алгоритмы раскладки графа и проведения ребер. |
| Автор: mgarin 9.8.2010, 09:34 |
| http://www.eclipse.org/gef/zest/ - судя по всему умеет кое-что делать, но возможно ли это использовать при наличии моих собственных объектов на моей области (на которой я сам все отрисовываю), которые необходимо обходить теми самыми линиями? http://www.yworks.com/en/products_yfiles_about.html - аналогичный с 1ым вопрос, только плюс - брать такого плана платную библиотеку ради 1% ее функционала... > Первое, что пришло на ум - волновой алгоритм. А вот об этом можно поподробнее?) Нашел только один пример реализации на Java (http://in7.org.ru/?p=4387), да и то, без пол-литра... |
| Автор: Amp 9.8.2010, 10:41 | ||
Зачем копаться в чужом коде? Алгоритм прост - почитайте описание и запрограммируйте. Если устроит его производительность, то можете использовать в своем приложении. |
| Автор: mgarin 9.8.2010, 12:32 |
| Нашел подробное описание алгоритма (http://www.codenet.ru/progr/alg/way.php) Впринципе, оно конечно должно работать, вот только у меня есть сомнения насчет оптимальности. У меня область может достигать размеров 10000х10000 и для каждой отдельной линии будет вестись пересчет при каждой отрисовке... Даже если кэштровать расчеты - любое передвижение объектов будет сбрасывать кэш и приводить к жутким подлагиваниям. Но это в теории... |
| Автор: jk1 9.8.2010, 13:47 |
| В целях оптимизации можно попробовать следующий подход: считать узлами графа для поиска пути не отдельные пиксели, а квадраты 10x10 или 20x20. А уже потом, в пределах полученного коридора, строить линию. Это правда потребует размещения объектов с шагом, соответствующим стороне квадрата. Также можно попробовать заменить волновой алгоритм 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. |
| Автор: maxim1000 9.8.2010, 22:11 |
| кратчайшая линия будет либо полностью прямой, либо иметь изломы на углах прямоугольников так что узлами графа можно считать углы прямоугольников и исходную с конечной точки рёбра - отрезки между точками, если они ничего не пересекают, если пересекают - нет ребра Добавлено через 1 минуту и 38 секунд отступ в первом приближении можно считать прямоугольником с бОльшими сторонами если прямоугольник с отступом будет более сложной фигурой, алгоритм соответственно усложнится... |
| Автор: kamre 10.8.2010, 13:10 | ||
Вроде бы там можно только алгоритм проведения ребер вытащить, хотя я сам не пробовал. Еще вот ссылки собраны по теме: http://rtsys.informatik.uni-kiel.de/trac/kieler/wiki/LayoutLibraries Встречался мне интересный пример с исходниками, где есть обход препятствий: http://www.javagaming.org/index.php/topic,21301.0.html Может быть из него удастся что-то полезное извлечь. |
| Автор: mgarin 17.8.2010, 14:30 |
| Вобщем, всем спасибо, буду думать над своим конкретным случаем и что будет оптимальнее применить. Вероятно придется повозиться и потестить  |
