!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";var e=function(e,n){if(void 0===e&&(e=[]),void 0===n&&(n=t),this.data=e,this.length=this.data.length,this.compare=n,this.length>0)for(var i=(this.length>>1)-1;i>=0;i--)this._down(i)};function t(e,t){return e<t?-1:e>t?1:0}function n(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 i(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}e.prototype.push=function(e){this.data.push(e),this.length++,this._up(this.length-1)},e.prototype.pop=function(){if(0!==this.length){var e=this.data[0],t=this.data.pop();return this.length--,this.length>0&&(this.data[0]=t,this._down(0)),e}},e.prototype.peek=function(){return this.data[0]},e.prototype._up=function(e){for(var t=this.data,n=this.compare,i=t[e];e>0;){var p=e-1>>1,r=t[p];if(n(i,r)>=0)break;t[e]=r,e=p}t[e]=i},e.prototype._down=function(e){for(var t=this.data,n=this.compare,i=this.length>>1,p=t[e];e<i;){var r=1+(e<<1),o=t[r],h=r+1;if(h<this.length&&n(t[h],o)<0&&(r=h,o=t[h]),n(o,p)>=0)break;t[e]=o,e=r}t[e]=p};var p=function(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};p.prototype.isSamePoint=function(e){return this.p.x===e.p.x&&this.p.y===e.p.y};var r=0,o=0,h=0;function f(e,t){var i="Feature"===e.type?e.geometry:e,f=i.coordinates;"Polygon"!==i.type&&"MultiLineString"!==i.type||(f=[f]),"LineString"===i.type&&(f=[[f]]);for(var s=0;s<f.length;s++)for(var a=0;a<f[s].length;a++){var v=f[s][a][0],u=null;o+=1;for(var l=0;l<f[s][a].length-1;l++){u=f[s][a][l+1];var g=new p(v,r,o,h),E=new p(u,r,o,h+1);g.otherEvent=E,E.otherEvent=g,n(g,E)>0?(E.isLeftEndpoint=!0,g.isLeftEndpoint=!1):(g.isLeftEndpoint=!0,E.isLeftEndpoint=!1),t.push(g),t.push(E),v=u,h+=1}}r+=1}var s=function(e){this.leftSweepEvent=e,this.rightSweepEvent=e.otherEvent};function a(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;var n=e.leftSweepEvent.p.x,i=e.leftSweepEvent.p.y,p=e.rightSweepEvent.p.x,r=e.rightSweepEvent.p.y,o=t.leftSweepEvent.p.x,h=t.leftSweepEvent.p.y,f=t.rightSweepEvent.p.x,s=t.rightSweepEvent.p.y,a=(s-h)*(p-n)-(f-o)*(r-i),v=(f-o)*(i-h)-(s-h)*(n-o),u=(p-n)*(i-h)-(r-i)*(n-o);if(0===a)return!1;var l=v/a,g=u/a;return l>=0&&l<=1&&g>=0&&g<=1&&[n+l*(p-n),i+l*(r-i)]}return function(t,p){var r=new e([],n);return function(e,t){if("FeatureCollection"===e.type)for(var n=e.features,i=0;i<n.length;i++)f(n[i],t);else f(e,t)}(t,r),function(t,n){n=n||!1;for(var p=[],r=new e([],i);t.length;){var o=t.pop();if(o.isLeftEndpoint){for(var h=new s(o),f=0;f<r.data.length;f++){var v=r.data[f];if(!n||v.leftSweepEvent.featureId!==o.featureId){var u=a(h,v);!1!==u&&p.push(u)}}r.push(h)}else!1===o.isLeftEndpoint&&r.pop()}return p}(r,p)}});