de9im

de9im is a Javascript library that provides spatial predicate functions defined by the Dimensionally Extended Nine-Intersection Model (DE-9IM) and works with GeoJSON objects. It can test if two geometries have one of the following relationships: contains, coveredby, covers, crosses, disjoint, equals, intersects, overlaps, touches, within. It can be used client-side in a browser or server-side with Node.js.

See de9im examples for examples of geometries that satisfy the various predicates using de9im.

See pouchdb-geospatial for an example application that uses de9im to perform spatial querying of GeoJSON objects in a database.

GETTING STARTED

de9im depends on the Turf.js library for performing spatial operations which must be also included for client-side processing since Turf.js is not bundled with de9im.

In a browser

<script src="https://unpkg.com/@turf/turf" charset="utf-8"></script>
<script src="https://unpkg.com/de9im" charset="utf-8"></script>

In Node

npm install de9im
const de9im = require('de9im');

Then call a predicate function on two geometries

const line = {'type': 'LineString', 'coordinates': [[0, 0], [1, 1], [2, 2]]};
const point = {'type': 'Point', 'coordinates': [1, 1]};
de9im.contains(line, point);
// = true
de9im.disjoint(line, point);
// = false

USAGE

API

The de9im object has the following spatial predicate functions available:

contains
coveredby
covers
crosses
disjoint
equals
intersects
overlaps
touches
within

Each predicate takes two GeoJSON arguments and an optional boolean argument:

de9im.predicate(geojson1, geojson2, [error=true])

It returns true, false, or throws an exception if the geometry types provided are not supported. If the optional argument error is false then unsupported geometries return false instead of throwing an exception. Each predicate should be interpreted as the first argument operating on the second. For example,

de9im.contains(line, point)

should be read as

line contains point?

Data Types

The arguments for every predicate can be any GeoJSON type: Geometry, Feature, GeometryCollection, FeatureCollection. All geometry types are supported: Point, LineString, Polygon, MultiPoint, MultiLineString, MultiPolygon. However, only homogenous geometries are supported in collections. For example, a FeatureCollection can have points but can not mix points and lines.

Argument Types

Each predicate has a unique combination of first and second argument geometries that it supports.

• contains, covers

  1st / 2nd	Point	Line	Polygon
  Point	✔️	❌	❌
  Line	✔️	✔️	❌
  Polygon	✔️	✔️	✔️

• coveredby, within

  1st / 2nd	Point	Line	Polygon
  Point	✔️	✔️	✔️
  Line	❌	✔️	✔️
  Polygon	❌	❌	✔️

• crosses

  1st / 2nd	Point	Line	Polygon
  Point	❌	✔️	✔️
  Line	✔️	✔️	✔️
  Polygon	✔️	✔️	❌

• disjoint, intersects

  1st / 2nd	Point	Line	Polygon
  Point	✔️	✔️	✔️
  Line	✔️	✔️	✔️
  Polygon	✔️	✔️	✔️

• equals, overlaps

  1st / 2nd	Point	Line	Polygon
  Point	✔️	❌	❌
  Line	❌	✔️	❌
  Polygon	❌	❌	✔️

• touches

  1st / 2nd	Point	Line	Polygon
  Point	❌	✔️	✔️
  Line	✔️	✔️	✔️
  Polygon	✔️	✔️	✔️

TIPS

The following are some best practices on using de9im:

• Data is expected to be in WGS 84 coordinates as per the GeoJSON standard.

• Data with the GeoJSON bbox attribute already defined will process faster.

• Data with complex geometries (e.g., self-intersections, repeated coordinates) may produce invalid results.

• Data coordinates should be truncated to avoid unrealistically high precision (more than 6 decimal places).

ALGORITHM NOTES

The de9im library uses a partition approach to determine if two geometries satisfy a given relation. This approach is different from the standard node/edge labeling used by most DE-9IM implementations. Labeling approaches are only defined for single geometries and not multi-geometries or collections and it is not clear how to extend them to cover those cases.

Instead, de9im partitions each input geometry into elementary facets, where each facet is either inside or outside the other geometry. For example, to test two (multi-) polygons, the first (multi-) polygon is triangulated. This triangulation gets intersected with the other (multi-) polygon's triangulation. This intersection gets re-triangulated to create a decomposition of the first (multi-) polygon such that each partition triangle (facet) is entirely inside or outside the second (multi-) polygon. Finally, the decision of whether the geometries satisfy the given predicate can be reduced to determining if the individual facets satisfy the relation. The same goes for lines using segments as the facets instead of triangles. This allows any geometry or collection type to be processed.

Finally, while de9im has turf as a dependency, it does not use its DE-9IM functions since it has only limited functionality and only covers a small subset of all possible geometry and predicate combinations. The goal of de9im is to cover all possible combinations. The turf library is only used for basic spatial processing and geometry utility functions.

BUILD

To build and test the library locally:

npm install
npm test

BENCHMARK

Benchmark timing results can be found at bench.md.

LICENSE

Copyright (c) 2019 Daniel Pulido mailto:[email protected]

Source code is released under the MIT License.