As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened,
visit the help center for guidance.
Closed 8 years ago.
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 http://img260.imageshack.us/img260/5458/nodesr.png
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.
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.
Why don't you look in Dia source code to see how they are doing it?
http://live.gnome.org/Dia/Download
to extend @honk answer: for smoother curves you can just take 3 or 4 pivot points and connect them using quadratic/cubic bezier lines.
this is an example in javascript from raphael plotting library
There's not really a need for anything dramatic beyond directly drawing onto Cartesian coordinates. Simple heuristics can be used to handle the pathing and likely to hit the optimal minimum number of angles the majority of the time, but and likely the shortest length path even more often. All of this can be done dynamically as you require, but while maintaining precision of graphics without breaking the screen up more discretely that it needs to (pixels should remain the most discrete level) and without the need for complex algorithms.
For the overlay, just set all pixels to the color of your lines and modify the alpha channel bits to transparent or opaque depending on if the pixel is or isn't part of the line. To figure out which bits that are part of the line requires a bit of geometry, but that's a piece of cake once you have everything in place.
To figure out how to draw your line onto the alpha channel, you'll need to figure out the style of your lines. A lot of what you'll do depends on style. A common style is using straight lines that are horizontally and veritcally aligned with quarter circles for right angles.
For the "avoidance" algorithms, these aren't too difficult to implement when you just want to avoid the "boxes" representing your nodes... to decluster all your lines is a bit larger of a task and something that not even Visio employs. To avoid the boxes/nodes, using the midpoint between the edges of the box (such as the vertical edges between geo1 and geo3) is nice to do for symmetry and then picking a simple predefined distance to keep non-connecting lines (that is lines that do not connect to that particular box) away from the boxes also works well. A generalized algorithm for this is simple to do, but a little too verbose to describe here, but is essentially a set of generalized checks and switches working on horizontally and vertically align lines and quarter turns. If you end up wanting more detail on how to do this, just post a comment on this answer.
If you're looking for something that's already made for you, the type of connections and rearranging that you want really depends on the application and not a lot of people make tools that are low in demand or too specific of a demand. Obviously this type of software is out there since Visio and others employ it, but whether or not it's available as open source or part of some other free libraries I'm not certain.
