Fixed: materialise_chunk(fun = "sum") assigned 1 to interior run cells
instead of adding 1, so where polygon interiors overlapped the sum
undercounted (and disagreed with extract_burn(fun = "sum"), which
documents that it reproduces materialise_chunk()). Interiors now
accumulate like edges, lines and points.
Fixed: a non-finite extent (Inf, or a span that overflows double
precision) reached the core with an infinite cell size and crashed R
with a C stack overflow. burn() now errors, and the core's own grid
validation rejects non-finite bounds for every binding.
?burn no longer says that materialise_chunk() refuses mixed geometry
kinds or refers to an id = filter it doesn't have. It sums whatever it
is given; extract_burn(fun = "sum") is the one that refuses mixed
kinds.
The row-centre crossing fix below (#19) is now also part of the shared
parity fixtures (fixtures/), so the C++, R and Python suites all check
it.
Fixed: in coverage mode, a vertex lying a few ulp off a cell edge (e.g. a
vertex at 0.3 on a grid with resolution 0.1, where the edge is computed as
3 * 0.1 = 0.30000000000000004) sent the cell walker off the grid along the
extrapolated edge until memory was exhausted; where it did return, a
degenerate corner exit made left_hand_area() over-count the cell.
Vertices within 1e-9 of a cell (relative to resolution) of an edge are now
snapped onto it before the walk; a crossing computed beyond a segment's end
is clamped to the cell; and a non-converging ring walk throws a clear error
instead of bad_alloc. The same input crashes exactextractr, so this is
inherited from the exactextract traversal. Fix lives in
cpp/src/scanline.cpp and is synced to src/.
Fixed: in coverage mode, an edge crossing a row's centre line exactly on a column wall registered no winding delta in either adjacent cell, and the row lost its interior runs from that column on. Pre-existing (the Falkland Islands from Natural Earth 110m lose two cells at 0.5 degrees), but the lattice snapping above puts many more crossings exactly on walls and made it far more visible. The crossing test is now half-open at the row centre in coverage mode as it already was in approx mode. Natural Earth 110m at 0.01 degree is now 0.035 square degrees short of the planar area, versus 0.50 before; no geometry gets worse.
Fixed: in approx mode, a vertex sitting on a row's centre line (as a user computes it, one ulp from the same line recomputed from the extent) could flip the sign of that edge's intercept, after which the row filled from the polygon to the right edge of the grid. The crossing direction now comes from the edge's own endpoints. Found by the property-based suite in controlledburn-rs.
materialise_chunk() gains a target argument: materialise only a
sub-window of the burn grid, via crop_burn(), without allocating the full
grid. The chunk is identical to the corresponding sub-matrix of the full
materialisation.
Internal: the vendored C++ core now emits 0-based indices with an
exclusive col_end and id = k (aligning with controlledburn-rs and
every non-R consumer). The cpp11 shim (src/scanline_shim.cpp) adds 1
to row/col/col_start/id to restore the package's 1-based, inclusive
contract, so R output is unchanged.
burn() replaces burn_scanline() as the main entry point.
burn_scanline() remains as a deprecated wrapper.
burn_sparse() removed. The function is now a deprecated stub
that errors with a message directing users to burn(). All
GEOS-dependent code has been removed; the package no longer depends
on libgeos.
Polygon boundary cells: $edges$weight renamed to $edges$fraction
(done in a previous dev cycle, retained here for completeness).
extract_burn() to extract values at points
mode = c("coverage", "approx") parameter on burn().
"coverage" (default) computes exact coverage fractions for polygon
boundary cells via the analytical traversal engine. "approx" uses
the cell-centre rule (fasterize semantics): boundary cells are
included as full run cells iff the cell centre is inside the polygon.
No $edges produced in approx mode. Lines and points are unaffected
by mode.
crop_burn(x, target) extracts a sub-window from a
controlledburn result. Filters and clips runs/edges/lines/points
to the target extent (snapped outward to cell boundaries), re-bases
row/col indices. Pure R data frame filtering — no dense allocation.
Lightweight approx sweep. Approx mode uses a dedicated edge-row intersection sweep (~120 lines of C++) that bypasses the exactextract walker entirely. On CGAZ (218 countries, 10.1M vertices), this is 1.6–14.5× faster than the walker-based path and crosses over fasterize at ~134 million cells. At 537M cells, controlledburn is 6.8× faster than fasterize; at 8.6 billion cells (where fasterize runs out of memory), the sweep completes in 2.4 seconds.
Cell-for-cell fasterize parity. On NC counties at 2000×800, the lightweight sweep produces identical output to fasterize (zero discrepant cells). Boundary conventions match fasterize: left-inclusive, top-inclusive, half-open interval for horizontal edges at cell-centre y-coordinates.
C++ core (cpp/): pure C++17 library with zero external
dependencies, built and tested independently via CMake/CTest.
tools/sync-core.sh derives R package sources from the canonical
core.
Python bindings (python/): pybind11 + scikit-build-core.
burn() accepts WKB bytes and supports mode="coverage" and
mode="approx". 33 pytest cases pass.
Shared parity fixtures (fixtures/): CSV files with WKT, WKB
hex, grid specs, and expected results. Read by C++, R, and Python
test suites for cross-language consistency.
CI for all three surfaces: C++ ctest, Python pytest, R CMD check.
libgeos (LinkingTo and Imports). The vendored
exactextract subset is trimmed to 9 GEOS-free analytical geometry
files.cpp11 (LinkingTo), wk (Imports).sf, fasterize) are optional and gated behind
skip_if_not_installed(). NC county test fixture is bundled as
serialised WKB — no sf or vapour needed at test time.Unified geometry rasterization: burn() handles polygon, line, and
point input through a single entry point with type-pure output
tables ($runs, $edges, $lines, $points).
process_polygon_approx(): the lightweight sweep. For each polygon
edge, computes x-intercepts at each row's y_mid, accumulates winding
per row, sweeps left-to-right to emit runs. Top-inclusive half-open
interval (ya, yb] matches the walker's crossing convention.
process_polygon(): the full walker path for coverage mode. Uses
the exactextract traversal engine for exact analytical coverage
fractions.
Edge zoo (tests/testthat/test-edge-zoo.R) pins canonical
rasterizer edge cases by category. Each test pins a convention,
not just a numerical expectation.
vignette("architecture") documents the full development story:
fasterize origins, exactextract integration, GEOS replacement,
dual-mode engine, and scaling characteristics.
Complete rewrite of controlledburn using the exactextract algorithm (Daniel Baston, vendored from exactextractr) for exact polygon-grid coverage fractions.
burn_scanline(): O(perimeter) scanline sweep with winding-number interior
classification and exact boundary coverage fractions. No dense matrix
allocation — output is sparse runs + edges tables.
burn_sparse(): Reference implementation using the exactextract dense
algorithm, compressed to the same sparse output format.
materialise_chunk(): Opt-in expansion to dense matrix or vector, with
per-polygon-id filtering.
Default grid parameters: extent derived from geometry bbox via wk::wk_bbox(),
dimension auto-fitted to 256 cells on the long axis preserving aspect ratio,
or specified as resolution.
Geometry input via wk::wkb(), geos_geometry, sfc, blob, or raw WKB
list (compatible with vapour/gdalraster output).
Moved from Rcpp to cpp11, using libgeos for GEOS access.
Scanline algorithm: lightweight walk using Box::crossing() directly (no
Cell class allocation), winding-count interior classification, analytical
single-traversal coverage via perimeter_distance().
Validated against burn_sparse across 52 test cases: simple shapes, NC counties, shared boundaries, edge cases (grid-aligned edges, slivers, extent clipping, degenerate shapes).
O(perimeter) scaling confirmed by benchmark: 17× faster than dense at 3200×3200 resolution for complex shapes. Memory: sparse output ~50 MB vs ~2 GB dense for real-world 32K×16K grids.
Derived from fasterize (Noam Ross, EcoHealth Alliance) — original scanline edge logic for polygon rasterization.
Previous controlledburn (0.0.2) returned binary in/out run-length indexes
without coverage fractions. That code is archived at
archive0-2026-02-13 branch.
Basic function working, return a list of triplets of zero-index start,end,line index.
Raster package objects and use removed.
Converted from fasterize edge scanline logic, to not materialize any raster data. Armadillo usage removed.