How to draw S-curved arrows between boxes

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

by alex_stoddard • 5 years ago

664 57 5 years ago

dragonman225.js.org

nescioquid• 5 years ago

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.

pintxo• 5 years ago

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

kazinator2• 5 years ago

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.

db48x• 5 years ago

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

allenu• 5 years ago

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.

gunshowmo• 5 years ago

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

anonymous5322• 5 years ago

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.

anamexis• 5 years ago

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.

AceJohnny22• 5 years ago

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

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

quickthrower2• 5 years ago

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.

anonymous5322• 5 years ago

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.

dragonwriter• 5 years ago

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

monkeycantype3• 5 years ago

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

mbrodersen• 5 years ago

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?

arendtio• 5 years ago

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.

Minor49er• 5 years ago

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.

klyrs• 5 years ago

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?

javajosh• 5 years ago

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.

kazinator2• 5 years ago

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.

Akronymus• 5 years ago

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_• 5 years ago

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/

vjeux• 5 years ago

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!

runeb• 5 years ago

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

jamessb• 5 years ago

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

rvnx• 5 years ago

Excellent :)

melony• 5 years ago

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.

jimmygrapes• 5 years ago

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.

TacticalCoder• 5 years ago

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)

raphlinus• 5 years ago

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

OnlyMortal• 5 years ago

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.

throw10920• 5 years ago

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

adolph• 5 years ago

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

jedberg• 5 years ago

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!

alejohausner2• 5 years ago

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

matsemann• 5 years ago

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

amelius• 5 years ago

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.

alejohausner2• 5 years ago

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

alhirzel2• 5 years ago

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.

monkeycantype3• 5 years ago

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}"`;

jeffreygoesto• 5 years ago

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

graphviz2• 5 years ago

Agree.

CyberSimon• 5 years ago

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

bullen• 5 years ago

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

Waterluvian• 5 years ago

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_malhar• 5 years ago

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.

resonious• 5 years ago

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 ;)

zestyping• 5 years ago

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

thewisenerd• 5 years ago

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

cyber_kinetist• 5 years ago

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.

How to draw S-curved arrows between boxes

Related Stories