A fast module for checking if segment intersections exist using the Shamos-Hoey algorithm. Can be used for
- detecting if a geometry has self-intersections, or
- if multiple geometries have segments which intersect
Note: This module only detects if an intersection does exist, not where, or how many. If you need to find the points of intersection I suggest using the sweepline-intersections module.
npm install shamos-hoey
Valid inputs: Geojson Feature or Geometry including Polygon, LineString, MultiPolygon, MultiLineString, as well as FeatureCollection's.
Returns true if there are no intersections
Returns false if there are intersections
const noIntersections = require('shamos-hoey')
const box = {type: 'Polygon', coordinates: [[[0, 0], [1, 0], [1, 1], [0, 1], [0, 0]]]}
noIntersections(box)
// => trueThis library also provide a class-based approach which is helpful if you need to check multiple geometries against a single geometry. This allows you to save the state of the initial event queue with the primary geometry.
import ShamosHoeyClass from 'shamos-hoey/dist/ShamosHoeyClass'
// create the base instance
const sh = new ShamosHoeyClass()
// populate the event queue with your primary geometry
sh.addData(largeGeoJson)
// clone the event queue in the original state so you can reuse it
const origQueue = sh.cloneEventQueue()
// now you can iterate through some other set of features saving
// the overhead of having to populate the complete queue multiple times
someOtherFeatureCollection.features.forEach(feature => {
// add another feature to test against your original data
sh.addData(feature, origQueue)
// check if those two features intersect
sh.noIntersections()
})new ShamosHoeyClass() - creates a new instance
.addData(geojson, existingQueue) - add geojson to the event queue. The second argument for an existingQueue is optional, and takes a queue generated from .cloneEventQueue()
.cloneEventQueue() - clones the state of the existing event queue that's been populated with geojson. Returns a queue that you can pass to the addData method
.noIntersections() - Checks for segment intersections. Returns true if there are no segment intersections or false if there are intersections.
If you need to find the points of self-intersection I suggest using the sweepline-intersections module. The sweeline-intersections module is also smaller (4kb vs 12kb) and very fast for most use cases. It uses alot of the same logic although doesn't inlude a tree structure which makes up the major dependency for this library.
Detecting an intersection in a polygon with roughly 700 vertices. Note that the other libraries report the intersection point/s.
// Has intersections
// ShamosHoey x 4,132 ops/sec ±0.60% (95 runs sampled)
// SweeplineIntersections x 2,124 ops/sec ±0.70% (92 runs sampled)
// GPSI x 36.85 ops/sec ±1.06% (64 runs sampled)
// - Fastest is ShamosHoey
For the class-based module vs the basic use on a very large geojson file (approx. 14,000 vertices)
// Class-based reuse vs Basic
// ShamosHoey x 1,011 ops/sec ±8.12% (89 runs sampled)
// ShamosHoeyClass x 2,066 ops/sec ±0.60% (93 runs sampled)
// - Fastest is ShamosHoeyClass
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent