Security News
Highlights from the 2024 Rails Community Survey
A record 2,709 developers participated in the 2024 Ruby on Rails Community Survey, revealing key tools, practices, and trends shaping the Rails ecosystem.
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
's.
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 intersection points
This library also provide a class-based approach which is helpful if you need 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
const intersectionPoints = sl.getIntersections()
})
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
.intersect()
- Checks for segment intersections. Returns true
if there are no segment intersections or false
if there are intersections.
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.2.0
FAQs
A module to check if a polygon self-intersects using a sweepline algorithm
The npm package sweepline-intersections receives a total of 92,286 weekly downloads. As such, sweepline-intersections popularity was classified as 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
A record 2,709 developers participated in the 2024 Ruby on Rails Community Survey, revealing key tools, practices, and trends shaping the Rails ecosystem.
Security News
In 2023, data breaches surged 78% from zero-day and supply chain attacks, but developers are still buried under alerts that are unable to prevent these threats.
Security News
Solo open source maintainers face burnout and security challenges, with 60% unpaid and 60% considering quitting.