sweepline-intersections
Advanced tools
sweepline-intersections - npm Package Compare versions
Comparing version 1.0.1 to 1.1.1
@@ -80,15 +80,7 @@ class TinyQueue { | ||
| class Segment { | ||
| constructor (event) { | ||
| this.leftSweepEvent = event; | ||
| this.rightSweepEvent = event.otherEvent; | ||
| } | ||
| } | ||
| function checkWhichEventIsLeft (e1, e2) { | ||
| if (e1.p.x > e2.p.x) return 1; | ||
| if (e1.p.x < e2.p.x) return -1; | ||
| if (e1.p.x > e2.p.x) return 1 | ||
| if (e1.p.x < e2.p.x) return -1 | ||
| if (e1.p.y !== e2.p.y) return e1.p.y > e2.p.y ? 1 : -1; | ||
| if (e1.p.y !== e2.p.y) return e1.p.y > e2.p.y ? 1 : -1 | ||
| return 1 | ||
@@ -98,6 +90,6 @@ } | ||
| function checkWhichSegmentHasRightEndpointFirst (seg1, seg2) { | ||
| if (seg1.rightSweepEvent.p.x > seg2.rightSweepEvent.p.x) return 1; | ||
| if (seg1.rightSweepEvent.p.x < seg2.rightSweepEvent.p.x) return -1; | ||
| if (seg1.rightSweepEvent.p.x > seg2.rightSweepEvent.p.x) return 1 | ||
| if (seg1.rightSweepEvent.p.x < seg2.rightSweepEvent.p.x) return -1 | ||
| if (seg1.rightSweepEvent.p.y !== seg2.rightSweepEvent.p.y) return seg1.rightSweepEvent.p.y < seg2.rightSweepEvent.p.y ? 1 : -1; | ||
| if (seg1.rightSweepEvent.p.y !== seg2.rightSweepEvent.p.y) return seg1.rightSweepEvent.p.y < seg2.rightSweepEvent.p.y ? 1 : -1 | ||
| return 1 | ||
@@ -118,3 +110,3 @@ } | ||
| isSamePoint(eventToCheck) { | ||
| isSamePoint (eventToCheck) { | ||
| return this.p.x === eventToCheck.p.x && this.p.y === eventToCheck.p.y | ||
@@ -125,32 +117,44 @@ } | ||
| function fillEventQueue (geojson, eventQueue) { | ||
| const geom = geojson.type === 'Feature' ? geojson.geometry : geojson; | ||
| if (geojson.type === 'FeatureCollection') { | ||
| const features = geojson.features; | ||
| for (let i = 0; i < features.length; i++) { | ||
| processFeature(features[i], eventQueue); | ||
| } | ||
| } else { | ||
| processFeature(geojson, eventQueue); | ||
| } | ||
| } | ||
| function processFeature (featureOrGeometry, eventQueue) { | ||
| const geom = featureOrGeometry.type === 'Feature' ? featureOrGeometry.geometry : featureOrGeometry; | ||
| let coords = geom.coordinates; | ||
| // standardise the input | ||
| if (geom.type === 'Polygon') coords = [coords]; | ||
| if (geom.type === 'Polygon' || geom.type === 'MultiLineString') coords = [coords]; | ||
| if (geom.type === 'LineString') coords = [[coords]]; | ||
| for (let i = 0; i < coords[0].length; i++) { | ||
| let currentP = coords[0][i][0]; | ||
| let nextP = null; | ||
| for (let i = 0; i < coords.length; i++) { | ||
| for (let ii = 0; ii < coords[i].length; ii++) { | ||
| let currentP = coords[i][ii][0]; | ||
| let nextP = null; | ||
| for (let ii = 0; ii < coords[0][i].length - 1; ii++) { | ||
| nextP = coords[0][i][ii + 1]; | ||
| for (let iii = 0; iii < coords[i][ii].length - 1; iii++) { | ||
| nextP = coords[i][ii][iii + 1]; | ||
| const e1 = new Event(currentP); | ||
| const e2 = new Event(nextP); | ||
| const e1 = new Event(currentP); | ||
| const e2 = new Event(nextP); | ||
| e1.otherEvent = e2; | ||
| e2.otherEvent = e1; | ||
| e1.otherEvent = e2; | ||
| e2.otherEvent = e1; | ||
| if (checkWhichEventIsLeft(e1, e2) > 0) { | ||
| e2.isLeftEndpoint = true; | ||
| e1.isLeftEndpoint = false; | ||
| } else { | ||
| e1.isLeftEndpoint = true; | ||
| e2.isLeftEndpoint = false; | ||
| if (checkWhichEventIsLeft(e1, e2) > 0) { | ||
| e2.isLeftEndpoint = true; | ||
| e1.isLeftEndpoint = false; | ||
| } else { | ||
| e1.isLeftEndpoint = true; | ||
| e2.isLeftEndpoint = false; | ||
| } | ||
| eventQueue.push(e1); | ||
| eventQueue.push(e2); | ||
| currentP = nextP; | ||
| } | ||
| eventQueue.push(e1); | ||
| eventQueue.push(e2); | ||
| currentP = nextP; | ||
| } | ||
@@ -160,47 +164,51 @@ } | ||
| function testSegmentIntersect (seg1, seg2) { | ||
| if (seg1 === null || seg2 === null) return false | ||
| class Segment { | ||
| if (seg1.rightSweepEvent.isSamePoint(seg2.leftSweepEvent) || | ||
| seg1.rightSweepEvent.isSamePoint(seg2.rightSweepEvent) || | ||
| seg1.leftSweepEvent.isSamePoint(seg2.leftSweepEvent) || | ||
| seg1.leftSweepEvent.isSamePoint(seg2.rightSweepEvent)) return false | ||
| constructor (event) { | ||
| this.leftSweepEvent = event; | ||
| this.rightSweepEvent = event.otherEvent; | ||
| } | ||
| } | ||
| const x1 = seg1.leftSweepEvent.p.x; | ||
| const y1 = seg1.leftSweepEvent.p.y; | ||
| const x2 = seg1.rightSweepEvent.p.x; | ||
| const y2 = seg1.rightSweepEvent.p.y; | ||
| const x3 = seg2.leftSweepEvent.p.x; | ||
| const y3 = seg2.leftSweepEvent.p.y; | ||
| const x4 = seg2.rightSweepEvent.p.x; | ||
| const y4 = seg2.rightSweepEvent.p.y; | ||
| function testSegmentIntersect (seg1, seg2) { | ||
| if (seg1 === null || seg2 === null) return false | ||
| const denom = ((y4 - y3) * (x2 - x1)) - ((x4 - x3) * (y2 - y1)); | ||
| const numeA = ((x4 - x3) * (y1 - y3)) - ((y4 - y3) * (x1 - x3)); | ||
| const numeB = ((x2 - x1) * (y1 - y3)) - ((y2 - y1) * (x1 - x3)); | ||
| if (seg1.rightSweepEvent.isSamePoint(seg2.leftSweepEvent) || | ||
| seg1.rightSweepEvent.isSamePoint(seg2.rightSweepEvent) || | ||
| seg1.leftSweepEvent.isSamePoint(seg2.leftSweepEvent) || | ||
| seg1.leftSweepEvent.isSamePoint(seg2.rightSweepEvent)) return false | ||
| if (denom === 0) { | ||
| if (numeA === 0 && numeB === 0) return false | ||
| return false | ||
| } | ||
| const x1 = seg1.leftSweepEvent.p.x; | ||
| const y1 = seg1.leftSweepEvent.p.y; | ||
| const x2 = seg1.rightSweepEvent.p.x; | ||
| const y2 = seg1.rightSweepEvent.p.y; | ||
| const x3 = seg2.leftSweepEvent.p.x; | ||
| const y3 = seg2.leftSweepEvent.p.y; | ||
| const x4 = seg2.rightSweepEvent.p.x; | ||
| const y4 = seg2.rightSweepEvent.p.y; | ||
| const uA = numeA / denom; | ||
| const uB = numeB / denom; | ||
| const denom = ((y4 - y3) * (x2 - x1)) - ((x4 - x3) * (y2 - y1)); | ||
| const numeA = ((x4 - x3) * (y1 - y3)) - ((y4 - y3) * (x1 - x3)); | ||
| const numeB = ((x2 - x1) * (y1 - y3)) - ((y2 - y1) * (x1 - x3)); | ||
| if (uA >= 0 && uA <= 1 && uB >= 0 && uB <= 1) { | ||
| const x = x1 + (uA * (x2 - x1)); | ||
| const y = y1 + (uA * (y2 - y1)); | ||
| return [x, y] | ||
| } | ||
| if (denom === 0) { | ||
| if (numeA === 0 && numeB === 0) return false | ||
| return false | ||
| } | ||
| const uA = numeA / denom; | ||
| const uB = numeB / denom; | ||
| if (uA >= 0 && uA <= 1 && uB >= 0 && uB <= 1) { | ||
| const x = x1 + (uA * (x2 - x1)); | ||
| const y = y1 + (uA * (y2 - y1)); | ||
| return [x, y] | ||
| } | ||
| return false | ||
| } | ||
| // import {debugEventAndSegments, debugRemovingSegment} from './debug' | ||
| function bentleyOttmann (geojson) { | ||
| function runCheck (eventQueue) { | ||
| const intersectionPoints = []; | ||
| const eventQueue = new TinyQueue([], checkWhichEventIsLeft); | ||
| fillEventQueue(geojson, eventQueue); | ||
| const outQueue = new TinyQueue([], checkWhichSegmentHasRightEndpointFirst); | ||
@@ -219,3 +227,4 @@ | ||
| } else if (event.isLeftEndpoint === false) { | ||
| const seg = outQueue.pop(); | ||
| outQueue.pop(); | ||
| // const seg = outQueue.pop() | ||
| // debugRemovingSegment(event.p, seg) | ||
@@ -227,2 +236,8 @@ } | ||
| export default bentleyOttmann; | ||
| function sweeplineIntersections (geojson) { | ||
| const eventQueue = new TinyQueue([], checkWhichEventIsLeft); | ||
| fillEventQueue(geojson, eventQueue); | ||
| return runCheck(eventQueue) | ||
| } | ||
| export default sweeplineIntersections; |
@@ -5,3 +5,3 @@ (function (global, factory) { | ||
| (global = global || self, global.sweeplineIntersections = factory()); | ||
| }(this, function () { 'use strict'; | ||
| }(this, (function () { 'use strict'; | ||
@@ -87,15 +87,7 @@ class TinyQueue { | ||
| class Segment { | ||
| constructor (event) { | ||
| this.leftSweepEvent = event; | ||
| this.rightSweepEvent = event.otherEvent; | ||
| } | ||
| } | ||
| function checkWhichEventIsLeft (e1, e2) { | ||
| if (e1.p.x > e2.p.x) return 1; | ||
| if (e1.p.x < e2.p.x) return -1; | ||
| if (e1.p.x > e2.p.x) return 1 | ||
| if (e1.p.x < e2.p.x) return -1 | ||
| if (e1.p.y !== e2.p.y) return e1.p.y > e2.p.y ? 1 : -1; | ||
| if (e1.p.y !== e2.p.y) return e1.p.y > e2.p.y ? 1 : -1 | ||
| return 1 | ||
@@ -105,6 +97,6 @@ } | ||
| function checkWhichSegmentHasRightEndpointFirst (seg1, seg2) { | ||
| if (seg1.rightSweepEvent.p.x > seg2.rightSweepEvent.p.x) return 1; | ||
| if (seg1.rightSweepEvent.p.x < seg2.rightSweepEvent.p.x) return -1; | ||
| if (seg1.rightSweepEvent.p.x > seg2.rightSweepEvent.p.x) return 1 | ||
| if (seg1.rightSweepEvent.p.x < seg2.rightSweepEvent.p.x) return -1 | ||
| if (seg1.rightSweepEvent.p.y !== seg2.rightSweepEvent.p.y) return seg1.rightSweepEvent.p.y < seg2.rightSweepEvent.p.y ? 1 : -1; | ||
| if (seg1.rightSweepEvent.p.y !== seg2.rightSweepEvent.p.y) return seg1.rightSweepEvent.p.y < seg2.rightSweepEvent.p.y ? 1 : -1 | ||
| return 1 | ||
@@ -125,3 +117,3 @@ } | ||
| isSamePoint(eventToCheck) { | ||
| isSamePoint (eventToCheck) { | ||
| return this.p.x === eventToCheck.p.x && this.p.y === eventToCheck.p.y | ||
@@ -132,32 +124,44 @@ } | ||
| function fillEventQueue (geojson, eventQueue) { | ||
| const geom = geojson.type === 'Feature' ? geojson.geometry : geojson; | ||
| if (geojson.type === 'FeatureCollection') { | ||
| const features = geojson.features; | ||
| for (let i = 0; i < features.length; i++) { | ||
| processFeature(features[i], eventQueue); | ||
| } | ||
| } else { | ||
| processFeature(geojson, eventQueue); | ||
| } | ||
| } | ||
| function processFeature (featureOrGeometry, eventQueue) { | ||
| const geom = featureOrGeometry.type === 'Feature' ? featureOrGeometry.geometry : featureOrGeometry; | ||
| let coords = geom.coordinates; | ||
| // standardise the input | ||
| if (geom.type === 'Polygon') coords = [coords]; | ||
| if (geom.type === 'Polygon' || geom.type === 'MultiLineString') coords = [coords]; | ||
| if (geom.type === 'LineString') coords = [[coords]]; | ||
| for (let i = 0; i < coords[0].length; i++) { | ||
| let currentP = coords[0][i][0]; | ||
| let nextP = null; | ||
| for (let i = 0; i < coords.length; i++) { | ||
| for (let ii = 0; ii < coords[i].length; ii++) { | ||
| let currentP = coords[i][ii][0]; | ||
| let nextP = null; | ||
| for (let ii = 0; ii < coords[0][i].length - 1; ii++) { | ||
| nextP = coords[0][i][ii + 1]; | ||
| for (let iii = 0; iii < coords[i][ii].length - 1; iii++) { | ||
| nextP = coords[i][ii][iii + 1]; | ||
| const e1 = new Event(currentP); | ||
| const e2 = new Event(nextP); | ||
| const e1 = new Event(currentP); | ||
| const e2 = new Event(nextP); | ||
| e1.otherEvent = e2; | ||
| e2.otherEvent = e1; | ||
| e1.otherEvent = e2; | ||
| e2.otherEvent = e1; | ||
| if (checkWhichEventIsLeft(e1, e2) > 0) { | ||
| e2.isLeftEndpoint = true; | ||
| e1.isLeftEndpoint = false; | ||
| } else { | ||
| e1.isLeftEndpoint = true; | ||
| e2.isLeftEndpoint = false; | ||
| if (checkWhichEventIsLeft(e1, e2) > 0) { | ||
| e2.isLeftEndpoint = true; | ||
| e1.isLeftEndpoint = false; | ||
| } else { | ||
| e1.isLeftEndpoint = true; | ||
| e2.isLeftEndpoint = false; | ||
| } | ||
| eventQueue.push(e1); | ||
| eventQueue.push(e2); | ||
| currentP = nextP; | ||
| } | ||
| eventQueue.push(e1); | ||
| eventQueue.push(e2); | ||
| currentP = nextP; | ||
| } | ||
@@ -167,47 +171,51 @@ } | ||
| function testSegmentIntersect (seg1, seg2) { | ||
| if (seg1 === null || seg2 === null) return false | ||
| class Segment { | ||
| if (seg1.rightSweepEvent.isSamePoint(seg2.leftSweepEvent) || | ||
| seg1.rightSweepEvent.isSamePoint(seg2.rightSweepEvent) || | ||
| seg1.leftSweepEvent.isSamePoint(seg2.leftSweepEvent) || | ||
| seg1.leftSweepEvent.isSamePoint(seg2.rightSweepEvent)) return false | ||
| constructor (event) { | ||
| this.leftSweepEvent = event; | ||
| this.rightSweepEvent = event.otherEvent; | ||
| } | ||
| } | ||
| const x1 = seg1.leftSweepEvent.p.x; | ||
| const y1 = seg1.leftSweepEvent.p.y; | ||
| const x2 = seg1.rightSweepEvent.p.x; | ||
| const y2 = seg1.rightSweepEvent.p.y; | ||
| const x3 = seg2.leftSweepEvent.p.x; | ||
| const y3 = seg2.leftSweepEvent.p.y; | ||
| const x4 = seg2.rightSweepEvent.p.x; | ||
| const y4 = seg2.rightSweepEvent.p.y; | ||
| function testSegmentIntersect (seg1, seg2) { | ||
| if (seg1 === null || seg2 === null) return false | ||
| const denom = ((y4 - y3) * (x2 - x1)) - ((x4 - x3) * (y2 - y1)); | ||
| const numeA = ((x4 - x3) * (y1 - y3)) - ((y4 - y3) * (x1 - x3)); | ||
| const numeB = ((x2 - x1) * (y1 - y3)) - ((y2 - y1) * (x1 - x3)); | ||
| if (seg1.rightSweepEvent.isSamePoint(seg2.leftSweepEvent) || | ||
| seg1.rightSweepEvent.isSamePoint(seg2.rightSweepEvent) || | ||
| seg1.leftSweepEvent.isSamePoint(seg2.leftSweepEvent) || | ||
| seg1.leftSweepEvent.isSamePoint(seg2.rightSweepEvent)) return false | ||
| if (denom === 0) { | ||
| if (numeA === 0 && numeB === 0) return false | ||
| return false | ||
| } | ||
| const x1 = seg1.leftSweepEvent.p.x; | ||
| const y1 = seg1.leftSweepEvent.p.y; | ||
| const x2 = seg1.rightSweepEvent.p.x; | ||
| const y2 = seg1.rightSweepEvent.p.y; | ||
| const x3 = seg2.leftSweepEvent.p.x; | ||
| const y3 = seg2.leftSweepEvent.p.y; | ||
| const x4 = seg2.rightSweepEvent.p.x; | ||
| const y4 = seg2.rightSweepEvent.p.y; | ||
| const uA = numeA / denom; | ||
| const uB = numeB / denom; | ||
| const denom = ((y4 - y3) * (x2 - x1)) - ((x4 - x3) * (y2 - y1)); | ||
| const numeA = ((x4 - x3) * (y1 - y3)) - ((y4 - y3) * (x1 - x3)); | ||
| const numeB = ((x2 - x1) * (y1 - y3)) - ((y2 - y1) * (x1 - x3)); | ||
| if (uA >= 0 && uA <= 1 && uB >= 0 && uB <= 1) { | ||
| const x = x1 + (uA * (x2 - x1)); | ||
| const y = y1 + (uA * (y2 - y1)); | ||
| return [x, y] | ||
| } | ||
| if (denom === 0) { | ||
| if (numeA === 0 && numeB === 0) return false | ||
| return false | ||
| } | ||
| const uA = numeA / denom; | ||
| const uB = numeB / denom; | ||
| if (uA >= 0 && uA <= 1 && uB >= 0 && uB <= 1) { | ||
| const x = x1 + (uA * (x2 - x1)); | ||
| const y = y1 + (uA * (y2 - y1)); | ||
| return [x, y] | ||
| } | ||
| return false | ||
| } | ||
| // import {debugEventAndSegments, debugRemovingSegment} from './debug' | ||
| function bentleyOttmann (geojson) { | ||
| function runCheck (eventQueue) { | ||
| const intersectionPoints = []; | ||
| const eventQueue = new TinyQueue([], checkWhichEventIsLeft); | ||
| fillEventQueue(geojson, eventQueue); | ||
| const outQueue = new TinyQueue([], checkWhichSegmentHasRightEndpointFirst); | ||
@@ -226,3 +234,4 @@ | ||
| } else if (event.isLeftEndpoint === false) { | ||
| const seg = outQueue.pop(); | ||
| outQueue.pop(); | ||
| // const seg = outQueue.pop() | ||
| // debugRemovingSegment(event.p, seg) | ||
@@ -234,4 +243,10 @@ } | ||
| return bentleyOttmann; | ||
| function sweeplineIntersections (geojson) { | ||
| const eventQueue = new TinyQueue([], checkWhichEventIsLeft); | ||
| fillEventQueue(geojson, eventQueue); | ||
| return runCheck(eventQueue) | ||
| } | ||
| })); | ||
| return sweeplineIntersections; | ||
| }))); |
@@ -1,1 +0,1 @@ | ||
| !function(t,e){"object"==typeof exports&&"undefined"!=typeof module?module.exports=e():"function"==typeof define&&define.amd?define(e):(t=t||self).sweeplineIntersections=e()}(this,function(){"use strict";class t{constructor(t=[],e=function(t,e){return t<e?-1:t>e?1:0}){if(this.data=t,this.length=this.data.length,this.compare=e,this.length>0)for(let t=(this.length>>1)-1;t>=0;t--)this._down(t)}push(t){this.data.push(t),this.length++,this._up(this.length-1)}pop(){if(0===this.length)return;const t=this.data[0];return this.length--,this.length>0&&(this.data[0]=this.data[this.length],this._down(0)),this.data.pop(),t}peek(){return this.data[0]}_up(t){const{data:e,compare:n}=this,i=e[t];for(;t>0;){const p=t-1>>1,s=e[p];if(n(i,s)>=0)break;e[t]=s,t=p}e[t]=i}_down(t){const{data:e,compare:n}=this,i=this.length>>1,p=e[t];for(;t<i;){let i=1+(t<<1),s=e[i];const h=i+1;if(h<this.length&&n(e[h],s)<0&&(i=h,s=e[h]),n(s,p)>=0)break;e[t]=s,t=i}e[t]=p}}class e{constructor(t){this.leftSweepEvent=t,this.rightSweepEvent=t.otherEvent}}function n(t,e){return t.p.x>e.p.x?1:t.p.x<e.p.x?-1:t.p.y!==e.p.y?t.p.y>e.p.y?1:-1:1}function i(t,e){return t.rightSweepEvent.p.x>e.rightSweepEvent.p.x?1:t.rightSweepEvent.p.x<e.rightSweepEvent.p.x?-1:t.rightSweepEvent.p.y!==e.rightSweepEvent.p.y?t.rightSweepEvent.p.y<e.rightSweepEvent.p.y?1:-1:1}class p{constructor(t){this.p={x:t[0],y:t[1]},this.otherEvent=null,this.isLeftEndpoint=null}isSamePoint(t){return this.p.x===t.p.x&&this.p.y===t.p.y}}function s(t,e){if(null===t||null===e)return!1;if(t.rightSweepEvent.isSamePoint(e.leftSweepEvent)||t.rightSweepEvent.isSamePoint(e.rightSweepEvent)||t.leftSweepEvent.isSamePoint(e.leftSweepEvent)||t.leftSweepEvent.isSamePoint(e.rightSweepEvent))return!1;const n=t.leftSweepEvent.p.x,i=t.leftSweepEvent.p.y,p=t.rightSweepEvent.p.x,s=t.rightSweepEvent.p.y,h=e.leftSweepEvent.p.x,o=e.leftSweepEvent.p.y,r=e.rightSweepEvent.p.x,l=e.rightSweepEvent.p.y,f=(l-o)*(p-n)-(r-h)*(s-i),u=(r-h)*(i-o)-(l-o)*(n-h),a=(p-n)*(i-o)-(s-i)*(n-h);if(0===f)return!1;const c=u/f,E=a/f;if(c>=0&&c<=1&&E>=0&&E<=1){return[n+c*(p-n),i+c*(s-i)]}return!1}return function(h){const o=[],r=new t([],n);!function(t,e){const i="Feature"===t.type?t.geometry:t;let s=i.coordinates;"Polygon"===i.type&&(s=[s]);for(let t=0;t<s[0].length;t++){let i=s[0][t][0],h=null;for(let o=0;o<s[0][t].length-1;o++){h=s[0][t][o+1];const r=new p(i),l=new p(h);r.otherEvent=l,l.otherEvent=r,n(r,l)>0?(l.isLeftEndpoint=!0,r.isLeftEndpoint=!1):(r.isLeftEndpoint=!0,l.isLeftEndpoint=!1),e.push(r),e.push(l),i=h}}}(h,r);const l=new t([],i);for(;r.length;){const t=r.pop();if(t.isLeftEndpoint){const n=new e(t);for(let t=0;t<l.data.length;t++){const e=s(n,l.data[t]);!1!==e&&o.push(e)}l.push(n)}else!1===t.isLeftEndpoint&&l.pop()}return o}}); | ||
| !function(t,e){"object"==typeof exports&&"undefined"!=typeof module?module.exports=e():"function"==typeof define&&define.amd?define(e):(t=t||self).sweeplineIntersections=e()}(this,function(){"use strict";class t{constructor(t=[],e=function(t,e){return t<e?-1:t>e?1:0}){if(this.data=t,this.length=this.data.length,this.compare=e,this.length>0)for(let t=(this.length>>1)-1;t>=0;t--)this._down(t)}push(t){this.data.push(t),this.length++,this._up(this.length-1)}pop(){if(0===this.length)return;const t=this.data[0];return this.length--,this.length>0&&(this.data[0]=this.data[this.length],this._down(0)),this.data.pop(),t}peek(){return this.data[0]}_up(t){const{data:e,compare:n}=this,i=e[t];for(;t>0;){const p=t-1>>1,s=e[p];if(n(i,s)>=0)break;e[t]=s,t=p}e[t]=i}_down(t){const{data:e,compare:n}=this,i=this.length>>1,p=e[t];for(;t<i;){let i=1+(t<<1),s=e[i];const o=i+1;if(o<this.length&&n(e[o],s)<0&&(i=o,s=e[o]),n(s,p)>=0)break;e[t]=s,t=i}e[t]=p}}function e(t,e){return t.p.x>e.p.x?1:t.p.x<e.p.x?-1:t.p.y!==e.p.y?t.p.y>e.p.y?1:-1:1}function n(t,e){return t.rightSweepEvent.p.x>e.rightSweepEvent.p.x?1:t.rightSweepEvent.p.x<e.rightSweepEvent.p.x?-1:t.rightSweepEvent.p.y!==e.rightSweepEvent.p.y?t.rightSweepEvent.p.y<e.rightSweepEvent.p.y?1:-1:1}class i{constructor(t){this.p={x:t[0],y:t[1]},this.otherEvent=null,this.isLeftEndpoint=null}isSamePoint(t){return this.p.x===t.p.x&&this.p.y===t.p.y}}function p(t,n){const p="Feature"===t.type?t.geometry:t;let s=p.coordinates;"Polygon"!==p.type&&"MultiLineString"!==p.type||(s=[s]),"LineString"===p.type&&(s=[[s]]);for(let t=0;t<s.length;t++)for(let p=0;p<s[t].length;p++){let o=s[t][p][0],r=null;for(let h=0;h<s[t][p].length-1;h++){r=s[t][p][h+1];const l=new i(o),f=new i(r);l.otherEvent=f,f.otherEvent=l,e(l,f)>0?(f.isLeftEndpoint=!0,l.isLeftEndpoint=!1):(l.isLeftEndpoint=!0,f.isLeftEndpoint=!1),n.push(l),n.push(f),o=r}}}class s{constructor(t){this.leftSweepEvent=t,this.rightSweepEvent=t.otherEvent}}function o(t,e){if(null===t||null===e)return!1;if(t.rightSweepEvent.isSamePoint(e.leftSweepEvent)||t.rightSweepEvent.isSamePoint(e.rightSweepEvent)||t.leftSweepEvent.isSamePoint(e.leftSweepEvent)||t.leftSweepEvent.isSamePoint(e.rightSweepEvent))return!1;const n=t.leftSweepEvent.p.x,i=t.leftSweepEvent.p.y,p=t.rightSweepEvent.p.x,s=t.rightSweepEvent.p.y,o=e.leftSweepEvent.p.x,r=e.leftSweepEvent.p.y,h=e.rightSweepEvent.p.x,l=e.rightSweepEvent.p.y,f=(l-r)*(p-n)-(h-o)*(s-i),u=(h-o)*(i-r)-(l-r)*(n-o),c=(p-n)*(i-r)-(s-i)*(n-o);if(0===f)return!1;const a=u/f,g=c/f;if(a>=0&&a<=1&&g>=0&&g<=1){return[n+a*(p-n),i+a*(s-i)]}return!1}return function(i){const r=new t([],e);return function(t,e){if("FeatureCollection"===t.type){const n=t.features;for(let t=0;t<n.length;t++)p(n[t],e)}else p(t,e)}(i,r),function(e){const i=[],p=new t([],n);for(;e.length;){const t=e.pop();if(t.isLeftEndpoint){const e=new s(t);for(let t=0;t<p.data.length;t++){const n=o(e,p.data[t]);!1!==n&&i.push(n)}p.push(e)}else!1===t.isLeftEndpoint&&p.pop()}return i}(r)}}); |
| { | ||
| "name": "sweepline-intersections", | ||
| "version": "1.0.1", | ||
| "version": "1.1.1", | ||
| "description": "A module to check if a polygon self-intersects using a sweepline algorithm", | ||
@@ -32,2 +32,5 @@ "main": "dist/sweeplineIntersections.js", | ||
| "2d-polygon-self-intersections": "^1.3.1", | ||
| "@rollup/plugin-commonjs": "^11.1.0", | ||
| "@rollup/plugin-node-resolve": "^7.1.3", | ||
| "@rollup/plugin-strip": "^1.3.2", | ||
| "ava": "^1.0.1", | ||
@@ -48,6 +51,3 @@ "benchmark": "^2.1.4", | ||
| "nyc": "^13.1.0", | ||
| "rollup": "^1.16.2", | ||
| "rollup-plugin-commonjs": "^10.0.1", | ||
| "rollup-plugin-node-resolve": "^4.0.0", | ||
| "rollup-plugin-strip": "^1.2.1", | ||
| "rollup": "^2.7.6", | ||
| "rollup-plugin-terser": "^4.0.2", | ||
@@ -54,0 +54,0 @@ "vue": "^2.5.22", |
| # sweepline-intersections | ||
| A small module using a sweepline algorithm to detect self-intersections in polygons or polylines. | ||
| A small and fast module using a sweepline algorithm to detect intersections between polygons and/or polylines. | ||
| ## Install | ||
| ## Documentation | ||
| ### Install | ||
| ```` | ||
@@ -9,5 +11,7 @@ npm install sweepline-intersections | ||
| ## Documentation | ||
| Valid inputs: Geojson `Polygon`, `MultiPolygon`, `LineString`, `MultiLineString` | ||
| ### Basic Use | ||
| Valid inputs: Geojson `Feature` or `Geometry` including `Polygon`, `LineString`, `MultiPolygon`, `MultiLineString`, as well as `FeatureCollection`'s. | ||
| Returns an array[{x, y}] of intersection points | ||
| ````js | ||
@@ -17,7 +21,39 @@ 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 | ||
| const intersections = findIntersections(box) | ||
| // returns an array of intersection points | ||
| ```` | ||
| ### Complex Use | ||
| 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. | ||
| ````js | ||
| 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() | ||
| }) | ||
| ```` | ||
| #### 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 | ||
| `.intersect()` - Checks for segment intersections. Returns `true` if there are no segment intersections or `false` if there are intersections. | ||
| ## Benchmarks | ||
@@ -34,3 +70,3 @@ Tested against | ||
| // isects x 14.29 ops/sec ±2.16% (40 runs sampled) | ||
| // - Fastest is sweepline | ||
| // - Fastest is sweepline (this library) | ||
@@ -41,3 +77,8 @@ // Simple Case (6 vertices) | ||
| // sweepline x 1,157,425 ops/sec ±1.04% (94 runs sampled) | ||
| // - Fastest is sweepline | ||
| // - 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) | ||
| ```` | ||
@@ -60,6 +101,7 @@ | ||
| 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. | ||
| 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. | ||
| 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 | ||
@@ -66,0 +108,0 @@ - Vertices are entered into a priority queue sorted from left to right |
@@ -1,5 +0,5 @@ | ||
| import commonjs from 'rollup-plugin-commonjs'; | ||
| import resolve from 'rollup-plugin-node-resolve' | ||
| import commonjs from '@rollup/plugin-commonjs' | ||
| import resolve from '@rollup/plugin-node-resolve' | ||
| import strip from '@rollup/plugin-strip' | ||
| import {terser} from 'rollup-plugin-terser' | ||
| import strip from 'rollup-plugin-strip' | ||
@@ -6,0 +6,0 @@ const output = (file, format, plugins) => ({ |
Sorry, the diff of this file is not supported yet
New alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Fixed alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Improved metrics
- Number of lines in readme file
- increased by61.76%
110
Worsened metrics
- Total package byte prevSize
- decreased by-7.04%
27576
- Number of package files
- decreased by-40%
9
- Lines of code
- decreased by-20.59%
432
No dependency changes