mirror of
https://github.com/Kpa-clawbot/meshcore-analyzer.git
synced 2026-11-22 05:57:12 +00:00
Refs #2424. Second step after #2426: `TestViewshedMatchesReference` is the slowest test in the server package. ## What changes Only `cmd/server/planner_viewshed_test.go`. 1. **30 km equivalence cases.** Of the three 30 km terrains (fake, flat, ridge) only the ridge case stays. Up to 30 km the cell size is the 0.2 km floor (`viewshedCellKm` = `max(0.2, r/150)`, `planner_viewshed.go:50`), so the 30 km cases add a bigger grid and longer rays (more samples per profile, `planProfileSamples`), not a different cell size. The ridge case keeps one full-size grid in the regular suite, with level ground west of the ridge and shadow east of it. 2. **Missing-tile case.** The old case could not reach its missing tile. The tile `{31,-98}` starts at lat 31; the 30 km bbox around lat 30.5, expanded by 1 km, ends near lat 30.78. So it was a second copy of the 30 km fake case. It now uses a site at lat 30.95 (0.05 degrees, about 5.6 km, south of the tile edge) with a 12 km range. 3. **New guard `TestViewshedMissingTileCaseReachesTheTile`.** It checks that the case touches the missing tile (`MissingTiles()` = 1 of at least 2), that every in-range cell north of the edge is NoData, and that cells south of it have data. With the old site (lat 30.5) it fails: `MissingTiles() = 0 of 1, want 1 of at least 2`. ## Measured Native, Windows, Go 1.26.1, `go test -count=1 -run '^TestViewshedMatchesReference$' -v .` with a temporary timer per case: | case | before | after | |---|---|---| | fake/30km | 3.49 s | removed | | flat/30km | 3.07 s | removed | | ridge/30km | 2.78 s | kept | | missing-tile | 4.05 s (30 km) | 12 km | | whole test | 17.0 s | 6.2 s | Before this change the test was 16.1 of 101 s for the whole server package in a local `-json` run (16%). `go test -count=1 -run 'TestViewshed|TestPlanner|TestClearance|TestCoverage' .` passes; `gofmt` and `go vet` are clean. ## Not done - Not measured under `-race` and coverage, the way CI runs it. The CI time comes from the hosted run of this PR. - No equivalence case above 30 km, where the cell grows past 0.2 km. The old suite had none either; `TestViewshedCellKm` covers the formula and `BenchmarkViewshedWorkCount` the 60 km counts. - The CI job split (running `-race` in shards next to the coverage run) is a separate PR.
833 lines
27 KiB
Go
833 lines
27 KiB
Go
package main
|
|
|
|
import (
|
|
"bytes"
|
|
"context"
|
|
"errors"
|
|
"fmt"
|
|
"math"
|
|
"math/rand"
|
|
"sort"
|
|
"sync/atomic"
|
|
"testing"
|
|
)
|
|
|
|
// flatTerrainView is level ground everywhere.
|
|
type flatTerrainView struct{ elevM float64 }
|
|
|
|
func (v flatTerrainView) ElevationAt(lat, lon float64) (float64, bool) { return v.elevM, true }
|
|
|
|
// ridgeTerrainView is level ground with a north-south ridge between two
|
|
// longitudes.
|
|
type ridgeTerrainView struct {
|
|
baseM, ridgeM float64
|
|
west, east float64
|
|
}
|
|
|
|
func (v ridgeTerrainView) ElevationAt(lat, lon float64) (float64, bool) {
|
|
if lon >= v.west && lon <= v.east {
|
|
return v.baseM + v.ridgeM, true
|
|
}
|
|
return v.baseM, true
|
|
}
|
|
|
|
var viewshedTestSite = geoPoint{Lat: 30.5, Lon: -97.5}
|
|
|
|
func viewshedTestParams(rangeKm float64) viewshedParams {
|
|
return viewshedParams{
|
|
Site: viewshedTestSite, SiteM: 10, RxM: 5, RangeKm: rangeKm,
|
|
FreqMHz: 869.525, KFactor: 4.0 / 3.0,
|
|
Reach: PlannerUserReach{D50Km: defaultPlannerUserD50Km, Slope: defaultPlannerUserSlope},
|
|
}
|
|
}
|
|
|
|
// viewshedCellCenter mirrors the documented grid layout: row 0 north,
|
|
// row-major, cell centres at the middle of equal bbox divisions.
|
|
func viewshedCellCenter(g viewshedGrid, r, c int) geoPoint {
|
|
return geoPoint{
|
|
Lat: g.BBox.N - (float64(r)+0.5)*(g.BBox.N-g.BBox.S)/float64(g.Rows),
|
|
Lon: g.BBox.W + (float64(c)+0.5)*(g.BBox.E-g.BBox.W)/float64(g.Cols),
|
|
}
|
|
}
|
|
|
|
func mustViewshed(t testing.TB, v terrainView, p viewshedParams) viewshedGrid {
|
|
t.Helper()
|
|
g, err := computeViewshed(context.Background(), v, p, nil)
|
|
checkViewshedGrid(t, g, err)
|
|
return g
|
|
}
|
|
|
|
func checkViewshedGrid(t testing.TB, g viewshedGrid, err error) {
|
|
t.Helper()
|
|
if err != nil {
|
|
t.Fatalf("computeViewshed: %v", err)
|
|
}
|
|
if len(g.Cells) != g.Rows*g.Cols || g.Rows == 0 || g.Cols == 0 {
|
|
t.Fatalf("grid %dx%d with %d cells", g.Rows, g.Cols, len(g.Cells))
|
|
}
|
|
}
|
|
|
|
func TestUserReachP(t *testing.T) {
|
|
r := PlannerUserReach{D50Km: 2.7, Slope: 0.30}
|
|
if p := userReachP(2.7, r); math.Abs(p-0.5) > 1e-9 {
|
|
t.Errorf("P(2.7) = %v, want 0.5", p)
|
|
}
|
|
if p := userReachP(1.0, r); !(p > 0.95) {
|
|
t.Errorf("P(1) = %v, want > 0.95", p)
|
|
}
|
|
if p := userReachP(10, r); !(p < 0.02) {
|
|
t.Errorf("P(10) = %v, want < 0.02", p)
|
|
}
|
|
}
|
|
|
|
func TestUserReachClassBounds(t *testing.T) {
|
|
for _, tc := range []struct {
|
|
p float64
|
|
want byte
|
|
}{{0.0999, 1}, {0.10, 2}, {0.2499, 2}, {0.25, 3}, {0.50, 4}, {0.75, 5}} {
|
|
if got := userReachClass(tc.p); got != tc.want {
|
|
t.Errorf("userReachClass(%v) = %d, want %d", tc.p, got, tc.want)
|
|
}
|
|
}
|
|
}
|
|
|
|
func TestRepeaterClass(t *testing.T) {
|
|
for _, tc := range []struct {
|
|
c float64
|
|
want byte
|
|
}{
|
|
{1.5, 3}, {1, 3}, {0.6, 3}, {0, 3},
|
|
{-0.0001, 2}, {-0.2, 2},
|
|
{-0.2001, 1}, {-1, 1}, {-6, 1},
|
|
} {
|
|
if got := repeaterClass(tc.c); got != tc.want {
|
|
t.Errorf("repeaterClass(%v) = %d, want %d", tc.c, got, tc.want)
|
|
}
|
|
}
|
|
}
|
|
|
|
func TestViewshedCellKm(t *testing.T) {
|
|
if got := viewshedCellKm(10); got != 0.2 {
|
|
t.Errorf("viewshedCellKm(10) = %v, want 0.2", got)
|
|
}
|
|
if got := viewshedCellKm(100); math.Abs(got-100.0/150) > 1e-12 {
|
|
t.Errorf("viewshedCellKm(100) = %v, want %v", got, 100.0/150)
|
|
}
|
|
}
|
|
|
|
// On flat ground the Repeaters verdict depends on distance only. With the
|
|
// planner's default heights (10 m site, 5 m receiver) the first Fresnel zone
|
|
// already grazes the ground well inside 3 km, so the "clear within 3 km"
|
|
// check runs with masts high enough for it (30 m / 15 m); both cases check
|
|
// the analyzeLOS equality, the plain Users curve and monotonic classes.
|
|
func TestViewshedFlatTerrainIsPlainCurve(t *testing.T) {
|
|
for _, tc := range []struct {
|
|
name string
|
|
siteM, rxM float64
|
|
clearWithinKm float64 // 0: not asserted
|
|
}{
|
|
{"masts 30m/15m", 30, 15, 3},
|
|
{"defaults 10m/5m", 10, 5, 0},
|
|
} {
|
|
t.Run(tc.name, func(t *testing.T) {
|
|
p := viewshedTestParams(30)
|
|
p.SiteM, p.RxM = tc.siteM, tc.rxM
|
|
checkFlatViewshed(t, p, tc.clearWithinKm)
|
|
})
|
|
}
|
|
}
|
|
|
|
func checkFlatViewshed(t *testing.T, p viewshedParams, clearWithinKm float64) {
|
|
const elev = 50.0
|
|
v := flatTerrainView{elevM: elev}
|
|
g := mustViewshed(t, v, p)
|
|
if g.Rows > 305 || g.Cols > 305 {
|
|
t.Errorf("grid %dx%d exceeds ~300x300", g.Rows, g.Cols)
|
|
}
|
|
lp := losParams{FreqMHz: p.FreqMHz, KFactor: p.KFactor, AntennaAM: p.SiteM, AntennaBM: p.RxM}
|
|
type cell struct {
|
|
d float64
|
|
rep byte
|
|
}
|
|
var cells []cell
|
|
for r := 0; r < g.Rows; r++ {
|
|
for c := 0; c < g.Cols; c++ {
|
|
pt := viewshedCellCenter(g, r, c)
|
|
d := geoDistKm(p.Site, pt)
|
|
b := g.Cells[r*g.Cols+c]
|
|
if d > p.RangeKm {
|
|
continue
|
|
}
|
|
users, rep := b&0x0f, b>>4
|
|
if want := userReachClass(userReachP(d, p.Reach)); users != want {
|
|
t.Fatalf("cell (%d,%d) at %.2f km: users %d, want plain curve %d", r, c, d, users, want)
|
|
}
|
|
profile := make([]float64, planProfileSamples(d))
|
|
for i := range profile {
|
|
profile[i] = elev
|
|
}
|
|
res, ok := analyzeLOS(profile, d, lp)
|
|
if !ok {
|
|
t.Fatalf("analyzeLOS failed at %.2f km", d)
|
|
}
|
|
if want := repeaterClass(res.Clearance); rep != want {
|
|
t.Fatalf("cell (%d,%d) at %.2f km: repeaters %d, want %d (%s)", r, c, d, rep, want, res.Verdict)
|
|
}
|
|
if d <= clearWithinKm && rep != 3 {
|
|
t.Fatalf("cell (%d,%d) at %.2f km: repeaters %d, want 3 within %.0f km", r, c, d, rep, clearWithinKm)
|
|
}
|
|
cells = append(cells, cell{d, rep})
|
|
}
|
|
}
|
|
if len(cells) == 0 {
|
|
t.Fatal("no cell in range")
|
|
}
|
|
// Flat terrain: the class depends on distance only, so along every ray
|
|
// (and across all of them) it never increases with distance.
|
|
sort.Slice(cells, func(i, j int) bool { return cells[i].d < cells[j].d })
|
|
for i := 1; i < len(cells); i++ {
|
|
if cells[i].rep > cells[i-1].rep {
|
|
t.Fatalf("repeaters class rises from %d at %.3f km to %d at %.3f km",
|
|
cells[i-1].rep, cells[i-1].d, cells[i].rep, cells[i].d)
|
|
}
|
|
}
|
|
// First distance at which each class appears, for the report.
|
|
first := map[byte]float64{}
|
|
for _, c := range cells {
|
|
if _, seen := first[c.rep]; !seen {
|
|
first[c.rep] = c.d
|
|
}
|
|
}
|
|
t.Logf("site %.0f m / rx %.0f m: repeaters class first seen at km %v (4 clear, 3 clear60, 2 marginal, 1 blocked)",
|
|
p.SiteM, p.RxM, first)
|
|
|
|
// R2: where earth curvature alone puts the handheld path into deep
|
|
// shadow on flat terrain, up to the largest range the planner offers.
|
|
e := newPlanLinkEval(context.Background(), v, p.FreqMHz, p.KFactor)
|
|
for d := 0.1; d <= defaultPlannerMaxLegKm; d += 0.1 {
|
|
pt := geoPoint{Lat: p.Site.Lat, Lon: p.Site.Lon + d/(plannerKmPerDeg*math.Cos(p.Site.Lat*math.Pi/180))}
|
|
dd := geoDistKm(p.Site, pt)
|
|
if c, _ := e.clearance(p.Site, pt, dd, p.SiteM, viewshedUserRxM, math.Inf(-1)); c < viewshedShadowClearance {
|
|
t.Logf("site %.0f m: users-layer curvature shadow starts at %.1f km (plain curve class there %d)",
|
|
p.SiteM, dd, userReachClass(userReachP(dd, p.Reach)))
|
|
return
|
|
}
|
|
}
|
|
t.Logf("site %.0f m: no users-layer curvature shadow within %.0f km", p.SiteM, defaultPlannerMaxLegKm)
|
|
}
|
|
|
|
func TestViewshedRidgeShadow(t *testing.T) {
|
|
p := viewshedTestParams(30)
|
|
// A wider handheld reach so the curve is still high 10 km out and the
|
|
// shadow drop is visible above the class-1 floor.
|
|
p.Reach = PlannerUserReach{D50Km: 20, Slope: 0.30}
|
|
cosLat := math.Cos(p.Site.Lat * math.Pi / 180)
|
|
kmToLon := func(km float64) float64 { return km / (plannerKmPerDeg * cosLat) }
|
|
ridge := ridgeTerrainView{
|
|
baseM: 50, ridgeM: 300,
|
|
west: p.Site.Lon + kmToLon(4.8), east: p.Site.Lon + kmToLon(5.2),
|
|
}
|
|
flat := mustViewshed(t, flatTerrainView{elevM: 50}, p)
|
|
g := mustViewshed(t, ridge, p)
|
|
if flat.Rows != g.Rows || flat.Cols != g.Cols {
|
|
t.Fatalf("grid shape differs: %dx%d vs %dx%d", flat.Rows, flat.Cols, g.Rows, g.Cols)
|
|
}
|
|
east, west := 0, 0
|
|
for r := 0; r < g.Rows; r++ {
|
|
for c := 0; c < g.Cols; c++ {
|
|
pt := viewshedCellCenter(g, r, c)
|
|
if math.Abs(pt.Lat-p.Site.Lat)*plannerKmPerDeg > 1 {
|
|
continue
|
|
}
|
|
dx := (pt.Lon - p.Site.Lon) * plannerKmPerDeg * cosLat
|
|
i := r*g.Cols + c
|
|
fu, gu, gr := flat.Cells[i]&0x0f, g.Cells[i]&0x0f, g.Cells[i]>>4
|
|
switch {
|
|
case math.Abs(dx-10) <= 0.5:
|
|
east++
|
|
if gr != 1 {
|
|
t.Errorf("east cell (%d,%d): repeaters %d, want 1 (blocked)", r, c, gr)
|
|
}
|
|
if fu < 1+viewshedShadowDrop {
|
|
t.Fatalf("east cell (%d,%d): flat users %d leaves no room for the drop", r, c, fu)
|
|
}
|
|
if gu > fu-viewshedShadowDrop {
|
|
t.Errorf("east cell (%d,%d): users %d, want at most %d (flat %d)", r, c, gu, fu-viewshedShadowDrop, fu)
|
|
}
|
|
case math.Abs(dx+10) <= 0.5:
|
|
west++
|
|
if g.Cells[i] != flat.Cells[i] {
|
|
t.Errorf("west cell (%d,%d): %#x, want flat %#x", r, c, g.Cells[i], flat.Cells[i])
|
|
}
|
|
}
|
|
}
|
|
}
|
|
if east == 0 || west == 0 {
|
|
t.Fatalf("checked %d east and %d west cells", east, west)
|
|
}
|
|
}
|
|
|
|
// Runs at the default heights and at mast heights so every verdict class
|
|
// is in the sample: 200 cells each.
|
|
func TestViewshedAgreesWithAnalyzeLOS(t *testing.T) {
|
|
verdicts := map[string]int{}
|
|
for _, h := range [][2]float64{{10, 5}, {30, 15}} {
|
|
p := viewshedTestParams(30)
|
|
p.SiteM, p.RxM = h[0], h[1]
|
|
checkViewshedAgainstLOS(t, p, verdicts)
|
|
}
|
|
if len(verdicts) < 4 {
|
|
t.Errorf("sample covers only verdicts %v; want all four", verdicts)
|
|
}
|
|
t.Logf("verdicts sampled: %v", verdicts)
|
|
}
|
|
|
|
func checkViewshedAgainstLOS(t *testing.T, p viewshedParams, verdicts map[string]int) {
|
|
v := fakeTerrainView{bb: plannerExpandBBox(viewshedBBox(p.Site, p.RangeKm), 1)}
|
|
g := mustViewshed(t, v, p)
|
|
lp := losParams{FreqMHz: p.FreqMHz, KFactor: p.KFactor, AntennaAM: p.SiteM, AntennaBM: p.RxM}
|
|
rng := rand.New(rand.NewSource(2391))
|
|
for checked := 0; checked < 200; {
|
|
r, c := rng.Intn(g.Rows), rng.Intn(g.Cols)
|
|
pt := viewshedCellCenter(g, r, c)
|
|
d := geoDistKm(p.Site, pt)
|
|
if d > p.RangeKm {
|
|
continue
|
|
}
|
|
checked++
|
|
prof, ok := sampleTerrainProfile(v, p.Site, pt, planProfileSamples(d))
|
|
if !ok {
|
|
t.Fatalf("no profile to cell (%d,%d)", r, c)
|
|
}
|
|
res, ok := analyzeLOS(prof, d, lp)
|
|
if !ok {
|
|
t.Fatalf("analyzeLOS failed for cell (%d,%d)", r, c)
|
|
}
|
|
verdicts[res.Verdict]++
|
|
if got, want := g.Cells[r*g.Cols+c]>>4, repeaterClass(res.Clearance); got != want {
|
|
t.Errorf("cell (%d,%d) at %.2f km: repeaters %d, analyzeLOS %d (%s, clearance %.4f)",
|
|
r, c, d, got, want, res.Verdict, res.Clearance)
|
|
}
|
|
}
|
|
}
|
|
|
|
func TestViewshedMissingTerrainIsNoData(t *testing.T) {
|
|
p := viewshedTestParams(30)
|
|
p.Site = geoPoint{Lat: 30.9, Lon: -97.5}
|
|
bb := plannerExpandBBox(viewshedBBox(p.Site, p.RangeKm), 1)
|
|
v := fakeTerrainView{bb: bb, missing: map[[2]int]bool{{31, -98}: true}}
|
|
g := mustViewshed(t, v, p)
|
|
missing, classed := 0, 0
|
|
for r := 0; r < g.Rows; r++ {
|
|
for c := 0; c < g.Cols; c++ {
|
|
pt := viewshedCellCenter(g, r, c)
|
|
b := g.Cells[r*g.Cols+c]
|
|
if v.MissingAt(pt.Lat, pt.Lon) {
|
|
missing++
|
|
if b != 0 {
|
|
t.Fatalf("cell (%d,%d) on missing terrain has %#x, want 0", r, c, b)
|
|
}
|
|
} else if b != 0 {
|
|
classed++
|
|
}
|
|
}
|
|
}
|
|
if missing == 0 || classed == 0 {
|
|
t.Fatalf("%d cells on missing terrain, %d classed elsewhere", missing, classed)
|
|
}
|
|
}
|
|
|
|
func TestViewshedMissingSiteIsAllNoData(t *testing.T) {
|
|
// A missing site still allocates the largest offered grid.
|
|
p := viewshedTestParams(60)
|
|
v := fakeTerrainView{bb: plannerExpandBBox(viewshedBBox(p.Site, p.RangeKm), 1),
|
|
missing: map[[2]int]bool{{30, -98}: true}}
|
|
g := mustViewshed(t, v, p)
|
|
if g.Rows > 305 || g.Cols > 305 {
|
|
t.Fatalf("60 km grid %dx%d exceeds ~300x300", g.Rows, g.Cols)
|
|
}
|
|
for i, b := range g.Cells {
|
|
if b != 0 {
|
|
t.Fatalf("cell %d = %#x with the site on missing terrain", i, b)
|
|
}
|
|
}
|
|
}
|
|
|
|
func TestViewshedOutsideRangeIsNoData(t *testing.T) {
|
|
p := viewshedTestParams(20)
|
|
g := mustViewshed(t, flatTerrainView{elevM: 50}, p)
|
|
for _, rc := range [][2]int{{0, 0}, {0, g.Cols - 1}, {g.Rows - 1, 0}, {g.Rows - 1, g.Cols - 1}} {
|
|
if b := g.Cells[rc[0]*g.Cols+rc[1]]; b != 0 {
|
|
t.Errorf("corner cell %v = %#x, want 0", rc, b)
|
|
}
|
|
}
|
|
mid := g.Cells[(g.Rows/2)*g.Cols+g.Cols/2]
|
|
if mid&0x0f == 0 || mid>>4 == 0 {
|
|
t.Errorf("centre cell = %#x, want both layers classed", mid)
|
|
}
|
|
}
|
|
|
|
func TestViewshedHonoursContext(t *testing.T) {
|
|
ctx, cancel := context.WithCancel(context.Background())
|
|
cancel()
|
|
_, err := computeViewshed(ctx, flatTerrainView{elevM: 50}, viewshedTestParams(30), nil)
|
|
if !errors.Is(err, context.Canceled) {
|
|
t.Fatalf("err = %v, want context.Canceled", err)
|
|
}
|
|
}
|
|
|
|
func TestViewshedReportsProgress(t *testing.T) {
|
|
var last float64
|
|
calls := 0
|
|
_, err := computeViewshed(context.Background(), flatTerrainView{elevM: 50}, viewshedTestParams(10),
|
|
func(f float64) {
|
|
if f < last {
|
|
t.Errorf("progress went back from %v to %v", last, f)
|
|
}
|
|
last = f
|
|
calls++
|
|
})
|
|
if err != nil {
|
|
t.Fatal(err)
|
|
}
|
|
if calls == 0 || last != 1 {
|
|
t.Errorf("progress: %d calls, last %v; want calls ending at 1", calls, last)
|
|
}
|
|
}
|
|
|
|
// computeViewshedRef is the original single-goroutine, two-walk
|
|
// computeViewshed, kept as the oracle the optimised one must match byte for
|
|
// byte. computeViewshed profiles site→cell for every cell in range: two
|
|
// clearance walks per cell (receiver at RxM for Repeaters, at
|
|
// viewshedUserRxM for the Users shadow test). progress gets the fraction of
|
|
// rows done. Errors: ctx.Err() only.
|
|
func computeViewshedRef(ctx context.Context, v terrainView, p viewshedParams, progress func(float64)) (viewshedGrid, error) {
|
|
cellKm := viewshedCellKm(p.RangeKm)
|
|
bb := viewshedBBox(p.Site, p.RangeKm)
|
|
cosLat := math.Cos(p.Site.Lat * math.Pi / 180)
|
|
rows := max(1, int(math.Ceil((bb.N-bb.S)*plannerKmPerDeg/cellKm)))
|
|
cols := max(1, int(math.Ceil((bb.E-bb.W)*plannerKmPerDeg*cosLat/cellKm)))
|
|
g := viewshedGrid{BBox: bb, Rows: rows, Cols: cols, CellKm: cellKm, Cells: make([]byte, rows*cols)}
|
|
if err := ctx.Err(); err != nil {
|
|
return viewshedGrid{}, err
|
|
}
|
|
if _, ok := v.ElevationAt(p.Site.Lat, p.Site.Lon); !ok {
|
|
return g, nil // no terrain at the site: every cell is no data
|
|
}
|
|
e := newPlanLinkEval(ctx, v, p.FreqMHz, p.KFactor)
|
|
dLat := (bb.N - bb.S) / float64(rows)
|
|
dLon := (bb.E - bb.W) / float64(cols)
|
|
for r := 0; r < rows; r++ {
|
|
lat := bb.N - (float64(r)+0.5)*dLat
|
|
for c := 0; c < cols; c++ {
|
|
cell := geoPoint{Lat: lat, Lon: bb.W + (float64(c)+0.5)*dLon}
|
|
d := geoDistKm(p.Site, cell)
|
|
if d > p.RangeKm {
|
|
continue
|
|
}
|
|
cr, ok := e.clearance(p.Site, cell, d, p.SiteM, p.RxM, math.Inf(-1))
|
|
if !ok {
|
|
continue // no terrain on the path (or ctx cancelled: checked below)
|
|
}
|
|
users := userReachClass(userReachP(d, p.Reach))
|
|
// Same path as above, so terrain is present; the walk stops at
|
|
// the first sample below the shadow threshold.
|
|
if cu, ok := e.clearance(p.Site, cell, d, p.SiteM, viewshedUserRxM, viewshedShadowClearance); !ok && cu < viewshedShadowClearance {
|
|
if users > viewshedShadowDrop {
|
|
users -= viewshedShadowDrop
|
|
} else {
|
|
users = 1
|
|
}
|
|
}
|
|
g.Cells[r*cols+c] = users | repeaterClass(cr)<<4
|
|
}
|
|
if e.err != nil {
|
|
return viewshedGrid{}, e.err
|
|
}
|
|
if progress != nil {
|
|
progress(float64(r+1) / float64(rows))
|
|
}
|
|
}
|
|
if err := ctx.Err(); err != nil {
|
|
return viewshedGrid{}, err
|
|
}
|
|
return g, nil
|
|
}
|
|
|
|
// roughSRTMView is a real srtmView (bilinear lookups over int16 tiles) over
|
|
// bb (relief scaled by scale: 1 rough, 0.1 gentle), with deterministic hills and a few sharp ridges, so the paths see
|
|
// shadow, partial blockage and clear ground.
|
|
func roughSRTMView(bb geoBBox, scale float64) *srtmView {
|
|
sp, _ := srtmSpanOf(bb)
|
|
v := &srtmView{span: sp, grids: make([][]int16, sp.count())}
|
|
for i := range v.grids {
|
|
k := sp.key(i)
|
|
g := make([]int16, srtmSide*srtmSide)
|
|
for r := 0; r < srtmSide; r++ {
|
|
lat := float64(k.lat+1) - float64(r)/srtmCells
|
|
for c := 0; c < srtmSide; c++ {
|
|
lon := float64(k.lon) + float64(c)/srtmCells
|
|
e := 300 + scale*(120*math.Sin(lat*37)*math.Cos(lon*29)+60*math.Sin(lat*151+lon*113))
|
|
if math.Mod(lon*40, 1) < 0.08 { // N-S ridges ~2 km wide every ~2.5 km
|
|
e += 90 * scale
|
|
}
|
|
g[r*srtmSide+c] = int16(e)
|
|
}
|
|
}
|
|
v.grids[i] = g
|
|
}
|
|
return v
|
|
}
|
|
|
|
// viewshedEquivalenceCases are the terrains and parameters the optimised
|
|
// code is compared with computeViewshedRef on.
|
|
func viewshedEquivalenceCases() []struct {
|
|
name string
|
|
v terrainView
|
|
p viewshedParams
|
|
} {
|
|
var cs []struct {
|
|
name string
|
|
v terrainView
|
|
p viewshedParams
|
|
}
|
|
sites := []geoPoint{viewshedTestSite, {Lat: 45.2, Lon: 7.1}, {Lat: -33.9, Lon: 151.2}}
|
|
for _, site := range sites {
|
|
for _, rng := range []float64{3, 12, 30} {
|
|
if rng == 30 && site != viewshedTestSite {
|
|
continue // the slow case once is enough
|
|
}
|
|
p := viewshedTestParams(rng)
|
|
p.Site = site
|
|
bb := plannerExpandBBox(viewshedBBox(site, rng), 1)
|
|
ridge := ridgeTerrainView{baseM: 100, ridgeM: 80, west: site.Lon + 0.05, east: site.Lon + 0.07}
|
|
// The full-size 30 km grid costs about 3 s per terrain. Its cell
|
|
// size is the same 0.2 km floor as 12 km; what it adds is longer
|
|
// rays with more samples per profile. The ridge terrain covers
|
|
// those, with level ground west of the ridge and shadow east of it.
|
|
if rng != 30 {
|
|
cs = append(cs,
|
|
struct {
|
|
name string
|
|
v terrainView
|
|
p viewshedParams
|
|
}{fmt.Sprintf("fake/%.1f,%.1f/%gkm", site.Lat, site.Lon, rng), fakeTerrainView{bb: bb}, p},
|
|
struct {
|
|
name string
|
|
v terrainView
|
|
p viewshedParams
|
|
}{fmt.Sprintf("flat/%.1f,%.1f/%gkm", site.Lat, site.Lon, rng), flatTerrainView{elevM: 50}, p},
|
|
)
|
|
}
|
|
cs = append(cs, struct {
|
|
name string
|
|
v terrainView
|
|
p viewshedParams
|
|
}{fmt.Sprintf("ridge/%.1f,%.1f/%gkm", site.Lat, site.Lon, rng), ridgeTerrainView{ridge.baseM, ridge.ridgeM, ridge.west, ridge.east}, p})
|
|
}
|
|
}
|
|
return cs
|
|
}
|
|
|
|
func TestViewshedMatchesReference(t *testing.T) {
|
|
check := func(name string, v terrainView, p viewshedParams) {
|
|
want, err := computeViewshedRef(context.Background(), v, p, nil)
|
|
if err != nil {
|
|
t.Fatalf("%s: ref: %v", name, err)
|
|
}
|
|
for _, workers := range []int{1, 3, 7} {
|
|
got, err := computeViewshedN(context.Background(), v, p, workers, nil)
|
|
if err != nil {
|
|
t.Fatalf("%s: workers=%d: %v", name, workers, err)
|
|
}
|
|
if got.Rows != want.Rows || got.Cols != want.Cols || got.BBox != want.BBox || got.CellKm != want.CellKm ||
|
|
!bytes.Equal(got.Cells, want.Cells) {
|
|
diff := 0
|
|
for i := range want.Cells {
|
|
if got.Cells[i] != want.Cells[i] {
|
|
diff++
|
|
}
|
|
}
|
|
t.Fatalf("%s: workers=%d: %d of %d cells differ from the reference", name, workers, diff, len(want.Cells))
|
|
}
|
|
}
|
|
}
|
|
for _, c := range viewshedEquivalenceCases() {
|
|
check(c.name, c.v, c.p)
|
|
}
|
|
// Real tile lookups with ridges and shadow, and a tile without data.
|
|
for _, rng := range []float64{8, 20} {
|
|
p := viewshedTestParams(rng)
|
|
bb := viewshedBBox(p.Site, rng)
|
|
v := roughSRTMView(bb, 1)
|
|
check(fmt.Sprintf("srtm/%gkm", rng), v, p)
|
|
holed := &srtmView{span: v.span, grids: append([][]int16(nil), v.grids...)}
|
|
holed.grids[0] = nil
|
|
check(fmt.Sprintf("srtm-hole/%gkm", rng), holed, p)
|
|
}
|
|
mv, mp := viewshedMissingTileCase()
|
|
check("missing-tile", mv, mp)
|
|
}
|
|
|
|
// viewshedMissingTileCase puts the site 0.05 degrees (about 5.6 km) south of a
|
|
// missing SRTM tile, so the 12 km range reaches into it.
|
|
func viewshedMissingTileCase() (fakeTerrainView, viewshedParams) {
|
|
p := viewshedTestParams(12)
|
|
p.Site = geoPoint{Lat: 30.95, Lon: -97.5}
|
|
return fakeTerrainView{bb: plannerExpandBBox(viewshedBBox(p.Site, p.RangeKm), 1),
|
|
missing: map[[2]int]bool{{31, -98}: true}}, p
|
|
}
|
|
|
|
// TestViewshedMissingTileCaseReachesTheTile guards the missing-tile case of
|
|
// the equivalence test: it only checks missing terrain if cells in range
|
|
// have their endpoint on the missing tile and are NoData, while cells south
|
|
// of it are not.
|
|
func TestViewshedMissingTileCaseReachesTheTile(t *testing.T) {
|
|
v, p := viewshedMissingTileCase()
|
|
if missing, total := v.MissingTiles(); missing != 1 || total < 2 {
|
|
t.Fatalf("MissingTiles() = %d of %d, want 1 of at least 2", missing, total)
|
|
}
|
|
g := mustViewshed(t, v, p)
|
|
var northNoData, northData, southData int
|
|
for r := 0; r < g.Rows; r++ {
|
|
for c := 0; c < g.Cols; c++ {
|
|
pt := viewshedCellCenter(g, r, c)
|
|
if geoDistKm(p.Site, pt) > p.RangeKm*0.9 {
|
|
continue
|
|
}
|
|
b := g.Cells[r*g.Cols+c]
|
|
switch {
|
|
case pt.Lat > 31.001 && b == 0:
|
|
northNoData++
|
|
case pt.Lat > 31.001:
|
|
northData++
|
|
case pt.Lat < 30.999 && b != 0:
|
|
southData++
|
|
}
|
|
}
|
|
}
|
|
if northNoData == 0 || northData != 0 || southData == 0 {
|
|
t.Fatalf("north of the tile edge %d NoData / %d with data, south %d with data; want >0 / 0 / >0",
|
|
northNoData, northData, southData)
|
|
}
|
|
}
|
|
|
|
// TestViewshedRoughTerrainHasEveryClass guards the equivalence test above:
|
|
// it is only worth something if the terrain exercises shadow and every
|
|
// Repeaters class.
|
|
func TestViewshedRoughTerrainHasEveryClass(t *testing.T) {
|
|
p := viewshedTestParams(25)
|
|
g := mustViewshed(t, roughSRTMView(viewshedBBox(p.Site, p.RangeKm), 1), p)
|
|
var rep [4]int
|
|
for _, b := range g.Cells {
|
|
rep[b>>4]++
|
|
}
|
|
if rep[1] == 0 || rep[2] == 0 || rep[3] == 0 {
|
|
t.Fatalf("repeater class counts %v: terrain too tame", rep)
|
|
}
|
|
}
|
|
|
|
// TestClearancePairMatchesClearance pins clearancePair to the two
|
|
// e.clearance calls it replaces, sample for sample, on rough terrain.
|
|
func TestClearancePairMatchesClearance(t *testing.T) {
|
|
p := viewshedTestParams(40)
|
|
v := roughSRTMView(viewshedBBox(p.Site, p.RangeKm), 1)
|
|
rng := rand.New(rand.NewSource(1))
|
|
e := newPlanLinkEval(context.Background(), v, p.FreqMHz, p.KFactor)
|
|
ref := newPlanLinkEval(context.Background(), v, p.FreqMHz, p.KFactor)
|
|
for i := 0; i < 400; i++ {
|
|
b := geoPoint{Lat: p.Site.Lat + (rng.Float64()-0.5)*0.6, Lon: p.Site.Lon + (rng.Float64()-0.5)*0.6}
|
|
d := geoDistKm(p.Site, b)
|
|
cr, ok, shadow := e.clearancePair(p.Site, b, d, p.SiteM, p.RxM, viewshedUserRxM, viewshedShadowClearance)
|
|
wantCr, wantOK := ref.clearance(p.Site, b, d, p.SiteM, p.RxM, math.Inf(-1))
|
|
cu, uok := ref.clearance(p.Site, b, d, p.SiteM, viewshedUserRxM, viewshedShadowClearance)
|
|
wantShadow := !uok && cu < viewshedShadowClearance
|
|
if ok != wantOK || (ok && math.Float64bits(cr) != math.Float64bits(wantCr)) || shadow != wantShadow {
|
|
t.Fatalf("b=%v d=%.2f: pair (%v,%v,%v) want (%v,%v,%v)", b, d, cr, ok, shadow, wantCr, wantOK, wantShadow)
|
|
}
|
|
}
|
|
}
|
|
|
|
func TestViewshedParallelProgress(t *testing.T) {
|
|
for _, workers := range []int{2, 4} {
|
|
var last float64
|
|
calls := 0
|
|
_, err := computeViewshedN(context.Background(), flatTerrainView{elevM: 50}, viewshedTestParams(10), workers,
|
|
func(f float64) { // would race under -race if not serialised
|
|
if f < last {
|
|
t.Errorf("workers=%d: progress went back from %v to %v", workers, last, f)
|
|
}
|
|
last = f
|
|
calls++
|
|
})
|
|
if err != nil {
|
|
t.Fatal(err)
|
|
}
|
|
if calls == 0 || last != 1 {
|
|
t.Errorf("workers=%d: %d calls, last %v; want calls ending at exactly 1", workers, calls, last)
|
|
}
|
|
}
|
|
}
|
|
|
|
// cancelAfterView cancels its context after n lookups.
|
|
type cancelAfterView struct {
|
|
terrainView
|
|
n int64
|
|
seen atomic.Int64
|
|
cancel context.CancelFunc
|
|
}
|
|
|
|
func (v *cancelAfterView) ElevationAt(lat, lon float64) (float64, bool) {
|
|
if v.seen.Add(1) == v.n {
|
|
v.cancel()
|
|
}
|
|
return v.terrainView.ElevationAt(lat, lon)
|
|
}
|
|
|
|
func TestViewshedParallelCancelsPromptly(t *testing.T) {
|
|
p := viewshedTestParams(12)
|
|
total := countingElevations(t, p)
|
|
for _, workers := range []int{1, 4} {
|
|
ctx, cancel := context.WithCancel(context.Background())
|
|
v := &cancelAfterView{terrainView: flatTerrainView{elevM: 50}, n: 1000, cancel: cancel}
|
|
_, err := computeViewshedN(ctx, v, p, workers, nil)
|
|
cancel()
|
|
if !errors.Is(err, context.Canceled) {
|
|
t.Fatalf("workers=%d: err = %v, want context.Canceled", workers, err)
|
|
}
|
|
// Each worker may finish its current 16-cell ctx window plus its row.
|
|
if got := v.seen.Load(); got > total/20 {
|
|
t.Errorf("workers=%d: %d lookups after cancel at 1000 (full run %d): not prompt", workers, got, total)
|
|
}
|
|
}
|
|
}
|
|
|
|
// A panic in a worker must surface on the caller's goroutine, where the job
|
|
// runner recovers it, not kill the process.
|
|
func TestViewshedWorkerPanicReachesCaller(t *testing.T) {
|
|
// The site lookup in computeViewshedN is on the caller; let it pass.
|
|
v := &panicAfterView{terrainView: flatTerrainView{elevM: 50}, after: 1}
|
|
defer func() {
|
|
if r := recover(); r != "boom" {
|
|
t.Fatalf("recovered %v, want boom", r)
|
|
}
|
|
}()
|
|
_, _ = computeViewshedN(context.Background(), v, viewshedTestParams(10), 4, nil)
|
|
t.Fatal("no panic")
|
|
}
|
|
|
|
type panicAfterView struct {
|
|
terrainView
|
|
after int64
|
|
seen atomic.Int64
|
|
}
|
|
|
|
func (v *panicAfterView) ElevationAt(lat, lon float64) (float64, bool) {
|
|
if v.seen.Add(1) > v.after {
|
|
panic("boom")
|
|
}
|
|
return v.terrainView.ElevationAt(lat, lon)
|
|
}
|
|
|
|
// countView counts ElevationAt calls.
|
|
type countView struct {
|
|
terrainView
|
|
n atomic.Int64
|
|
}
|
|
|
|
func (v *countView) ElevationAt(lat, lon float64) (float64, bool) {
|
|
v.n.Add(1)
|
|
return v.terrainView.ElevationAt(lat, lon)
|
|
}
|
|
|
|
func countingElevations(t testing.TB, p viewshedParams) int64 {
|
|
v := &countView{terrainView: flatTerrainView{elevM: 50}}
|
|
if _, err := computeViewshedRef(context.Background(), v, p, nil); err != nil {
|
|
t.Fatal(err)
|
|
}
|
|
return v.n.Load()
|
|
}
|
|
|
|
func measureViewshedWork(t testing.TB, rangeKm float64) (reference, singlePass int64) {
|
|
t.Helper()
|
|
p := viewshedTestParams(rangeKm)
|
|
v := &countView{terrainView: flatTerrainView{elevM: 50}}
|
|
g, err := computeViewshedN(context.Background(), v, p, 1, nil)
|
|
checkViewshedGrid(t, g, err)
|
|
cells := 0
|
|
for _, b := range g.Cells {
|
|
if b != 0 {
|
|
cells++
|
|
}
|
|
}
|
|
if cells == 0 {
|
|
t.Fatal("flat terrain produced no cells in range")
|
|
}
|
|
reference, singlePass = countingElevations(t, p), v.n.Load()
|
|
t.Logf("%gkm: grid %dx%d, cell %.3f km, %d cells in range; ElevationAt calls: reference %d, single pass %d",
|
|
rangeKm, g.Rows, g.Cols, g.CellKm, cells, reference, singlePass)
|
|
return reference, singlePass
|
|
}
|
|
|
|
func TestViewshedWorkCount(t *testing.T) {
|
|
reference, singlePass := measureViewshedWork(t, 5)
|
|
// Both implementations look up the site once before walking the cells.
|
|
if singlePass <= 1 || singlePass-1 > (reference-1)/2 {
|
|
t.Fatalf("elevation lookups: reference %d, single pass %d; want at most half the path lookups", reference, singlePass)
|
|
}
|
|
}
|
|
|
|
// Run the full diagnostic with go test -run '^$' -bench '^BenchmarkViewshedWorkCount$' -benchtime=1x.
|
|
func BenchmarkViewshedWorkCount(b *testing.B) {
|
|
for _, rangeKm := range []float64{30, 60} {
|
|
b.Run(fmt.Sprintf("%gkm", rangeKm), func(b *testing.B) {
|
|
for i := 0; i < b.N; i++ {
|
|
reference, singlePass := measureViewshedWork(b, rangeKm)
|
|
b.ReportMetric(float64(reference), "reference-lookups/op")
|
|
b.ReportMetric(float64(singlePass), "single-pass-lookups/op")
|
|
}
|
|
})
|
|
}
|
|
}
|
|
|
|
func benchmarkViewshed(b *testing.B, rangeKm float64, relief float64, workers int) {
|
|
p := viewshedTestParams(rangeKm)
|
|
var v terrainView = fakeTerrainView{bb: plannerExpandBBox(viewshedBBox(p.Site, p.RangeKm), 1)}
|
|
if relief > 0 {
|
|
v = roughSRTMView(viewshedBBox(p.Site, p.RangeKm), relief)
|
|
}
|
|
b.ResetTimer()
|
|
for i := 0; i < b.N; i++ {
|
|
var err error
|
|
if workers == 0 {
|
|
_, err = computeViewshedRef(context.Background(), v, p, nil)
|
|
} else {
|
|
_, err = computeViewshedN(context.Background(), v, p, workers, nil)
|
|
}
|
|
if err != nil {
|
|
b.Fatal(err)
|
|
}
|
|
}
|
|
}
|
|
|
|
func BenchmarkViewshed30km(b *testing.B) { benchmarkViewshed(b, 30, 0, viewshedWorkers()) }
|
|
|
|
// BenchmarkViewshedMaxLeg: the largest range the planner offers (60 km).
|
|
func BenchmarkViewshedMaxLeg(b *testing.B) { benchmarkViewshed(b, 60, 0, viewshedWorkers()) }
|
|
|
|
// BenchmarkViewshedVariants: workers=0 is the reference implementation.
|
|
// fake is the plane fakeTerrainView; srtm and srtm-gentle are real tile
|
|
// lookups over rough and gentle relief.
|
|
func BenchmarkViewshedVariants(b *testing.B) {
|
|
for _, rangeKm := range []float64{30, 60} {
|
|
for _, terrain := range []struct {
|
|
name string
|
|
relief float64
|
|
}{{"fake", 0}, {"srtm", 1}, {"srtm-gentle", 0.1}} {
|
|
for _, w := range []int{0, 1, 2, 4, 6} {
|
|
b.Run(fmt.Sprintf("%gkm/%s/w%d", rangeKm, terrain.name, w), func(b *testing.B) { benchmarkViewshed(b, rangeKm, terrain.relief, w) })
|
|
}
|
|
}
|
|
}
|
|
}
|