workout-suggester/internal/routes/routes.go

// Package routes finds signposted cycling, walking and running routes near a
// point using OpenStreetMap data from the Overpass API, and picks the ones
// that fit a target distance.
package routes

import (
	"context"
	"encoding/json"
	"errors"
	"fmt"
	"io"
	"math"
	"net/http"
	"net/url"
	"os"
	"path/filepath"
	"strings"
	"sync"
	"time"
)

// Kind is what a route is signposted for.
type Kind string

const (
	Bike Kind = "bike"
	Foot Kind = "foot"
)

// Point is a WGS84 coordinate.
type Point struct {
	Lat float64 `json:"lat"`
	Lon float64 `json:"lon"`
}

// Route is a named OSM route relation with its geometry.
type Route struct {
	ID       int64     `json:"id"`
	Name     string    `json:"name"`
	Kind     Kind      `json:"kind"`
	LengthKm float64   `json:"length_km"`
	Loop     bool      `json:"loop"`
	Ways     [][]Point `json:"ways"` // unordered pieces, as OSM stores them

	// Set for loops generated by BRouter rather than signposted in OSM.
	Generated bool `json:"generated,omitempty"`
	Heading   int  `json:"heading,omitempty"`   // direction it sets off in, degrees
	AscentM   int  `json:"ascent_m,omitempty"`  // total climb
	PavedPct  int  `json:"paved_pct,omitempty"` // -1 when unknown
}

// Junction is a numbered node of the Belgian/Dutch node networks
// (fietsknooppunt / wandelknooppunt).
type Junction struct {
	Ref   string `json:"ref"`
	Kind  Kind   `json:"kind"`
	Point Point  `json:"point"`
}

// Area holds everything found around one spot.
type Area struct {
	Routes    []Route    `json:"routes"`
	Junctions []Junction `json:"junctions"`
	Fetched   time.Time  `json:"fetched"`
}

// Client queries Overpass for signposted routes, keeping results in memory
// and on disk so an area you've loaded once keeps working without a
// connection, and BRouter for loops generated from your door.
type Client struct {
	URLs       []string // Overpass endpoints, tried in order
	BRouterURL string   // e.g. https://brouter.de/brouter; empty or "-" disables loops
	HTTP       *http.Client
	CacheDir   string // empty: no disk cache

	mu      sync.Mutex
	areas   map[string]*Area
	byID    map[int64]*Route
	locks   map[string]*sync.Mutex
	loops   map[string]cachedLoops
	loopSeq int64
}

func (c *Client) initLocked() {
	if c.byID == nil {
		c.areas, c.byID, c.locks, c.loops = map[string]*Area{}, map[int64]*Route{}, map[string]*sync.Mutex{}, map[string]cachedLoops{}
	}
}

const (
	bikeRadius     = 15000 // m
	footRadius     = 8000  // m
	junctionRadius = 3000  // m
	cacheFor       = 7 * 24 * time.Hour
	userAgent      = "workout-suggester/0.1 (+https://git.b0b.be/bdeb/workout-suggester)"
)

// cell snaps a coordinate to a ~2 km grid so nearby requests share a cache
// entry and the exact location never leaves the machine.
func cell(lat, lon float64) (float64, float64, string) {
	lat, lon = math.Round(lat*50)/50, math.Round(lon*50)/50
	return lat, lon, fmt.Sprintf("%.2f_%.2f", lat, lon)
}

// Near returns the routes and junctions around a point.
func (c *Client) Near(ctx context.Context, lat, lon float64) (*Area, error) {
	clat, clon, key := cell(lat, lon)

	// One fetch per cell at a time; concurrent callers wait for it.
	c.mu.Lock()
	c.initLocked()
	l, ok := c.locks[key]
	if !ok {
		l = &sync.Mutex{}
		c.locks[key] = l
	}
	c.mu.Unlock()
	l.Lock()
	defer l.Unlock()

	c.mu.Lock()
	a := c.areas[key]
	c.mu.Unlock()
	if a == nil {
		a = c.readDisk(key)
	}
	if a != nil && time.Since(a.Fetched) < cacheFor {
		c.remember(key, a)
		return a, nil
	}

	fresh, err := c.fetch(ctx, clat, clon)
	if err != nil {
		if a != nil { // stale beats nothing
			c.remember(key, a)
			return a, nil
		}
		return nil, err
	}
	c.remember(key, fresh)
	c.writeDisk(key, fresh)
	return fresh, nil
}

// Route looks up a route seen in an earlier Near call.
func (c *Client) Route(id int64) (*Route, bool) {
	c.mu.Lock()
	defer c.mu.Unlock()
	c.initLocked()
	r, ok := c.byID[id]
	return r, ok
}

func (c *Client) remember(key string, a *Area) {
	c.mu.Lock()
	defer c.mu.Unlock()
	c.areas[key] = a
	for i := range a.Routes {
		c.byID[a.Routes[i].ID] = &a.Routes[i]
	}
}

func (c *Client) readDisk(key string) *Area {
	if c.CacheDir == "" {
		return nil
	}
	b, err := os.ReadFile(filepath.Join(c.CacheDir, key+".json"))
	if err != nil {
		return nil
	}
	var a Area
	if json.Unmarshal(b, &a) != nil {
		return nil
	}
	return &a
}

func (c *Client) writeDisk(key string, a *Area) {
	if c.CacheDir == "" {
		return
	}
	b, err := json.Marshal(a)
	if err != nil || os.MkdirAll(c.CacheDir, 0o755) != nil {
		return
	}
	tmp := filepath.Join(c.CacheDir, key+".json.tmp")
	if os.WriteFile(tmp, b, 0o644) == nil {
		os.Rename(tmp, filepath.Join(c.CacheDir, key+".json"))
	}
}

func query(lat, lon float64) string {
	at := func(r int) string { return fmt.Sprintf("(around:%d,%.4f,%.4f)", r, lat, lon) }
	return `[out:json][timeout:25];(` +
		`relation["type"="route"]["route"="bicycle"]["network"~"^(lcn|rcn)$"]["network:type"!="node_network"]` + at(bikeRadius) + `;` +
		`relation["type"="route"]["route"~"^(hiking|foot|walking|running)$"]["network"~"^(lwn|rwn)$"]["network:type"!="node_network"]` + at(footRadius) + `;` +
		`);out geom;(` +
		`node["rcn_ref"]` + at(junctionRadius) + `;` +
		`node["rwn_ref"]` + at(junctionRadius) + `;` +
		`);out;`
}

// fetch tries each Overpass endpoint, retrying busy servers a couple of times.
func (c *Client) fetch(ctx context.Context, lat, lon float64) (*Area, error) {
	hc := c.HTTP
	if hc == nil {
		hc = http.DefaultClient
	}
	body := url.Values{"data": {query(lat, lon)}}.Encode()
	var errs []error
	for attempt := range 3 {
		for _, u := range c.URLs {
			req, err := http.NewRequestWithContext(ctx, http.MethodPost, u, strings.NewReader(body))
			if err != nil {
				return nil, err
			}
			req.Header.Set("Content-Type", "application/x-www-form-urlencoded")
			req.Header.Set("Accept", "application/json") // overpass-api.de answers 406 without it
			req.Header.Set("User-Agent", userAgent)
			resp, err := hc.Do(req)
			if err != nil {
				if ctx.Err() != nil {
					return nil, ctx.Err()
				}
				errs = append(errs, err)
				continue
			}
			if resp.StatusCode != http.StatusOK {
				resp.Body.Close()
				errs = append(errs, fmt.Errorf("%s: %s", u, resp.Status))
				continue
			}
			a, err := parse(resp.Body)
			resp.Body.Close()
			if err != nil {
				errs = append(errs, err)
				continue
			}
			return a, nil
		}
		select { // busy servers (429/504) usually recover within seconds
		case <-ctx.Done():
			return nil, ctx.Err()
		case <-time.After(time.Duration(attempt+1) * 2 * time.Second):
		}
	}
	return nil, fmt.Errorf("overpass: %w", errors.Join(errs...))
}

func parse(r io.Reader) (*Area, error) {
	var out struct {
		Elements []struct {
			Type    string            `json:"type"`
			ID      int64             `json:"id"`
			Lat     float64           `json:"lat"`
			Lon     float64           `json:"lon"`
			Tags    map[string]string `json:"tags"`
			Members []struct {
				Type     string  `json:"type"`
				Role     string  `json:"role"`
				Geometry []Point `json:"geometry"`
			} `json:"members"`
		} `json:"elements"`
		Remark string `json:"remark"`
	}
	if err := json.NewDecoder(r).Decode(&out); err != nil {
		return nil, fmt.Errorf("decode overpass: %w", err)
	}
	if strings.Contains(out.Remark, "runtime error") {
		return nil, fmt.Errorf("overpass: %s", out.Remark)
	}
	a := &Area{Fetched: time.Now()}
	for _, e := range out.Elements {
		t := e.Tags
		switch e.Type {
		case "node":
			if ref := t["rcn_ref"]; ref != "" {
				a.Junctions = append(a.Junctions, Junction{Ref: ref, Kind: Bike, Point: Point{e.Lat, e.Lon}})
			}
			if ref := t["rwn_ref"]; ref != "" {
				a.Junctions = append(a.Junctions, Junction{Ref: ref, Kind: Foot, Point: Point{e.Lat, e.Lon}})
			}
		case "relation":
			name := t["name"]
			if name == "" {
				name = t["ref"]
			}
			if name == "" {
				continue
			}
			r := Route{ID: e.ID, Name: name, Kind: Foot, Loop: t["roundtrip"] == "yes"}
			if t["route"] == "bicycle" {
				r.Kind = Bike
			}
			for _, m := range e.Members {
				if m.Type != "way" || len(m.Geometry) < 2 {
					continue
				}
				r.LengthKm += pathKm(m.Geometry)
				r.Ways = append(r.Ways, simplify(m.Geometry, 0.015))
			}
			if r.LengthKm < 0.5 {
				continue
			}
			r.LengthKm = math.Round(r.LengthKm*10) / 10
			a.Routes = append(a.Routes, r)
		}
	}
	return a, nil
}

// Km is the great-circle distance between two points.
func Km(a, b Point) float64 {
	const R = 6371.0
	la1, la2 := a.Lat*math.Pi/180, b.Lat*math.Pi/180
	dla, dlo := la2-la1, (b.Lon-a.Lon)*math.Pi/180
	h := math.Sin(dla/2)*math.Sin(dla/2) + math.Cos(la1)*math.Cos(la2)*math.Sin(dlo/2)*math.Sin(dlo/2)
	return 2 * R * math.Asin(math.Sqrt(h))
}

func pathKm(pts []Point) float64 {
	var d float64
	for i := 1; i < len(pts); i++ {
		d += Km(pts[i-1], pts[i])
	}
	return d
}

// simplify drops points closer than minKm to the last kept one, which is
// plenty for a map or a GPX track and keeps the page small.
func simplify(pts []Point, minKm float64) []Point {
	out := []Point{pts[0]}
	for i := 1; i < len(pts)-1; i++ {
		if Km(out[len(out)-1], pts[i]) >= minKm {
			out = append(out, pts[i])
		}
	}
	return append(out, pts[len(pts)-1])
}

// Closest returns the point of the route nearest to p and its distance.
func (r *Route) Closest(p Point) (Point, float64) {
	best, bestKm := Point{}, math.Inf(1)
	for _, w := range r.Ways {
		for _, q := range w {
			if d := Km(p, q); d < bestKm {
				best, bestKm = q, d
			}
		}
	}
	return best, bestKm
}

// NearestJunction finds the closest node-network junction of a kind.
func (a *Area) NearestJunction(kind Kind, p Point) (Junction, float64, bool) {
	var best Junction
	bestKm := math.Inf(1)
	for _, j := range a.Junctions {
		if j.Kind != kind {
			continue
		}
		if d := Km(p, j.Point); d < bestKm {
			best, bestKm = j, d
		}
	}
	return best, bestKm, !math.IsInf(bestKm, 1)
}