Security News
GitHub Removes Malicious Pull Requests Targeting Open Source Repositories
GitHub removed 27 malicious pull requests attempting to inject harmful code across multiple open source repositories, in another round of low-effort attacks.
sweepline-intersections
Advanced tools
A module to check if a polygon self-intersects using a sweepline algorithm
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
// 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)
npm run debug
.
debug/src/App.vue
npm 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.
1.4.0
FAQs
A module to check if a polygon self-intersects using a sweepline algorithm
The npm package sweepline-intersections receives a total of 0 weekly downloads. As such, sweepline-intersections popularity was classified as not popular.
We found that sweepline-intersections demonstrated a not healthy version release cadence and project activity because the last version was released a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
GitHub removed 27 malicious pull requests attempting to inject harmful code across multiple open source repositories, in another round of low-effort attacks.
Security News
RubyGems.org has added a new "maintainer" role that allows for publishing new versions of gems. This new permission type is aimed at improving security for gem owners and the service overall.
Security News
Node.js will be enforcing stricter semver-major PR policies a month before major releases to enhance stability and ensure reliable release candidates.