javascript d3.js geometry observablehq cubic-bezier

D3.js force-directed graph with dynamically offset arrows?

I have a force-directed graph in D3.js where the node radius is proportional to a property of that data (e.g., pageviews) and the link width is proportional to a property of the linking data (e.g., clicks). I would like to give the link curve an indicator of its direction. The problem is that the links travel to the center of the data node, so if I use marker-end, I get:

(Data nodes are normally filled with a color linked to another data category...)

I create my ~~arcs~~ curves using:

positionLink = (d) => {
    const offset = 100;
    const midpoint_x = (d.source.x + d.target.x) / 2;
    const midpoint_y = (d.source.y + d.target.y) / 2;
  
    const dx = d.source.x - d.target.x;
    const dy = d.source.y - d.target.y;
  
    // Perpendicular vector 
    const nx = -dy;
    const ny = dx;
    const norm_length = Math.sqrt((nx*nx)+(ny*ny));
    const normx = nx / norm_length;
    const normy = ny / norm_length;
  
    const offset_x = parseFloat(midpoint_x + offset * normx.toFixed(2));
    const offset_y = parseFloat(midpoint_y + offset * normy.toFixed(2));
    const arc = `M ${d.source.x.toFixed(2)} ${d.source.y.toFixed(2)} S ${offset_x} ${offset_y} ${d.target.x.toFixed(2)} ${d.target.y.toFixed(2)}`;

    return arc;
  };

What my code calls arc is an SVG "S" path, which is a "Smooth curveto" but I'm not wed to that in particular: I just need to pull the arcs apart from each other so that I can show the difference between data in one direction and in the other.

How can I locate the intersection of the Bezier curve with the circle?

(Since the target of the curve is the center of the circle, I suppose this could be rephrased as "The value of the Bezier curve at distance r from its ending point")

If I had that one point, I could make it the apex of an arrowhead.

(Even better would be if I had the slope of the Bezier at that point so I could really align it, but I think I can get away with just aligning it to the line between the midpoint and the anchor...)

Solution

Consider the following iterative method:

Using path.getPointAtLength, you can traverse the path until you find a point that is exactly r from the centre of the circle, and then redraw the path using those coordinates instead.

const data = [{
  x: 50,
  y: 100,
  r: 20
}, {
  x: 100,
  y: 30,
  r: 5
}];
const links = [{
    source: data[0],
    target: data[1]
  },
  {
    source: data[1],
    target: data[0]
  }
];

positionLink = (source, target) => {
  const offsetPx = 100;
  const midpoint = {
    x: (source.x + target.x) / 2,
    y: (source.y + target.y) / 2
  };

  const dx = source.x - target.x;
  const dy = source.y - target.y;

  // Perpendicular vector 
  const nx = -dy;
  const ny = dx;
  const norm_length = Math.sqrt((nx * nx) + (ny * ny));
  const normx = nx / norm_length;
  const normy = ny / norm_length;

  const offset = {
    x: parseFloat(midpoint.x + offsetPx * normx.toFixed(2)),
    y: parseFloat(midpoint.y + offsetPx * normy.toFixed(2)),
  };

  const arc = `M ${source.x.toFixed(2)} ${source.y.toFixed(2)} S ${offset.x} ${offset.y} ${target.x.toFixed(2)} ${target.y.toFixed(2)}`;

  return arc;
};

euclidean = (point, other) => Math.sqrt(point.x * other.x + point.y * other.y);

findPointAtLength = (path, point, fromEnd) => {
  // For the target we need to start at the other side of the path
  let offset = point.r;
  if (fromEnd) {
    const totalLength = path.getTotalLength();
    offset = totalLength - offset;
  }

  let current = path.getPointAtLength(offset);

  // Gradually increase the offset until we're exactly 
  // `r` away from the circle centre
  while (euclidean(point, current) < point.r) {
    offset += 1;
    current = path.getPointAtLength(offset);
  }

  return {
    x: current.x,
    y: current.y
  };
};

// Use function because we want access to `this`,
// which points to the current path HTMLElement
positionLinkAtEdges = function(d) {
  // First, place the path in the old way
  d3.select(this).attr("d", positionLink(d.source, d.target));

  // Then, position the path away from the source
  const source = findPointAtLength(this, d.source, false);
  const target = findPointAtLength(this, d.target, true);

  return positionLink(source, target);
}

const svg = d3.select("svg").append("g");

svg
  .selectAll("circle")
  .data(data)
  .enter()
  .append("circle")
  .attr("cx", d => d.x)
  .attr("cy", d => d.y)
  .attr("r", d => d.r);

svg
  .selectAll("path")
  .data(links)
  .enter()
  .append("path")
  .attr("d", positionLinkAtEdges)
  .attr("marker-end", "url(#triangle)");

g circle,
g path {
  fill: none;
  stroke: black;
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/5.7.0/d3.min.js"></script>
<svg>
  <defs>
    <marker id="triangle" viewBox="0 0 10 10"
          refX="10" refY="5" 
          markerUnits="strokeWidth"
          markerWidth="10" markerHeight="10"
          orient="auto">
      <path d="M 0 0 L 10 5 L 0 10 z" fill="#f00"/>
    </marker>
  </defs>
</svg>