A small and fast module using a sweepline algorithm to detect intersections between polygons and/or polylines.
npm install sweepline-intersections
Valid inputs: Geojson Feature or Geometry including Polygon, LineString, MultiPolygon, MultiLineString, as well as FeatureCollection.
Returns an array of intersection points eg, [[x1, y1], [x2, y2]]
const findIntersections = require('sweepline-intersections')
const box = {type: 'Polygon', coordinates: [[[0, 0], [1, 0], [1, 1], [0, 1], [0, 0]]]}
const intersections = findIntersections(box)
// returns an array of self-intersection points
Also accepts an optional boolean argument second which when set to true means the module won’t detect self-intersections and will only report intersections between different features. This defaults to false. eg
const findIntersections = require('sweepline-intersections')
const intersectionsBetweenFeature = findIntersections(featureCollection, true)
// returns an array of intersection points between features
This library also provide a class-based approach which is helpful if you want 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 SweeplineIntersectionsClass from 'sweepline-intersections/dist/SweeplineIntersectionsClass'
// create the base instance
const sl = new SweeplineIntersectionsClass()
// populate the event queue with your primary geometry
sl.addData(largeGeoJson)
// clone the event queue in the original state so you can reuse it
const origQueue = sl.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
sl.addData(feature, origQueue)
// check if those two features intersect
// add an optional boolean argument to ignore self-intersections
const intersectionPoints = sl.getIntersections(true)
})
new SweeplineIntersectionsClass() - 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
.getIntersections(ignoreSelfIntersections) - Checks for segment intersections. Accepts an optional boolean argument to ignore self intersections are only report intersections between features.
Tested against
// Simple Case (6 vertices) // gpsi x 246,512 ops/sec ±1.23% (90 runs sampled) // bentleyOttmann x 546,326 ops/sec ±0.66% (92 runs sampled) // sweepline x 1,157,425 ops/sec ±1.04% (94 runs sampled) // - Fastest is sweepline (this library)
// Chile - Vertical geometry (17,000 vertices) // sweepline x 35.64 ops/sec ±1.20% (62 runs sampled) ````
npm run debug.
debug/src/App.vuenpm run test runs all testsnpm run test:e2e does a general test that the correct number of self-intersections are found in the test/fixtures foldernpm run test:unit is unit style tests to make sure functions & methods do the right thing
The basic concept of this algorithm is based on a sweepline. Where this algorithm differs from the bentley-ottmann algorithm is that there is no use of a tree data structure to store the segments. The reason for the modification is because if you are dealing with polygons or polylines (rather than a random group of line segments) there is a reasonable assumption that there are going to be very few segments that lie on the same x plane.
Removing the tree structure greatly simplifies the code. The tree structure is replaced with a priority queue of segments which is sorted by the x vertex of the right endpoint of the segments. A priority queue is already used to sort the vertices which means only 1 data structure is required.
The package size of this module is 3kb compared to my implementation of the bentley-ottmann algorithm which is 16kb while performance is typically faster than bentley-ottmann.
Bentley-ottman only outperforms this library when there are several thousands vertices, however I’m also less confident in the results of my bentley-ottman lib as it occassionally misses intersections and is much harder to write tests for due to the more complex logic.
Each pair of segments are only tested once. And only segments that overlap on the x plane are tested against each other.