Motivation

I recently worked on some visualization with d3, rendering a directed graph of nodes with a force simulation. An easy way to render the edges of the graph is to simply draw a straight line, but that’s not very pretty. Instead, a neat trick is to introduce an invisible node inbetween two connected nodes, and then render a quadratic Bézier curve between the nodes, using the invisible node as control point.

This example shows the curved link between two nodes, without force simulation, the nodes can be dragged around interactively. The nodes are transparent to illustrate the actual ends of the curve.

The relevant code for rendering the path of the edges in d3:

var edgeElements = edgeLayer
    .selectAll(".edge")
    .data(edges);

edgeElements.enter()
    .append("path")
    .attr("class", "edge")
    .attr("stroke", "#ddd")
    .attr("stroke-width", 5);

// on update
edgeLayer
    .selectAll(".edge")
    .attr("d", e => {
        return "M" + e.source.x + "," + e.source.y
            + "Q" + e.intermediate.x + "," + e.intermediate.y
            + " " + e.target.x + "," + e.target.y;
    });

(See SVG:path docs for explanation of the M and Q commands.)

This connects the centers of each node, which is great for undirected graphs, but not very useful for directed graphs. Where and how should the arrow be rendered? And how can the curve be rendered only from node edge to node edge? This is particularly important if the nodes are transparent, as above, or have non-circular shapes, for instance based on an SVG pattern fill, a logo, etc..

Solution

Finding the touching points

The first step must be finding the touching points of the curve with the rim of the node. The “rim” will be assumed based on the radius of the node, even if the node itself might have an irregular shape, but since I want a little spacing between node and curve anyway, this is sufficient.

Wikipedia has a more thorough explanation of Bézier curves, but for what I’m doing I need this function:

\[ B\colon [0, 1] \Rightarrow \mathbb{R}^2 \] \[ B(t) \, = \, (1 - t)^2 P_0 + 2 (1 - t) t P_1 + t^2 P_2 \]

Where \(P_0\) and \(P_2\) are the end points of the curve and \(P_1\) is the control point. It’s easy to see that \(B(0) = P_0\) and \(B(1) = P_2\).

Let’s assume the radius of our node around \(P_0\) is \(r\), then we need to find the smallest \(t\), such that \(|B(t) - P_0| = r\), i.e. the \(t\) at which the curve is at a distance of \(r\) from \(P_0\) for the first time. In most curves there’ll only be one such point, but just in case the nodes are very close together, perhaps even overlapping, the first one is the point we want. The same can be done from the end.

I tried to solve this mathematically, but even for quadratic Bézier curves this grows into big expressions and polynomials of 4th degree, so I went with a binary search for a close approximation instead:

function calculateBezierPoint(P0, P1, P2, t) {
    return {
        x: (1 - t) * (1 - t) * P0.x + 2 * (1 - t) * t * P1.x + t * t * P2.x,
        y: (1 - t) * (1 - t) * P0.y + 2 * (1 - t) * t * P1.y + t * t * P2.y
    };
}

function findProximityPoint(P0, P1, P2, r) {
    var rSquared = r * r;

    var dt = 0.05;
    var t = dt;
    var lastWasLower = true;

    while (t >= 0 && t <= 1) {
        var p = calculateBezierPoint(P0, P1, P2, t);
        p.t = t;

        var distSquared = (p.x - P0.x) * (p.x - P0.x) +
                          (p.y - P0.y) * (p.y - P0.y);
        if (lastWasLower && distSquared > rSquared) {
            dt /= -2;
            lastWasLower = false;
        } else if (!lastWasLower && distSquared <= rSquared) {
            dt /= -2;
            lastWasLower = true;
        }

        if (Math.abs(dt) < 0.001 && distSquared > rSquared) {
            return p;
        }

        t += dt;
    }

    return {
        x: P0.x,
        y: P0.y,
        t: 0
    };
}

And the relevant code in d3 to render the path of the edge, which now first calculates the points on the curve close to the node edges and then uses those points as start and end of the curve:

edgeLayer
    .selectAll(".edge")
    .attr("d", e => {
        var start = findProximityPoint(e.source, e.intermediate, e.target, e.source.radius + 2);
        var end = findProximityPoint(e.target, e.intermediate, e.source, e.target.radius + 2);

        return "M" + start.x + "," + start.y
            + "Q" + e.intermediate.x + "," + e.intermediate.y
            + " " + end.x + "," + end.y;
    });

This works quite well, but it isn’t perfect. Since we use the same control point with different start points, the curve differs quite a bit. The ends also don’t necessarily point towards the center of the nodes anymore, which you can easily see by moving the control point around one of the points.

Adding an arrow

To illustrate this, below the same example with the original edge included, and including an arrow marker to better see where it points. For that the end’s proximity point must be pushed out a bit further (by the length of the arrow) and the arrow is achieved like this:

var defs = svg.append('svg:defs');
var arrowMarker = defs.append("marker")
    .attr("id", "arrow")
    .attr("markerWidth", 10)
    .attr("markerHeight", 10)
    .attr("refX", 4)
    .attr("refY", 3)
    .attr("orient", "auto")
    .attr("markerUnits", "strokeWidth");
arrowMarker.append("path")
    .attr("d", "M1,3 L0,5 L6,3 L0,1 z")
    .attr("fill", "#ddd");

// applying it to the edges

var edgeElements = edgeLayer
    .selectAll(".edge")
    .data(edges);

edgeElements.enter()
    .append("path")
    .attr("class", "edge")
    .attr("stroke", "#ddd")
    .attr("stroke-width", 5)
    .attr("marker-end", "url(#arrow)");

Construct a partial curve

Ideally the curve between the two touching points follows the original curve. We know the values \(t_{start}\) and \(t_{end}\) for which \(B(t_{start}) = P_{start}\) and \(B(t_{end}) = P_{end}\), so \(B(t)\) could simply be rendered for \(t \in [t_{start}, t_{end}]\) instead of \(t \in [0, 1]\). Unfortunately SVG’s path commands don’t support such a feature.

To achieve the effect nonetheless, we first define a new function \(C\) which follows \(B\) along the relevant interval, but itself using the domain \([0, 1]\):

\[ C\colon [0, 1] \Rightarrow \mathbb{R}^2 \] \[ C(t) = B(t_{start} + (t_{end} - t_{start}) t) \]

We also know the start and end points:

\[ P_{start} = C(0) = B(t_{start}) \] \[ P_{end} = C(1) = B(t_{end}) \]

Finally, we want \(C\) to be a Bézier curve, so it must have the same structure. Calling the control point \(X\) we have:

\[ C(t) \, = \, (1 - t)^2 P_{start} + 2 (1 - t) t X + t^2 P_{end} \]

Putting it all together it is: \[ (1 - t)^2 P_{start} + 2 (1 - t) t X + t^2 P_{end} \, = \, \] \[ (1 - (t_{start} + (t_{end} - t_{start}) t))^2 P_0 + \] \[ 2 (1 - (t_{start} + (t_{end} - t_{start}) t)) (t_{start} + \] \[(t_{end} - t_{start}) t) P_1 + (t_{start} + (t_{end} - t_{start}) t)^2 P_2 \]

which means

\[ (1 - t)^2 ((1 - t_{start})^2 P_0 + 2 (1 - t_{start}) t_{start} P_1 + t_{start}^2 P_2) + \] \[ 2 (1 - t) t X + \] \[ t^2 ((1 - t_{end})^2 P_0 + 2 (1 - t_{end}) t_{end} P_1 + t_{end}^2 P_2) \, = \, \] \[ (1 - (t_{start} + (t_{end} - t_{start}) t))^2 P_0 + \] \[ 2 (1 - (t_{start} + (t_{end} - t_{start}) t)) (t_{start} + \] \[(t_{end} - t_{start}) t) P_1 + (t_{start} + (t_{end} - t_{start}) t)^2 P_2 \]

and sympy helps us with that, yielding:

\[ X \, = \, t_{start} t_{end} (P_0 - 2 P_1 + P_2) + (1 - t_{start} - t_{end}) P_0 + (t_{start} + t_{end}) P_1 \]

So finally we can construct a new Bézier curve from \(P_{start}\) to \(P_{end}\), using control point \(X\). In code it looks like this:

edgeLayer
    .selectAll(".edge")
    .attr("d", e => {
        var start = findProximityPoint(e.source, e.intermediate, e.target, e.source.radius + 2);
        var end = findProximityPoint(e.target, e.intermediate, e.source, e.target.radius + 10);
        var P0 = e.source;
        var P1 = e.intermediate;
        var P2 = e.target;
        var tStart = start.t;
        var tEnd = 1 - end.t;

        var adjustedIntermediate = {
            x: tStart * tEnd * (P0.x - 2 * P1.x + P2.x) + (1 - tStart - tEnd) * P0.x + (tStart + tEnd) * P1.x,
            y: tStart * tEnd * (P0.y - 2 * P1.y + P2.y) + (1 - tStart - tEnd) * P0.y + (tStart + tEnd) * P1.y,
        };

        return "M" + start.x + "," + start.y
            + "Q" + adjustedIntermediate.x + "," + adjustedIntermediate.y
            + " " + end.x + "," + end.y;
    });

For the final result (the wrongly cropped curve included for comparison):