Заголовок, однозначно, требует пояснение.

Думаю, многие работали с тем же Visio или подобными приложениями - там есть возможность линковать
различные фигуры линиями или стрелками.

Так вот меня интересует подобный функционал...


1. Предположим есть некая абстрактная область на которой лежит 10 прямоуголников (в случайных местах, могут пересекаться или полностью перекрываться друг другом) 
2. Есть точка A(x,y) и точка B(x2,y2)

Необходимо отрисовать линию из A в B избегая вех прямоугольников но при этом кратчайшим путем. Также необходим некий настраиваемый отступ от прямоугольников.


Думаю, тема изъезженная, но найти что-либо сложно ибо поисковики пока не умеют искать по описанию-трактату =/

Интересует - есть ли какая готовая библиотека или готовый алгоритм на данную тему?

Первое, что пришло на ум - волновой алгоритм.

Готовая библотека: http://www.yworks.com/en/products_yfiles_about.html
Из open source есть библиотека http://www.eclipse.org/gef/zest/, в которой реализованы алгоритмы раскладки графа и проведения ребер.

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:42

Нашел подробное описание алгоритма (http://www.codenet.ru/progr/alg/way.php)
Впринципе, оно конечно должно работать, вот только у меня есть сомнения насчет оптимальности.

У меня область может достигать размеров 10000х10000 и для каждой отдельной линии будет вестись пересчет при каждой отрисовке...
Даже если кэштровать расчеты - любое передвижение объектов будет сбрасывать кэш и приводить к жутким подлагиваниям.

Но это в теории...

В целях оптимизации можно попробовать следующий подход: считать узлами графа для поиска пути не отдельные пиксели, а квадраты 10x10 или 20x20. А уже потом, в пределах полученного коридора, строить линию. Это правда потребует размещения объектов с шагом, соответствующим стороне квадрата.

Также можно попробовать заменить волновой алгоритм алгоритмом Дейкстры.

Это сообщение отредактировал(а) jk1 - 9.8.2010, 13:47

кратчайшая линия будет либо полностью прямой, либо иметь изломы на углах прямоугольников

так что узлами графа можно считать углы прямоугольников и исходную с конечной точки
рёбра - отрезки между точками, если они ничего не пересекают, если пересекают - нет ребра

Добавлено через 1 минуту и 38 секунд
отступ в первом приближении можно считать прямоугольником с бОльшими сторонами

если прямоугольник с отступом будет более сложной фигурой, алгоритм соответственно усложнится...

Вроде бы там можно только алгоритм проведения ребер вытащить, хотя я сам не пробовал.

Еще вот ссылки собраны по теме: http://rtsys.informatik.uni-kiel.de/trac/k...LayoutLibraries

Встречался мне интересный пример с исходниками, где есть обход препятствий: http://www.javagaming.org/index.php/topic,21301.0.html Может быть из него удастся что-то полезное извлечь.

Вобщем, всем спасибо, буду думать над своим конкретным случаем и что будет оптимальнее применить.
Вероятно придется повозиться и потестить