[HN Gopher] How to draw S-curved arrows between boxes
___________________________________________________________________
How to draw S-curved arrows between boxes
Author : alex_stoddard
Score : 605 points
Date : 2021-12-22 17:11 UTC (1 days ago)
(HTM) web link (dragonman225.js.org)
(TXT) w3m dump (dragonman225.js.org)
| nescioquid wrote:
| 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.
| kazinator wrote:
| 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 wrote:
| That's what I do too. Then I make the graph output into a
| test.
| pintxo wrote:
| If you want to add another level of complexity, add (non-
| overlapping) labels to your boxes and arrows ...
| [deleted]
| allenu wrote:
| 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.
| Waterluvian wrote:
| 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.
| kazinator wrote:
| 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.
| cyber_kinetist wrote:
| 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.
| alejohausner wrote:
| 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
| SPDurkee wrote:
| This is a great github to play around with dot online:
| https://dreampuf.github.io/GraphvizOnline/
| alhirzel wrote:
| 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.
| jeffreygoesto wrote:
| 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
| monkeycantype wrote:
| 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}"`;
| alhirzel wrote:
| Cool, I appreciate you sharing the info on your process!
| monkeycantype wrote:
| You're welcome
| resonious wrote:
| 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 ;)
| bullen wrote:
| 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
| klyrs wrote:
| 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 wrote:
| _> 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.
| jedberg wrote:
| 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!
| alejohausner wrote:
| 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 wrote:
| 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
| anonymous532 wrote:
| 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 wrote:
| > 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.
| AceJohnny2 wrote:
| Not so weird. Here's a random example, from Wikipedia:
|
| https://en.wikipedia.org/wiki/Force-
| directed_graph_drawing#/...
| TobTobXX wrote:
| These are straight lines. Not sure you even _want_ Bezier
| curves in this context, striaght lines are probably clearer
| in these graphs with hundreds of connections.
| AceJohnny2 wrote:
| Ah, good point.
| dragonwriter wrote:
| Is someone selling it as some kind of universal solution for
| production diagramming problems of all scales, or is this just
| unnecessary negativity?
| mbrodersen wrote:
| 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?
| monkeycantype wrote:
| 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
| arendtio wrote:
| 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.
| quickthrower2 wrote:
| 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.
| anonymous532 wrote:
| 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_thibedeau wrote:
| There is a section in Graphics Gems 3 that describes a
| layout system for an Atari ST DAW app.
| drudru wrote:
| Which chapter in Gems III has this? I couldn't find it.
| sriram_malhar wrote:
| 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.
| Minor49er wrote:
| 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.
| gunshowmo wrote:
| Fantastic article. This kind of insight into how people break
| down complicated problems into more manageable pieces is
| extremely valuable.
| emmanueloga_ wrote:
| 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/
| throw10920 wrote:
| 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 wrote:
| Agreed, maybe something expressed in human learnable non-code
| procedural notation.
| TacticalCoder wrote:
| 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 wrote:
| 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
| vjeux wrote:
| 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 wrote:
| Very interesting, thank you for this! Just a note that your
| demos do not seem to load images.
| jamessb wrote:
| Another related blog post is "Building the Image Grid from
| Google Photos": https://medium.com/@danrschlosser/building-
| the-image-grid-fr...
| rvnx wrote:
| Excellent :)
| melony wrote:
| 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 wrote:
| 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.
| amelius wrote:
| 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.
| zestyping wrote:
| 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 wrote:
| slightly(?) related: https://www.zindlerb.com/improving-
| flowchart-editing-tools/
|
| didn't gather a lot of discussion though...
___________________________________________________________________
(page generated 2021-12-23 23:02 UTC)