Results 1 to 8 of 8

Thread: Somewhat OT, line routing for diagramming tool

  1. #1
    Join Date
    Aug 2006
    Posts
    250
    Thanks
    19
    Thanked 49 Times in 36 Posts
    Qt products
    Qt4
    Platforms
    Windows

    Default Somewhat OT, line routing for diagramming tool

    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.
    Attached Images Attached Images

  2. #2
    Join Date
    Oct 2006
    Location
    New Delhi, India
    Posts
    2,467
    Thanks
    8
    Thanked 334 Times in 317 Posts
    Qt products
    Qt4
    Platforms
    Unix/X11 Windows

    Default Re: Somewhat OT, line routing for diagramming tool

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

  3. #3
    Join Date
    Aug 2006
    Posts
    250
    Thanks
    19
    Thanked 49 Times in 36 Posts
    Qt products
    Qt4
    Platforms
    Windows

    Default Re: Somewhat OT, line routing for diagramming tool

    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.

  4. #4
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,365
    Thanks
    3
    Thanked 5,014 Times in 4,792 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: Somewhat OT, line routing for diagramming tool

    What have you tried so far?

  5. #5
    Join Date
    May 2007
    Location
    Lublin, Poland
    Posts
    345
    Thanks
    40
    Thanked 8 Times in 4 Posts
    Qt products
    Qt3 Qt4
    Platforms
    MacOS X Unix/X11 Windows

    Default Re: Somewhat OT, line routing for diagramming tool

    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.
    Qt allows you to use everything you want
    wysota
    --------------------------------------------------------------------------------
    #if defined(Q_OS_UNIX) && defined(QT_DEBUG)
    abort(); // trap; generates core dump
    #else
    exit(1); // goodbye cruel world
    #endif

  6. #6
    Join Date
    Aug 2006
    Posts
    250
    Thanks
    19
    Thanked 49 Times in 36 Posts
    Qt products
    Qt4
    Platforms
    Windows

    Default Re: Somewhat OT, line routing for diagramming tool

    Quote Originally Posted by wysota View Post
    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.
    Attached Images Attached Images

  7. #7
    Join Date
    Aug 2006
    Posts
    250
    Thanks
    19
    Thanked 49 Times in 36 Posts
    Qt products
    Qt4
    Platforms
    Windows

    Default Re: Somewhat OT, line routing for diagramming tool

    Quote Originally Posted by maverick_pol View Post
    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.
    Attached Images Attached Images

  8. #8
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,365
    Thanks
    3
    Thanked 5,014 Times in 4,792 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: Somewhat OT, line routing for diagramming tool

    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.

Similar Threads

  1. QTcpSocket exception.
    By Fastman in forum Qt Programming
    Replies: 9
    Last Post: 29th January 2008, 14:51
  2. Some very weird compilation warnings
    By MarkoSan in forum Qt Programming
    Replies: 21
    Last Post: 23rd January 2008, 17:48
  3. Qwizard crashed when created in a slot
    By joshlareau in forum Qt Programming
    Replies: 9
    Last Post: 15th January 2008, 10:16
  4. KDE/QWT doubt on debian sarge
    By hildebrand in forum KDE Forum
    Replies: 13
    Last Post: 25th April 2007, 07:13
  5. QTableView paints too much
    By Jimmy2775 in forum Qt Programming
    Replies: 2
    Last Post: 26th July 2006, 19:42

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Digia, Qt and their respective logos are trademarks of Digia Plc in Finland and/or other countries worldwide.