sweepline-intersections

A small and fast module using a sweepline algorithm to detect intersections between polygons and/or polylines.

Documentation

$3

```
npm install sweepline-intersections
``

$3

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]]

``js
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
``js
const findIntersections = require('sweepline-intersections')
const intersectionsBetweenFeature = findIntersections(featureCollection, true)
// returns an array of intersection points between features
``

$3

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.

``js
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)
})
``

#### API
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.




Benchmarks


Tested against
- bentley-ottmann-intersections - https://www.npmjs.com/package/bentley-ottmann-intersections
- gpsi - https://www.npmjs.com/package/geojson-polygon-self-intersections
- isects - https://www.npmjs.com/package/2d-polygon-self-intersections
``
// Switzerland (~700 vertices)
// gpsi x 37.05 ops/sec ±1.77% (49 runs sampled)
// bentleyOttmann x 2,010 ops/sec ±1.52% (89 runs sampled)
// sweepline x 2,621 ops/sec ±0.29% (95 runs sampled)
// isects x 14.29 ops/sec ±2.16% (40 runs sampled)
// - Fastest is sweepline (this library)

// 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)
``

Contributing


- For a live dev server run npm run debug.
- The geometry being tested can be modified in debug/src/App.vue
- There are a couple of test suites
- npm run test runs all tests
- npm run test:e2e does a general test that the correct number of self-intersections are found in the test/fixtures folder
- npm run test:unit` is unit style tests to make sure functions & methods do the right thing
- these need some love

Algorithm notes

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.

$3

- Vertices are entered into a priority queue sorted from left to right
- An empty priority queue is created to store segments encountered
- An item is removed from the priority queue
- If the vertex is the left endpoint of a segment, we test it against every other segment in the segment queue for intersections with any intersection recorded. We then add the vertex (and it's associated right endpoint) to the segment queue.
- When we encounter a right endpoint we remove the first item from the segment queue.

Each pair of segments are only tested once. And only segments that overlap on the x plane are tested against each other.