sweepline-intersections

sweepline-intersections

A small module using a sweepline algorithm to detect self-intersections in polygons or polylines.

Install

npm install sweepline-intersections

Documentation

Valid inputs: Geojson Polygon, MultiPolygon, LineString, MultiLineString

    const findIntersections = require('sweepline-intersections')

    const box = {type: 'Polygon', coordinates: [[[0, 0], [1, 0], [1, 1], [0, 1], [0, 0]]]}
    findIntersections(box)
    // returns array of intersection points

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

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

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.

I did have some concerns that a really vertical geometry (eg think of the border of the Chile) would not perform well but it still beat the bentley ottman implementation.

Algorithm Steps

• 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.