Somewhat OT, line routing for diagramming tool

[pherthyl]

Hi everyone,

Sorry, this is a little off topic. I have a "boxes and lines" type program using QGraphicsView, where people can drag boxes and connect them with "smart" connectors. Just like Visio, openoffice draw, Dia, etc. A connector line can be attached from any side of one box to any side of another box, and be routed so that it won't cross the start or end box. (I've attached a pic of some example routings it would do)

I've got a simple implementation, but it's not smart at all, just does a sort of ok job most of the time. What I want is something that can connect two boxes with a line and respect some basic rules of symmetry (like putting the corners halfway between two points)...

It seems like such a simple problem, but I can't for the life of me figure out a good way to do it. I thought about just special casing all the different scenarios, but that just seems like it'll be a mess. In the past I've also implemented an A* pathfinding algorithm, but it seems way overkill for something as simple as this, and I don't know how I would divide up the space into a coarser grid if the start and end points can be at any pixel coordinates...

So, anyone done this before? I must not be searching for the right terms because my google searching is bringing up nothing and I'm getting really discouraged... Any help greatly appreciated.

[aamer4yu]

Did you have a look at the Diagram scene example in Qt demo ? may be it will give u some idea :)

[pherthyl]

The diagram example is unfortunately of no help. They only have straight arrows, which are easy. What I need is rectilinear connecting lines, and thus an algorithm to find the path for them.

[wysota]

What have you tried so far?

[maverick_pol]

Hi,

It look as not a very complex task. Could you list the things you need to be done so I can list my ideas for the issues? thanks.

[pherthyl]

What have you tried so far?

Well, in the very beginning of this app, before graphicsview existed, the scene was based on a grid, and I implemented line routing using an A* pathfinding algorithm. This worked fairly well. However, it was quite computationally intensive even for very simple paths, and at the time I could always guarantee that my line start and endpoints were on grid corners (ie, start/end pt.x%GRIDSIZE == 0 and start/end pt.y%GRIDSIZE == 0) which simplified things greatly.

My current implementation on graphicsview is much less intelligent, If both ends of the line are connected to a side of a box, it will make a line with two corners connecting the two. This works for some cases (see attached screenshot of cases where it does and doesn't work), but is far from ideal. If you use a program like Visio, it makes much more intelligent decisions about where to route lines when connecting boxes.

[pherthyl]

Hi,

It look as not a very complex task. Could you list the things you need to be done so I can list my ideas for the issues? thanks.

Yes, indeed it seems like it should be simple.. That's why I'm pulling my hair out because I've spent so much time on it. :(

I've attached a diagram of the scenarios that the line routing algorithm should behave well in. The first three examples of connection types are critical, the last two are less important, since people are unlikely to use them much. Of course, each example can also be connected to different sides of each box, the examples are just representative of the types of line routing that should be supported. So far my algorithm only does scenario 1 well.

[wysota]

I'd say a possible nice solution is to make a direct connection and then try to fix it if it breaks some rules. You should probably minimize the Manhattan distance and the number of intermediate points (the latter having a higher priority). There is a number of heuristic algorithms that should work just fine (simulated annealing, for instance) but you can invent your own heuristic algorithm as well. When you have a direct connection, there are only two possible solutions with one intermediate point. Try them. If that fails, find a bounding rect of objects blocking you and try to go around using two intermediate points (two solutions again, I think). In most cases this should be sufficient. If not, try to divide your problem into subproblems and try the same algorithm.