@studnicky/spatial

Zero-dependency spatial primitives: point-in-polygon, bounding-box zone index, grid-based nearest-neighbor search.

A small set of geometry primitives for working with GeoJSON-shaped points, polygons, and bounding boxes. pointInPolygon and the bbox helpers are standalone functions; ZoneIndex and PointGridIndex build on top of them to answer "which zone contains this point" and "which point is nearest" queries efficiently over large datasets, without pulling in a full GIS library.

Install

pnpm add @studnicky/spatial

Requires @studnicky:registry=https://npm.pkg.github.com in .npmrc.

Point-in-polygon

The ray-cast point-in-polygon test, including support for a hole cut out of the outer ring. Try it live — edit the code and press Execute:

Point-in-polygon, including a hole

/** pointInPolygon — demonstrates the ray-cast point-in-polygon test, including a hole. Run: npx tsx examples/pointInPolygon.ts */

import assert from 'node:assert/strict';

// #region usage
import { pointInPolygon } from '../src/index.js';

function demonstratePointInPolygon(): number[][][] {
  // A 4x4 degree square, with a 1x1 degree hole cut out of its center.
  const outer = [[0, 0], [4, 0], [4, 4], [0, 4], [0, 0]];
  const hole = [[1.5, 1.5], [2.5, 1.5], [2.5, 2.5], [1.5, 2.5], [1.5, 1.5]];
  const rings = [outer, hole];

  // A point inside the outer ring and outside the hole is inside the polygon.
  console.log('(1, 1) inside:', pointInPolygon(1, 1, rings));

  // A point inside the hole is not inside the polygon.
  console.log('(2, 2) inside:', pointInPolygon(2, 2, rings));

  // A point outside the outer ring is not inside the polygon.
  console.log('(10, 10) inside:', pointInPolygon(10, 10, rings));

  return rings;
}
// #endregion usage

const rings = demonstratePointInPolygon();

assert.equal(pointInPolygon(1, 1, rings), true);
assert.equal(pointInPolygon(2, 2, rings), false);
assert.equal(pointInPolygon(10, 10, rings), false);

console.log('pointInPolygon: all assertions passed');

Output

Press Execute to run this example against the real library.

Zone index

Building a ZoneIndex from named polygon features and querying it by point and by bbox:

import type { ZoneGeometryType } from '../src/index.js';

import { ZoneIndex } from '../src/index.js';

// json-schema-uninexpressible: example-only demonstration fixture inline in a runnable usage script, not a package data contract requiring schema derivation
type District = {
  'name': string;
  'polygon': number[][];
};

function names(matches: District[]): string[] {
  const result: string[] = [];
  for (const match of matches) {
    result.push(match.name);
  }
  return result;
}

function demonstrateZoneIndex(): { 'hit': string[]; 'miss': string[]; 'overlapping': string[] } {
  const districts: District[] = [
    { 'name': 'north', 'polygon': [[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]] },
    { 'name': 'south', 'polygon': [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]] }
  ];

  const index = ZoneIndex.build<District>(
    districts,
    (district): ZoneGeometryType => { return { 'coordinates': [district.polygon], 'type': 'Polygon' }; }
  );

  // zonesContaining resolves a point to every zone whose polygon contains it.
  const hit = names(index.zonesContaining(1, 1));
  console.log('zones containing (1, 1):', hit);

  // A point outside every polygon resolves to an empty array.
  const miss = names(index.zonesContaining(10, 10));
  console.log('zones containing (10, 10):', miss);

  // zonesOverlapping runs a broad-phase bbox test against every zone's own bbox.
  const overlapping = names(index.zonesOverlapping([0, 1, 2, 3]));
  console.log('zones overlapping [0, 1, 2, 3]:', overlapping);

  return { 'hit': hit, 'miss': miss, 'overlapping': overlapping };
}

Point grid index

Grid-based nearest-neighbor search over a set of points:

import { PointGridIndex } from '../src/index.js';

// json-schema-uninexpressible: example-only demonstration fixture inline in a runnable usage script, not a package data contract requiring schema derivation
type Airport = {
  'code': string;
  'lat': number;
  'lon': number;
};

function demonstratePointGridIndex(): { 'emptyNearest': Airport | null; 'nearestToMidtown': Airport | null } {
  const airports: Airport[] = [
    { 'code': 'JFK', 'lat': 40.6413, 'lon': -73.7781 },
    { 'code': 'LGA', 'lat': 40.7769, 'lon': -73.8740 },
    { 'code': 'EWR', 'lat': 40.6895, 'lon': -74.1745 },
    { 'code': 'BOS', 'lat': 42.3656, 'lon': -71.0096 }
  ];

  const index = PointGridIndex.build(airports);

  // nearest finds the closest indexed point, with its great-circle distance in nautical miles.
  const nearestToMidtown = index.nearest(40.7549, -73.9840);
  console.log('nearest airport to Midtown Manhattan:', nearestToMidtown);

  // An empty index returns null instead of throwing.
  const emptyIndex = PointGridIndex.build<Airport>([]);
  const emptyNearest = emptyIndex.nearest(0, 0);
  console.log('nearest in an empty index:', emptyNearest);

  return { 'emptyNearest': emptyNearest, 'nearestToMidtown': nearestToMidtown };
}

Source on GitHub