How to draw S-curved arrows between boxes(dragonman225.js.org)

664 pointsby alex_stoddardvor 5 Jahren57 comments

dragonman225.js.org

How to draw S-curved arrows between boxes

https://dragonman225.js.org/curved-arrows.html

58 comments

I enjoyed reading this because it reminded me of a moment of hubris as junior developer. I was working with a complicated data structure I wanted to visualize, so I decided to write some quick code to basically read the data structure and output a graph as rectangles and lines connecting them.

I was chastened by the complexity of just drawing the lines between boxes so that they didn't overlap (as much as possible) and were drawn on facing sides (one of the later problems discussed in the article). I don't recall how I did it, but I do remember a sudden refresher on matrix multiplication.

It drove home how simple things can be more complicated than you might expect.

EDIT: also, I appreciated the way the article was written. No cruft.

pintxovor 5 Jahren

If you want to add another level of complexity, add (non-overlapping) labels to your boxes and arrows ...

[deleted]vor 5 Jahren

kazinatorvor 5 Jahren

Today (or twenty years ago, for that matter) I'd just output the data structure in graphviz syntax and throw it at the dot tool.

db48xvor 5 Jahren

That’s what I do too. Then I make the graph output into a test.

allenuvor 5 Jahren

I've had similar experiences on many projects. You start out thinking something is going to be super simple and you provide estimates that match your naive design and later find it'll take 2.5x-5x longer than you wanted. It's definitely humbling.

Nowadays when I have new work that has a lot of unknowns, I try to jump in and create a proof of concept as quickly as I can, even if it requires a ton of hacks. I want to know right off the bat if there's something obvious that's going to make the task take much longer than I wanted.

gunshowmovor 5 Jahren

Fantastic article. This kind of insight into how people break down complicated problems into more manageable pieces is extremely valuable.

anonymous532vor 5 Jahren

It's cute and definitely a great way to "draw S-curved arrow between boxes", but, under the assumption of being built to be used within a real project with dozens or hundreds of overlapping connections, this, like many other node systems, fails to be usable unless you push the complexity somewhere else.

anamexisvor 5 Jahren

> under the assumption of being built to be used within a real project with dozens or hundreds of overlapping connections

This is an odd assumption to make.

AceJohnny2vor 5 Jahren

Not so weird. Here's a random example, from Wikipedia:

https://en.wikipedia.org/wiki/Force-directed_graph_drawing#/...

TobTobXXvor 5 Jahren

These are straight lines. Not sure you even _want_ Bézier curves in this context, striaght lines are probably clearer in these graphs with hundreds of connections.

AceJohnny2vor 5 Jahren

Ah, good point.

quickthrower2vor 5 Jahren

In that case the tool would need to lay out everything holistically but while it might do great arrow wise it could be useless for the user if they wanted the diagram a certain way for a reason.

anonymous532vor 5 Jahren

Yes, that is what I've noticed too. On medium/big projects macro-level(holistic) arrow functionality is far more important than having beautifully curved arrows from node A to node B. Solving that problem strangely resembles routing on a circuit board with buses, labels, colors, layers etc.

kevin_thibedeauvor 5 Jahren

There is a section in Graphics Gems 3 that describes a layout system for an Atari ST DAW app.

drudruvor 5 Jahren

Which chapter in Gems III has this? I couldn’t find it.

dragonwritervor 5 Jahren

Is someone selling it as some kind of universal solution for production diagramming problems of all scales, or is this just unnecessary negativity?

monkeycantypevor 5 Jahren

but it's solving one part of the problem, and doing a good job at it. I've been making diagrams using graphviz, but setting the positions and edge curves manually, pulling the nodes and edges out of a list in excel

https://github.com/mathew-j-davis/boxesandarrows

I've been setting the 'waypoints' for more complex curves (curves with many bends) manually (typing the bezier numbers in by hand), while I try and figure out how I want them routed, you're right it's not easy figuring out rules for where edge should go, let alone implementing it

mbrodersenvor 5 Jahren

I don’t think the author is making any claims about the algorithm being able to handle more than the 2 box case. Why the negativity?

arendtiovor 5 Jahren

I think it depends on the use case and the organization/ordering of the boxes, which is not the focus of this library.

So for example, if the user is responsible for organizing the boxes and there is also a way to create custom arrows, this library can be used to suggest arrows, which might be good 95% of the time. That would be better than many of the tools I have used over the years.

However, if you want to generate a final diagram and can't guarantee, that the order of boxes doesn't allow for overlapping connections, this library is probably the wrong choice.

Minor49ervor 5 Jahren

This reminds me of a project I worked on that had an interface with draggable boxes just like this. The library that we used rendered the boxes as divs while the arrows were drawn as SVGs. Apparently there was a bug on Internet Explorer 11 where CSS transforms being applied to SVGs would cause the browser to slow to a crawl, or crash entirely if too many were happening at once.

To get around it, I switched the line drawing function for IE11 so that it would draw two divs that would extend from the middle of each box and touch corners in the middle (basically figure 4 in the article), then style them with a curved border on the appropriate side. While not as elegant as what's shown here, it was convincing enough that nobody noticed any visual difference between it and the regular version.

klyrsvor 5 Jahren

Such an innocent-sounding problem, but I've drawn tons of figures in inkscape, tikz and matplotlib and I swear, I'd never stop fidgeting with curved arrows if time was immaterial.

But of course, I have Opinions that would keep me from using this in practice. For example, my favorite style is similar to a half curly-bracket (or, taste depending, an integral symbol) -- two small semicircles connected by an axis-aligned line.

Edit: oh, and question from the peanut gallery... what if one box is fully within the other, and centered?

javajoshvor 5 Jahren

>I have Opinions

Good. Then fork the library and modify it to your liking, optionally republish.

>one box is fully within the other, and centered

This implies containment/stacking and wouldn't require an arrow. However, you could do worse than drawing 4 arrows from the edges of the surrounding rectangle.

kazinatorvor 5 Jahren

In cases when the boxes overlap, there are ways to choose an arrow which will not cross the boxes. But this is prevented by the constraint that the starting and ending points must be on the midpoint of a box edge. If the midpoint of the a given edge is occluded by a box, or occludes a box, then that edge is not considered, even though it is partially visible and has a viable point for the arrow.

E.g. if we could start an arrow in the middle of the small protruding "ledge" of the bottom box, we could do this:

    ,-------.
   :         :
   :         v
   : +----------------+
   : |                |
  +----------------+  |
  |                |--+
  |                |
  +----------------+

It's not written in stone that box-and-arrow diagrams must be connected by edge midpoints. That can't even work well any time you have multiple arrows emanating or terminating on the same edge.

Very good first iteration round, though.

Akronymusvor 5 Jahren

So, you could take the midpoint of non overlapped edge segments? And split that segment as more arrows leave from it? Sounds like a good further step.

Another one would be reducing the amount of crossover between different arrows.

emmanueloga_vor 5 Jahren

GUI algorithms like these are not well documented anywhere (except, of course, all over the web and in source code! :-) ...

Would be nice to have a site, maybe a wiki, dedicated to this kind of thing.

Other interesting problems in this area:

* Layout algorithms

* Automatic assignment of keys for navigation (for nav w/o using a mouse)

* Popup menu prediction [1]

* Text breaking / paragraph layout [2]

* Etc, etc, etc ...

1: https://bjk5.com/post/44698559168/breaking-down-amazons-mega...

2: https://xxyxyz.org/line-breaking/

vjeuxvor 5 Jahren

Back in 2012 I made a series of blog posts about all the unique image algorithms I could find:

- Facebook (that I designed): https://blog.vjeux.com/2012/image/image-layout-algorithm-fac...

- Google Plus: https://blog.vjeux.com/2012/javascript/image-layout-algorith...

- Google Plus, finding best breaks, which also explains fancy text layout algorithm: https://blog.vjeux.com/2014/image/google-plus-layout-find-be...

- Lightbox: https://blog.vjeux.com/2012/javascript/image-layout-algorith...

- Lightbox Android: https://blog.vjeux.com/2012/javascript/image-layout-algorith...

- 500px: https://blog.vjeux.com/2012/javascript/image-layout-algorith...

I hope that’s useful!

runebvor 5 Jahren

Very interesting, thank you for this! Just a note that your demos do not seem to load images.

jamessbvor 5 Jahren

Another related blog post is "Building the Image Grid from Google Photos": https://medium.com/@danrschlosser/building-the-image-grid-fr...

rvnxvor 5 Jahren

Excellent :)

melonyvor 5 Jahren

One of the most difficult programming challenges I have encountered is calculating and displaying automatic drag and drop alignment guidelines/rulers (like those in Figma and PowerPoint that show up when you drag two element close to each other or near certain ratios) efficiently. They are not documented anywhere despite being a very common pattern. Most drag and drop libraries and framework don't have out of the box support for it as it requires deep low level integration.

jimmygrapesvor 5 Jahren

On a related note, the tab stop/indent marker/ruler in MS Word (and the related ruler/guidelines in Photoshop and others) are sorely missing in the generally available UI elements. For text on the web I get it, since it's all markdown and/or html, not exactly WYSIWYG-emulating-paper. Guidelines for the purposes of snap alignment are relatively easy to implement and have tons of use, but I have not seen any good ones in the wild yet.

TacticalCodervor 5 Jahren

That line-breaking link is really great, I enjoyed it a lot! However it barely scratches the surface: there's no good line-breaking without hyphenation. And then even once you have a great H & J algorithm (Hyphenation and Justification), you have the visual problem of "rivers" (be it text or print): a "river" behind when on one line you have the space between two words nearly matching another space between two words on the next line, then third line, etc.

I don't know if modern typesetting software like InDesign do solve this automatically or not. The web certainly don't (although with CSS and the "shy" Unicode char you at least get some control on the 'H' part of "H & J"). Back in my typesetting days QuarkXPress had nothing to help with rivers: you had to detect them visually and then "fudge" the paragraph a bit (by forcing a line-break or an hyphenation).

I always wondered: certainly if you start with a good H & J algorithm, it must be possible to try a few candidates and determine, programatically, which one has the least obvious rivers? Fascinating stuff IMHO.

P.S: I also wonder if it's because algorithms for layout out paragraphs are so bad on the web that justification is typically frowned upon on the Web? (it certainly rules king in printed books)

raphlinusvor 5 Jahren

Android has a sophisticated algorithm for line breaking, including hyphenation. It's similar to that of InDesign (both were strongly inspired by the Knuth-Plass algorithm used by TeX), but tuned for mobile use. In particular, it's pretty shy about adding hyphens, but if a well-placed hyphen will prevent a two-line sentence from spilling to three (in which the last word is by itself), it will do so fairly aggressively. I'm quite proud of that.

Unfortunately, I don't have a good writeup of that, but some of the details are in this ATypI talk[1].

[1]: https://www.youtube.com/watch?v=L8LD0BM-Vjk

maxwell86vor 5 Jahren

Sounds like a topic for your blog.

OnlyMortalvor 5 Jahren

It’s been many a year since I thought of XPress.

I recall I did a Mac XPress XTension that used GUSI (sockets) to talk to a 4D server to grab artwork. I even had it multi-threading (co-operative of course) and a UI using PowerPlant. Rather a hack.

throw10920vor 5 Jahren

Yes! Please! Every one of these problems are interesting ones that have been solved before...but the solutions are packaged up into massive systems (good luck finding the code for actually executing element layout in Chromium) and then it seems like are never discussed again on places like Reddit, HN, Stack Exchange, or even among other programmers I know IRL.

In particular, I'm incredibly interested in layout algorithms - I'm working on building a GUI toolkit, for which I need layout algorithms to lay out widgets, but can't find anything other than descriptions of how to use existing systems...

adolphvor 5 Jahren

Agreed, maybe something expressed in human learnable non-code procedural notation.

jedbergvor 5 Jahren

We recently redid our landscaping, which included making the edge of the driveway and S curve. I thought my landscaper was pretty clever.

He took a flimsy pvc pipe, nailed it down at the beginning and end of the curve, and it bent into a perfect S curve that he then spray painted down to follow.

It’s amazing how physics and nature can solve these problems for you!

alejohausnervor 5 Jahren

This is a mechanical spline [1]: a thin strip of wood constrained at one or more points, or "knots". They were used by ship builders and draftsmen before mathematicians and programmers invented cubic curves for computer aided design. IIRC, bending a beam with a single point force and no bending moments at the ends gives you a quadratic curve shape, and other, and adding bending moments gives you cubic curves.

1: https://en.m.wikipedia.org/wiki/Flat_spline

matsemannvor 5 Jahren

Reminds me of a video I saw of someone using bendable woods to draw curves in the old days. Managed to find the concept again https://en.m.wikipedia.org/wiki/Flat_spline

ameliusvor 5 Jahren

This looks like a nice result that can be useful in some cases, but it is limited to a single arrow. When you have more than one arrow, you get constraints like "minimize the number of crossings" and then "minimize total arrow line length". At this point, it becomes way more complicated.

alejohausnervor 5 Jahren

The graphviz system [1], originally from at&t labs, has a program called "dot" that does this kind of thing very well, including routing the arrows around other boxes that may be in the way. It's been open sourced. It's also been ported to the web [2]

1: https://graphviz.org/

2: http://www.webgraphviz.com/?tab=map

CyberSimonvor 5 Jahren

This is a great github to play around with dot online: https://dreampuf.github.io/GraphvizOnline/

alhirzelvor 5 Jahren

Sometimes I wish there were a more modern replacement for Graphviz. There are things that it doesn't handle very well (e.g., nested subgraphs) and I feel like there are good (albeit proprietary) algorithms which could make their way into a general package.

monkeycantypevor 5 Jahren

I use dot, and manually position everything, then use the neato -n2 option to render:

`dot -T ${format} -n${n} ${verbose>1?"-v ":""}-Goverlap-true -Gsplines=false -Kneato -o "${ output }" "${ input }"`

this still doesn't do subgraphs well,

so I sometime do the 'groups' in a separate document, then composite the layers with image magick

`magick composite ${verbose>1?"-verbose ":""}-gravity NorthWest "${a}" "${b}" "${png_output}"`;

alhirzelvor 5 Jahren

Cool, I appreciate you sharing the info on your process!

monkeycantypevor 5 Jahren

You’re welcome

jeffreygoestovor 5 Jahren

Not as easy to use, because it does not have a simple cli, but nested layouts are better than dot's with the Eclipse Layout Kernel. There is a JavaScript version, as well and you can try it in recent plantuml versions.

[0] https://www.eclipse.org/elk

[1] https://github.com/eclipse/elk

[2] https://plantuml.com/elk

graphvizvor 5 Jahren

Agree.

graphvizvor 5 Jahren

Also, this is a great problem, and we tried to solve it in a more general context. http://dpd.cs.princeton.edu/Papers/DGKN97.pdf

I believe it's an open problem what makes a curve look "natural" or how to do a good job of routing multiple splines around obstacles so they do not intersect each other, though the work of Keean Crane at CMU seems promising: https://www.cs.cmu.edu/~kmcrane/Projects/RepulsiveCurves/ind...

bullenvor 5 Jahren

Or you just draw stright lines and save yourself some trouble.

Because they are eaiser to stack without getting garbled!

http://move.rupy.se/file/logic.html

Waterluvianvor 5 Jahren

I think this post finally made something click for me: runtime generated SVG is incredibly powerful and I really need to add it to my toolbox.

sriram_malharvor 5 Jahren

I don't see why arrows must start at the middle of an edge. Sometimes multiple arrows from an edge look better if the end points are spaced apart (to emphasise the connectivity visually, for example). There are times when an arrow is positioned just on the inside of a corner, depending on what it is connected to and the angle of the arrow with respect to the edge.

In the final analysis, one should strive to get a visually balanced look, which takes into account placement, thickness of lines, density of information etc. There is no one-size fits all.

resoniousvor 5 Jahren

This is a really great writeup. Whenever I try to draw diagrams using software tools, I always run into stuff like this and am disappointed with the tool's ability to help me out.

I've actually taken up hand-drawing diagrams lately and it's worked well. I get a lot of comments at work - "haha wow nice art!" (sarcasm) followed by "actually this is really easy to follow". I feel like it's both faster to draw and a more accurate representation of my mental model when I draw by hand.

But hey, if the diagramming tools were smart like in this post, maybe I'd go back to the tools for awhile ;)

zestypingvor 5 Jahren

The algorithm selects the arrow option with the shortest curve length, but I think the results would look better if it selected for the option with the least bends and inflection points.

Here's a specific example: https://imgur.com/a/1n2JiB3

thewisenerdvor 5 Jahren

slightly(?) related: https://www.zindlerb.com/improving-flowchart-editing-tools/

didn't gather a lot of discussion though...

cyber_kinetistvor 5 Jahren

The blog post is not bad, but as a graphics programmer I don't get why this one algorithm is made as a full NPM package. (Getting some left-pad vibes again...) The actual source code is about 200 lines (which can probably be shortened down to 50 if you try enough), why don't you just include it as a code snippet in that blog post for others to copy in their codebase? The code itself is pretty straightforward to understand, and you're probably going to make some little modifications to suit your needs.