npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

sweepline-intersections

v2.0.1

Published

A module to check if a polygon self-intersects using a sweepline algorithm

Downloads

680,713

Readme

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

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

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.