sweepline-intersections - npm Package Compare versions

Comparing version 1.2.2 to 1.3.0

CHANGELOG.md

@@ -0,1 +1,4 @@
+## 1.3.0
+- Add a second argument, `ignoreSelfIntersections` which only checks for intersections between different features.
+
 ## 1.2.2
@@ -2,0 +5,0 @@ - Fix the missing dist files for the class-based approach

dist/sweeplineIntersections.esm.js

@@ -98,3 +98,3 @@ class TinyQueue {
 
-    constructor (p, ringId) {
+    constructor (p, featureId, ringId, eventId) {
         this.p = {
@@ -104,3 +104,5 @@ x: p[0],
         };
+        this.featureId = featureId;
         this.ringId = ringId;
+        this.eventId = eventId;
 
@@ -127,3 +129,5 @@ this.otherEvent = null;
 
+let featureId = 0;
 let ringId = 0;
+let eventId = 0;
 function processFeature (featureOrGeometry, eventQueue) {
@@ -144,4 +148,4 @@ const geom = featureOrGeometry.type === 'Feature' ? featureOrGeometry.geometry : featureOrGeometry;
 
-                const e1 = new Event(currentP, ringId);
-                const e2 = new Event(nextP, ringId);
+                const e1 = new Event(currentP, featureId, ringId, eventId);
+                const e2 = new Event(nextP, featureId, ringId, eventId + 1);
 
@@ -162,5 +166,7 @@ e1.otherEvent = e2;
                 currentP = nextP;
+                eventId = eventId + 1;
             }
         }
     }
+    featureId = featureId + 1;
 }
@@ -210,3 +216,10 @@
         const y = y1 + (uA * (y2 - y1));
-        return [x, y]
+        return {
+            x,
+            y,
+            seg1Left: seg1.leftSweepEvent.eventId,
+            seg1Right: seg1.rightSweepEvent.eventId,
+            seg2Left: seg2.leftSweepEvent.eventId,
+            seg2Right: seg2.rightSweepEvent.eventId,
+        }
     }
@@ -218,3 +231,5 @@ return false
 
-function runCheck (eventQueue) {
+function runCheck (eventQueue, ignoreSelfIntersections) {
+    ignoreSelfIntersections = ignoreSelfIntersections ? ignoreSelfIntersections : false;
+
     const intersectionPoints = [];
@@ -229,3 +244,7 @@ const outQueue = new TinyQueue([], checkWhichSegmentHasRightEndpointFirst);
             for (let i = 0; i < outQueue.data.length; i++) {
-                const intersection = testSegmentIntersect(segment, outQueue.data[i]);
+                const otherSeg = outQueue.data[i];
+                if (ignoreSelfIntersections) {
+                    if (otherSeg.leftSweepEvent.featureId === event.featureId) continue
+                }
+                const intersection = testSegmentIntersect(segment, otherSeg);
                 if (intersection !== false) intersectionPoints.push(intersection);
@@ -243,8 +262,8 @@ }
 
-function sweeplineIntersections (geojson) {
+function sweeplineIntersections (geojson, ignoreSelfIntersections) {
     const eventQueue = new TinyQueue([], checkWhichEventIsLeft);
     fillEventQueue(geojson, eventQueue);
-    return runCheck(eventQueue)
+    return runCheck(eventQueue, ignoreSelfIntersections)
 }
 
 export default sweeplineIntersections;

dist/sweeplineIntersections.js

@@ -104,3 +104,3 @@ (function (global, factory) {
 
-        constructor (p, ringId) {
+        constructor (p, featureId, ringId, eventId) {
             this.p = {
@@ -110,3 +110,5 @@ x: p[0],
             };
+            this.featureId = featureId;
             this.ringId = ringId;
+            this.eventId = eventId;
 
@@ -133,3 +135,5 @@ this.otherEvent = null;
 
+    let featureId = 0;
     let ringId = 0;
+    let eventId = 0;
     function processFeature (featureOrGeometry, eventQueue) {
@@ -150,4 +154,4 @@ const geom = featureOrGeometry.type === 'Feature' ? featureOrGeometry.geometry : featureOrGeometry;
 
-                    const e1 = new Event(currentP, ringId);
-                    const e2 = new Event(nextP, ringId);
+                    const e1 = new Event(currentP, featureId, ringId, eventId);
+                    const e2 = new Event(nextP, featureId, ringId, eventId + 1);
 
@@ -168,5 +172,7 @@ e1.otherEvent = e2;
                     currentP = nextP;
+                    eventId = eventId + 1;
                 }
             }
         }
+        featureId = featureId + 1;
     }
@@ -216,3 +222,10 @@
             const y = y1 + (uA * (y2 - y1));
-            return [x, y]
+            return {
+                x,
+                y,
+                seg1Left: seg1.leftSweepEvent.eventId,
+                seg1Right: seg1.rightSweepEvent.eventId,
+                seg2Left: seg2.leftSweepEvent.eventId,
+                seg2Right: seg2.rightSweepEvent.eventId,
+            }
         }
@@ -224,3 +237,5 @@ return false
 
-    function runCheck (eventQueue) {
+    function runCheck (eventQueue, ignoreSelfIntersections) {
+        ignoreSelfIntersections = ignoreSelfIntersections ? ignoreSelfIntersections : false;
+
         const intersectionPoints = [];
@@ -235,3 +250,7 @@ const outQueue = new TinyQueue([], checkWhichSegmentHasRightEndpointFirst);
                 for (let i = 0; i < outQueue.data.length; i++) {
-                    const intersection = testSegmentIntersect(segment, outQueue.data[i]);
+                    const otherSeg = outQueue.data[i];
+                    if (ignoreSelfIntersections) {
+                        if (otherSeg.leftSweepEvent.featureId === event.featureId) continue
+                    }
+                    const intersection = testSegmentIntersect(segment, otherSeg);
                     if (intersection !== false) intersectionPoints.push(intersection);
@@ -249,6 +268,6 @@ }
 
-    function sweeplineIntersections (geojson) {
+    function sweeplineIntersections (geojson, ignoreSelfIntersections) {
         const eventQueue = new TinyQueue([], checkWhichEventIsLeft);
         fillEventQueue(geojson, eventQueue);
-        return runCheck(eventQueue)
+        return runCheck(eventQueue, ignoreSelfIntersections)
     }
@@ -255,0 +274,0 @@

dist/sweeplineIntersections.min.js

@@ -1,1 +0,1 @@
-!function(t,e){"object"==typeof exports&&"undefined"!=typeof module?module.exports=e():"function"==typeof define&&define.amd?define(e):(t="undefined"!=typeof globalThis?globalThis: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],e=this.data.pop();return this.length--,this.length>0&&(this.data[0]=e,this._down(0)),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,e){this.p={x:t[0],y:t[1]},this.ringId=e,this.otherEvent=null,this.isLeftEndpoint=null}isSamePoint(t){return this.p.x===t.p.x&&this.p.y===t.p.y}}let p=0;function s(t,n){const s="Feature"===t.type?t.geometry:t;let o=s.coordinates;"Polygon"!==s.type&&"MultiLineString"!==s.type||(o=[o]),"LineString"===s.type&&(o=[[o]]);for(let t=0;t<o.length;t++)for(let s=0;s<o[t].length;s++){let r=o[t][s][0],h=null;p+=1;for(let l=0;l<o[t][s].length-1;l++){h=o[t][s][l+1];const f=new i(r,p),u=new i(h,p);f.otherEvent=u,u.otherEvent=f,e(f,u)>0?(u.isLeftEndpoint=!0,f.isLeftEndpoint=!1):(f.isLeftEndpoint=!0,u.isLeftEndpoint=!1),n.push(f),n.push(u),r=h}}}class o{constructor(t){this.leftSweepEvent=t,this.rightSweepEvent=t.otherEvent}}function r(t,e){if(null===t||null===e)return!1;if(t.leftSweepEvent.ringId===e.leftSweepEvent.ringId&&(t.rightSweepEvent.isSamePoint(e.leftSweepEvent)||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),g=(p-n)*(i-r)-(s-i)*(n-o);if(0===f)return!1;const a=u/f,c=g/f;if(a>=0&&a<=1&&c>=0&&c<=1){return[n+a*(p-n),i+a*(s-i)]}return!1}return function(i){const p=new t([],e);return function(t,e){if("FeatureCollection"===t.type){const n=t.features;for(let t=0;t<n.length;t++)s(n[t],e)}else s(t,e)}(i,p),function(e){const i=[],p=new t([],n);for(;e.length;){const t=e.pop();if(t.isLeftEndpoint){const e=new o(t);for(let t=0;t<p.data.length;t++){const n=r(e,p.data[t]);!1!==n&&i.push(n)}p.push(e)}else!1===t.isLeftEndpoint&&p.pop()}return i}(p)}});
+!function(e,t){"object"==typeof exports&&"undefined"!=typeof module?module.exports=t():"function"==typeof define&&define.amd?define(t):(e="undefined"!=typeof globalThis?globalThis:e||self).sweeplineIntersections=t()}(this,function(){"use strict";class e{constructor(e=[],t=function(e,t){return e<t?-1:e>t?1:0}){if(this.data=e,this.length=this.data.length,this.compare=t,this.length>0)for(let e=(this.length>>1)-1;e>=0;e--)this._down(e)}push(e){this.data.push(e),this.length++,this._up(this.length-1)}pop(){if(0===this.length)return;const e=this.data[0],t=this.data.pop();return this.length--,this.length>0&&(this.data[0]=t,this._down(0)),e}peek(){return this.data[0]}_up(e){const{data:t,compare:n}=this,i=t[e];for(;e>0;){const p=e-1>>1,s=t[p];if(n(i,s)>=0)break;t[e]=s,e=p}t[e]=i}_down(e){const{data:t,compare:n}=this,i=this.length>>1,p=t[e];for(;e<i;){let i=1+(e<<1),s=t[i];const r=i+1;if(r<this.length&&n(t[r],s)<0&&(i=r,s=t[r]),n(s,p)>=0)break;t[e]=s,e=i}t[e]=p}}function t(e,t){return e.p.x>t.p.x?1:e.p.x<t.p.x?-1:e.p.y!==t.p.y?e.p.y>t.p.y?1:-1:1}function n(e,t){return e.rightSweepEvent.p.x>t.rightSweepEvent.p.x?1:e.rightSweepEvent.p.x<t.rightSweepEvent.p.x?-1:e.rightSweepEvent.p.y!==t.rightSweepEvent.p.y?e.rightSweepEvent.p.y<t.rightSweepEvent.p.y?1:-1:1}class i{constructor(e,t,n,i){this.p={x:e[0],y:e[1]},this.featureId=t,this.ringId=n,this.eventId=i,this.otherEvent=null,this.isLeftEndpoint=null}isSamePoint(e){return this.p.x===e.p.x&&this.p.y===e.p.y}}let p=0,s=0,r=0;function o(e,n){const o="Feature"===e.type?e.geometry:e;let h=o.coordinates;"Polygon"!==o.type&&"MultiLineString"!==o.type||(h=[h]),"LineString"===o.type&&(h=[[h]]);for(let e=0;e<h.length;e++)for(let o=0;o<h[e].length;o++){let f=h[e][o][0],l=null;s+=1;for(let u=0;u<h[e][o].length-1;u++){l=h[e][o][u+1];const g=new i(f,p,s,r),a=new i(l,p,s,r+1);g.otherEvent=a,a.otherEvent=g,t(g,a)>0?(a.isLeftEndpoint=!0,g.isLeftEndpoint=!1):(g.isLeftEndpoint=!0,a.isLeftEndpoint=!1),n.push(g),n.push(a),f=l,r+=1}}p+=1}class h{constructor(e){this.leftSweepEvent=e,this.rightSweepEvent=e.otherEvent}}function f(e,t){if(null===e||null===t)return!1;if(e.leftSweepEvent.ringId===t.leftSweepEvent.ringId&&(e.rightSweepEvent.isSamePoint(t.leftSweepEvent)||e.rightSweepEvent.isSamePoint(t.leftSweepEvent)||e.rightSweepEvent.isSamePoint(t.rightSweepEvent)||e.leftSweepEvent.isSamePoint(t.leftSweepEvent)||e.leftSweepEvent.isSamePoint(t.rightSweepEvent)))return!1;const n=e.leftSweepEvent.p.x,i=e.leftSweepEvent.p.y,p=e.rightSweepEvent.p.x,s=e.rightSweepEvent.p.y,r=t.leftSweepEvent.p.x,o=t.leftSweepEvent.p.y,h=t.rightSweepEvent.p.x,f=t.rightSweepEvent.p.y,l=(f-o)*(p-n)-(h-r)*(s-i),u=(h-r)*(i-o)-(f-o)*(n-r),g=(p-n)*(i-o)-(s-i)*(n-r);if(0===l)return!1;const a=u/l,E=g/l;if(a>=0&&a<=1&&E>=0&&E<=1){return{x:n+a*(p-n),y:i+a*(s-i),seg1Left:e.leftSweepEvent.eventId,seg1Right:e.rightSweepEvent.eventId,seg2Left:t.leftSweepEvent.eventId,seg2Right:t.rightSweepEvent.eventId}}return!1}return function(i,p){const s=new e([],t);return function(e,t){if("FeatureCollection"===e.type){const n=e.features;for(let e=0;e<n.length;e++)o(n[e],t)}else o(e,t)}(i,s),function(t,i){i=i||!1;const p=[],s=new e([],n);for(;t.length;){const e=t.pop();if(e.isLeftEndpoint){const t=new h(e);for(let n=0;n<s.data.length;n++){const r=s.data[n];if(i&&r.leftSweepEvent.featureId===e.featureId)continue;const o=f(t,r);!1!==o&&p.push(o)}s.push(t)}else!1===e.isLeftEndpoint&&s.pop()}return p}(s,p)}});

dist/SweeplineIntersectionsClass.esm.js

@@ -98,3 +98,3 @@ class TinyQueue {
 
-    constructor (p, ringId) {
+    constructor (p, featureId, ringId, eventId) {
         this.p = {
@@ -104,3 +104,5 @@ x: p[0],
         };
+        this.featureId = featureId;
         this.ringId = ringId;
+        this.eventId = eventId;
 
@@ -127,3 +129,5 @@ this.otherEvent = null;
 
+let featureId = 0;
 let ringId = 0;
+let eventId = 0;
 function processFeature (featureOrGeometry, eventQueue) {
@@ -144,4 +148,4 @@ const geom = featureOrGeometry.type === 'Feature' ? featureOrGeometry.geometry : featureOrGeometry;
 
-                const e1 = new Event(currentP, ringId);
-                const e2 = new Event(nextP, ringId);
+                const e1 = new Event(currentP, featureId, ringId, eventId);
+                const e2 = new Event(nextP, featureId, ringId, eventId + 1);
 
@@ -162,5 +166,7 @@ e1.otherEvent = e2;
                 currentP = nextP;
+                eventId = eventId + 1;
             }
         }
     }
+    featureId = featureId + 1;
 }
@@ -210,3 +216,10 @@
         const y = y1 + (uA * (y2 - y1));
-        return [x, y]
+        return {
+            x,
+            y,
+            seg1Left: seg1.leftSweepEvent.eventId,
+            seg1Right: seg1.rightSweepEvent.eventId,
+            seg2Left: seg2.leftSweepEvent.eventId,
+            seg2Right: seg2.rightSweepEvent.eventId,
+        }
     }
@@ -218,3 +231,5 @@ return false
 
-function runCheck (eventQueue) {
+function runCheck (eventQueue, ignoreSelfIntersections) {
+    ignoreSelfIntersections = ignoreSelfIntersections ? ignoreSelfIntersections : false;
+
     const intersectionPoints = [];
@@ -229,3 +244,7 @@ const outQueue = new TinyQueue([], checkWhichSegmentHasRightEndpointFirst);
             for (let i = 0; i < outQueue.data.length; i++) {
-                const intersection = testSegmentIntersect(segment, outQueue.data[i]);
+                const otherSeg = outQueue.data[i];
+                if (ignoreSelfIntersections) {
+                    if (otherSeg.leftSweepEvent.featureId === event.featureId) continue
+                }
+                const intersection = testSegmentIntersect(segment, otherSeg);
                 if (intersection !== false) intersectionPoints.push(intersection);
@@ -268,4 +287,4 @@ }
 
-    getIntersections () {
-        return runCheck(this._eventQueue)
+    getIntersections (ignoreSelfIntersections) {
+        return runCheck(this._eventQueue, ignoreSelfIntersections)
     }
@@ -272,0 +291,0 @@ }

dist/SweeplineIntersectionsClass.js

@@ -104,3 +104,3 @@ (function (global, factory) {
 
-        constructor (p, ringId) {
+        constructor (p, featureId, ringId, eventId) {
             this.p = {
@@ -110,3 +110,5 @@ x: p[0],
             };
+            this.featureId = featureId;
             this.ringId = ringId;
+            this.eventId = eventId;
 
@@ -133,3 +135,5 @@ this.otherEvent = null;
 
+    let featureId = 0;
     let ringId = 0;
+    let eventId = 0;
     function processFeature (featureOrGeometry, eventQueue) {
@@ -150,4 +154,4 @@ const geom = featureOrGeometry.type === 'Feature' ? featureOrGeometry.geometry : featureOrGeometry;
 
-                    const e1 = new Event(currentP, ringId);
-                    const e2 = new Event(nextP, ringId);
+                    const e1 = new Event(currentP, featureId, ringId, eventId);
+                    const e2 = new Event(nextP, featureId, ringId, eventId + 1);
 
@@ -168,5 +172,7 @@ e1.otherEvent = e2;
                     currentP = nextP;
+                    eventId = eventId + 1;
                 }
             }
         }
+        featureId = featureId + 1;
     }
@@ -216,3 +222,10 @@
             const y = y1 + (uA * (y2 - y1));
-            return [x, y]
+            return {
+                x,
+                y,
+                seg1Left: seg1.leftSweepEvent.eventId,
+                seg1Right: seg1.rightSweepEvent.eventId,
+                seg2Left: seg2.leftSweepEvent.eventId,
+                seg2Right: seg2.rightSweepEvent.eventId,
+            }
         }
@@ -224,3 +237,5 @@ return false
 
-    function runCheck (eventQueue) {
+    function runCheck (eventQueue, ignoreSelfIntersections) {
+        ignoreSelfIntersections = ignoreSelfIntersections ? ignoreSelfIntersections : false;
+
         const intersectionPoints = [];
@@ -235,3 +250,7 @@ const outQueue = new TinyQueue([], checkWhichSegmentHasRightEndpointFirst);
                 for (let i = 0; i < outQueue.data.length; i++) {
-                    const intersection = testSegmentIntersect(segment, outQueue.data[i]);
+                    const otherSeg = outQueue.data[i];
+                    if (ignoreSelfIntersections) {
+                        if (otherSeg.leftSweepEvent.featureId === event.featureId) continue
+                    }
+                    const intersection = testSegmentIntersect(segment, otherSeg);
                     if (intersection !== false) intersectionPoints.push(intersection);
@@ -274,4 +293,4 @@ }
 
-        getIntersections () {
-            return runCheck(this._eventQueue)
+        getIntersections (ignoreSelfIntersections) {
+            return runCheck(this._eventQueue, ignoreSelfIntersections)
         }
@@ -278,0 +297,0 @@ }

package.json

 {
   "name": "sweepline-intersections",
-  "version": "1.2.2",
+  "version": "1.3.0",
   "description": "A module to check if a polygon self-intersects using a sweepline algorithm",
@@ -5,0 +5,0 @@ "main": "dist/sweeplineIntersections.js",

README.md

@@ -12,3 +12,3 @@ # sweepline-intersections
 ### Basic Use
-Valid inputs: Geojson `Feature` or `Geometry` including `Polygon`, `LineString`, `MultiPolygon`, `MultiLineString`, as well as `FeatureCollection`'s.
+Valid inputs: Geojson `Feature` or `Geometry` including `Polygon`, `LineString`, `MultiPolygon`, `MultiLineString`, as well as `FeatureCollection`.
 
@@ -22,7 +22,15 @@ Returns an array of intersection points eg, [[x1, y1], [x2, y2]]
     const intersections = findIntersections(box)
-    // returns an array of intersection points
+    // 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 
+````js
+    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 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.
+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.
 
@@ -45,3 +53,4 @@ ````js
         // check if those two features intersect
-        const intersectionPoints = sl.getIntersections()
+        // add an optional boolean argument to ignore self-intersections 
+        const intersectionPoints = sl.getIntersections(true)
     })
@@ -57,3 +66,3 @@ ````
 
-`.intersect()` - Checks for segment intersections. Returns `true` if there are no segment intersections or `false` if there are intersections.
+`.getIntersections(ignoreSelfIntersections)` - Checks for segment intersections. Accepts an optional boolean argument to ignore self intersections are only report intersections between features.
 
@@ -60,0 +69,0 @@

New alerts

License Policy Violation

License

This 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

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

48471

increased by10.21%

Lines of code

922

increased by8.6%

Number of lines in readme file

119

increased by8.18%

No dependency changes