What are some good algorithms for drawing lines between graph nodes?

views:

115

answers:

+3 Q:

What are some good algorithms for drawing lines between graph nodes?

What I'm specifically grappling with is not just the layout of a graph, but when a user selects a graph node and starts to drag it around the screen area, the line has to constantly be redrawn to reflect what it would look like if the user were to release the node. I suppose this is part of the layout algorithm?

Also some applications get a bit fancy and don't simply draw the line in a nice curvy way, but also bend the line around the square shaped node in almost right angles. See attached image and keep in mind that as a node is dragged, the line is drawn as marching ants, and re-arranged nicely, while retaining its curved style.

alt text

+1 A:

If your diagrams are not crazy full you should not need an extra-fancy algorithm for this, but just use some common sense.

Cover the surface with a rectangular grid and then find a way to connect to boxes with straight lines along grid lines with a minimum number of angles: if the boxes are not on the same grid lines and you don't care where you connect you need one angle if there is no other node in between. If there are e.g. nodes in the way you need at least one more angle.
As a second step for fuller diagrams add code that not only optimizes for minimal number of edges but also for minimal length of the lines. If your diagrams are not crazy full this should be hardly noticeable in terms of application response.
For extra eye candy round the angles taking into account the lengths of both legs and checking for intersections with other objects on the surface. I would use 90°-pies of circles and adjust the radius of the circles (apparently not what was done above) -- for longer legs the radius should be bigger. Maybe the toolkit you are using can help you here.

honk 2010-03-17 04:49:09

for 1 a full grid probably isn't necessary, a hanan grid of the points to connect and bits to avoid should suffice i think

jk 2010-03-17 09:43:22

Thanks, I'm not looking to reinvent the wheel, although I'm sure we could all come up with close approximations of finely tuned algorithms. I'm wondering if there is anything out there already that does this for you to some greater extent?

ApplePieIsGood 2010-03-17 11:17:26

Are you familiar with Graphviz? I'm not sure how "dynamic" and resuable the layout algorithms are, but it could be a good starting point.

Dan 2010-03-30 06:19:02

Why don't you look in Dia source code to see how they are doing it? http://live.gnome.org/Dia/Download

Fakrudeen 2010-03-30 08:49:57

ansaurus

tags:

views:

answers:

What are some good algorithms for drawing lines between graph nodes?

related questions