mg4/server/maps.go

package main

import (
	"bytes"
	"compress/gzip"
	"context"
	"encoding/json"
	"errors"
	"fmt"
	"io"
	"log/slog"
	"math"
	"net/http"
	"net/url"
	"strings"
	"sync"
	"time"
)

// Maps serves the roads around the car for the Overview's map (the "Grid with map" style),
// taken from OpenStreetMap through an Overpass API and cached here, so the car only ever
// talks to this server and asks Overpass nothing itself.
//
//	POST /v1/map/roads   {"z":14,"x":…,"y":…}
//	                     → {"z","x","y","extent":4096,"ways":[{"c":class,"p":[x,y,x,y,…]}]}
//
// The car names a web-mercator tile at zoom 14 (about 1.5 km across in central Europe), not
// its position, and the request goes in the body so the tile stays out of access logs. Points
// are tile-local in 0..4096 (they may lie a little outside: a road is kept up to the first
// point beyond the edge), simplified to about 1.5 m. Classes: 0 motorway and trunk, 1 primary
// and secondary, 2 tertiary and unclassified, 3 residential and living streets.
//
// Overpass is asked one tile at a time, at most once a second; a tile is kept for 30 days,
// up to mapCacheTiles of them. The tile's coordinates never appear in the log.
type Maps struct {
	OverpassURL string
	UserAgent   string
	Client      *http.Client

	mu    sync.Mutex
	tiles map[mapTile]mapEntry

	fetchMu   sync.Mutex // one Overpass request at a time
	lastFetch time.Time
	gap       time.Duration
}

const (
	mapZoom          = 14
	mapExtent        = 4096
	mapCacheTiles    = 3000
	mapCacheAge      = 30 * 24 * time.Hour
	maxOverpassBytes = 32 << 20
	// The simplification tolerance in tile units (about 0.37 m each at 52° N).
	mapTolerance = 4.0
	// DefaultOverpassURL is the public instance of the Overpass API.
	DefaultOverpassURL = "https://overpass-api.de/api/interpreter"
	// mapUserAgent names this service to Overpass, as its usage policy asks.
	mapUserAgent = "nils-mg4-server/2.7 (private car dashboard; roads for an in-car map)"
)

type mapTile struct{ Z, X, Y int }

type mapEntry struct {
	body []byte
	at   time.Time
}

// roadClasses maps OSM's highway values to the four classes the car draws.
var roadClasses = map[string]int{
	"motorway": 0, "motorway_link": 0, "trunk": 0, "trunk_link": 0,
	"primary": 1, "primary_link": 1, "secondary": 1, "secondary_link": 1,
	"tertiary": 2, "tertiary_link": 2, "unclassified": 2,
	"residential": 3, "living_street": 3,
}

type roadTile struct {
	Z      int    `json:"z"`
	X      int    `json:"x"`
	Y      int    `json:"y"`
	Extent int    `json:"extent"`
	Ways   []road `json:"ways"`
}

type road struct {
	C int   `json:"c"`
	P []int `json:"p"`
}

func NewMaps(overpassURL, userAgent string) *Maps {
	return &Maps{OverpassURL: overpassURL, UserAgent: userAgent, gap: time.Second}
}

func (m *Maps) client() *http.Client {
	if m.Client != nil {
		return m.Client
	}
	return &http.Client{Timeout: 60 * time.Second}
}

// tileBounds is the tile's south, west, north and east edge in degrees.
func tileBounds(t mapTile) (s, w, n, e float64) {
	scale := math.Exp2(float64(t.Z))
	lon := func(x float64) float64 { return x/scale*360 - 180 }
	lat := func(y float64) float64 { return math.Atan(math.Sinh(math.Pi*(1-2*y/scale))) * 180 / math.Pi }
	return lat(float64(t.Y + 1)), lon(float64(t.X)), lat(float64(t.Y)), lon(float64(t.X + 1))
}

// tilePoint is a position in the tile's own units: 0..extent across, y downwards.
func tilePoint(t mapTile, lat, lon float64) (int, int) {
	scale := math.Exp2(float64(t.Z)) * mapExtent
	x := (lon + 180) / 360 * scale
	r := lat * math.Pi / 180
	y := (1 - math.Log(math.Tan(r)+1/math.Cos(r))/math.Pi) / 2 * scale
	return int(math.Round(x - float64(t.X)*mapExtent)), int(math.Round(y - float64(t.Y)*mapExtent))
}

// overpassQuery asks for the drivable roads in the tile, with a small margin so that roads
// crossing its edge reach a point beyond it.
func overpassQuery(t mapTile) string {
	s, w, n, e := tileBounds(t)
	dy, dx := (n-s)*0.03, (e-w)*0.03
	box := fmt.Sprintf("%.6f,%.6f,%.6f,%.6f", s-dy, w-dx, n+dy, e+dx)
	return "[out:json][timeout:50];way[\"highway\"~\"^(motorway|motorway_link|trunk|trunk_link|primary|primary_link|" +
		"secondary|secondary_link|tertiary|tertiary_link|unclassified|residential|living_street)$\"](" + box +
		");out geom(" + box + ");"
}

type overpassResult struct {
	Elements []struct {
		Type     string            `json:"type"`
		Tags     map[string]string `json:"tags"`
		Geometry []*struct {
			Lat float64 `json:"lat"`
			Lon float64 `json:"lon"`
		} `json:"geometry"`
	} `json:"elements"`
}

// buildTile turns Overpass's answer into the tile the car reads. A missing point (outside
// the clipped geometry) splits a road in two.
func buildTile(t mapTile, raw []byte) ([]byte, error) {
	var res overpassResult
	if err := json.Unmarshal(raw, &res); err != nil {
		return nil, fmt.Errorf("overpass answer: %w", err)
	}
	out := roadTile{Z: t.Z, X: t.X, Y: t.Y, Extent: mapExtent, Ways: []road{}}
	for _, el := range res.Elements {
		class, ok := roadClasses[el.Tags["highway"]]
		if el.Type != "way" || !ok {
			continue
		}
		var run [][2]int
		flush := func() {
			if pts := simplify(run, mapTolerance); len(pts) >= 2 {
				flat := make([]int, 0, len(pts)*2)
				for _, p := range pts {
					flat = append(flat, p[0], p[1])
				}
				out.Ways = append(out.Ways, road{C: class, P: flat})
			}
			run = nil
		}
		for _, g := range el.Geometry {
			if g == nil {
				flush()
				continue
			}
			x, y := tilePoint(t, g.Lat, g.Lon)
			if n := len(run); n > 0 && run[n-1] == [2]int{x, y} {
				continue
			}
			run = append(run, [2]int{x, y})
		}
		flush()
	}
	return json.Marshal(out)
}

// simplify is Douglas–Peucker: the points that keep the line within tol of the original.
func simplify(pts [][2]int, tol float64) [][2]int {
	if len(pts) < 3 {
		return pts
	}
	keep := make([]bool, len(pts))
	keep[0], keep[len(pts)-1] = true, true
	type span struct{ a, b int }
	stack := []span{{0, len(pts) - 1}}
	for len(stack) > 0 {
		s := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		best, at := 0.0, -1
		for i := s.a + 1; i < s.b; i++ {
			if d := segmentDistance(pts[i], pts[s.a], pts[s.b]); d > best {
				best, at = d, i
			}
		}
		if at >= 0 && best > tol {
			keep[at] = true
			stack = append(stack, span{s.a, at}, span{at, s.b})
		}
	}
	var out [][2]int
	for i, k := range keep {
		if k {
			out = append(out, pts[i])
		}
	}
	return out
}

func segmentDistance(p, a, b [2]int) float64 {
	px, py := float64(p[0]), float64(p[1])
	ax, ay, bx, by := float64(a[0]), float64(a[1]), float64(b[0]), float64(b[1])
	dx, dy := bx-ax, by-ay
	if dx == 0 && dy == 0 {
		return math.Hypot(px-ax, py-ay)
	}
	u := math.Max(0, math.Min(1, ((px-ax)*dx+(py-ay)*dy)/(dx*dx+dy*dy)))
	return math.Hypot(px-ax-u*dx, py-ay-u*dy)
}

// Tile returns the tile's roads as JSON, from the cache or from Overpass, and whether it
// came from the cache.
func (m *Maps) Tile(ctx context.Context, t mapTile) ([]byte, bool, error) {
	if body, ok := m.cached(t); ok {
		return body, true, nil
	}
	m.fetchMu.Lock()
	defer m.fetchMu.Unlock()
	// Another request may have fetched it while this one waited.
	if body, ok := m.cached(t); ok {
		return body, true, nil
	}
	if wait := m.gap - time.Since(m.lastFetch); wait > 0 {
		select {
		case <-time.After(wait):
		case <-ctx.Done():
			return nil, false, ctx.Err()
		}
	}
	m.lastFetch = time.Now()
	raw, err := m.fetch(ctx, t)
	if err != nil {
		return nil, false, err
	}
	body, err := buildTile(t, raw)
	if err != nil {
		return nil, false, err
	}
	m.store(t, body)
	return body, false, nil
}

func (m *Maps) cached(t mapTile) ([]byte, bool) {
	m.mu.Lock()
	defer m.mu.Unlock()
	e, ok := m.tiles[t]
	if !ok || time.Since(e.at) > mapCacheAge {
		return nil, false
	}
	return e.body, true
}

// store keeps the tile, dropping the oldest when the cache is full.
func (m *Maps) store(t mapTile, body []byte) {
	m.mu.Lock()
	defer m.mu.Unlock()
	if m.tiles == nil {
		m.tiles = map[mapTile]mapEntry{}
	}
	if len(m.tiles) >= mapCacheTiles {
		var oldest mapTile
		var at time.Time
		for k, e := range m.tiles {
			if at.IsZero() || e.at.Before(at) {
				oldest, at = k, e.at
			}
		}
		delete(m.tiles, oldest)
	}
	m.tiles[t] = mapEntry{body: body, at: time.Now()}
}

// fetch asks Overpass. The query goes in the body, so its errors never carry the tile.
func (m *Maps) fetch(ctx context.Context, t mapTile) ([]byte, error) {
	form := url.Values{"data": {overpassQuery(t)}}.Encode()
	req, err := http.NewRequestWithContext(ctx, http.MethodPost, m.OverpassURL, strings.NewReader(form))
	if err != nil {
		return nil, err
	}
	req.Header.Set("Content-Type", "application/x-www-form-urlencoded")
	req.Header.Set("User-Agent", m.UserAgent)
	resp, err := m.client().Do(req)
	if err != nil {
		return nil, errors.New("overpass could not be reached")
	}
	defer resp.Body.Close()
	if resp.StatusCode != http.StatusOK {
		_, _ = io.Copy(io.Discard, io.LimitReader(resp.Body, 1<<16))
		return nil, fmt.Errorf("overpass answered %d", resp.StatusCode)
	}
	raw, err := io.ReadAll(io.LimitReader(resp.Body, maxOverpassBytes+1))
	if err != nil {
		return nil, errors.New("overpass answer could not be read")
	}
	if len(raw) > maxOverpassBytes {
		return nil, errors.New("overpass answer is too large")
	}
	return raw, nil
}

func (a *API) mapRoutes(mux *http.ServeMux) {
	mux.HandleFunc("POST /v1/map/roads", a.ingest(a.mapRoads))
}

func (a *API) mapRoads(w http.ResponseWriter, r *http.Request, c caller, body []byte) error {
	if a.Maps == nil {
		writeJSON(w, http.StatusNotFound, map[string]string{"error": "maps are not enabled"})
		return nil
	}
	var req struct {
		Z, X, Y *int
	}
	if err := json.Unmarshal(body, &req); err != nil || req.Z == nil || req.X == nil || req.Y == nil {
		return invalid("z, x and y are required")
	}
	if *req.Z != mapZoom {
		return invalid("z must be %d", mapZoom)
	}
	limit := 1 << mapZoom
	if *req.X < 0 || *req.X >= limit || *req.Y < 0 || *req.Y >= limit {
		return invalid("x and y must be within the zoom level")
	}
	t := mapTile{Z: *req.Z, X: *req.X, Y: *req.Y}
	data, cached, err := a.Maps.Tile(r.Context(), t)
	if err != nil {
		slog.Warn("map tile not available", "installation", who(c), "error", err)
		writeJSON(w, http.StatusServiceUnavailable, map[string]string{"error": "map data not available, try again later"})
		return nil
	}
	if !cached {
		slog.Info("map tile fetched", "installation", who(c), "ways", strings.Count(string(data), `"c":`),
			"bytes", len(data))
	}
	w.Header().Set("Content-Type", "application/json")
	if strings.Contains(r.Header.Get("Accept-Encoding"), "gzip") {
		var buf bytes.Buffer
		zw := gzip.NewWriter(&buf)
		_, _ = zw.Write(data)
		_ = zw.Close()
		w.Header().Set("Content-Encoding", "gzip")
		data = buf.Bytes()
	}
	w.WriteHeader(http.StatusOK)
	_, _ = w.Write(data)
	return nil
}