Geospatial

ParticleDB includes native geospatial support with 2D geometry types, distance and containment functions, an R-tree spatial index for efficient range and nearest-neighbor queries, and Well-Known Text (WKT) serialization.

Geometry Types

Three geometry types are supported:

Type	Description	Example
Point	A 2D point with longitude (lon) and latitude (lat)	POINT(-73.9857 40.7484)
Polygon	A closed ring of vertices (first == last)	POLYGON((-73.98 40.74, -73.97 40.74, ...))
LineString	An ordered sequence of connected points	LINESTRING(-73.98 40.74, -73.97 40.75)

All three types are wrapped in a Geometry union type that can hold any of them.

Spatial Functions

ST_Distance(p1, p2)

Compute the Haversine great-circle distance between two points, returned in meters. Uses the WGS-84 mean Earth radius (6,371,008.8 m).

SELECT ST_Distance(
  ST_MakePoint(-73.9857, 40.7484),   -- Empire State Building
  ST_MakePoint(-73.9680, 40.7614)    -- Central Park
) AS distance_meters;
-- ≈ 1,827 m

ST_Distance_Euclidean(p1, p2)

Compute the Euclidean (flat-plane) distance between two points. Useful for projected coordinate systems where Haversine curvature correction is unnecessary.

SELECT ST_Distance_Euclidean(
  ST_MakePoint(0, 0),
  ST_MakePoint(3, 4)
) AS distance;
-- 5.0

ST_Within(point, polygon)

Returns true if a point lies inside a polygon. Uses the ray-casting algorithm to handle arbitrary simple polygons (including concave shapes).

SELECT ST_Within(
  ST_MakePoint(-73.9857, 40.7484),
  ST_GeomFromText('POLYGON((-74.0 40.7, -73.9 40.7, -73.9 40.8, -74.0 40.8, -74.0 40.7))')
) AS inside;
-- true

ST_Contains(polygon, point)

The inverse of ST_Within — returns true if the polygon contains the point. Semantically identical to ST_Within with swapped arguments.

SELECT ST_Contains(
  ST_GeomFromText('POLYGON((-74.0 40.7, -73.9 40.7, -73.9 40.8, -74.0 40.8, -74.0 40.7))'),
  ST_MakePoint(-73.9857, 40.7484)
) AS contains;
-- true

ST_DWithin(p1, p2, distance_meters)

Returns true if two points are within the given distance in meters. This is a convenience wrapper around ST_Distance that avoids computing the full distance when only a threshold check is needed.

-- Find all stores within 2 km of the user
SELECT name FROM stores
WHERE ST_DWithin(location, ST_MakePoint(-73.9857, 40.7484), 2000);

Additional Spatial Functions

Function	Description
ST_MakePoint(lon, lat)	Create a Point from longitude and latitude
ST_X(point)	Extract the longitude of a point
ST_Y(point)	Extract the latitude of a point
ST_Envelope(geometry)	Compute the bounding box of any geometry
ST_Area(polygon)	Compute the signed area of a polygon (Shoelace formula)
ST_Length(linestring)	Compute the total Haversine length of a line string
ST_Centroid(polygon)	Compute the centroid of a polygon

R-Tree Spatial Index

For efficient spatial lookups, ParticleDB provides an R-tree index that organizes geometries by their bounding boxes. The R-tree supports two query modes:

Range Query

Find all geometries whose bounding box intersects a search rectangle:

-- Conceptual: find all points within a bounding box
SELECT * FROM locations
WHERE ST_Within(point, ST_Envelope(ST_MakePoint(-74, 40), ST_MakePoint(-73, 41)));

Internally, the R-tree traverses only those subtrees whose bounding boxes overlap the search rectangle, pruning large portions of the dataset without examining individual rows.

Nearest-Neighbor Query (k-NN)

Find the k closest geometries to a given point, ordered by distance:

-- Find the 10 nearest restaurants
SELECT name, ST_Distance(location, ST_MakePoint(-73.9857, 40.7484)) AS dist
FROM restaurants
ORDER BY dist
LIMIT 10;

The R-tree uses a priority-queue traversal (best-first search) to find the k nearest neighbors without scanning the entire index.

R-Tree Structure

The index is a balanced tree where:

• Leaf nodes store (row_id, bounding_box) pairs.
• Internal nodes store bounding boxes that enclose all children.
• Insertions use minimum-area-enlargement to choose the best subtree, keeping the tree balanced and minimizing bounding-box overlap.

The R-tree supports both point insertions (insert) and bounding-box insertions (insert_bbox) for polygon and line-string geometries.

WKT Serialization

All geometry types support Well-Known Text (WKT) round-trip serialization:

-- Geometry to WKT
SELECT ST_AsText(location) FROM stores LIMIT 1;
-- 'POINT(-73.9857 40.7484)'

-- WKT to Geometry
SELECT ST_GeomFromText('POLYGON((-74.0 40.7, -73.9 40.7, -73.9 40.8, -74.0 40.8, -74.0 40.7))');

Supported WKT formats:

WKT	Geometry Type
POINT(lon lat)	Point
POLYGON((lon lat, lon lat, ...))	Polygon
LINESTRING(lon lat, lon lat, ...)	LineString