How to draw the shortest path between circles

Question

I am building a web app (in Qwik) that requires parsing a .xctsk file (paragliding competition tasks), and drawing the task on a map. A task consists of a bunch of circles in a given order.

I have successfully implemented the file parsing, and drawing the circles, and I now need to draw the shortest path that links every circle in the given order. It should end up looking like this:

I can easily connect the circles' centers with polylines, like the screenshot below, but I have no clue on how to find the points that give the shortest path. Any idea would be very much welcome!

Here is my code:

        task?.turnpoints.forEach((tp, index) => {
          circle([tp.waypoint.lat, tp.waypoint.lon], {
            radius: tp.radius,
            color: "orange",
          }).addTo(mapContainer$.value!);

          if (index < task.turnpoints.length - 1) {
            polyline(
              [
                [
                  task.turnpoints[index].waypoint.lat,
                  task.turnpoints[index].waypoint.lon,
                ],
                [
                  task.turnpoints[index + 1].waypoint.lat,
                  task.turnpoints[index + 1].waypoint.lon,
                ],
              ],
              { color: "black" },
            ).addTo(mapContainer$.value!);
          }
        });

I tried looking for information on other forums, as well as math formulas, but did not find any clue.

Answer 1

Since it seems that you want to reach the closest edge of the circle instead of the center, something like this might work:

(note that if radius isn't in degrees - same as lat and lon - then some additional conversion is needed)

This will give you a shorter path, but not the shortest. If you want the true shortest path, then you might consider asking this on the mathematics stack exchange.

This also may not handle traversing from an inner circle to an outer circle too well (since once you're in the inner circle, you should just skip the waypoint to the outer circle as you're already inside it - though since this problem is declared as 'in given order' - that shouldn't be a problem? since it would violate the order) There would need to be additional checks implemented for that - which someone might be happy to help with if you were to post a working example (snippet, fiddle, etc)

This also doesn't take Mike's comment into account about the earth being a sphere and hence a curved surface.

    actualPoints = [{
      x: task.turnpoints[0].waypoint.lat,
      y: task.turnpoints[0].waypoint.lon,
    }];

    task?.turnpoints.forEach((tp, index) => {
        circle([tp.waypoint.lat, tp.waypoint.lon], {
          radius: tp.radius,
          color: "orange",
        }).addTo(mapContainer$.value!);

        if (index < task.turnpoints.length - 1) {

          const pointA = actualPoints[0]

          const pointB = {
            x: task.turnpoints[index + 1].waypoint.lat,
            y: task.turnpoints[index + 1].waypoint.lon,
          }

          const vectorDistance = {
            x: pointA.x - pointB.x,
            y: pointA.y - pointB.y,
          }

          const angle = Math.atan2(vectorDistance.x, vectorDistance.y)

          const normalExtended = {
            x: Math.cos(angle) * tp.radius,
            y: Math.sin(angle) * tp.radius,
          }

          const newPoint = {
            x: normalExtended.x + pointB.x,
            y: normalExtended.y + pointB.y,
          }

          actualPoints[index + 1] = newPoint

          polyline(
            [
              [
                pointA.x,
                pointA.y
              ],
              [
                newPoint.x,
                newPoint.y
              ],
            ],
            { color: "black" },
          ).addTo(mapContainer$.value!);
        }
      });

Answer 2

Interesting math problem here. The shortest path has the property that it bounces off the circles like a ball. More mathematically,the normal of the circle at the touching point should be the bisector between the incoming and outgoing path. This makes a very simple algorithm: intersect the bisector of each angle in your inital path connecting the centers (in black in your second image) with the corresponding circle and choose this point as the new corner. It will not be optimal as the new path will not have exactly the bisector property, but quite close. You can enhance by iterating: computing the bisector of the new path, and placing the point where the circle normal has the same direction. To be optimal you also have to check if a circle is intersected by the segment from the previous corner to the next. In this case you can simply remove the corner relative to this circle as after removing the circle will still be touched (intersected).

Edit: I've put a python code that solves the problem here: shortest_path_circle.py Feel free to to use it. Here is also an illustration of the optimization iterations