1

I'm in the process of making a swimlane diagram but can't come up with a good algorithm to automatically lay out the lines that connect the nodes in the diagram. What I essentially want is this.

enter image description here

However, I don't have any protection against lines overlapping or intersecting right now and it sometimes gets very messy.

Does anyone know a way to detect if a line will intersect ANY of the lines already drawn? One idea that I've come up with is to store the paths in an array or table and check the entire table every time a new line is slated to be drawn but that does not seem efficient.

I'm doing this in javascript and java through the use of GWT so maybe there is an easy way to solve this using one of the tools provided by these languages?

MadProgrammer
  • 343,457
  • 22
  • 230
  • 366
Offset
  • 11
  • 2
  • Something like [this](http://stackoverflow.com/questions/15594424/line-crosses-rectangle-how-to-find-the-cross-points/15594751#15594751) might help - Also, pick a language. JavaScript and Java are not the same thing or related in any way... – MadProgrammer Jul 16 '13 at 22:32
  • I can program in both javascript and java. If javascript, it will end up getting wrapped in JSNI in GWT (for ease of debugging later on). If Java, then GWT will output to javascript anyways. The link you provided isn't really related to my problem because I'm not checking if the lines intersect a square. Also I can't exactly check if lines intersect via slope because these lines will be bent. I could potentially separate each line into segments, however, that would be very tedious. I'll save that as a last resort. – Offset Jul 16 '13 at 23:24
  • Line intersection is line intersection, the fact that the example was focusing on a rectangle and line intersection is slightly irrelevant as the solution breaks it down to line/line intersection – MadProgrammer Jul 16 '13 at 23:38
  • If you are constructing a diagram with the same properties as the picture you showed, and the node locations are pre-determined and can't be changed, then there should be an easy-to-define method to draw your bent lines to minimize the number of intersections, and so detecting intersections might not even be necessary (unless you want to draw the little jump over the intersection). If you can minimize the number of intersections, do you still want to detect them? – user2566092 Jul 16 '13 at 23:42
  • Yes, I'm writing this with the intention that once the nodes are drawn, they cannot be moved. And YES, I'm definitely fine with minimizing intersections and skipping intersection detection. What is this magical algorithm you speak of? o__o – Offset Jul 16 '13 at 23:45

1 Answers1

0

If your real issue is to minimize the line intersections, there are several algorithms that try to accomplish this in diagrams. Check this link for example, there are also more algorithms that are used in auto routing for electric design automation that are also used in this kind of diagrams, like Lee algorithm, or A* Algorithm.

I don't know if the tools that you are using have enough flexibility to implement this kind of algorithms, usually you need to implement your own heuristic according to the specific type of diagram, but I hope that this links are enough to give you good ideas.

Minimizing the line intersections in a graph is a difficult NP-Hard problem, check this link (about the crossing number) for more information.

Good luck.

Miguel A. Carrasco
  • 1,379
  • 1
  • 15
  • 26