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...
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.
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.
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)
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].
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.
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:
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.
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.
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.
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]
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.
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.
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...
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!
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.
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?
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.
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.
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 ;)
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.
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.
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.
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.
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.
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.
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.
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.
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
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
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.
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/