planefill

Coverage path planning algorithms for GeoJSON polygons. Give it a polygon and a spacing, get back a Feature<LineString> that sweeps the interior — ready to feed to a drone, robot, or anything else that needs to cover an area.

Built during a vibe-coding session with Claude.

Install

npm install planefill

@turf/turf is a peer dependency and will be installed automatically.

Quick start

import { planPath } from 'planefill';

const polygon = {
  type: 'Feature',
  geometry: {
    type: 'Polygon',
    coordinates: [[
      [-0.005, -0.005], [0.005, -0.005],
      [0.005,  0.005],  [-0.005,  0.005],
      [-0.005, -0.005],
    ]],
  },
};

const path = planPath(polygon, { strategy: 'boustrophedon', spacing: 50 });
// → Feature<LineString>  with properties.strategy and properties.spacing

API

planPath(geojson, options)

Plan a single-agent coverage path over a polygon.

| Parameter | Type | Description | |---|---|---| | geojson | Feature<Polygon\|MultiPolygon> or bare geometry | The area to cover | | options.spacing | number | Row / ring separation in metres. Required. | | options.strategy | Strategy | Which algorithm to use. Default: 'boustrophedon' | | options.angle | number | Sweep rotation in degrees (clockwise from East). Only used by 'boustrophedon' and 'diagonal'. Default: 0 |

Returns Feature<LineString> with properties.strategy and properties.spacing.

import { planPath } from 'planefill';

const path = planPath(polygon, {
  strategy: 'hilbert',
  spacing: 30,
});

planMultiPath(geojson, options)

Divide a polygon into N regions and plan a coverage path in each. Returns a FeatureCollection<LineString> — one feature per party — with a properties.party index on each.

| Parameter | Type | Description | |---|---|---| | options.parties | number | Number of regions / agents. Default: 2 | | options.divisionStrategy | DivisionStrategy | How to divide the polygon. Default: 'vertical' | | options.coverageStrategy | Strategy | Coverage algorithm for each region. Default: 'boustrophedon' | | options.spacing | number | Row / ring separation in metres. Required. | | options.angle | number | Sweep angle (boustrophedon / diagonal only). Default: 0 |

import { planMultiPath } from 'planefill';

const collection = planMultiPath(polygon, {
  parties: 4,
  divisionStrategy: 'balanced',
  coverageStrategy: 'boustrophedon',
  spacing: 50,
});

for (const feature of collection.features) {
  console.log(`Party ${feature.properties.party}:`, feature.geometry.coordinates.length, 'waypoints');
}

dividePolygon(polygon, n, strategy?)

Low-level utility — divide a Feature<Polygon> into up to n non-empty sub-polygons without planning paths. Useful if you want to handle the coverage step yourself.

import { dividePolygon } from 'planefill';

const regions = dividePolygon(polygon, 3, 'balanced');
// → Feature<Polygon>[]  (may be fewer than 3 for small / irregular polygons)

STRATEGIES

Record<Strategy, fn> — the map of all registered strategy implementations. Useful for building UI dropdowns or validating user input.

import { STRATEGIES } from 'planefill';

console.log(Object.keys(STRATEGIES));
// ['boustrophedon', 'diagonal', 'outer-in', 'inner-out', 'hilbert', 'grid-spiral']

DIVISION_STRATEGIES

DivisionStrategy[] — ordered list of all division strategy names.

import { DIVISION_STRATEGIES } from 'planefill';

console.log(DIVISION_STRATEGIES);
// ['vertical', 'horizontal', 'grid', 'balanced']

Coverage strategies

| Strategy | Description | |---|---| | boustrophedon | Classic lawnmower pattern — parallel scan lines alternating left→right and right→left. Accepts an angle parameter to rotate the sweep direction. | | diagonal | Boustrophedon at a fixed 45° angle. | | outer-in | Concentric rings eroding inward from the polygon boundary toward the centre. | | inner-out | Same concentric rings, traversed from the centre outward. | | hilbert | Hilbert space-filling curve mapped to a cell grid. Visits every cell in a locality-preserving order. | | grid-spiral | Outward expanding-square spiral over a cell grid (same grid size as Hilbert). Each step is exactly one cell horizontal or vertical — self-avoiding on convex polygons. |

All strategies go through a Ramer-Douglas-Peucker simplification pass (tolerance = 5% of spacing) before the path is returned, removing redundant collinear waypoints.

Division strategies

| Strategy | Description | |---|---| | vertical | N equal-width vertical strips clipped to the polygon. | | horizontal | N equal-height horizontal strips clipped to the polygon. | | grid | ⌈√N⌉ × ⌈N/⌈√N⌉⌉ bounding-box grid (e.g. 4 parties → 2×2, 6 → 3×2). | | balanced | Recursive binary split along the longer bbox dimension. Each bisection is positioned by binary search so both halves receive area proportional to their leaf count — producing roughly equal-area regions even for irregular polygons and odd values of N. |

TypeScript

The package ships a hand-authored declaration file (dist/index.d.ts). All public types are exported:

import {
  planPath,
  planMultiPath,
  dividePolygon,
  type Strategy,
  type DivisionStrategy,
  type PolygonInput,
  type PlanPathOptions,
  type PlanMultiPathOptions,
  type PathProperties,
  type MultiPathProperties,
} from 'planefill';

Browser / bundler usage

The package exports both ESM (dist/index.mjs) and CJS (dist/index.cjs). Modern bundlers (Vite, esbuild, Webpack 5+) will pick up the ESM build automatically via the exports field. @turf/turf is kept external — your bundler resolves it from node_modules.

Development

git clone <repo>
npm install

npm test           # run the test suite (vitest)
npm run build      # compile dist/ (ESM + CJS + types)
npm run build:ui   # bundle the demo UI (esbuild IIFE → ui/bundle.js)
npm run dev:ui     # same, with --watch

The demo UI (ui/) is a Leaflet app that lets you visualise every strategy interactively. Open ui/index.html after running build:ui. It is not published to npm.

License

MIT