Files
11eb72f578 feat(planner): Coverage tab, reach of a candidate repeater site (#2406)
The repeater planner (#2391) gets a fourth tab, **Coverage**: put a
marker where you are thinking of placing a repeater, set its antenna
height, and see on the map who would hear it. It answers the siting
question "what does a repeater reach if we put it here", with two
layers: handheld users and other repeaters.

## What it shows

- **Users layer:** the chance that a handheld at 1.5 m hears the site,
in 4 bands (10-25%, 25-50%, 50-75%, 75% and up; below 10% is not
painted). The chance comes from a distance curve `P(d) = 1 / (1 +
exp((ln d - ln d50) / slope))`, fitted on drive-test receptions of 41
Belgian repeaters (d50 2.7 km, slope 0.30). Terrain only lowers a cell
by 2 bands where a 1.5 m receiver sits deeper than 1 first-Fresnel
radius under the terrain (`cmd/server/planner_viewshed.go:19-21`).
Antenna height does not change the curve: in the drive tests, handheld
reach barely changed between 1, 7 and 15 m. The panel says so in one
line.
- **Repeaters layer:** first-Fresnel clearance from the site to every
cell, for a receiver at "Repeaters at" height (default
`planner.existingAntennaM`). 3 classes: line of sight (clearance 0% or
more), slightly blocked (-20% to 0%), blocked (not painted). Every known
repeater within range gets its link computed with the existing planner
link code, a dot in its class colour, a line for line of sight and
slightly blocked, and an entry in a list.
- **Compute button:** changing site, height or range moves the marker
and updates the URL hash right away, and dims an existing result with an
"Outdated" note. Only "Compute coverage" starts a job. A shared link
that carries a site computes once on open. The planner has 1 heavy-job
slot shared with Area and allows 6 jobs per minute per IP, so
recomputing on every change would burn both.

State is in the hash:
`#/tools/planner?mode=coverage&site=51.06,4.41&h=10&rx=5&range=30&layer=repeaters`.

This builds on the repeater planner @zfouts wrote in #2391: the terrain
tiles, the first-Fresnel analysis, the link code, the job protocol and
the Area module pattern are all reused here. Thanks for that work, it
made this tab a small addition instead of a new subsystem.

## Why the Repeaters classes are not the route LOS verdicts

The route verdicts (clear 100%+, clear60 60%+, marginal 0%+, blocked)
almost never show on Shuttle Radar Topography Mission (SRTM) terrain at
mast heights. At 10 m / 5 m, 30 km around Mechelen, 109 of 70,980 cells
reach clear60 or clear. SRTM includes trees and roofs, so the line
between 2 masts rarely clears 60% of the Fresnel zone.

I checked the clearance against one Belgian repeater (28 m, receivers at
5 m) and the repeaters live data shows it actually hears:

| Distance | Heard, clearance >= 0 | Heard, clearance < 0 |
|---|---|---|
| 0-10 km | 9 of 11 | none in range |
| 10-20 km | 3 of 4 | 1 of 8 |
| 20-30 km | 0 of 6 | 3 of 35 |
| 30-60 km | 1 of 2 | 0 of 84 |

Every link heard within 16 km had a clearance between 2% and 54%, so
"marginal" is where working links live. The map classes follow that
(`repeaterClass`, `cmd/server/planner_viewshed.go:75-89`). Chain, Relay
and Area keep the shared verdicts; `losVerdict` is unchanged. This rests
on 17 heard links from 1 repeater, which is why the -20% band is narrow
and the panel says line of sight stops being enough beyond about 20 km.

## Server

- `GET /api/planner/viewshed?site=&h=&rx=&range=`
(`cmd/server/planner_api.go:603`, route `cmd/server/routes.go:393`).
Same job protocol, result cache, rate limits and opt-in as the other
planner endpoints: 404 while `planner.enabled` is false.
- One byte per cell: low nibble Users class 1-5, high nibble Repeaters
class 1-3, 0 for no data. The grid is about 300 x 300 at every range:
0.2 km cells up to 30 km, `range/150` above (`planner_viewshed.go:47`).
- Links skip rooms, stale repeaters and a repeater within 100 m of the
site (that is the site itself). They carry no `elev_m` profile.
- `truncated` is true only when the 300-node cap may have dropped a
repeater within range (`viewshedTruncated`, `planner_api.go:694`).
- Tile cap: `Viewshed` in the planner tile limits, sized from the
largest offered range (60 km).
- New config: `planner.userReach.{d50Km,slope}` with a `_comment` in
`config.example.json`. Bounds 0.2-50 km and 0.05-2.
- No writes, no new `map[string]interface{}`; response types
`PlannerViewshedResponse/Params/Link` in `planner_types.go`.

## Frontend

- `public/planner-coverage.js` + `.css`, mounted like `planner-area.js`.
`planner.js` gets a `MODULES` table (`public/planner.js:31`) so Area and
Coverage share one enter/leave path.
- Canvas raster in an `L.imageOverlay`; the layer switch repaints
locally without a new request. Requests go through `fetchJob` / `CSApi`.
- Colours are CSS variables `--pl-cov-user-2..5` and `--pl-cov-rep-1..3`
in `:root` and both dark blocks of `style.css`; the Repeaters ones point
at `--status-*`, so a theme that changes those changes the map.

## Performance

The job is opt-in and runs in the existing planner job slot, never in a
hot path. Measured on real SRTM tiles, local build, 304 Belgian
repeaters:

| Site | Range | Mast | Job time |
|---|---|---|---|
| Maasvallei (hilly) | 30 km | 10 m | 2.07 s |
| Maasvallei | 30 km | 30 m | 2.57 s |
| Maasvallei | 60 km | 10 m | 3.98 s |
| Mechelen (flat) | 30 km | 10 m | 2.61 s |

On a staging instance (ARM64, cold tile cache) a 30 km job took 6.8 s
including the tile downloads. Response size at 60 km with 115 links:
239,942 bytes with link elevation profiles, 149,984 without (what this
PR ships). `BenchmarkViewshedMaxLeg` covers the 60 km worst case on a
synthetic terrain view.

## Verification

- Go: 26 viewshed tests and benchmarks in `planner_viewshed_test.go`,
`planner_api_test.go`, `planner_config_test.go` and
`planner_tiles_test.go`, among them: flat terrain equals the plain curve
and `analyzeLOS`, a ridge shadows only its far side, missing terrain is
"no data", the `truncated` rule (proven to fail on the old rule), links
without `elev_m`, the repeater at the site left out. `go test ./...` in
`cmd/server` passes.
- Frontend: `tests/unit/test-planner-coverage.js` (23 tests, in
`test-all.sh`): grid decode, class-to-colour mapping, unpainted classes,
hash round trip, no fetch on parameter change, 1 fetch per click,
deep-link autorun once, stale responses ignored, link classes at the
boundaries, escaped repeater names.
- E2E: 5 Coverage cases in `tests/e2e/test-planner-e2e.js` (stubbed
viewshed): click and compute, layer switch without a request, outdated
then recompute, deep link, leaving the tab removes the overlay. Planner
E2E 25/25 locally.
- eslint 0 errors. Browser: light and dark theme, Users and Repeaters on
flat, hilly and coastal sites, deep links, no console errors; also on a
staging instance with live data.

## Not in this PR

- The `--pl-cov-*` colours are not in the customizer's `THEME_CSS_MAP`
yet. They follow `--status-*` for the Repeaters layer; the Users colours
need their own entries (AGENTS.md rule 8, later milestone).
- In Flanders the Users layer is close to a circle: 0.3% of cells differ
from the plain curve around Mechelen, 42% in the Maasvallei, 64% in the
Ardennes. The terrain correction is untested in hilly areas, the drive
tests had no repeater there.
- The Repeaters calibration uses 1 repeater. Other operators with drive
tests or neighbour data can tighten it.
- A link's class comes from `clearance_pct`, rounded to 0.1%, while the
grid uses the raw clearance: within 0.05% of a bound a link can land 1
class off the cell under it. List, line and dot always agree with each
other.
- An OS dark-mode switch without the theme toggle does not repaint the
overlay until the next compute, the same as the planner's tile layer.

---------

Co-authored-by: zfouts <zachary.fouts@gmail.com>
Co-authored-by: Claude Opus 5.5 <noreply@anthropic.com>
2026-11-17 23:19:49 +01:00

1304 lines
41 KiB
Go
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
package main
// Planner search: the repeater backbone plan (runCoveragePlan) and the
// single-relay search (runRelaySearch).
//
// Both are deterministic: single-threaded, no map iteration, and every sort
// is a total order (ties fall to an index). Every terrain link goes through
// planLinkEval, which samples the points sampleTerrainProfile samples and
// applies analyzeLOS's formulas in the same operand order, so a link the plan
// calls solid reads the same on /api/planner/profile. (Equal up to rounding:
// the compiler may fuse a multiply-add differently in the two copies, moving
// a sample by an ulp, ~1 nm.)
import (
"cmp"
"context"
"errors"
"fmt"
"math"
"slices"
"time"
)
// planInputs is everything a coverage plan needs, snapshotted by the API
// layer outside any store lock.
type planInputs struct {
Area geoBBox // snapped
Nodes []plannerNode
Observed []plannerEdge
Truncated bool
Params PlannerPlanParams
}
const (
planGridKm = 1.0 // coverage candidate grid spacing
planPeakRadius = 2 // candidate = local maximum over a 5×5 window
planSiteSpacingKm = 2.0 // candidates keep this far from active nodes and chosen sites
planEdgesEnd = 0.4 // progress when the baseline edges are done
planCandsEnd = 0.75 // progress when the candidates are done
planSiteLinksOut = 12 // PlannerSite.Links cap
relayGridKm = 0.5
relayPeakRadius = 1 // 3×3 window
relayMaxOpen = 400 // open cells evaluated, highest first
relayMaxOptions = 5 // per list
relayDetour = 1.3 // d(A,R)+d(R,B) ≤ 1.3·max(D, relayMinBaseKm)
relayMinBaseKm = 1.0
relayExpand = 0.3 // open grid: bbox(A,B) grown by 0.3·D ...
relayMinExpandKm = 2.0 // ... but at least 2 km
relaySpacingKm = 1.0 // open options keep this far from a better one
relayMinLegKm = 0.1 // a relay this close to A or B is the endpoint itself
relayGridEnd = 0.1 // progress when the open grid is sampled
// relayWarnDirectNoTerrain: a sample of the direct path has no terrain,
// so Direct is not measured (Error no_terrain).
relayWarnDirectNoTerrain = "Direct link crosses missing terrain: not measured"
// planGridMaxSide caps grid rows/cols. A 250 km coverage area (the
// largest maxAreaKm) at 1 km fits, and so does a 200 km relay leg's
// corridor (the largest maxLegKm: 320 km at 500 m is 641 cells, a little
// more east-west at high latitude).
planGridMaxSide = 720
planCtxEvery = 16 // profiles between ctx checks (≤ ~1 ms of work)
planStride0 = 16 // first stride of the coarse-to-fine profile walk
)
// ─── Backbone plan ─────────────────────────────────────────────────────────
// runCoveragePlan computes the backbone plan. progress(frac) is called
// with 0..1 as stages complete. Must check ctx in its hot loops.
//
// Stages: baseline edges (observed, plus predicted pairs within range when
// Baseline is "predicted") → baseline graph and stats → candidate sites
// (1 km grid local maxima, plateaus thinned to one per 3 km, with ≥ 1
// solid link) → greedy picks → response.
// Terrain without data (ElevationAt ok=false) is skipped, never read as 0 m:
// no candidate stands on it and no predicted edge or candidate link crosses
// it. An observed edge is radio evidence and stays, its clearance unknown (0).
// A cancelled ctx returns ctx.Err() within one ctx-check interval; invalid
// inputs return an error before any work.
func runCoveragePlan(ctx context.Context, v terrainView, in planInputs, progress func(frac float64)) (PlannerPlanResponse, error) {
return planCoverage(ctx, v, in, progress, nil)
}
// planStageStats is what planCoverage spent per stage (benchmarks).
type planStageStats struct {
EdgesTime, CandsTime, GreedyTime, OutputTime time.Duration
Profiles, Peaks, Candidates, Sites int
}
func planCoverage(ctx context.Context, v terrainView, in planInputs, progress func(float64), stats *planStageStats) (PlannerPlanResponse, error) {
if err := checkPlanInputs(v, in); err != nil {
return PlannerPlanResponse{}, err
}
if err := ctx.Err(); err != nil {
return PlannerPlanResponse{}, err
}
if progress == nil {
progress = func(float64) {}
}
s := newCoverageSearch(ctx, v, in, progress)
var st planStageStats
t := time.Now()
if err := s.baselineEdges(); err != nil {
return PlannerPlanResponse{}, err
}
s.baselineGraph()
st.EdgesTime = time.Since(t)
t = time.Now()
peaks, err := s.findCandidates()
if err != nil {
return PlannerPlanResponse{}, err
}
st.CandsTime = time.Since(t)
t = time.Now()
if err := s.greedy(); err != nil {
return PlannerPlanResponse{}, err
}
st.GreedyTime = time.Since(t)
t = time.Now()
resp, err := s.response()
if err != nil {
return PlannerPlanResponse{}, err
}
st.OutputTime = time.Since(t)
st.Profiles, st.Peaks, st.Candidates, st.Sites = s.ev.profiles, peaks, len(s.cands), len(s.picks)
if stats != nil {
*stats = st
}
progress(1)
return resp, nil
}
// checkPlanInputs rejects what the API layer should never pass; the error
// names the field, never a value. Ranges are checked against the largest
// planner.maxLegKm an operator can set: the API layer enforces the one set.
func checkPlanInputs(v terrainView, in planInputs) error {
if v == nil {
return errors.New("planner: no terrain view")
}
a := in.Area
if !planCoordOK(a.S, a.W) || !planCoordOK(a.N, a.E) || a.S > a.N || a.W > a.E {
return errors.New("planner: invalid area")
}
if len(in.Nodes) > plannerMaxNodes {
return errors.New("planner: too many nodes")
}
for i := range in.Nodes {
if !planCoordOK(in.Nodes[i].Lat, in.Nodes[i].Lon) {
return errors.New("planner: invalid node position")
}
}
p := in.Params
switch {
case p.Sites < 0 || p.Sites > plannerMaxSites:
return errors.New("planner: invalid sites")
case !(p.RangeKm > 0 && p.RangeKm <= plannerLegKmMax):
return errors.New("planner: invalid range")
case !planHeightOK(p.NewAntennaM) || !planHeightOK(p.ExistingAntennaM):
return errors.New("planner: invalid antenna height")
case !planRadioOK(p.FrequencyMHz, p.KFactor):
return errors.New("planner: invalid radio parameters")
case !losFinite(p.MinClearance):
return errors.New("planner: invalid min clearance")
case p.Baseline != "predicted" && p.Baseline != "observed":
return errors.New("planner: invalid baseline")
}
return nil
}
func planCoordOK(lat, lon float64) bool {
return plannerFiniteCoord(lat, lon) && lat >= -90 && lat <= 90 && lon >= -180 && lon <= 180
}
func planHeightOK(h float64) bool { return h >= 0 && !math.IsInf(h, 1) }
// planRadioOK: the inputs analyzeLOS accepts (k = 0 means 4/3).
func planRadioOK(freqMHz, k float64) bool {
return freqMHz > 0 && losFinite(freqMHz) && k >= 0 && losFinite(k)
}
// coverageSearch is one plan computation. Node vertices are 0..n-1 in the
// backbone graph; the site picked at step s is vertex n+s-1.
type coverageSearch struct {
ctx context.Context
in planInputs
p PlannerPlanParams
progress func(float64)
ev *planLinkEval
pts []geoPoint
active []bool // !Stale || IncludeStale
counted []bool // active && InArea
countFn func(int) bool
inRange planNear // RangeKm prefilter
spacing planNear // planSiteSpacingKm prefilter
repeaters, staleExcluded int
observed, solid, marginal []plannerEdge
g *backboneGraph // baseline, then + each pick
s0, cur backboneStats
// linked: the node has an edge in g (observed, solid or to a site). A
// counted node without one is what a pick can newly "reach".
linked []bool
cands []planCand
picks []planPick
}
// planCand is a candidate site. links are its solid links to active nodes
// (peer = node index), siteLinks its solid links to chosen sites
// (peer = step); minClear is the lowest clearance over both.
type planCand struct {
idx int // grid index: stable identity and the last tie-break
pt geoPoint
elev float64
links []planCandLink
siteLinks []planCandLink
minClear float64
gone bool // picked, or within planSiteSpacingKm of a pick
}
type planCandLink struct {
peer int
dist, clear float64
}
type planPick struct {
cand int // index into cands
gain planGain
reason string
before backboneStats
after backboneStats
}
// planGain is a pick's lexicographic objective: components joined, then
// largest-component growth, then fragility removed, then repeaters reached.
type planGain struct{ comps, largest, frag, reach int }
func (a planGain) compare(b planGain) int {
if c := cmp.Compare(a.comps, b.comps); c != 0 {
return c
}
if c := cmp.Compare(a.largest, b.largest); c != 0 {
return c
}
if c := cmp.Compare(a.frag, b.frag); c != 0 {
return c
}
return cmp.Compare(a.reach, b.reach)
}
func newCoverageSearch(ctx context.Context, v terrainView, in planInputs, progress func(float64)) *coverageSearch {
n := len(in.Nodes)
p := in.Params
s := &coverageSearch{
ctx: ctx, in: in, p: p, progress: progress,
ev: newPlanLinkEval(ctx, v, p.FrequencyMHz, p.KFactor),
pts: make([]geoPoint, n),
active: make([]bool, n),
counted: make([]bool, n),
linked: make([]bool, n),
}
maxAbsLat := math.Max(math.Abs(in.Area.S), math.Abs(in.Area.N))
for i, nd := range in.Nodes {
s.pts[i] = geoPoint{nd.Lat, nd.Lon}
s.active[i] = !nd.Stale || p.IncludeStale
s.counted[i] = s.active[i] && nd.InArea
if s.counted[i] {
s.repeaters++
}
if nd.InArea && !s.active[i] {
s.staleExcluded++
}
maxAbsLat = math.Max(maxAbsLat, math.Abs(nd.Lat))
}
s.countFn = func(i int) bool { return i < n && s.counted[i] }
s.inRange = newPlanNear(p.RangeKm, maxAbsLat)
s.spacing = newPlanNear(planSiteSpacingKm, maxAbsLat)
return s
}
// baselineEdges: observed edges between active nodes (with their terrain
// clearance), then, for Baseline "predicted", every other active pair
// within range as solid or marginal. Pairs are canonical i<j, profiled i→j.
func (s *coverageSearch) baselineEdges() error {
n := len(s.pts)
he := s.p.ExistingAntennaM
predicted := s.p.Baseline == "predicted"
total := len(s.in.Observed)
if predicted {
total += n * (n - 1) / 2
}
done := 0
tick := func() error {
if done++; done%256 != 0 {
return nil
}
s.progress(planEdgesEnd * float64(done) / float64(total))
return s.ctx.Err()
}
isObserved := make([]bool, n*n) // n ≤ plannerMaxNodes
for _, e := range s.in.Observed {
if err := tick(); err != nil {
return err
}
a, b := e.A, e.B
if a > b {
a, b = b, a
}
if a < 0 || b >= n || a == b || !s.active[a] || !s.active[b] || isObserved[a*n+b] {
continue
}
isObserved[a*n+b] = true
d := geoDistKm(s.pts[a], s.pts[b])
pct := 0.0 // terrain unknown: a sample has no terrain
if c, ok := s.ev.clearance(s.pts[a], s.pts[b], d, he, he, math.Inf(-1)); ok {
pct = planPct(c)
}
if s.ev.err != nil {
return s.ev.err
}
s.observed = append(s.observed, plannerEdge{A: a, B: b, Class: "observed", DistanceKm: d, ClearancePct: pct})
}
if !predicted {
return nil
}
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if err := tick(); err != nil {
return err
}
if !s.active[i] || !s.active[j] || isObserved[i*n+j] || !s.inRange.maybe(s.pts[i], s.pts[j]) {
continue
}
d := geoDistKm(s.pts[i], s.pts[j])
if d > s.p.RangeKm {
continue
}
c, ok := s.ev.clearance(s.pts[i], s.pts[j], d, he, he, 0)
if s.ev.err != nil {
return s.ev.err
}
switch {
case !ok:
case c >= s.p.MinClearance:
s.solid = append(s.solid, plannerEdge{A: i, B: j, Class: "solid", DistanceKm: d, ClearancePct: planPct(c)})
default:
s.marginal = append(s.marginal, plannerEdge{A: i, B: j, Class: "marginal", DistanceKm: d, ClearancePct: planPct(c)})
}
}
}
return nil
}
// baselineGraph: only observed and solid edges connect the backbone.
func (s *coverageSearch) baselineGraph() {
edges := make([]plannerEdge, 0, len(s.observed)+len(s.solid))
edges = append(append(edges, s.observed...), s.solid...)
for _, e := range edges {
s.linked[e.A], s.linked[e.B] = true, true
}
s.g = newBackboneGraph(len(s.pts), s.active, edges)
s.s0 = s.g.Stats(s.countFn)
s.cur = s.s0
}
// findCandidates fills s.cands (grid order) and returns the number of grid
// cells profiled: local maxima more than planSiteSpacingKm from every active
// node, plateaus thinned.
func (s *coverageSearch) findCandidates() (int, error) {
grid, err := newPlanGrid(s.ctx, s.ev.v, s.in.Area, planGridKm)
if err != nil {
return 0, err
}
peaks := grid.peaks(planPeakRadius)
eligible := peaks[:0]
for k, gi := range peaks {
if k%256 == 0 {
if err := s.ctx.Err(); err != nil {
return 0, err
}
}
if !s.nearActiveNode(grid.point(gi)) {
eligible = append(eligible, gi)
}
}
peaks = grid.thin(eligible, planPeakRadius)
hr, he := s.p.NewAntennaM, s.p.ExistingAntennaM
for k, gi := range peaks {
if err := s.ctx.Err(); err != nil {
return 0, err
}
s.progress(planEdgesEnd + (planCandsEnd-planEdgesEnd)*float64(k)/float64(len(peaks)))
pt := grid.point(gi)
var links []planCandLink
for j, q := range s.pts {
if !s.active[j] || !s.inRange.maybe(pt, q) {
continue
}
d := geoDistKm(pt, q)
if d > s.p.RangeKm {
continue
}
c, ok := s.ev.clearance(pt, q, d, hr, he, s.p.MinClearance)
if s.ev.err != nil {
return 0, s.ev.err
}
if ok {
links = append(links, planCandLink{peer: j, dist: d, clear: c})
}
}
if len(links) == 0 {
continue
}
minC := math.Inf(1)
for _, l := range links {
minC = math.Min(minC, l.clear)
}
s.cands = append(s.cands, planCand{idx: gi, pt: pt, elev: grid.elev[gi], links: links, minClear: minC})
}
s.capCandidates()
return len(peaks), nil
}
func (s *coverageSearch) nearActiveNode(pt geoPoint) bool {
for j, q := range s.pts {
if s.active[j] && s.spacing.maybe(pt, q) && geoDistKm(pt, q) <= planSiteSpacingKm {
return true
}
}
return false
}
// capCandidates keeps the plannerMaxCands best by (distinct baseline
// components linked, solid links, elevation), then restores grid order.
func (s *coverageSearch) capCandidates() {
if len(s.cands) <= plannerMaxCands {
return
}
comps := make([]int, len(s.cands))
seen := make([]int, len(s.pts)) // ComponentOf ids are < n; stamp = k+1
for k := range s.cands {
for _, l := range s.cands[k].links {
if c := s.s0.ComponentOf[l.peer]; c >= 0 && seen[c] != k+1 {
seen[c] = k + 1
comps[k]++
}
}
}
order := make([]int, len(s.cands))
for k := range order {
order[k] = k
}
slices.SortFunc(order, func(x, y int) int {
a, b := &s.cands[x], &s.cands[y]
if c := cmp.Compare(comps[y], comps[x]); c != 0 {
return c
}
if c := cmp.Compare(len(b.links), len(a.links)); c != 0 {
return c
}
if c := cmp.Compare(b.elev, a.elev); c != 0 {
return c
}
return cmp.Compare(a.idx, b.idx)
})
order = order[:plannerMaxCands]
slices.Sort(order) // grid order again
kept := make([]planCand, len(order))
for k, o := range order {
kept[k] = s.cands[o]
}
s.cands = kept
}
// greedy picks up to Params.Sites sites, each the candidate with the best
// planGain against the current graph (ties: higher min clearance, higher
// elevation, lower grid index), stopping when the best gain is not positive.
func (s *coverageSearch) greedy() error {
var peers []int
for step := 1; step <= s.p.Sites; step++ {
best := -1
var bestGain planGain
var bestStats backboneStats
for k := range s.cands {
if k%32 == 0 {
if err := s.ctx.Err(); err != nil {
return err
}
frac := (float64(step-1) + float64(k)/float64(len(s.cands))) / float64(s.p.Sites)
s.progress(planCandsEnd + (1-planCandsEnd)*frac)
}
c := &s.cands[k]
if c.gone {
continue
}
peers = s.candPeers(c, peers[:0])
gc := s.g.Clone()
gc.AddVertex(peers)
st := gc.Stats(s.countFn)
gain := planGain{
comps: s.cur.Components - st.Components,
largest: st.Largest - s.cur.Largest,
frag: s.cur.Fragility - st.Fragility,
reach: s.reach(c),
}
if best < 0 || planCandBetter(gain, c, bestGain, &s.cands[best]) {
best, bestGain, bestStats = k, gain, st
}
}
if best < 0 || bestGain.compare(planGain{}) <= 0 {
break
}
if err := s.pick(best, step, bestGain, bestStats); err != nil {
return err
}
}
return nil
}
func (s *coverageSearch) candPeers(c *planCand, peers []int) []int {
for _, l := range c.links {
peers = append(peers, l.peer)
}
for _, l := range c.siteLinks {
peers = append(peers, len(s.pts)+l.peer-1)
}
return peers
}
// reach: counted nodes c links solidly that have no edge in the current
// graph. Nodes already on the backbone are not "reached" again, so a
// connected, redundant backbone yields no reach-only picks.
func (s *coverageSearch) reach(c *planCand) int {
r := 0
for _, l := range c.links {
if s.counted[l.peer] && !s.linked[l.peer] {
r++
}
}
return r
}
func planCandBetter(g planGain, c *planCand, bg planGain, b *planCand) bool {
if x := g.compare(bg); x != 0 {
return x > 0
}
if c.minClear != b.minClear {
return c.minClear > b.minClear
}
if c.elev != b.elev {
return c.elev > b.elev
}
return c.idx < b.idx
}
// pick commits candidate k as site step: adds it to g, removes it and every
// candidate within planSiteSpacingKm, and links it to the rest in range.
func (s *coverageSearch) pick(k, step int, gain planGain, after backboneStats) error {
c := &s.cands[k]
s.g.AddVertex(s.candPeers(c, nil))
reason := "reach"
switch {
case gain.comps > 0:
reason = "joins"
case gain.frag > 0 || after.CutVertices < s.cur.CutVertices:
reason = "redundancy"
}
s.picks = append(s.picks, planPick{cand: k, gain: gain, reason: reason, before: s.cur, after: after})
s.cur = after
for _, l := range c.links {
s.linked[l.peer] = true
}
hr := s.p.NewAntennaM
for k2 := range s.cands {
o := &s.cands[k2]
if o.gone || k2 == k {
continue
}
if s.spacing.maybe(c.pt, o.pt) && geoDistKm(c.pt, o.pt) <= planSiteSpacingKm {
o.gone = true
continue
}
if !s.inRange.maybe(c.pt, o.pt) {
continue
}
d := geoDistKm(c.pt, o.pt)
if d > s.p.RangeKm {
continue
}
cl, ok := s.ev.clearance(c.pt, o.pt, d, hr, hr, s.p.MinClearance)
if s.ev.err != nil {
return s.ev.err
}
if ok {
o.siteLinks = append(o.siteLinks, planCandLink{peer: step, dist: d, clear: cl})
o.minClear = math.Min(o.minClear, cl)
}
}
c.gone = true
return nil
}
func (s *coverageSearch) summary(st backboneStats) PlannerSummary {
return PlannerSummary{
Repeaters: s.repeaters,
Components: st.Components,
LargestComponent: st.Largest,
Isolated: st.Isolated,
CutVertices: st.CutVertices,
StaleExcluded: s.staleExcluded,
}
}
func (s *coverageSearch) response() (PlannerPlanResponse, error) {
in := s.in
resp := PlannerPlanResponse{
Area: geoBBoxJSON{S: in.Area.S, W: in.Area.W, N: in.Area.N, E: in.Area.E},
Params: s.p,
Baseline: s.summary(s.s0),
Final: s.summary(s.cur),
Nodes: make([]PlannerNodeOut, len(in.Nodes)),
Sites: make([]PlannerSite, 0, len(s.picks)),
Warnings: []string{},
Truncated: in.Truncated,
ComputedAt: time.Now().UTC(),
}
switch {
case s.s0.Components <= 1:
resp.Status = "connected"
case len(s.picks) > 0:
resp.Status = "improved"
default:
resp.Status = "no_gain"
}
for i, nd := range in.Nodes {
resp.Nodes[i] = PlannerNodeOut{
PubKey: nd.PubKey, Name: nd.Name, Role: nd.Role, Lat: nd.Lat, Lon: nd.Lon,
Stale: nd.Stale, InArea: nd.InArea, Component: s.s0.ComponentOf[i],
}
}
var cut bool
resp.Edges, cut = planEdgesOut(s.observed, s.solid, s.marginal)
resp.Truncated = resp.Truncated || cut
for step, pk := range s.picks {
site, err := s.siteOut(step+1, pk)
if err != nil {
return PlannerPlanResponse{}, err
}
resp.Sites = append(resp.Sites, site)
}
if s.staleExcluded > 0 {
resp.Warnings = append(resp.Warnings, plannerCount(s.staleExcluded, "stale repeater", "stale repeaters")+" excluded")
}
if len(s.cands) == 0 {
resp.Warnings = append(resp.Warnings, "Area has no candidate high ground with a usable link")
}
return resp, nil
}
// planEdgesOut: observed, then solid, then marginal, each by distance
// (ties by A, B), capped at plannerMaxEdgesOut.
func planEdgesOut(classes ...[]plannerEdge) ([]PlannerEdgeOut, bool) {
total := 0
for _, es := range classes {
total += len(es)
}
out := make([]PlannerEdgeOut, 0, int(math.Min(float64(total), plannerMaxEdgesOut)))
for _, es := range classes {
es = slices.Clone(es)
slices.SortFunc(es, func(x, y plannerEdge) int {
if c := cmp.Compare(x.DistanceKm, y.DistanceKm); c != 0 {
return c
}
if c := cmp.Compare(x.A, y.A); c != 0 {
return c
}
return cmp.Compare(x.B, y.B)
})
for _, e := range es {
if len(out) == plannerMaxEdgesOut {
return out, true
}
out = append(out, PlannerEdgeOut{
A: e.A, B: e.B, Class: e.Class,
DistanceKm: losRound(e.DistanceKm, 1000), ClearancePct: e.ClearancePct,
})
}
}
return out, false
}
// siteOut renders a pick. Links: its solid node and earlier-site links plus
// marginal node links (profiled again here, ≤ n per site), best first.
func (s *coverageSearch) siteOut(step int, pk planPick) (PlannerSite, error) {
c := &s.cands[pk.cand]
type ranked struct {
link PlannerSiteLink
clear float64
}
var links []ranked
isSolid := make([]bool, len(s.pts))
var comps []int
for _, l := range c.links {
isSolid[l.peer] = true
comps = append(comps, s.s0.ComponentOf[l.peer])
links = append(links, ranked{PlannerSiteLink{Node: l.peer, DistanceKm: losRound(l.dist, 1000),
ClearancePct: planPct(l.clear), Class: "solid"}, l.clear})
}
for _, l := range c.siteLinks {
links = append(links, ranked{PlannerSiteLink{Node: -1, PeerStep: l.peer, DistanceKm: losRound(l.dist, 1000),
ClearancePct: planPct(l.clear), Class: "solid"}, l.clear})
}
hr, he := s.p.NewAntennaM, s.p.ExistingAntennaM
for j, q := range s.pts {
if !s.active[j] || isSolid[j] || !s.inRange.maybe(c.pt, q) {
continue
}
d := geoDistKm(c.pt, q)
if d > s.p.RangeKm {
continue
}
cl, ok := s.ev.clearance(c.pt, q, d, hr, he, 0)
if s.ev.err != nil {
return PlannerSite{}, s.ev.err
}
if ok && cl < s.p.MinClearance {
links = append(links, ranked{PlannerSiteLink{Node: j, DistanceKm: losRound(d, 1000),
ClearancePct: planPct(cl), Class: "marginal"}, cl})
}
}
slices.SortFunc(links, func(x, y ranked) int {
if c := cmp.Compare(y.clear, x.clear); c != 0 {
return c
}
if c := cmp.Compare(x.link.DistanceKm, y.link.DistanceKm); c != 0 {
return c
}
if c := cmp.Compare(x.link.Node, y.link.Node); c != 0 {
return c
}
return cmp.Compare(x.link.PeerStep, y.link.PeerStep)
})
if len(links) > planSiteLinksOut {
links = links[:planSiteLinksOut]
}
out := make([]PlannerSiteLink, len(links))
for i, l := range links {
out[i] = l.link
}
slices.Sort(comps)
comps = slices.Compact(comps)
if comps == nil {
comps = []int{}
}
return PlannerSite{
Step: step, Lat: c.pt.Lat, Lon: c.pt.Lon, ElevM: losRound(c.elev, 10), AntennaM: hr,
Reason: pk.reason,
Gain: PlannerGain{
ComponentsJoined: pk.before.Components - pk.after.Components,
CutVerticesRemoved: pk.before.CutVertices - pk.after.CutVertices,
RepeatersReached: pk.gain.reach,
},
After: s.summary(pk.after),
Links: out,
JoinsComponents: comps,
}, nil
}
// ─── Relay search ──────────────────────────────────────────────────────────
// runRelaySearch finds the best single relay for A→B among known nodes and
// open terrain in the corridor.
//
// A relay R qualifies when both legs are within range, the detour
// d(A,R)+d(R,B) is at most 1.3·max(D, 1 km), and R is not within 100 m of
// A or B. Options rank by bottleneck clearance (the worse leg, as reported),
// then total distance, then node/grid index; up to 5 per list. Open cells
// are 500 m grid local maxima (3×3), the 400 highest evaluated, and none
// within 1 km of a better one. Options with a negative bottleneck are listed
// only when no option in either list reaches 0.
//
// Terrain without data is skipped, never read as 0 m: no relay stands on it
// and no option has a leg across it. A direct path across it is not
// measured (Error no_terrain, no verdict or profile) and gets
// relayWarnDirectNoTerrain.
func runRelaySearch(ctx context.Context, v terrainView, nodes []plannerNode, p PlannerRelayParams, progress func(frac float64)) (PlannerRelayResponse, error) {
if err := checkRelayParams(v, p); err != nil {
return PlannerRelayResponse{}, err
}
if err := ctx.Err(); err != nil {
return PlannerRelayResponse{}, err
}
if progress == nil {
progress = func(float64) {}
}
a, b := geoPoint{p.A.Lat, p.A.Lon}, geoPoint{p.B.Lat, p.B.Lon}
D := geoDistKm(a, b)
corridor := relayDetour * math.Max(D, relayMinBaseKm)
box := plannerExpandBBox(geoBBox{
S: math.Min(a.Lat, b.Lat), W: math.Min(a.Lon, b.Lon),
N: math.Max(a.Lat, b.Lat), E: math.Max(a.Lon, b.Lon),
}, math.Max(relayExpand*D, relayMinExpandKm))
grid, err := newPlanGrid(ctx, v, box, relayGridKm)
if err != nil {
return PlannerRelayResponse{}, err
}
progress(relayGridEnd)
maxAbsLat := math.Max(math.Abs(box.S), math.Abs(box.N))
for i := range nodes {
maxAbsLat = math.Max(maxAbsLat, math.Abs(nodes[i].Lat))
}
near := newPlanNear(p.RangeKm, maxAbsLat)
fits := func(pt geoPoint) (dA, dB float64, ok bool) {
if !near.maybe(a, pt) || !near.maybe(pt, b) {
return 0, 0, false
}
dA, dB = geoDistKm(a, pt), geoDistKm(pt, b)
ok = dA <= p.RangeKm && dB <= p.RangeKm && dA+dB <= corridor && dA >= relayMinLegKm && dB >= relayMinLegKm
return dA, dB, ok
}
var existing, open []relayCand
for i := range nodes {
nd := &nodes[i]
if nd.Stale || !planCoordOK(nd.Lat, nd.Lon) {
continue
}
pt := geoPoint{nd.Lat, nd.Lon}
dA, dB, ok := fits(pt)
if !ok {
continue
}
if e, okE := v.ElevationAt(pt.Lat, pt.Lon); okE && losFinite(e) {
existing = append(existing, relayCand{order: i, node: i, pt: pt, elev: e, dA: dA, dB: dB})
}
}
for _, gi := range grid.peaks(relayPeakRadius) {
pt := grid.point(gi)
if dA, dB, ok := fits(pt); ok {
open = append(open, relayCand{order: gi, node: -1, pt: pt, elev: grid.elev[gi], dA: dA, dB: dB})
}
}
// Highest first; on a plateau, the shortest detour.
slices.SortFunc(open, func(x, y relayCand) int {
if c := cmp.Compare(y.elev, x.elev); c != 0 {
return c
}
if c := cmp.Compare(x.dA+x.dB, y.dA+y.dB); c != 0 {
return c
}
return cmp.Compare(x.order, y.order)
})
if len(open) > relayMaxOpen {
open = open[:relayMaxOpen]
}
ev := newPlanLinkEval(ctx, v, p.FrequencyMHz, p.KFactor)
total, done := 2*(len(existing)+len(open)), 0
rank := func(list []relayCand, hR float64) ([]relayCand, error) {
kept := list[:0]
for _, c := range list {
ca, okA := ev.clearance(a, c.pt, c.dA, p.AntennaAM, hR, math.Inf(-1))
cb, okB := ev.clearance(c.pt, b, c.dB, hR, p.AntennaBM, math.Inf(-1))
if ev.err != nil {
return nil, ev.err
}
if done += 2; done%64 == 0 {
progress(relayGridEnd + (1-relayGridEnd)*float64(done)/float64(total))
}
if okA && okB { // a leg over missing terrain says nothing
c.pct = math.Min(planPct(ca), planPct(cb))
kept = append(kept, c)
}
}
slices.SortFunc(kept, relayCandCompare)
return kept, nil
}
if existing, err = rank(existing, p.ExistingAntennaM); err != nil {
return PlannerRelayResponse{}, err
}
if open, err = rank(open, p.RelayAntennaM); err != nil {
return PlannerRelayResponse{}, err
}
if len(existing) > relayMaxOptions {
existing = existing[:relayMaxOptions]
}
open = relaySpread(open)
// Lists are sorted, so a list has a usable option iff its head does.
if (len(existing) > 0 && existing[0].pct >= 0) || (len(open) > 0 && open[0].pct >= 0) {
existing, open = relayUsable(existing), relayUsable(open)
}
lp := losParams{FreqMHz: p.FrequencyMHz, KFactor: p.KFactor}
resp := PlannerRelayResponse{
Direct: relayLink(v, a, b, D, lp, p.AntennaAM, p.AntennaBM, true),
Existing: relayOptions(v, nodes, existing, a, b, lp, p, "existing", p.ExistingAntennaM),
Open: relayOptions(v, nodes, open, a, b, lp, p, "open", p.RelayAntennaM),
Params: p,
Warnings: []string{},
}
if resp.Direct.Error != "" {
resp.Warnings = append(resp.Warnings, relayWarnDirectNoTerrain)
}
best := math.Inf(-1)
for _, list := range [][]PlannerRelayOption{resp.Existing, resp.Open} {
if len(list) > 0 {
best = math.Max(best, list[0].BottleneckPct)
}
}
if best < plannerMinClearance*100 {
resp.Warnings = append(resp.Warnings, "No relay gives a clear first Fresnel zone")
}
progress(1)
return resp, nil
}
// checkRelayParams rejects what the API layer should never pass. The leg and
// range are checked against the largest planner.maxLegKm an operator can
// set (planGridMaxSide fits its corridor): the API layer enforces the one
// set.
func checkRelayParams(v terrainView, p PlannerRelayParams) error {
if v == nil {
return errors.New("planner: no terrain view")
}
switch {
case !planCoordOK(p.A.Lat, p.A.Lon) || !planCoordOK(p.B.Lat, p.B.Lon):
return errors.New("planner: invalid endpoint")
case !(haversineKm(p.A.Lat, p.A.Lon, p.B.Lat, p.B.Lon) <= plannerLegKmMax):
return errors.New("planner: leg too long")
case !(p.RangeKm > 0 && p.RangeKm <= plannerLegKmMax):
return errors.New("planner: invalid range")
case !planHeightOK(p.AntennaAM) || !planHeightOK(p.AntennaBM) ||
!planHeightOK(p.RelayAntennaM) || !planHeightOK(p.ExistingAntennaM):
return errors.New("planner: invalid antenna height")
case !planRadioOK(p.FrequencyMHz, p.KFactor):
return errors.New("planner: invalid radio parameters")
}
return nil
}
// relayCand: order is the node index (existing) or grid index (open);
// pct is the bottleneck as PlannerRelayOption.BottleneckPct reports it.
type relayCand struct {
order, node int // node −1 for open terrain
pt geoPoint
elev float64
dA, dB float64
pct float64
}
func relayCandCompare(x, y relayCand) int {
if c := cmp.Compare(y.pct, x.pct); c != 0 {
return c
}
if c := cmp.Compare(x.dA+x.dB, y.dA+y.dB); c != 0 {
return c
}
return cmp.Compare(x.order, y.order)
}
// relaySpread walks ranked open cells and keeps those more than
// relaySpacingKm from every option already kept, up to relayMaxOptions.
func relaySpread(ranked []relayCand) []relayCand {
var out []relayCand
for _, c := range ranked {
clash := false
for _, k := range out {
if geoDistKm(c.pt, k.pt) <= relaySpacingKm {
clash = true
break
}
}
if !clash {
if out = append(out, c); len(out) == relayMaxOptions {
break
}
}
}
return out
}
func relayUsable(list []relayCand) []relayCand {
return slices.DeleteFunc(list, func(c relayCand) bool { return c.pct < 0 })
}
// relayLink is a reported leg: the shared LOS summary, with its profile when
// withElev. A leg with a sample that has no terrain is not measured: Error
// no_terrain, no verdict and no profile, never a verdict read from 0 m.
func relayLink(v terrainView, a, b geoPoint, d float64, lp losParams, ha, hb float64, withElev bool) PlannerLink {
lp.AntennaAM, lp.AntennaBM = ha, hb
elev, ok := sampleTerrainProfile(v, a, b, planProfileSamples(d))
if !ok {
return PlannerLink{DistanceKm: losRound(math.Max(d, 0), 1000), Error: plannerErrNoTerrain}
}
return linkFromProfile(elev, d, lp, withElev)
}
func relayOptions(v terrainView, nodes []plannerNode, list []relayCand, a, b geoPoint, lp losParams,
p PlannerRelayParams, kind string, hR float64) []PlannerRelayOption {
out := make([]PlannerRelayOption, 0, len(list))
for _, c := range list {
legA := relayLink(v, a, c.pt, c.dA, lp, p.AntennaAM, hR, true)
legB := relayLink(v, c.pt, b, c.dB, lp, hR, p.AntennaBM, true)
if legA.Error != "" || legB.Error != "" {
// The search measured both legs, so only an interior sample an
// ulp across the edge of a tile without data gets here (planArc
// vs greatCircleSamples). An unmeasured leg is never offered.
continue
}
o := PlannerRelayOption{
Kind: kind, Lat: c.pt.Lat, Lon: c.pt.Lon, ElevM: losRound(c.elev, 10), AntennaM: hR,
LegA: legA, LegB: legB,
}
o.BottleneckPct = math.Min(o.LegA.ClearancePct, o.LegB.ClearancePct)
if c.node >= 0 {
o.PubKey, o.Name = nodes[c.node].PubKey, nodes[c.node].Name
}
out = append(out, o)
}
// The legs are recomputed from the same samples, so this is a no-op
// unless rounding disagrees; it keeps the list ordered as reported.
slices.SortStableFunc(out, func(x, y PlannerRelayOption) int { return cmp.Compare(y.BottleneckPct, x.BottleneckPct) })
return out
}
// ─── Shared terrain machinery ──────────────────────────────────────────────
// planPct is PlannerLink.ClearancePct for clearance c (linkFromProfile's
// rounding; +Inf, no interior sample, reads 999).
func planPct(c float64) float64 {
if math.IsInf(c, 1) {
return 999
}
return losRound(c*100, 10)
}
// planLinkEval profiles links without allocating. Not safe for concurrent
// use; each search owns one.
type planLinkEval struct {
ctx context.Context
v terrainView
freq float64
bulgeDen float64 // 2·k·R with k defaulted as analyzeLOS does
profiles int
err error // ctx.Err() once seen; every later call fails fast
}
func newPlanLinkEval(ctx context.Context, v terrainView, freqMHz, kFactor float64) *planLinkEval {
k := kFactor
if k == 0 {
k = 4.0 / 3.0
}
return &planLinkEval{ctx: ctx, v: v, freq: freqMHz, bulgeDen: 2 * k * earthRadiusKm}
}
// clearance returns the worst first-Fresnel clearance of a→b with antennas
// ha, hb metres above ground: analyzeLOS(sampleTerrainProfile(v, a, b,
// planProfileSamples(distKm)), distKm, …).Clearance, with distKm =
// geoDistKm(a, b). Interior samples are visited coarse-to-fine (stride 16,
// then the midpoints between) so an obstruction is usually met early, and
// the walk stops at the first sample below floor: ok=false. floor = −Inf
// evaluates every sample. ok=false also means a sample has no terrain
// (outside the view, or a tile without data: never read as 0 m) or ctx was
// cancelled (e.err is then set).
func (e *planLinkEval) clearance(a, b geoPoint, distKm, ha, hb, floor float64) (float64, bool) {
worst, _, ok := e.clearanceWalk(a, b, distKm, ha, hb, floor, 0, false)
return worst, ok
}
// clearanceWalk is the walk behind clearance. With two it also returns
// worst2, the worst clearance of the same path with the receiver hb2 metres
// above ground, from the same samples: the elevation lookups and the
// great-circle trigonometry, which dominate, are paid once. floor applies to
// hb only, so a caller that wants worst2 over every sample passes −Inf.
func (e *planLinkEval) clearanceWalk(a, b geoPoint, distKm, ha, hb, floor, hb2 float64, two bool) (worst, worst2 float64, ok bool) {
if e.err != nil {
return 0, 0, false
}
if e.profiles%planCtxEvery == 0 {
if err := e.ctx.Err(); err != nil {
e.err = err
return 0, 0, false
}
}
e.profiles++
eA, okA := e.v.ElevationAt(a.Lat, a.Lon)
eB, okB := e.v.ElevationAt(b.Lat, b.Lon)
if !okA || !okB || !losFinite(eA) || !losFinite(eB) {
return 0, 0, false
}
n := planProfileSamples(distKm)
arc := newPlanArc(a, b, distKm)
D := distKm
if !losFinite(D) || D < 0.001 {
D = 0.001
}
// Below, every expression keeps analyzeLOS's operand order; only loop
// invariants are hoisted.
last := float64(n - 1)
fDen := D * e.freq / 1000
yA, yB, yB2 := eA+ha, eB+hb, eB+hb2
worst, worst2 = math.Inf(1), math.Inf(1)
for s := planStride0; s >= 1; s /= 2 {
i, step := s, 2*s // odd multiples of s: the points the coarser passes skipped
if s == planStride0 {
step = s
}
for ; i <= n-2; i += step {
t := float64(i) / last
lat, lon := arc.at(t)
el, ok := e.v.ElevationAt(lat, lon)
if !ok || !losFinite(el) {
return 0, 0, false
}
d := t * D
tm := el + d*(D-d)/e.bulgeDen*1000
f1 := 17.32 * math.Sqrt(math.Max(d*(D-d), 1e-9)/fDen)
if two {
if c := (yA + (yB2-yA)*t - tm) / f1; c < worst2 {
worst2 = c
}
}
los := yA + (yB-yA)*t
if c := (los - tm) / f1; c < worst {
if worst = c; worst < floor {
return worst, worst2, false
}
}
}
}
return worst, worst2, true
}
// planArc is greatCircleSamples for one point at a time: the same formula
// and operand order, with the per-leg trigonometry hoisted (equal to an ulp).
type planArc struct {
a geoPoint
same bool
d, sd float64
cp1, sp1, cl1, sl1, cp2, sp2, cl2, sl2 float64
}
func newPlanArc(a, b geoPoint, distKm float64) planArc {
p1, l1 := a.Lat*math.Pi/180, a.Lon*math.Pi/180
p2, l2 := b.Lat*math.Pi/180, b.Lon*math.Pi/180
d := distKm / earthRadiusKm
if d < geoSamePointRadians {
return planArc{a: a, same: true}
}
return planArc{
a: a, d: d, sd: math.Sin(d),
cp1: math.Cos(p1), sp1: math.Sin(p1), cl1: math.Cos(l1), sl1: math.Sin(l1),
cp2: math.Cos(p2), sp2: math.Sin(p2), cl2: math.Cos(l2), sl2: math.Sin(l2),
}
}
// at is the point at fraction t (0 < t < 1; the ends are exact elsewhere).
func (r *planArc) at(t float64) (lat, lon float64) {
if r.same {
return r.a.Lat, r.a.Lon
}
A := math.Sin((1-t)*r.d) / r.sd
B := math.Sin(t*r.d) / r.sd
x := A*r.cp1*r.cl1 + B*r.cp2*r.cl2
y := A*r.cp1*r.sl1 + B*r.cp2*r.sl2
z := A*r.sp1 + B*r.sp2
return math.Atan2(z, math.Hypot(x, y)) * 180 / math.Pi, math.Atan2(y, x) * 180 / math.Pi
}
// planNear is a conservative degree-box prefilter for "within km": it
// never rejects a pair whose haversine distance is ≤ km when neither point
// is further from the equator than maxAbsLat. From the haversine formula,
// hav(d) ≥ hav(Δφ) and hav(d) ≥ cos²(maxAbsLat)·hav(Δλ).
type planNear struct{ latLim, lonLim float64 }
func newPlanNear(km, maxAbsLat float64) planNear {
const slack = 1 + 1e-9
r := km / earthRadiusKm // radians; haversineKm uses the same radius
p := planNear{latLim: r * 180 / math.Pi * slack, lonLim: 360}
if c := math.Cos(maxAbsLat * math.Pi / 180); c > 0 {
if q := math.Sin(r/2) / c; q < 1 {
p.lonLim = 2 * math.Asin(q) * 180 / math.Pi * slack
}
}
return p
}
func (p planNear) maybe(a, b geoPoint) bool {
if math.Abs(a.Lat-b.Lat) > p.latLim {
return false
}
dl := math.Abs(a.Lon - b.Lon)
if dl > 180 {
dl = 360 - dl
}
return dl <= p.lonLim
}
// planGrid samples terrain on a regular grid over a bbox: stepKm apart
// north–south and, at the box's middle latitude, east–west; centred in the
// box. Points are rounded to 5 decimals (what the API reports) and sampled
// there, so a reported site reproduces exactly.
type planGrid struct {
rows, cols int
lat, lon []float64 // per row, per column
elev []float64 // row-major
ok []bool // the view had terrain there
}
func newPlanGrid(ctx context.Context, v terrainView, b geoBBox, stepKm float64) (*planGrid, error) {
dLat := stepKm / plannerKmPerDeg
dLon := dLat / math.Max(math.Cos((b.S+b.N)/2*math.Pi/180), 0.01)
rows := int(math.Floor((b.N-b.S)/dLat+1e-9)) + 1
cols := int(math.Floor((b.E-b.W)/dLon+1e-9)) + 1
if rows < 1 || cols < 1 || rows > planGridMaxSide || cols > planGridMaxSide {
return nil, errors.New("planner: search area too large")
}
g := &planGrid{
rows: rows, cols: cols,
lat: make([]float64, rows), lon: make([]float64, cols),
elev: make([]float64, rows*cols), ok: make([]bool, rows*cols),
}
lat0 := b.S + ((b.N-b.S)-float64(rows-1)*dLat)/2
lon0 := b.W + ((b.E-b.W)-float64(cols-1)*dLon)/2
for r := range g.lat {
g.lat[r] = losRound(lat0+float64(r)*dLat, 1e5)
}
for c := range g.lon {
g.lon[c] = losRound(lon0+float64(c)*dLon, 1e5)
}
for r := 0; r < rows; r++ {
if err := ctx.Err(); err != nil {
return nil, err
}
for c := 0; c < cols; c++ {
if e, ok := v.ElevationAt(g.lat[r], g.lon[c]); ok && losFinite(e) {
g.elev[r*cols+c], g.ok[r*cols+c] = e, true
}
}
}
return g, nil
}
func (g *planGrid) point(i int) geoPoint { return geoPoint{g.lat[i/g.cols], g.lon[i%g.cols]} }
// peaks returns, in grid order, the valid cells at least as high as every
// valid cell within radius (a (2·radius+1)² window, clipped at the edges).
// Every cell of a plateau qualifies.
func (g *planGrid) peaks(radius int) []int {
var out []int
for r := 0; r < g.rows; r++ {
for c := 0; c < g.cols; c++ {
i := r*g.cols + c
if g.ok[i] && !g.window(r, c, radius, func(j int) bool { return g.ok[j] && g.elev[j] > g.elev[i] }) {
out = append(out, i)
}
}
}
return out
}
// thin walks peaks (grid order) and drops each one that has an already kept
// peak in its window. Two peaks in each other's window are necessarily equal,
// so this thins plateaus only, to one cell per (radius+1)² (every 3 km for
// the plan), and never drops an isolated peak. It bounds the plan on flat
// ground or sea, where every 1 km cell would otherwise be profiled to every
// node in range (14.9 s → 1.9 s with 100 m masts, BenchmarkCoveragePlanMax).
func (g *planGrid) thin(peaks []int, radius int) []int {
kept := make([]bool, len(g.elev))
out := peaks[:0:0]
for _, i := range peaks {
if !g.window(i/g.cols, i%g.cols, radius, func(j int) bool { return kept[j] }) {
kept[i] = true
out = append(out, i)
}
}
return out
}
// window reports whether hit holds for any cell within radius of (r, c).
func (g *planGrid) window(r, c, radius int, hit func(j int) bool) bool {
for rr := r - radius; rr <= r+radius; rr++ {
if rr < 0 || rr >= g.rows {
continue
}
for cc := c - radius; cc <= c+radius; cc++ {
if cc >= 0 && cc < g.cols && hit(rr*g.cols+cc) {
return true
}
}
}
return false
}
// plannerCount renders "1 stale repeater" / "3 stale repeaters".
func plannerCount(n int, one, many string) string {
if n == 1 {
return "1 " + one
}
return fmt.Sprintf("%d %s", n, many)
}