25:["$","title",null,{"children":"CoMapeo Area Metrics: Extent | Gregor MacLennan | Observable"}] 4c:T551,# CoMapeo Area Metrics: Extent The "extent" of CoMapeo mapping and monitoring data is an estimate of the territory a project team works in. In contrast, the [footprint](./footprint) counts only the ground within a short distance of each record; the extent also fills the gaps between records at a site, so it is the upper figure for "area mapped and monitored by CoMapeo". It must not bridge between separate sites, and it must not be inflated by stray records such as a training day outside the territory or a bad GPS fix. The estimate has five steps, each explained with its code below: 1. **Grow.** Every observation and track is grown by half the _linking distance_. 2. **Clusters.** Each separate piece of the grown shape is a cluster. 3. **Encircled ground.** Ground the grown shape surrounds on all sides is filled in, up to a chosen size. 4. **Shrink.** The shape is shrunk back by half the linking distance less the _margin_. Ground survives where grown records overlapped enough to fill the gap between them. 5. **Keep or drop.** A cluster far from the largest is dropped as stray unless the team recorded there on at least three separate days and its records span more than a kilometre. The extent is the area of the kept clusters. The data comes from the randomly generated [scenarios](./scenarios). Pick one to see its extent on the map below. 4d:T917,const keptStyle = { shape: "area", fill: PALETTE.keptHull, "fill-opacity": 0.18, stroke: PALETTE.keptHull, "stroke-width": 1.4 }; const droppedStyle = { shape: "area", fill: "none", stroke: PALETTE.droppedHull, "stroke-width": 1.4, "stroke-dasharray": "2 4" }; const grownStyle = { shape: "area", fill: "none", stroke: PALETTE.droppedHull, "stroke-width": 0.8, "stroke-dasharray": "4 3" }; view(scenarioMap({ toMetres: extent.projection.toMetres, xyRecords: extent.xyRecords, scenario, title: `${scenario.name}. Drag to pan, wheel to zoom, double-click to fit.`, overlay: drawClusters, legend: [ {...keptStyle, label: "kept cluster extent"}, {...droppedStyle, label: "dropped cluster"}, ...(showGrown ? [{...grownStyle, label: "grown shape, before shrinking"}] : []) ] })) function drawClusters({view, X, Y, k}) { const pathOf = (segments) => segments .map( ([[ax, ay], [bx, by]]) => `M${X(ax).toFixed(1)},${Y(ay).toFixed(1)}L${X(bx).toFixed(1)},${Y(by).toFixed(1)}` ) .join(""); if (showGrown) applyStyle(view.append("path"), grownStyle).attr( "d", pathOf(extent.grownOutline) ); for (const cluster of extent.clusters) { const style = cluster.kept ? keptStyle : droppedStyle; if (cluster.kept) { view .append("g") .attr("fill", style.fill) .attr("fill-opacity", style["fill-opacity"]) .selectAll("rect") .data(cluster.runs) .join("rect") .attr("x", (run) => X(run.x1)) .attr("y", (run) => Y(run.y2)) .attr("width", (run) => (run.x2 - run.x1) * k) .attr("height", (run) => (run.y2 - run.y1) * k); } applyStyle(view.append("path"), {...style, fill: "none"}).attr( "d", pathOf(cluster.outline) ); view .append("text") .attr("x", X(cluster.centroid[0]) + 6) .attr("y", Y(cluster.centroid[1]) - 6) .attr("font-size", 11) .attr("font-family", "var(--sans-serif)") .attr("fill", style.stroke) .attr("stroke", PAPER) .attr("stroke-width", 3) .attr("paint-order", "stroke") .text( cluster.kept ? `cluster ${cluster.id}` : `cluster ${cluster.id} dropped: ${cluster.reason}` ); } } 4e:T491,const ringAt = ([cx, cy], radius, count) => d3.range(count).map((i) => { const angle = (i / count) * 2 * Math.PI; return [cx + radius * Math.cos(angle), cy + radius * Math.sin(angle)]; }); const arms = [0.45, -0.45].flatMap((bend) => d3.range(8).map((i) => [2.6 + i * 0.45, bend * i * 0.45]) ); const figurePoints = [ ...ringAt([-2.4, 0], 0.4, 8), ...ringAt([0, 0], 1, 12), ...arms ]; const figureRecords = figurePoints.map((xy) => ({kind: "point", xy: [xy]})); const figureOptions = {linkM: 1.5, cellSize: 0.02, strayKm: Infinity}; function panel(title, runs) { return Plot.plot({ width: Math.min(width, 960), aspectRatio: 1, margin: 10, inset: 16, x: {axis: null}, y: {axis: null}, marks: [ Plot.frame({stroke: "var(--theme-foreground-faintest)"}), Plot.rect(runs, { x1: "x1", x2: "x2", y1: "y1", y2: "y2", fill: PALETTE.keptHull, fillOpacity: 0.35 }), Plot.dot(figurePoints, { x: (p) => p[0], y: (p) => p[1], fill: "currentColor" }), Plot.text([title], {frameAnchor: "top-left", dx: 6, dy: 6}) ] }); }4f:T13b6,class Raster { readonly frame: Frame; readonly cells: Cells; /** A raster of zeros on the frame, holding a typed array of the given kind. */ constructor(frame: Frame, type: new (length: number) => Cells) { this.frame = frame; this.cells = new type(frame.rows * frame.cols); } /** The grid's painted cells, on a frame sized around them with a one-cell border. */ static fromGrid(grid: Grid): Raster { const {cellSize} = grid; let [rowMin, rowMax, colMin, colMax] = [ Infinity, -Infinity, Infinity, -Infinity ]; for (const [row, words] of grid.wordsByRow) { rowMin = Math.min(rowMin, row); rowMax = Math.max(rowMax, row); for (const [word, bits] of words) { colMin = Math.min(colMin, word * WORD + lowestBit(bits)); colMax = Math.max(colMax, word * WORD + highestBit(bits)); } } if (rowMin > rowMax) [rowMin, rowMax, colMin, colMax] = [0, -1, 0, -1]; const frame = { rows: rowMax - rowMin + 3, cols: colMax - colMin + 3, cellSize, row0: rowMin - 1, col0: colMin - 1 }; const painted = new Raster(frame, Uint8Array); for (const cell of cellsOf(grid.wordsByRow)) painted.cells[painted.#indexOf(cell)] = 1; return painted; } /** The number of cells, the length of `cells`. */ get size(): number { return this.cells.length; } /** The value of the cell under a point in metres, or 0 outside the frame. */ at([x, y]: Point): number { const {rows, cols, cellSize, row0, col0} = this.frame; const [row, col] = [Math.floor(y / cellSize), Math.floor(x / cellSize)]; if (row < row0 || row >= row0 + rows || col < col0 || col >= col0 + cols) return 0; return this.cells[this.#indexOf([row, col])]; } /** The centre of the cell at an index, in metres. */ centreOf(index: number): Point { const [row, col] = this.#cellOf(index); return [ (col + 0.5) * this.frame.cellSize, (row + 0.5) * this.frame.cellSize ]; } /** The square the cell at an index covers, in metres. */ squareOf(index: number): Rect { const [row, col] = this.#cellOf(index); const {cellSize} = this.frame; return { x1: col * cellSize, y1: row * cellSize, x2: (col + 1) * cellSize, y2: (row + 1) * cellSize }; } /** Calls `visit` with the index of each cell above, below, left and right of a cell, leaving out any beyond the frame. */ forEachNeighbour(index: number, visit: (neighbour: number) => void): void { const {cols} = this.frame; const col = index % cols; if (index >= cols) visit(index - cols); if (index + cols < this.size) visit(index + cols); if (col > 0) visit(index - 1); if (col < cols - 1) visit(index + 1); } /** The first non-zero value among a cell's neighbours, or 0 if all are zero. */ neighbourValue(index: number): number { let value = 0; this.forEachNeighbour(index, (neighbour) => { if (!value) value = this.cells[neighbour]; }); return value; } /** Sets to 1 every cell within `r` metres of the line between the centres of the cells at `start` and `end`, which must lie in one row. */ markNear(start: number, end: number, r: number): void { const {cellSize} = this.frame; const [cxStart, cy] = this.centreOf(start); const [cxEnd] = this.centreOf(end); const [firstRow, lastRow] = this.#centredBetween(cy - r, cy + r); for (let row = firstRow; row <= lastRow; row++) { const y = (row + 0.5) * cellSize; const halfChord = Math.sqrt(Math.max(r * r - (y - cy) ** 2, 0)); this.#markRow(row, cxStart - halfChord, cxEnd + halfChord); } } // The first and last row or column whose centre lies between two coordinates in metres. #centredBetween(from: number, to: number): [first: number, last: number] { const {cellSize} = this.frame; return [Math.ceil(from / cellSize - 0.5), Math.floor(to / cellSize - 0.5)]; } #indexOf([row, col]: Cell): number { const {row0, col0, cols} = this.frame; return (row - row0) * cols + (col - col0); } #cellOf(index: number): Cell { const {row0, col0, cols} = this.frame; return [row0 + Math.floor(index / cols), col0 + (index % cols)]; } // The footprint grid's row painting: the cells of grid row `row` whose centres lie between `left` and `right` metres. #markRow(row: number, left: number, right: number): void { const {rows, cols, cellSize, row0, col0} = this.frame; if (row < row0 || row >= row0 + rows) return; const first = Math.max(Math.ceil(left / cellSize - 0.5), col0); const last = Math.min(Math.floor(right / cellSize - 0.5), col0 + cols - 1); if (first > last) return; const base = (row - row0) * cols - col0; this.cells.fill(1, base + first, base + last + 1); } } const lowestBit = (bits: number): number => 31 - Math.clz32(bits & -bits); const highestBit = (bits: number): number => 31 - Math.clz32(bits);50:T66b,const DAY_MS = 86400000; function measureClusters( {ids, sizes}: Regions, removed: Raster, records: XyRecord[] ): Measured[] { const {cellSize} = ids.frame; const count = sizes.length - 1; const keptCells = new Int32Array(count + 1); const sumX = new Float64Array(count + 1); const sumY = new Float64Array(count + 1); for (let index = 0; index < ids.size; index++) { const id = ids.cells[index]; if (!id) continue; const [x, y] = ids.centreOf(index); sumX[id] += x; sumY[id] += y; if (!removed.cells[index]) keptCells[id]++; } const recordCount = new Int32Array(count + 1); const days = Array.from({length: count + 1}, () => new Set()); const box = Array.from({length: count + 1}, () => [ Infinity, -Infinity, Infinity, -Infinity ]); for (const record of records) { if (record.kind === "implied") continue; const id = ids.at(record.xy[0]); if (!id) continue; recordCount[id]++; days[id].add(Math.floor((record.time ?? 0) / DAY_MS)); for (const [x, y] of record.xy) { box[id][0] = Math.min(box[id][0], x); box[id][1] = Math.max(box[id][1], x); box[id][2] = Math.min(box[id][2], y); box[id][3] = Math.max(box[id][3], y); } } return Array.from({length: count}, (_, i) => i + 1).map((id) => ({ cellCount: keptCells[id], area: keptCells[id] * cellSize * cellSize, centroid: [sumX[id] / sizes[id], sumY[id] / sizes[id]], records: recordCount[id], days: days[id].size, spanM: recordCount[id] ? Math.max(box[id][1] - box[id][0], box[id][3] - box[id][2]) : 0 })); }51:T4b3,const STRAY_MIN_DAYS = 3; const STRAY_MIN_SPAN_M = 1000; function keepOrDrop( clusters: (Measured & Traces)[], strayKm: number ): Cluster[] { const ordered = clusters.toSorted( (a, b) => b.records - a.records || a.centroid[0] - b.centroid[0] || a.centroid[1] - b.centroid[1] ); const [largest] = ordered; return ordered.map((cluster, index) => { const reason = strayReason(cluster, largest, strayKm); return {...cluster, id: index + 1, kept: !reason, reason}; }); } function strayReason( cluster: Measured, largest: Measured, strayKm: number ): string | null { if (cluster === largest) return null; const distanceKm = Math.hypot( cluster.centroid[0] - largest.centroid[0], cluster.centroid[1] - largest.centroid[1] ) / 1000; const stray = distanceKm > strayKm && (cluster.days < STRAY_MIN_DAYS || cluster.spanM < STRAY_MIN_SPAN_M); return stray ? `${distanceKm.toFixed(0)} km from the largest cluster, ${cluster.days} day${cluster.days === 1 ? "" : "s"}, ${spanText(cluster.spanM)} across` : null; } const spanText = (m: number): string => m < 1000 ? `${Math.round(m)} m` : `${(m / 1000).toFixed(1)} km`;52:T73a,function shapesForMap( {ids}: Regions, removed: Raster, measured: Measured[] ): Shapes { const none: Traces = {runs: [], outline: []}; const traces = tracesOf(ids, (index) => removed.cells[index] ? 0 : ids.cells[index] ); const grown = tracesOf(ids, (index) => (ids.cells[index] ? 1 : 0)).get(1) ?? none; return { clusters: measured.map((cluster, i) => ({ ...cluster, ...(traces.get(i + 1) ?? none) })), grown }; } function tracesOf( raster: Raster, shapeOf: (index: number) => number ): Map { const {rows, cols} = raster.frame; const traces = new Map(); for (let r = 0; r < rows; r++) { let run: Rect | null = null; let runShape = 0; for (let c = 0; c < cols; c++) { const index = r * cols + c; const shape = shapeOf(index); if (!shape) continue; const {x1, y1, x2, y2} = raster.squareOf(index); let trace = traces.get(shape); if (!trace) traces.set(shape, (trace = {runs: [], outline: []})); const {runs, outline} = trace; if (run && runShape === shape && run.x2 === x1) run.x2 = x2; else { run = {x1, y1, x2, y2}; runShape = shape; runs.push(run); } // A cell with a shape is never on the border, so all four neighbours are in the frame. if (shapeOf(index - cols) !== shape) outline.push([ [x1, y1], [x2, y1] ]); if (shapeOf(index + cols) !== shape) outline.push([ [x1, y2], [x2, y2] ]); if (shapeOf(index - 1) !== shape) outline.push([ [x1, y1], [x1, y2] ]); if (shapeOf(index + 1) !== shape) outline.push([ [x2, y1], [x2, y2] ]); } } return traces; }53:Tca8,type Point = [x: number, y: number]; /** The parts of a scenario that `buildRecords` reads. */ interface Scenario { points: {lon: number; lat: number; time: number; device: string}[]; tracks: { coords: [lon: number, lat: number][]; time: number; device: string; }[]; } interface ExtentOptions { linkingKm: number; marginM: number; holeKm2: number; cellSize: number; strayKm: number; impliedPaths: boolean; } /** A record projected into metres. */ interface XyRecord { kind: "point" | "track" | "implied"; /** One point for an observation, the vertices for a track or an implied path. */ xy: Point[]; /** Milliseconds since the epoch. */ time?: number; } /** The options in metres, as `closingExtent` takes them. */ interface ClosingOptions { linkM: number; marginM: number; cellSize: number; /** Defaults to 0: no encircled ground is filled. */ maxHoleM2?: number; strayKm: number; } /** row and a column of the grid, numbered from the origin of the projection. Its centre is at ((column + 0.5) * cellSize, (row + 0.5) * cellSize), and a cell is inside a shape when its centre is. */ type Cell = [row: number, column: number]; /** The rectangle a run's rasters cover: the grown shape with a one-cell border. Shared by every raster of the run. */ interface Frame { rows: number; cols: number; cellSize: number; /** The grid row and column of the first cell. */ row0: number; col0: number; } /** Connected regions. `ids` holds a region id per cell, 0 where the cell is in no region; ids run from 1 in the order the regions are first met scanning row by row, not by size. `sizes` is each region's size in cells by id; sizes[0] is unused, so there are sizes.length - 1 regions. */ interface Regions { ids: Raster; sizes: number[]; } /** Step 5's measurements of one cluster. */ interface Measured { /** Cells that survived the shrink. */ cellCount: number; /** cellCount times the area of a cell, in square metres. */ area: number; /** The mean of the centres of the cells carrying the cluster's id. */ centroid: Point; /** Records whose first point lies in the cluster. */ records: number; /** Separate days those records were made on. */ days: number; /** The longest side of the box around those records' vertices. */ spanM: number; } /** A rectangle for the map to fill, in metres. */ interface Run { x1: number; y1: number; x2: number; y2: number; } /** A side of a cell for the map to stroke. */ type Segment = [Point, Point]; /** The two cheaper forms of a shape that the map draws. */ interface Traces { runs: Run[]; outline: Segment[]; } /** What the map draws: each measured cluster with its traces, and the grown shape before shrinking. */ interface Shapes { clusters: (Measured & Traces)[]; grown: Traces; } /** A cluster with its shapes and the verdict. `id` is its rank by records, 1 for the largest. */ interface Cluster extends Measured, Traces { id: number; kept: boolean; /** Why it was dropped, in words; null when kept. */ reason: string | null; } interface Extent { clusters: Cluster[]; /** The area of the kept clusters, in square metres. */ area: number; grown: Traces; }54:[] 48:{"id":"d8382db063788bd7","slug":"extent","title":"CoMapeo Area Metrics: Extent","thumbnail":"5606707522d2faba4cdf17a0ffcda0df105681bbd52fd7b7be0a224ce602f444","access_level":"public","create_time":"$D2026-09-18T08:53:13.985Z","update_time":"$D2026-10-14T16:46:30.657Z","view_time":null,"first_public_time":"$D2026-10-12T11:18:12.312Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"b8f17b38290a2173","login":"gmaclennan","name":"Gregor MacLennan","avatar_url":"https://avatars-next.observableusercontent.com/63198fee32cdf9a62fee6dd70e000a4d5ed970cb33b7194192381ee674ab230d","tier":"starter_2024","bio":"","followed_by_you":false,"follows_you":false},"version":380,"publish_version":380,"role":null,"authored":false,"authors":[{"type":"individual","id":"fb7d131148ad1e60","login":"gmaclennan","name":"Gregor MacLennan","avatar_url":"https://avatars-next.observableusercontent.com/63198fee32cdf9a62fee6dd70e000a4d5ed970cb33b7194192381ee674ab230d","tier":null,"bio":"","followed_by_you":false,"follows_you":false}],"members":[{"type":"team","id":"b8f17b38290a2173","login":"gmaclennan","name":"Gregor MacLennan","avatar_url":"https://avatars-next.observableusercontent.com/63198fee32cdf9a62fee6dd70e000a4d5ed970cb33b7194192381ee674ab230d","tier":"starter_2024","role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"CoMapeo Area Metrics: Extent","cells":[{"id":1,"value":"$4c","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":43,"value":"const scenarioSpec = view(\n Inputs.select(scenarioCatalogue, {\n label: \"Scenario\",\n format: (spec) => spec.name\n })\n);","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":42,"value":"**${scenario.name}.** ${scenario.tests}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":22,"value":"$4d","pinned":false,"hidden":true,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":26,"value":"- **Extent: ${extentKm2.toFixed(2)} km²**, the sum of ${keptClusters.length} kept cluster${keptClusters.length === 1 ? \"\" : \"s\"} out of ${extent.clusters.length}, from ${d3.sum(keptClusters, (cluster) => cluster.cellCount).toLocaleString()} cells of ${cellSize} m.\n- **Territory: ${scenario.territoryKm2.toFixed(2)} km²**. ${scenario.territoryKm2 > 0 ? `The extent covers ${((100 * extentKm2) / scenario.territoryKm2).toFixed(1)} % of it.` : \"This scenario has no territory.\"}\n- **Records:** ${recordCount(\"point\")} observations and ${recordCount(\"track\")} tracks, plus ${recordCount(\"implied\")} implied paths.\n- **Compute time:** ${elapsedMs.toFixed(0)} ms.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":41,"value":"\nThe linking distance is our assumption about how far two points can be and still be counted as \"the same place\". Observations and tracks within ${linkingKm}km grow the territory; further apart and they count as two separate areas of territory.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":40,"value":"const linkingKm = view(\n Inputs.range([0.5, 20], {\n label: \"Linking distance (km)\",\n step: 0.5,\n value: 5\n })\n);","pinned":false,"hidden":true,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":39,"value":"The margin is how far beyond the closed shape the extent reaches, on the assumption that a team sees some distance beyond the points it records.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":38,"value":"const marginM = view(\n Inputs.range([0, 1000], {\n label: \"Margin (m)\",\n step: 50,\n value: 500\n })\n);","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":37,"value":"The size of hole in the data that we still count as area monitored. Sometimes a team's records form a ring with nothing inside: a patrol loop, or a sacred site that people walk around but never enter. If the records are close enough together that the ring closes, the ground inside is encircled. This control sets the largest encircled area that still counts as part of the extent. Above it, the hole stays open.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":36,"value":"const holeKm2 = view(\n Inputs.range([0, 400], {\n label: \"Fill encircled ground up to (km²)\",\n step: 5,\n value: 25\n })\n);","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"Stray clusters with records on fewer than three separate days and across less than 1km are ignored if they are more than ${strayKm}km from the rest of the data. This avoids points from trainings or random points taken during trips outside territory by the team distorting the area figure, while still counting distinct areas of territory that could be further apart.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":34,"value":"const strayKm = view(\n Inputs.range([10, 300], {\n label: \"Stray cluster distance (km)\",\n step: 10,\n value: 50\n })\n);","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":25,"value":"Inputs.table(\n extent.clusters.map((cluster) => ({\n cluster: cluster.id,\n records: cluster.records,\n days: cluster.days,\n \"across (km)\": cluster.spanM / 1e3,\n \"km²\": cluster.area / 1e6,\n status: cluster.kept\n ? cluster.id === 1\n ? \"kept (largest, always kept)\"\n : \"kept\"\n : `dropped: ${cluster.reason}`,\n })),\n {\n format: {\n \"km²\": (area) => area.toFixed(2),\n \"across (km)\": (km) => km.toFixed(1),\n },\n select: false,\n },\n)","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"The grid resolution for growing and shrinking. Smaller cells give a more accurate area and a slower calculation.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":32,"value":"const cellSize = view(\n Inputs.range([50, 500], {\n label: \"Cell size (m)\",\n step: 50,\n value: 100\n })\n);","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"Implied paths join consecutive observations by the same device on the same day, closer than 2 hours and 2 km apart, into a path that is grown like a track.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":30,"value":"const impliedPaths = view(Inputs.toggle({label: \"Implied paths\", value: true}));","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"Change the seed to see different randomly generated data for the scenarios.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":28,"value":"const seed = view(\n Inputs.number([0, 999999], {\n label: \"Seed\",\n value: 1,\n step: 1\n })\n);","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":24,"value":"The map fills each kept cluster's extent and outlines dropped clusters with dots. Turn on the grown shape to see the ground before shrinking: every record grown by half the linking distance, with any filled holes.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"const showGrown = view(\n Inputs.toggle({label: \"Show grown shape\", value: false})\n);","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"## Growing and shrinking, in pictures","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":18,"value":"### Grow\n\nEvery record is grown by half the linking distance. Records closer than the linking distance merge into one shape. The large ring keeps a hole, because a disc of half the linking distance still fits inside it; the small ring does not.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"panel(\n \"Grown by half the linking distance\",\n closingExtent(figureRecords, {...figureOptions, marginM: 0}).grown.runs\n)","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"### Shrink\n\nThe shape is shrunk back by the same amount. That takes away everything the growing added, except where grown records overlapped and left nothing for the shrink to work from. The arms stay joined where they are within a linking distance of each other, and the web recedes where they diverge. The small ring is filled.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"panel(\n \"Shrunk back by the same: the closing\",\n closingExtent(figureRecords, {\n ...figureOptions,\n marginM: 0\n }).clusters.flatMap((cluster) => cluster.runs)\n)","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":"### The margin\n\nActual shrink is half the linking distance minus the margin.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"panel(\n \"Shrunk back by less: the margin\",\n closingExtent(figureRecords, {\n ...figureOptions,\n marginM: 0.15\n }).clusters.flatMap((cluster) => cluster.runs)\n)","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"### Filling encircled ground\n\nWith encircled ground up to 4 square units filled, the large ring's interior, about 3.1 square units as the ring sees it, is added to the grown shape before shrinking, and the ring comes out solid. The web between the arms is unchanged, because open ground is not encircled.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"panel(\n \"Encircled ground filled before shrinking\",\n closingExtent(figureRecords, {\n ...figureOptions,\n marginM: 0.15,\n maxHoleM2: 4\n }).clusters.flatMap((cluster) => cluster.runs)\n)","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"$4e","pinned":false,"hidden":true,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"## How the extent is calculated\n\nRecords are stored as longitude and latitude. `extentOf` builds the record list for a scenario (observations, tracks and implied paths), projects it into metres, and hands it to `closingExtent`, which does the estimate. From here on every length is in metres and every area in square metres.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"function extentOf(\n scenario: Scenario,\n {linkingKm, marginM, holeKm2, cellSize, strayKm, impliedPaths}: ExtentOptions\n) {\n const records = buildRecords(scenario, {impliedPaths});\n const {projection, xyRecords} = projectRecords(records);\n const extent = closingExtent(xyRecords, {\n linkM: linkingKm * 1000,\n marginM,\n maxHoleM2: holeKm2 * 1e6,\n cellSize,\n strayKm\n });\n return {...extent, records, projection, xyRecords};\n}","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":44,"value":"`closingExtent` runs the five steps from the top of the page. The result is the list of clusters, each marked kept or dropped with the reason, and the extent: the area of the kept clusters. The last line adds the rectangles and outlines the map draws; they play no part in the calculation.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":45,"value":"function closingExtent(\n records: XyRecord[],\n {linkM, marginM, cellSize, maxHoleM2 = 0, strayKm}: ClosingOptions\n): Extent {\n const growM = linkM / 2;\n const shrinkM = Math.max(0, growM - marginM);\n\n const painted = Raster.fromGrid(grow(records, {growM, cellSize}));\n const clusters = numberClusters(painted);\n const filled = fillEncircledGround(painted, clusters, {maxHoleM2, growM});\n const removed = shrink(filled, shrinkM);\n const measured = measureClusters(filled, removed, records);\n const shapes = shapesForMap(filled, removed, measured);\n const ranked = keepOrDrop(shapes.clusters, strayKm);\n\n const area = ranked.reduce(\n (sum, cluster) => sum + (cluster.kept ? cluster.area : 0),\n 0\n );\n return {area, clusters: ranked, grown: shapes.grown};\n}","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":46,"value":"### 1. Grow\n\nGrowing uses the same algorithm as [footprint](./footprint) to create a grid of covered cells, using half the linking distance as the buffer. Two records exactly a linking distance apart end up just touching, so once everything is painted, records within the linking distance of each other have merged into one connected shape.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":47,"value":"function grow(\n records: XyRecord[],\n {growM, cellSize}: {growM: number; cellSize: number}\n): Grid {\n const grown = new Grid(cellSize);\n for (const record of records) {\n const line = simplifyLine(record.xy, cellSize / 2);\n for (const point of line) grown.markDisc(point, growM);\n for (let i = 1; i < line.length; i++)\n grown.markBand(line[i - 1], line[i], growM);\n }\n return grown;\n}","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":49,"value":"### Raster\n\nThe `Grid` is used for initially marking the area and is sparse, which is necessary for bounding memory usage when streaming records without knowing the extent first. The `Raster` is a fixed-size grid mapped onto a 1-dimensional array. The `Raster` is used for identifying connected cells for clusters; finding neighbours; and filling areas.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":52,"value":"$4f","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":54,"value":"### 2. Clusters\n\nA cluster is one connected piece of the grown shape, and `regions` finds connected pieces by a flood fill: Start at any cell that has the wanted value (`0` or `1`) and no id yet, give it the next id, and spread to its neighbours (horizontally and vertically, not diagonally) with the same value, then to their neighbours, until nothing more can be reached. Start again at the next cell without an id for the next id, and so on until none is left.\n\nThe spreading uses a queue: every cell given the id is added at the back, and cells are taken from the front to have their four neighbours checked. When the front catches up with the back the region is complete, and the number of cells added is its size.\n\n`numberClusters` runs this over the painted cells, step 3 (encircle) does the same for unpainted cells (gaps).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":55,"value":"function regions(painted: Raster, value: 0 | 1): Regions {\n const {cells, size} = painted;\n const ids = new Raster(painted.frame, Int32Array);\n const queue = new Int32Array(size);\n const sizes = [0];\n let id = 0;\n let tail = 0;\n const claim = (index: number) => {\n if (ids.cells[index] || cells[index] !== value) return;\n ids.cells[index] = id;\n queue[tail++] = index;\n };\n for (let start = 0; start < size; start++) {\n if (ids.cells[start] || cells[start] !== value) continue;\n id = sizes.length;\n tail = 0;\n claim(start);\n for (let head = 0; head < tail; head++)\n ids.forEachNeighbour(queue[head], claim);\n sizes.push(tail);\n }\n return {ids, sizes};\n}\n\nfunction numberClusters(painted: Raster): Regions {\n return regions(painted, 1);\n}","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":56,"value":"### 3. Encircled ground\n\nRunning `regions` over the unpainted cells numbers each connected piece of open ground: the outside, which is the region holding the border, and any encircled gaps.\n\nGrowing has already covered a band of half the linking distance inside every gap, so a gap is measured as a disc and grown back by that distance. Any gap that comes to no more than ${holeKm2} km² is filled with the id of the cluster around it.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":57,"value":"const encircledM2 = (gapM2: number, growM: number): number =>\n Math.PI * (Math.sqrt(gapM2 / Math.PI) + growM) ** 2;\n\nfunction fillEncircledGround(\n painted: Raster,\n clusters: Regions,\n {maxHoleM2, growM}: {maxHoleM2: number; growM: number}\n): Regions {\n const gaps = regions(painted, 0);\n const outside = gaps.ids.cells[0];\n const fill = gaps.sizes.map(\n (cells, gap) =>\n gap > 0 &&\n gap !== outside &&\n encircledM2(cells * painted.frame.cellSize ** 2, growM) <= maxHoleM2\n );\n if (!fill.includes(true)) return clusters;\n const ids = new Raster(painted.frame, Int32Array);\n ids.cells.set(clusters.ids.cells);\n const sizes = [...clusters.sizes];\n const around = new Int32Array(gaps.sizes.length);\n for (let index = 0; index < ids.size; index++) {\n const gap = gaps.ids.cells[index];\n if (!fill[gap]) continue;\n if (!around[gap]) around[gap] = clusters.ids.neighbourValue(index);\n ids.cells[index] = around[gap];\n sizes[around[gap]]++;\n }\n return {ids, sizes};\n}","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":59,"value":"### 4. Shrink\n\nShrinking removes every cell within the shrink distance of open ground, which is half the linking distance less the margin. Rather than test every cell, open cells that touch the shape are grown by the shrinking distance with `markNear`, marking `1` for each painted cell they overlap.\n\nThe result of growing-then-shrinking is that the gaps between records within linking distance are filled.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":60,"value":"function shrink({ids}: Regions, shrinkM: number): Raster {\n const {rows, cols} = ids.frame;\n const removed = new Raster(ids.frame, Uint8Array);\n const touchesShape = (index: number) =>\n ids.cells[index] === 0 && ids.neighbourValue(index) > 0;\n for (let r = 0; r < rows; r++)\n for (let c = 0; c < cols; c++) {\n if (!touchesShape(r * cols + c)) continue;\n const start = c;\n while (c + 1 < cols && touchesShape(r * cols + c + 1)) c++;\n removed.markNear(r * cols + start, r * cols + c, shrinkM);\n }\n return removed;\n}","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":64,"value":"### 5. Keep or drop\n\n`measureClusters` measures each cluster's area; centre (the mean of all its cells' centres); the number of records in the cluster; the number of separate days the records were created on; and the longest side of the bounding box around the records.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":61,"value":"$50","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":65,"value":"Clusters are sorted by the number of records, and the one with the most records is always kept. Others are dropped if they are more than ${strayKm} km from cluster 1, centre to centre, and either recorded on fewer than three separate days or span less than a kilometre. This filters out stray data from training days or trips that is not part of a territory, but keeps additional areas where ongoing monitoring is done.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":62,"value":"$51","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":66,"value":"### Shapes for the map\n\nThese functions create outlines of each cluster for drawing on the map — they aren't necessary for the area calculations, just the visualisation.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":63,"value":"$52","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"## Memory and performance\n\nRecords can be streamed as they are painted onto the `Grid`, and grid memory usage is bounded by the number of cells covered by the territory, not by the number of records. Memory usage by `Raster` is tied to the size of the bounding box around the territory, but in the application code we create a separate raster per \"island\" of data to avoid a territory in the Amazon combined with some points during a workshop in Europe generating a giant raster encompassing both areas that would result in an out-of-memory error. The example scenarios use at most 12Mb of memory and take about 15ms (on a Macbook Pro M2) to calculate the extent — fast enough to run on a low-end phone.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":53,"value":"## Types","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":48,"value":"$53","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3,"value":"## Imports\n\nThe grid and track simplification come from the [footprint](./footprint) notebook; scenarios and the map from the [scenarios](./scenarios) and [scenario map](./scenario-map) notebooks.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"import {\n scenarioCatalogue,\n makeScenario,\n buildRecords,\n projectRecords\n} from \"observable:@gmaclennan/scenarios\";\nimport {\n scenarioMap,\n applyStyle,\n PALETTE,\n PAPER\n} from \"observable:@gmaclennan/scenario-map\";\nimport {\n Grid,\n WORD,\n cellsOf,\n simplifyLine\n} from \"observable:@gmaclennan/footprint\";","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":27,"value":"const scenario = makeScenario(scenarioSpec, seed);\nconst started = performance.now();\nconst extent = extentOf(scenario, {\n linkingKm,\n marginM,\n holeKm2,\n cellSize,\n strayKm,\n impliedPaths\n});\nconst elapsedMs = performance.now() - started;\nconst extentKm2 = extent.area / 1e6;\nconst keptClusters = extent.clusters.filter((cluster) => cluster.kept);\nconst recordCount = (kind) =>\n extent.records.filter((record) => record.kind === kind).length;","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W54","stdlib":"2"}} 24:null