Skip to content

Latest commit

 

History

History
118 lines (90 loc) · 6.19 KB

README.md

File metadata and controls

118 lines (90 loc) · 6.19 KB
Raw

sweepline-intersections

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

Documentation

Install

npm install sweepline-intersections

Basic Use

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

Complex Use

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

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

// 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)
// bentleyOttmann x 50.22 ops/sec ±1.75% (65 runs sampled)
// sweepline x 35.64 ops/sec ±1.20% (62 runs sampled)
// - Fastest is bentleyOttmann (although it doesn't find intersection)

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.

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.