Generating a runnable route of exactly 42 km

"Give me a route of exactly 42 kilometres, starting here, through countries I choose, that I can actually navigate."

That's the core feature of Trevola, a travel app I built for a client. It sounds simple — every maps SDK does routing, right? But routing APIs answer a different question. They tell you the distance between two points you already know. Trevola's problem is inverted: the distance is the input, and the points are the output. No routing engine answers that directly, so I had to build the answer out of several pieces. This post walks through the whole algorithm.

Why "just scale a circle" doesn't work

The naive approach: draw a circle of radius distance / 2 around the start point, pick a point on it, route there and back. Two problems kill it immediately.

First, roads aren't straight lines. The road distance between two points is anywhere from 1.2× to 3× the straight-line distance depending on terrain, rivers, and road density. A 21 km straight-line target might produce a 55 km route through mountains.

Second, the endpoint might land somewhere useless — in the sea, across a border the user excluded, or in the middle of a lake. A real implementation needs geographic validation, not just geometry.

So the algorithm became: project, validate, route, measure, correct, repeat.

Step 1 — Project a candidate endpoint with Haversine

Given a start coordinate, a bearing, and a target straight-line distance, spherical trigonometry gives you the destination point. This is the standard forward Haversine projection:

LatLng project(LatLng start, double bearingRad, double distanceKm) {
  const R = 6371.0; // earth radius, km
  final d = distanceKm / R;
  final lat1 = start.latitudeInRad;
  final lon1 = start.longitudeInRad;

  final lat2 = asin(sin(lat1) * cos(d) +
      cos(lat1) * sin(d) * cos(bearingRad));
  final lon2 = lon1 +
      atan2(sin(bearingRad) * sin(d) * cos(lat1),
          cos(d) - sin(lat1) * sin(lat2));

  return LatLng.fromRadians(lat2, lon2);
}

The initial straight-line distance is the target route distance multiplied by a starting coefficient (empirically, roads add length, so you start by projecting shorter than the target). The bearing can be random or user-influenced.

Step 2 — Validate the endpoint is actually usable

This is the step most people skip and regret. A projected point is only a candidate until it passes geographic validation: is it on land, and is it inside one of the countries the user selected?

Trevola uses Natural Earth country boundary polygons for this. Each country is one or more polygons (mainland plus islands), and the test is classic ray casting: draw a ray from the candidate point and count how many times it crosses the polygon boundary. Odd count — inside. Even — outside.

bool pointInPolygon(LatLng p, List<LatLng> polygon) {
  var inside = false;
  for (var i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {
    final a = polygon[i], b = polygon[j];
    final intersects = ((a.longitude > p.longitude) !=
            (b.longitude > p.longitude)) &&
        (p.latitude <
            (b.latitude - a.latitude) *
                    (p.longitude - a.longitude) /
                    (b.longitude - a.longitude) +
                a.latitude);
    if (intersects) inside = !inside;
  }
  return inside;
}

If the candidate fails — it's in the sea, or in a country the user didn't pick — throw it away, rotate the bearing, and project again. This loop is cheap; the polygon test is microseconds. Never spend a routing request on a point you haven't validated.

Step 3 — Ask OSRM for the real route

With a validated endpoint, the actual road network comes from OSRM (Open Source Routing Machine), which routes over OpenStreetMap data and supports the three profiles Trevola needs — foot, bicycle, and driving. OSRM returns the route geometry as an encoded polyline plus the real travelled distance.

That real distance is the number that matters. The straight-line projection was 21 km; OSRM might come back with 31.4 km of actual road. Now the correction loop begins.

Step 4 — The coefficient correction loop

The key insight: for a given region and travel profile, the ratio between road distance and straight-line distance is locally stable. If projecting 21 km produced a 31.4 km route, the local road factor is about 1.5 — so to hit 42 km of road, project roughly 42 / 1.5 = 28 km instead.

Each iteration refines the coefficient with real measured data:

target        = 42.0 km
attempt 1: project 21.0 km  → OSRM says 31.4 km   (factor 1.50)
attempt 2: project 28.0 km  → OSRM says 44.9 km   (factor 1.60)
attempt 3: project 26.2 km  → OSRM says 42.6 km   ✓ within tolerance

The loop runs until the routed distance lands within tolerance of the target, capped at 20 attempts as a hard stop. In practice it converges in a handful of iterations because the coefficient method is essentially one-dimensional root finding on a well-behaved function. Every new candidate endpoint still goes through the polygon validation from step 2 — correction never gets to bypass geography.

Convergence failures do happen — ask for a 500 km walking route from a small island and there may be no valid answer. The cap turns that into a clean, explainable error instead of a hung request.

Step 5 — Stream progress to the UI

A multi-attempt loop with network calls takes seconds, and a frozen screen kills the feature's magic. The backend (FastAPI) streams progress as it works, and the Flutter client — using flutter_map with OpenStreetMap tiles — renders the state live: candidate found, routing, refining, done. When the route lands, the user sees the full polyline with draggable markers, and dragging a marker triggers a targeted re-route rather than a full regeneration.

Watching the algorithm visibly work turned out to be part of the product. Users trust a route more when they saw it being figured out.

What I'd generalise from this

The pattern here isn't about maps. It's the shape of many "inverse problem" features:

1. You can't ask the API your real question — so wrap it in a search loop that can.
2. Validate candidates before spending expensive calls on them. The cheap ray-casting filter protects the costly OSRM calls.
3. Use measured feedback, not fixed constants. The road factor is learned per-attempt, which is why the same code converges in the Alps and in Amsterdam.
4. Bound the loop and design the failure. Twenty attempts, then a human-readable "couldn't build this route here — try a shorter distance."
5. Stream long computations. If the work takes seconds, make the work visible.

Routing SDKs give everyone the same features. The differentiated feature — the one that made this app worth building — lived one abstraction layer above the SDK.