force-graph Curved arrows

Hi,

you probably know about this issue and that there isn't really a good solution to it (at least I couldn't find one): depending on link curvature and curve length, arrows look disconnected from nodes/links and get stretched/compressed.

before

<html>
  <head>
    <script src="https://unpkg.com/force-graph"></script>
    <!-- <script src="./dist/force-graph.js"></script> -->
  </head>
  <body>
    <div id="graph"></div>

    <script type="module">
      ForceGraph()(document.getElementById("graph")).graphData({
        nodes: [
          {id: "n1", fx: 0, fy: 0},
          {id: "n2", fx: 50, fy: 0},
          {id: "n3", fx: 100, fy: 0},
        ],
        links: [
          {source: "n1", target: "n1", curvature: 0.1, pos: 0},
          {source: "n2", target: "n2", curvature: 0.1, pos: 0.5},
          {source: "n3", target: "n3", curvature: 0.1, pos: 1},
          {source: "n1", target: "n1", curvature: 0.2, pos: 0},
          {source: "n2", target: "n2", curvature: 0.2, pos: 0.5},
          {source: "n3", target: "n3", curvature: 0.2, pos: 1},
          {source: "n1", target: "n1", curvature: 0.5, pos: 0},
          {source: "n2", target: "n2", curvature: 0.5, pos: 0.5},
          {source: "n3", target: "n3", curvature: 0.5, pos: 1},
          {source: "n1", target: "n1", curvature: 1, pos: 0},
          {source: "n2", target: "n2", curvature: 1, pos: 0.5},
          {source: "n3", target: "n3", curvature: 1, pos: 1},
          {source: "n1", target: "n1", curvature: 1.5, pos: 0},
          {source: "n2", target: "n2", curvature: 1.5, pos: 0.5},
          {source: "n3", target: "n3", curvature: 1.5, pos: 1},
        ],
      }).linkCurvature("curvature").linkDirectionalArrowRelPos("pos").linkDirectionalArrowLength(8).width(2560).height(1440).zoom(16);
    </script>
  </body>
</html>

I tried to fix it and eventually implemented curved arrows:

after

https://github.com/notEvil/force-graph/tree/curved_arrows

Bezier.getLUT() is used to better approximate the relationship between distance and t, and Bezier.normal() to bend arrows. Arrows on heavily curved links look strange of course, but this is easy to avoid by enforcing an upper limit on the curvature. If you really dislike the bend, its not difficult to draw them straight (let arrows look disconnected from links).

Oct 19 '23 15:10 notEvil

With straight arrows and reusing the existing code as much as possible*:

after 2

https://github.com/notEvil/force-graph/tree/i337

* the first proposal replaced rotation using sin cos with normal vectors. It should be faster since sin and cos are more complex.

Oct 20 '23 10:10 notEvil

The final proposal:

https://github.com/notEvil/force-graph/tree/i337-2

Compared to the others:

As fast as the current implementation on medium example (first 400 ticks)
Finds start and end t and uses linear interpolation between them
- position is not as accurate, but doesn't need to compute as many distances
Finds opposite side of arrow using straight distance instead of distance on link
- arrows are always the same size
Special cases for relative pos equal to 0 and 1 with the latter being the fastest

Oct 23 '23 10:10 notEvil