martinez-polygon-clipping - npm Package Compare versions

Comparing version 0.7.2 to 0.7.3

dist/martinez.min.js

 /**
- * martinez v0.7.2
+ * martinez v0.7.3
  * Martinez polygon clipping algorithm, does boolean operation on polygons (multipolygons, polygons with holes etc): intersection, union, difference, xor
@@ -9,2 +9,2 @@ *
  */
-(function(t,e){typeof exports==="object"&&typeof module!=="undefined"?e(exports):typeof define==="function"&&define.amd?define(["exports"],e):(t=t||self,e(t.martinez={}))})(this,function(t){"use strict";function i(t,e){return t>e?1:t<e?-1:0}var d=function t(e,r){if(e===void 0)e=i;if(r===void 0)r=false;this._compare=e;this._root=null;this._size=0;this._noDuplicates=!!r};var e={size:{configurable:true}};d.prototype.rotateLeft=function t(e){var r=e.right;if(r){e.right=r.left;if(r.left){r.left.parent=e}r.parent=e.parent}if(!e.parent){this._root=r}else if(e===e.parent.left){e.parent.left=r}else{e.parent.right=r}if(r){r.left=e}e.parent=r};d.prototype.rotateRight=function t(e){var r=e.left;if(r){e.left=r.right;if(r.right){r.right.parent=e}r.parent=e.parent}if(!e.parent){this._root=r}else if(e===e.parent.left){e.parent.left=r}else{e.parent.right=r}if(r){r.right=e}e.parent=r};d.prototype._splay=function t(e){while(e.parent){var r=e.parent;if(!r.parent){if(r.left===e){this.rotateRight(r)}else{this.rotateLeft(r)}}else if(r.left===e&&r.parent.left===r){this.rotateRight(r.parent);this.rotateRight(r)}else if(r.right===e&&r.parent.right===r){this.rotateLeft(r.parent);this.rotateLeft(r)}else if(r.left===e&&r.parent.right===r){this.rotateRight(r);this.rotateLeft(r)}else{this.rotateLeft(r);this.rotateRight(r)}}};d.prototype.splay=function t(e){var r,i,n,o,f;while(e.parent){r=e.parent;i=r.parent;if(i&&i.parent){n=i.parent;if(n.left===i){n.left=e}else{n.right=e}e.parent=n}else{e.parent=null;this._root=e}o=e.left;f=e.right;if(e===r.left){if(i){if(i.left===r){if(r.right){i.left=r.right;i.left.parent=i}else{i.left=null}r.right=i;i.parent=r}else{if(o){i.right=o;o.parent=i}else{i.right=null}e.left=i;i.parent=e}}if(f){r.left=f;f.parent=r}else{r.left=null}e.right=r;r.parent=e}else{if(i){if(i.right===r){if(r.left){i.right=r.left;i.right.parent=i}else{i.right=null}r.left=i;i.parent=r}else{if(f){i.left=f;f.parent=i}else{i.left=null}e.right=i;i.parent=e}}if(o){r.right=o;o.parent=r}else{r.right=null}e.left=r;r.parent=e}}};d.prototype.replace=function t(e,r){if(!e.parent){this._root=r}else if(e===e.parent.left){e.parent.left=r}else{e.parent.right=r}if(r){r.parent=e.parent}};d.prototype.minNode=function t(e){if(e===void 0)e=this._root;if(e){while(e.left){e=e.left}}return e};d.prototype.maxNode=function t(e){if(e===void 0)e=this._root;if(e){while(e.right){e=e.right}}return e};d.prototype.insert=function t(e,r){var i=this._root;var n=null;var o=this._compare;var f;if(this._noDuplicates){while(i){n=i;f=o(i.key,e);if(f===0){return}else if(o(i.key,e)<0){i=i.right}else{i=i.left}}}else{while(i){n=i;if(o(i.key,e)<0){i=i.right}else{i=i.left}}}i={key:e,data:r,left:null,right:null,parent:n};if(!n){this._root=i}else if(o(n.key,i.key)<0){n.right=i}else{n.left=i}this.splay(i);this._size++;return i};d.prototype.find=function t(e){var r=this._root;var i=this._compare;while(r){var n=i(r.key,e);if(n<0){r=r.right}else if(n>0){r=r.left}else{return r}}return null};d.prototype.contains=function t(e){var r=this._root;var i=this._compare;while(r){var n=i(e,r.key);if(n===0){return true}else if(n<0){r=r.left}else{r=r.right}}return false};d.prototype.remove=function t(e){var r=this.find(e);if(!r){return false}this.splay(r);if(!r.left){this.replace(r,r.right)}else if(!r.right){this.replace(r,r.left)}else{var i=this.minNode(r.right);if(i.parent!==r){this.replace(i,i.right);i.right=r.right;i.right.parent=i}this.replace(r,i);i.left=r.left;i.left.parent=i}this._size--;return true};d.prototype.removeNode=function t(e){if(!e){return false}this.splay(e);if(!e.left){this.replace(e,e.right)}else if(!e.right){this.replace(e,e.left)}else{var r=this.minNode(e.right);if(r.parent!==e){this.replace(r,r.right);r.right=e.right;r.right.parent=r}this.replace(e,r);r.left=e.left;r.left.parent=r}this._size--;return true};d.prototype.erase=function t(e){var r=this.find(e);if(!r){return}this.splay(r);var i=r.left;var n=r.right;var o=null;if(i){i.parent=null;o=this.maxNode(i);this.splay(o);this._root=o}if(n){if(i){o.right=n}else{this._root=n}n.parent=o}this._size--};d.prototype.pop=function t(){var e=this._root,r=null;if(e){while(e.left){e=e.left}r={key:e.key,data:e.data};this.remove(e.key)}return r};d.prototype.next=function t(e){var r=e;if(r){if(r.right){r=r.right;while(r&&r.left){r=r.left}}else{r=e.parent;while(r&&r.right===e){e=r;r=r.parent}}}return r};d.prototype.prev=function t(e){var r=e;if(r){if(r.left){r=r.left;while(r&&r.right){r=r.right}}else{r=e.parent;while(r&&r.left===e){e=r;r=r.parent}}}return r};d.prototype.forEach=function t(e){var r=this._root;var i=[],n=false,o=0;while(!n){if(r){i.push(r);r=r.left}else{if(i.length>0){r=i.pop();e(r,o++);r=r.right}else{n=true}}}return this};d.prototype.range=function t(e,r,i,n){var o=[];var f=this._compare;var a=this._root,l;while(o.length!==0||a){if(a){o.push(a);a=a.left}else{a=o.pop();l=f(a.key,r);if(l>0){break}else if(f(a.key,e)>=0){if(i.call(n,a)){return this}}a=a.right}}return this};d.prototype.keys=function t(){var e=this._root;var r=[],i=[],n=false;while(!n){if(e){r.push(e);e=e.left}else{if(r.length>0){e=r.pop();i.push(e.key);e=e.right}else{n=true}}}return i};d.prototype.values=function t(){var e=this._root;var r=[],i=[],n=false;while(!n){if(e){r.push(e);e=e.left}else{if(r.length>0){e=r.pop();i.push(e.data);e=e.right}else{n=true}}}return i};d.prototype.at=function t(e){var r=this._root;var i=[],n=false,o=0;while(!n){if(r){i.push(r);r=r.left}else{if(i.length>0){r=i.pop();if(o===e){return r}o++;r=r.right}else{n=true}}}return null};d.prototype.load=function t(e,r,i){if(e===void 0)e=[];if(r===void 0)r=[];if(i===void 0)i=false;if(this._size!==0){throw new Error("bulk-load: tree is not empty")}var n=e.length;if(i){u(e,r,0,n-1,this._compare)}this._root=s(null,e,r,0,n);this._size=n;return this};d.prototype.min=function t(){var e=this.minNode(this._root);if(e){return e.key}else{return null}};d.prototype.max=function t(){var e=this.maxNode(this._root);if(e){return e.key}else{return null}};d.prototype.isEmpty=function t(){return this._root===null};e.size.get=function(){return this._size};d.createTree=function t(e,r,i,n,o){return new d(i,o).load(e,r,n)};Object.defineProperties(d.prototype,e);function s(t,e,r,i,n){var o=n-i;if(o>0){var f=i+Math.floor(o/2);var a=e[f];var l=r[f];var u={key:a,data:l,parent:t};u.left=s(u,e,r,i,f);u.right=s(u,e,r,f+1,n);return u}return null}function u(t,e,r,i,n){if(r>=i){return}var o=t[r+i>>1];var f=r-1;var a=i+1;while(true){do{f++}while(n(t[f],o)<0);do{a--}while(n(t[a],o)>0);if(f>=a){break}var l=t[f];t[f]=t[a];t[a]=l;l=e[f];e[f]=e[a];e[a]=l}u(t,e,r,a,n);u(t,e,a+1,i,n)}var f=0;var l=1;var h=2;var p=3;var y=0;var a=1;var w=2;var v=3;function E(t,e,r){if(e===null){t.inOut=false;t.otherInOut=true}else{if(t.isSubject===e.isSubject){t.inOut=!e.inOut;t.otherInOut=e.otherInOut}else{t.inOut=!e.otherInOut;t.otherInOut=e.isVertical()?!e.inOut:e.inOut}if(e){t.prevInResult=!n(e,r)||e.isVertical()?e.prevInResult:e}}var i=n(t,r);if(i){t.resultTransition=o(t,r)}else{t.resultTransition=0}}function n(t,e){switch(t.type){case f:switch(e){case y:return!t.otherInOut;case a:return t.otherInOut;case w:return t.isSubject&&t.otherInOut||!t.isSubject&&!t.otherInOut;case v:return true}break;case h:return e===y||e===a;case p:return e===w;case l:return false}return false}function o(t,e){var r=!t.inOut;var i=!t.otherInOut;var n;switch(e){case y:n=r&&i;break;case a:n=r||i;break;case v:n=r^i;break;case w:if(t.isSubject){n=r&&!i}else{n=i&&!r}break}return n?+1:-1}var c=function t(e,r,i,n,o){this.left=r;this.point=e;this.otherEvent=i;this.isSubject=n;this.type=o||f;this.inOut=false;this.otherInOut=false;this.prevInResult=null;this.resultTransition=0;this.otherPos=-1;this.outputContourId=-1;this.isExteriorRing=true};var r={inResult:{configurable:true}};c.prototype.isBelow=function t(e){var r=this.point,i=this.otherEvent.point;return this.left?(r[0]-e[0])*(i[1]-e[1])-(i[0]-e[0])*(r[1]-e[1])>0:(i[0]-e[0])*(r[1]-e[1])-(r[0]-e[0])*(i[1]-e[1])>0};c.prototype.isAbove=function t(e){return!this.isBelow(e)};c.prototype.isVertical=function t(){return this.point[0]===this.otherEvent.point[0]};r.inResult.get=function(){return this.resultTransition!==0};c.prototype.clone=function t(){var e=new c(this.point,this.left,this.otherEvent,this.isSubject,this.type);e.contourId=this.contourId;e.resultTransition=this.resultTransition;e.prevInResult=this.prevInResult;e.isExteriorRing=this.isExteriorRing;e.inOut=this.inOut;e.otherInOut=this.otherInOut;return e};Object.defineProperties(c.prototype,r);function g(t,e){if(t[0]===e[0]){if(t[1]===e[1]){return true}else{return false}}return false}var I=11102230246251565e-32;var T=134217729;var L=(3+8*I)*I;function B(t,e,r,i,n){var o,f,a,l;var u=e[0];var s=i[0];var h=0;var p=0;if(s>u===s>-u){o=u;u=e[++h]}else{o=s;s=i[++p]}var v=0;if(h<t&&p<r){if(s>u===s>-u){f=u+o;a=o-(f-u);u=e[++h]}else{f=s+o;a=o-(f-s);s=i[++p]}o=f;if(a!==0){n[v++]=a}while(h<t&&p<r){if(s>u===s>-u){f=o+u;l=f-o;a=o-(f-l)+(u-l);u=e[++h]}else{f=o+s;l=f-o;a=o-(f-l)+(s-l);s=i[++p]}o=f;if(a!==0){n[v++]=a}}}while(h<t){f=o+u;l=f-o;a=o-(f-l)+(u-l);u=e[++h];o=f;if(a!==0){n[v++]=a}}while(p<r){f=o+s;l=f-o;a=o-(f-l)+(s-l);s=i[++p];o=f;if(a!==0){n[v++]=a}}if(o!==0||v===0){n[v++]=o}return v}function C(t,e){var r=e[0];for(var i=1;i<t;i++){r+=e[i]}return r}function _(t){return new Float64Array(t)}var b=(3+16*I)*I;var A=(2+12*I)*I;var D=(9+64*I)*I*I;var F=_(4);var V=_(8);var U=_(12);var X=_(16);var q=_(4);function O(t,e,r,i,n,o,f){var a,l,u,s;var h,p,v,c,g,d,y,w,E,I,_,b,O,k;var m=t-n;var R=r-n;var j=e-o;var x=i-o;I=m*x;p=T*m;v=p-(p-m);c=m-v;p=T*x;g=p-(p-x);d=x-g;_=c*d-(I-v*g-c*g-v*d);b=j*R;p=T*j;v=p-(p-j);c=j-v;p=T*R;g=p-(p-R);d=R-g;O=c*d-(b-v*g-c*g-v*d);y=_-O;h=_-y;F[0]=_-(y+h)+(h-O);w=I+y;h=w-I;E=I-(w-h)+(y-h);y=E-b;h=E-y;F[1]=E-(y+h)+(h-b);k=w+y;h=k-w;F[2]=w-(k-h)+(y-h);F[3]=k;var S=C(4,F);var N=A*f;if(S>=N||-S>=N){return S}h=t-m;a=t-(m+h)+(h-n);h=r-R;u=r-(R+h)+(h-n);h=e-j;l=e-(j+h)+(h-o);h=i-x;s=i-(x+h)+(h-o);if(a===0&&l===0&&u===0&&s===0){return S}N=D*f+L*Math.abs(S);S+=m*s+x*a-(j*u+R*l);if(S>=N||-S>=N){return S}I=a*x;p=T*a;v=p-(p-a);c=a-v;p=T*x;g=p-(p-x);d=x-g;_=c*d-(I-v*g-c*g-v*d);b=l*R;p=T*l;v=p-(p-l);c=l-v;p=T*R;g=p-(p-R);d=R-g;O=c*d-(b-v*g-c*g-v*d);y=_-O;h=_-y;q[0]=_-(y+h)+(h-O);w=I+y;h=w-I;E=I-(w-h)+(y-h);y=E-b;h=E-y;q[1]=E-(y+h)+(h-b);k=w+y;h=k-w;q[2]=w-(k-h)+(y-h);q[3]=k;var z=B(4,F,4,q,V);I=m*s;p=T*m;v=p-(p-m);c=m-v;p=T*s;g=p-(p-s);d=s-g;_=c*d-(I-v*g-c*g-v*d);b=j*u;p=T*j;v=p-(p-j);c=j-v;p=T*u;g=p-(p-u);d=u-g;O=c*d-(b-v*g-c*g-v*d);y=_-O;h=_-y;q[0]=_-(y+h)+(h-O);w=I+y;h=w-I;E=I-(w-h)+(y-h);y=E-b;h=E-y;q[1]=E-(y+h)+(h-b);k=w+y;h=k-w;q[2]=w-(k-h)+(y-h);q[3]=k;var M=B(z,V,4,q,U);I=a*s;p=T*a;v=p-(p-a);c=a-v;p=T*s;g=p-(p-s);d=s-g;_=c*d-(I-v*g-c*g-v*d);b=l*u;p=T*l;v=p-(p-l);c=l-v;p=T*u;g=p-(p-u);d=u-g;O=c*d-(b-v*g-c*g-v*d);y=_-O;h=_-y;q[0]=_-(y+h)+(h-O);w=I+y;h=w-I;E=I-(w-h)+(y-h);y=E-b;h=E-y;q[1]=E-(y+h)+(h-b);k=w+y;h=k-w;q[2]=w-(k-h)+(y-h);q[3]=k;var P=B(M,U,4,q,X);return X[P-1]}function k(t,e,r,i,n,o){var f=(e-o)*(r-n);var a=(t-n)*(i-o);var l=f-a;if(f===0||a===0||f>0!==a>0){return l}var u=Math.abs(f+a);if(Math.abs(l)>=b*u){return l}return-O(t,e,r,i,n,o,u)}function m(t,e,r){var i=k(t[0],t[1],e[0],e[1],r[0],r[1]);if(i>0){return-1}if(i<0){return 1}return 0}function R(t,e){var r=t.point;var i=e.point;if(r[0]>i[0]){return 1}if(r[0]<i[0]){return-1}if(r[1]!==i[1]){return r[1]>i[1]?1:-1}return j(t,e,r)}function j(t,e,r,i){if(t.left!==e.left){return t.left?1:-1}if(m(r,t.otherEvent.point,e.otherEvent.point)!==0){return!t.isBelow(e.otherEvent.point)?1:-1}return!t.isSubject&&e.isSubject?1:-1}function x(t,e,r){var i=new c(e,false,t,t.isSubject);var n=new c(e,true,t.otherEvent,t.isSubject);if(g(t.point,t.otherEvent.point)){console.warn("what is that, a collapsed segment?",t)}i.contourId=n.contourId=t.contourId;if(R(n,t.otherEvent)>0){t.otherEvent.left=true;n.left=false}t.otherEvent.otherEvent=n;t.otherEvent=i;r.push(n);r.push(i);return r}function S(t,e){return t[0]*e[1]-t[1]*e[0]}function N(t,e){return t[0]*e[0]+t[1]*e[1]}function z(t,e,r,i,n){var o=[e[0]-t[0],e[1]-t[1]];var f=[i[0]-r[0],i[1]-r[1]];function a(t,e,r){return[t[0]+e*r[0],t[1]+e*r[1]]}var l=[r[0]-t[0],r[1]-t[1]];var u=S(o,f);var s=u*u;var h=N(o,o);if(s>0){var p=S(l,f)/u;if(p<0||p>1){return null}var v=S(l,o)/u;if(v<0||v>1){return null}if(p===0||p===1){return n?null:[a(t,p,o)]}if(v===0||v===1){return n?null:[a(r,v,f)]}return[a(t,p,o)]}u=S(l,o);s=u*u;if(s>0){return null}var c=N(o,l)/h;var g=c+N(o,f)/h;var d=Math.min(c,g);var y=Math.max(c,g);if(d<=1&&y>=0){if(d===1){return n?null:[a(t,d>0?d:0,o)]}if(y===0){return n?null:[a(t,y<1?y:1,o)]}if(n&&d===0&&y===1){return null}return[a(t,d>0?d:0,o),a(t,y<1?y:1,o)]}return null}function M(t,e,r){var i=z(t.point,t.otherEvent.point,e.point,e.otherEvent.point);var n=i?i.length:0;if(n===0){return 0}if(n===1&&(g(t.point,e.point)||g(t.otherEvent.point,e.otherEvent.point))){return 0}if(n===2&&t.isSubject===e.isSubject){return 0}if(n===1){if(!g(t.point,i[0])&&!g(t.otherEvent.point,i[0])){x(t,i[0],r)}if(!g(e.point,i[0])&&!g(e.otherEvent.point,i[0])){x(e,i[0],r)}return 1}var o=[];var f=false;var a=false;if(g(t.point,e.point)){f=true}else if(R(t,e)===1){o.push(e,t)}else{o.push(t,e)}if(g(t.otherEvent.point,e.otherEvent.point)){a=true}else if(R(t.otherEvent,e.otherEvent)===1){o.push(e.otherEvent,t.otherEvent)}else{o.push(t.otherEvent,e.otherEvent)}if(f&&a||f){e.type=l;t.type=e.inOut===t.inOut?h:p;if(f&&!a){x(o[1].otherEvent,o[0].point,r)}return 2}if(a){x(o[0],o[1].point,r);return 3}if(o[0]!==o[3].otherEvent){x(o[0],o[1].point,r);x(o[1],o[2].point,r);return 3}x(o[0],o[1].point,r);x(o[3].otherEvent,o[2].point,r);return 3}function P(t,e){if(t===e){return 0}if(m(t.point,t.otherEvent.point,e.point)!==0||m(t.point,t.otherEvent.point,e.otherEvent.point)!==0){if(g(t.point,e.point)){return t.isBelow(e.otherEvent.point)?-1:1}if(t.point[0]===e.point[0]){return t.point[1]<e.point[1]?-1:1}if(R(t,e)===1){return e.isAbove(t.point)?-1:1}return t.isBelow(e.point)?-1:1}if(t.isSubject===e.isSubject){var r=t.point,i=e.point;if(r[0]===i[0]&&r[1]===i[1]){r=t.otherEvent.point;i=e.otherEvent.point;if(r[0]===i[0]&&r[1]===i[1]){return 0}else{return t.contourId>e.contourId?1:-1}}}else{return t.isSubject?-1:1}return R(t,e)===1?1:-1}function G(t,e,r,i,n,o){var f=new d(P);var a=[];var l=Math.min(i[2],n[2]);var u,s,h;while(t.length!==0){var p=t.pop();a.push(p);if(o===y&&p.point[0]>l||o===w&&p.point[0]>i[2]){break}if(p.left){s=u=f.insert(p);h=f.minNode();if(u!==h){u=f.prev(u)}else{u=null}s=f.next(s);var v=u?u.key:null;var c=void 0;E(p,v,o);if(s){if(M(p,s.key,t)===2){E(p,v,o);E(s.key,p,o)}}if(u){if(M(u.key,p,t)===2){var g=u;if(g!==h){g=f.prev(g)}else{g=null}c=g?g.key:null;E(v,c,o);E(p,v,o)}}}else{p=p.otherEvent;s=u=f.find(p);if(u&&s){if(u!==h){u=f.prev(u)}else{u=null}s=f.next(s);f.remove(p);if(s&&u){M(u.key,s.key,t)}}}}return a}var H=function t(){this.points=[];this.holeIds=[];this.holeOf=null;this.depth=null};H.prototype.isExterior=function t(){return this.holeOf==null};function J(t){var e,r,i,n;var o=[];for(r=0,i=t.length;r<i;r++){e=t[r];if(e.left&&e.inResult||!e.left&&e.otherEvent.inResult){o.push(e)}}var f=false;while(!f){f=true;for(r=0,i=o.length;r<i;r++){if(r+1<i&&R(o[r],o[r+1])===1){n=o[r];o[r]=o[r+1];o[r+1]=n;f=false}}}for(r=0,i=o.length;r<i;r++){e=o[r];e.otherPos=r}for(r=0,i=o.length;r<i;r++){e=o[r];if(!e.left){n=e.otherPos;e.otherPos=e.otherEvent.otherPos;e.otherEvent.otherPos=n}}return o}function K(t,e,r,i){var n=t+1,o=e[t].point,f;var a=e.length;if(n<a){f=e[n].point}while(n<a&&f[0]===o[0]&&f[1]===o[1]){if(!r[n]){return n}else{n++}f=e[n].point}n=t-1;while(r[n]&&n>i){n--}return n}function Q(t,e,r){var i=new H;if(t.prevInResult!=null){var n=t.prevInResult;var o=n.outputContourId;var f=n.resultTransition;if(f>0){var a=e[o];if(a.holeOf!=null){var l=a.holeOf;e[l].holeIds.push(r);i.holeOf=l;i.depth=e[o].depth}else{e[o].holeIds.push(r);i.holeOf=o;i.depth=e[o].depth+1}}else{i.holeOf=null;i.depth=e[o].depth}}else{i.holeOf=null;i.depth=0}return i}function W(t){var f,e;var a=J(t);var l={};var u=[];var r=function(){if(l[f]){return}var e=u.length;var t=Q(a[f],u,e);var r=function(t){l[t]=true;a[t].outputContourId=e};var i=f;var n=f;var o=a[f].point;t.points.push(o);while(true){r(i);i=a[i].otherPos;r(i);t.points.push(a[i].point);i=K(i,a,l,n);if(i==n){break}}u.push(t)};for(f=0,e=a.length;f<e;f++)r();return u}var Y=$;var Z=$;function $(t,e){if(!(this instanceof $)){return new $(t,e)}this.data=t||[];this.length=this.data.length;this.compare=e||tt;if(this.length>0){for(var r=(this.length>>1)-1;r>=0;r--){this._down(r)}}}function tt(t,e){return t<e?-1:t>e?1:0}$.prototype={push:function(t){this.data.push(t);this.length++;this._up(this.length-1)},pop:function(){if(this.length===0){return undefined}var t=this.data[0];this.length--;if(this.length>0){this.data[0]=this.data[this.length];this._down(0)}this.data.pop();return t},peek:function(){return this.data[0]},_up:function(t){var e=this.data;var r=this.compare;var i=e[t];while(t>0){var n=t-1>>1;var o=e[n];if(r(i,o)>=0){break}e[t]=o;t=n}e[t]=i},_down:function(t){var e=this.data;var r=this.compare;var i=this.length>>1;var n=e[t];while(t<i){var o=(t<<1)+1;var f=o+1;var a=e[o];if(f<this.length&&r(e[f],a)<0){o=f;a=e[f]}if(r(a,n)>=0){break}e[t]=a;t=o}e[t]=n}};Y.default=Z;var et=Math.max;var rt=Math.min;var it=0;function nt(t,e,r,i,n,o){var f,a,l,u,s,h;for(f=0,a=t.length-1;f<a;f++){l=t[f];u=t[f+1];s=new c(l,false,undefined,e);h=new c(u,false,s,e);s.otherEvent=h;if(l[0]===u[0]&&l[1]===u[1]){continue}s.contourId=h.contourId=r;if(!o){s.isExteriorRing=false;h.isExteriorRing=false}if(R(s,h)>0){h.left=true}else{s.left=true}var p=l[0],v=l[1];n[0]=rt(n[0],p);n[1]=rt(n[1],v);n[2]=et(n[2],p);n[3]=et(n[3],v);i.push(s);i.push(h)}}function ot(t,e,r,i,n){var o=new Y(null,R);var f,a,l,u,s,h;for(l=0,u=t.length;l<u;l++){f=t[l];for(s=0,h=f.length;s<h;s++){a=s===0;if(a){it++}nt(f[s],true,it,o,r,a)}}for(l=0,u=e.length;l<u;l++){f=e[l];for(s=0,h=f.length;s<h;s++){a=s===0;if(n===w){a=false}if(a){it++}nt(f[s],false,it,o,i,a)}}return o}var ft=[];function at(t,e,r){var i=null;if(t.length*e.length===0){if(r===y){i=ft}else if(r===w){i=t}else if(r===a||r===v){i=t.length===0?e:t}}return i}function lt(t,e,r,i,n){var o=null;if(r[0]>i[2]||i[0]>r[2]||r[1]>i[3]||i[1]>r[3]){if(n===y){o=ft}else if(n===w){o=t}else if(n===a||n===v){o=t.concat(e)}}return o}function ut(t,e,r){if(typeof t[0][0][0]==="number"){t=[t]}if(typeof e[0][0][0]==="number"){e=[e]}var i=at(t,e,r);if(i){return i===ft?null:i}var n=[Infinity,Infinity,-Infinity,-Infinity];var o=[Infinity,Infinity,-Infinity,-Infinity];var f=ot(t,e,n,o,r);i=lt(t,e,n,o,r);if(i){return i===ft?null:i}var a=G(f,t,e,n,o,r);var l=W(a);var u=[];for(var s=0;s<l.length;s++){var h=l[s];if(h.isExterior()){var p=[h.points];for(var v=0;v<h.holeIds.length;v++){var c=h.holeIds[v];p.push(l[c].points)}u.push(p)}}return u}function st(t,e){return ut(t,e,a)}function ht(t,e){return ut(t,e,w)}function pt(t,e){return ut(t,e,v)}function vt(t,e){return ut(t,e,y)}var ct={UNION:a,DIFFERENCE:w,INTERSECTION:y,XOR:v};t.diff=ht;t.intersection=vt;t.operations=ct;t.union=st;t.xor=pt;Object.defineProperty(t,"__esModule",{value:true})});
+(function(t,e){typeof exports==="object"&&typeof module!=="undefined"?e(exports):typeof define==="function"&&define.amd?define(["exports"],e):(t=t||self,e(t.martinez={}))})(this,function(t){"use strict";function N(t,e){return t>e?1:t<e?-1:0}var d=function t(e,r){if(e===void 0)e=N;if(r===void 0)r=false;this._compare=e;this._root=null;this._size=0;this._noDuplicates=!!r};var e={size:{configurable:true}};d.prototype.rotateLeft=function t(e){var r=e.right;if(r){e.right=r.left;if(r.left){r.left.parent=e}r.parent=e.parent}if(!e.parent){this._root=r}else if(e===e.parent.left){e.parent.left=r}else{e.parent.right=r}if(r){r.left=e}e.parent=r};d.prototype.rotateRight=function t(e){var r=e.left;if(r){e.left=r.right;if(r.right){r.right.parent=e}r.parent=e.parent}if(!e.parent){this._root=r}else if(e===e.parent.left){e.parent.left=r}else{e.parent.right=r}if(r){r.right=e}e.parent=r};d.prototype._splay=function t(e){while(e.parent){var r=e.parent;if(!r.parent){if(r.left===e){this.rotateRight(r)}else{this.rotateLeft(r)}}else if(r.left===e&&r.parent.left===r){this.rotateRight(r.parent);this.rotateRight(r)}else if(r.right===e&&r.parent.right===r){this.rotateLeft(r.parent);this.rotateLeft(r)}else if(r.left===e&&r.parent.right===r){this.rotateRight(r);this.rotateLeft(r)}else{this.rotateLeft(r);this.rotateRight(r)}}};d.prototype.splay=function t(e){var r,i,n,o,f;while(e.parent){r=e.parent;i=r.parent;if(i&&i.parent){n=i.parent;if(n.left===i){n.left=e}else{n.right=e}e.parent=n}else{e.parent=null;this._root=e}o=e.left;f=e.right;if(e===r.left){if(i){if(i.left===r){if(r.right){i.left=r.right;i.left.parent=i}else{i.left=null}r.right=i;i.parent=r}else{if(o){i.right=o;o.parent=i}else{i.right=null}e.left=i;i.parent=e}}if(f){r.left=f;f.parent=r}else{r.left=null}e.right=r;r.parent=e}else{if(i){if(i.right===r){if(r.left){i.right=r.left;i.right.parent=i}else{i.right=null}r.left=i;i.parent=r}else{if(f){i.left=f;f.parent=i}else{i.left=null}e.right=i;i.parent=e}}if(o){r.right=o;o.parent=r}else{r.right=null}e.left=r;r.parent=e}}};d.prototype.replace=function t(e,r){if(!e.parent){this._root=r}else if(e===e.parent.left){e.parent.left=r}else{e.parent.right=r}if(r){r.parent=e.parent}};d.prototype.minNode=function t(e){if(e===void 0)e=this._root;if(e){while(e.left){e=e.left}}return e};d.prototype.maxNode=function t(e){if(e===void 0)e=this._root;if(e){while(e.right){e=e.right}}return e};d.prototype.insert=function t(e,r){var i=this._root;var n=null;var o=this._compare;var f;if(this._noDuplicates){while(i){n=i;f=o(i.key,e);if(f===0){return}else if(o(i.key,e)<0){i=i.right}else{i=i.left}}}else{while(i){n=i;if(o(i.key,e)<0){i=i.right}else{i=i.left}}}i={key:e,data:r,left:null,right:null,parent:n};if(!n){this._root=i}else if(o(n.key,i.key)<0){n.right=i}else{n.left=i}this.splay(i);this._size++;return i};d.prototype.find=function t(e){var r=this._root;var i=this._compare;while(r){var n=i(r.key,e);if(n<0){r=r.right}else if(n>0){r=r.left}else{return r}}return null};d.prototype.contains=function t(e){var r=this._root;var i=this._compare;while(r){var n=i(e,r.key);if(n===0){return true}else if(n<0){r=r.left}else{r=r.right}}return false};d.prototype.remove=function t(e){var r=this.find(e);if(!r){return false}this.splay(r);if(!r.left){this.replace(r,r.right)}else if(!r.right){this.replace(r,r.left)}else{var i=this.minNode(r.right);if(i.parent!==r){this.replace(i,i.right);i.right=r.right;i.right.parent=i}this.replace(r,i);i.left=r.left;i.left.parent=i}this._size--;return true};d.prototype.removeNode=function t(e){if(!e){return false}this.splay(e);if(!e.left){this.replace(e,e.right)}else if(!e.right){this.replace(e,e.left)}else{var r=this.minNode(e.right);if(r.parent!==e){this.replace(r,r.right);r.right=e.right;r.right.parent=r}this.replace(e,r);r.left=e.left;r.left.parent=r}this._size--;return true};d.prototype.erase=function t(e){var r=this.find(e);if(!r){return}this.splay(r);var i=r.left;var n=r.right;var o=null;if(i){i.parent=null;o=this.maxNode(i);this.splay(o);this._root=o}if(n){if(i){o.right=n}else{this._root=n}n.parent=o}this._size--};d.prototype.pop=function t(){var e=this._root,r=null;if(e){while(e.left){e=e.left}r={key:e.key,data:e.data};this.remove(e.key)}return r};d.prototype.next=function t(e){var r=e;if(r){if(r.right){r=r.right;while(r&&r.left){r=r.left}}else{r=e.parent;while(r&&r.right===e){e=r;r=r.parent}}}return r};d.prototype.prev=function t(e){var r=e;if(r){if(r.left){r=r.left;while(r&&r.right){r=r.right}}else{r=e.parent;while(r&&r.left===e){e=r;r=r.parent}}}return r};d.prototype.forEach=function t(e){var r=this._root;var i=[],n=false,o=0;while(!n){if(r){i.push(r);r=r.left}else{if(i.length>0){r=i.pop();e(r,o++);r=r.right}else{n=true}}}return this};d.prototype.range=function t(e,r,i,n){var o=[];var f=this._compare;var a=this._root,l;while(o.length!==0||a){if(a){o.push(a);a=a.left}else{a=o.pop();l=f(a.key,r);if(l>0){break}else if(f(a.key,e)>=0){if(i.call(n,a)){return this}}a=a.right}}return this};d.prototype.keys=function t(){var e=this._root;var r=[],i=[],n=false;while(!n){if(e){r.push(e);e=e.left}else{if(r.length>0){e=r.pop();i.push(e.key);e=e.right}else{n=true}}}return i};d.prototype.values=function t(){var e=this._root;var r=[],i=[],n=false;while(!n){if(e){r.push(e);e=e.left}else{if(r.length>0){e=r.pop();i.push(e.data);e=e.right}else{n=true}}}return i};d.prototype.at=function t(e){var r=this._root;var i=[],n=false,o=0;while(!n){if(r){i.push(r);r=r.left}else{if(i.length>0){r=i.pop();if(o===e){return r}o++;r=r.right}else{n=true}}}return null};d.prototype.load=function t(e,r,i){if(e===void 0)e=[];if(r===void 0)r=[];if(i===void 0)i=false;if(this._size!==0){throw new Error("bulk-load: tree is not empty")}var n=e.length;if(i){u(e,r,0,n-1,this._compare)}this._root=s(null,e,r,0,n);this._size=n;return this};d.prototype.min=function t(){var e=this.minNode(this._root);if(e){return e.key}else{return null}};d.prototype.max=function t(){var e=this.maxNode(this._root);if(e){return e.key}else{return null}};d.prototype.isEmpty=function t(){return this._root===null};e.size.get=function(){return this._size};d.createTree=function t(e,r,i,n,o){return new d(i,o).load(e,r,n)};Object.defineProperties(d.prototype,e);function s(t,e,r,i,n){var o=n-i;if(o>0){var f=i+Math.floor(o/2);var a=e[f];var l=r[f];var u={key:a,data:l,parent:t};u.left=s(u,e,r,i,f);u.right=s(u,e,r,f+1,n);return u}return null}function u(t,e,r,i,n){if(r>=i){return}var o=t[r+i>>1];var f=r-1;var a=i+1;while(true){do{f++}while(n(t[f],o)<0);do{a--}while(n(t[a],o)>0);if(f>=a){break}var l=t[f];t[f]=t[a];t[a]=l;l=e[f];e[f]=e[a];e[a]=l}u(t,e,r,a,n);u(t,e,a+1,i,n)}var f=0;var l=1;var h=2;var p=3;var y=0;var a=1;var w=2;var v=3;function E(t,e,r){if(e===null){t.inOut=false;t.otherInOut=true}else{if(t.isSubject===e.isSubject){t.inOut=!e.inOut;t.otherInOut=e.otherInOut}else{t.inOut=!e.otherInOut;t.otherInOut=e.isVertical()?!e.inOut:e.inOut}if(e){t.prevInResult=!n(e,r)||e.isVertical()?e.prevInResult:e}}var i=n(t,r);if(i){t.resultTransition=z(t,r)}else{t.resultTransition=0}}function n(t,e){switch(t.type){case f:switch(e){case y:return!t.otherInOut;case a:return t.otherInOut;case w:return t.isSubject&&t.otherInOut||!t.isSubject&&!t.otherInOut;case v:return true}break;case h:return e===y||e===a;case p:return e===w;case l:return false}return false}function z(t,e){var r=!t.inOut;var i=!t.otherInOut;var n;switch(e){case y:n=r&&i;break;case a:n=r||i;break;case v:n=r^i;break;case w:if(t.isSubject){n=r&&!i}else{n=i&&!r}break}return n?+1:-1}var c=function t(e,r,i,n,o){this.left=r;this.point=e;this.otherEvent=i;this.isSubject=n;this.type=o||f;this.inOut=false;this.otherInOut=false;this.prevInResult=null;this.resultTransition=0;this.otherPos=-1;this.outputContourId=-1;this.isExteriorRing=true};var r={inResult:{configurable:true}};c.prototype.isBelow=function t(e){var r=this.point,i=this.otherEvent.point;return this.left?(r[0]-e[0])*(i[1]-e[1])-(i[0]-e[0])*(r[1]-e[1])>0:(i[0]-e[0])*(r[1]-e[1])-(r[0]-e[0])*(i[1]-e[1])>0};c.prototype.isAbove=function t(e){return!this.isBelow(e)};c.prototype.isVertical=function t(){return this.point[0]===this.otherEvent.point[0]};r.inResult.get=function(){return this.resultTransition!==0};c.prototype.clone=function t(){var e=new c(this.point,this.left,this.otherEvent,this.isSubject,this.type);e.contourId=this.contourId;e.resultTransition=this.resultTransition;e.prevInResult=this.prevInResult;e.isExteriorRing=this.isExteriorRing;e.inOut=this.inOut;e.otherInOut=this.otherInOut;return e};Object.defineProperties(c.prototype,r);function g(t,e){if(t[0]===e[0]){if(t[1]===e[1]){return true}else{return false}}return false}var i=11102230246251565e-32;var T=134217729;var F=(3+8*i)*i;function L(t,e,r,i,n){var o,f,a,l;var u=e[0];var s=i[0];var h=0;var p=0;if(s>u===s>-u){o=u;u=e[++h]}else{o=s;s=i[++p]}var v=0;if(h<t&&p<r){if(s>u===s>-u){f=u+o;a=o-(f-u);u=e[++h]}else{f=s+o;a=o-(f-s);s=i[++p]}o=f;if(a!==0){n[v++]=a}while(h<t&&p<r){if(s>u===s>-u){f=o+u;l=f-o;a=o-(f-l)+(u-l);u=e[++h]}else{f=o+s;l=f-o;a=o-(f-l)+(s-l);s=i[++p]}o=f;if(a!==0){n[v++]=a}}}while(h<t){f=o+u;l=f-o;a=o-(f-l)+(u-l);u=e[++h];o=f;if(a!==0){n[v++]=a}}while(p<r){f=o+s;l=f-o;a=o-(f-l)+(s-l);s=i[++p];o=f;if(a!==0){n[v++]=a}}if(o!==0||v===0){n[v++]=o}return v}function V(t,e){var r=e[0];for(var i=1;i<t;i++){r+=e[i]}return r}function o(t){return new Float64Array(t)}var M=(3+16*i)*i;var U=(2+12*i)*i;var X=(9+64*i)*i*i;var B=o(4);var C=o(8);var A=o(12);var q=o(16);var D=o(4);function P(t,e,r,i,n,o,f){var a,l,u,s;var h,p,v,c,g,d,y,w,E,I,_,b,O,k;var m=t-n;var R=r-n;var j=e-o;var x=i-o;I=m*x;p=T*m;v=p-(p-m);c=m-v;p=T*x;g=p-(p-x);d=x-g;_=c*d-(I-v*g-c*g-v*d);b=j*R;p=T*j;v=p-(p-j);c=j-v;p=T*R;g=p-(p-R);d=R-g;O=c*d-(b-v*g-c*g-v*d);y=_-O;h=_-y;B[0]=_-(y+h)+(h-O);w=I+y;h=w-I;E=I-(w-h)+(y-h);y=E-b;h=E-y;B[1]=E-(y+h)+(h-b);k=w+y;h=k-w;B[2]=w-(k-h)+(y-h);B[3]=k;var S=V(4,B);var N=U*f;if(S>=N||-S>=N){return S}h=t-m;a=t-(m+h)+(h-n);h=r-R;u=r-(R+h)+(h-n);h=e-j;l=e-(j+h)+(h-o);h=i-x;s=i-(x+h)+(h-o);if(a===0&&l===0&&u===0&&s===0){return S}N=X*f+F*Math.abs(S);S+=m*s+x*a-(j*u+R*l);if(S>=N||-S>=N){return S}I=a*x;p=T*a;v=p-(p-a);c=a-v;p=T*x;g=p-(p-x);d=x-g;_=c*d-(I-v*g-c*g-v*d);b=l*R;p=T*l;v=p-(p-l);c=l-v;p=T*R;g=p-(p-R);d=R-g;O=c*d-(b-v*g-c*g-v*d);y=_-O;h=_-y;D[0]=_-(y+h)+(h-O);w=I+y;h=w-I;E=I-(w-h)+(y-h);y=E-b;h=E-y;D[1]=E-(y+h)+(h-b);k=w+y;h=k-w;D[2]=w-(k-h)+(y-h);D[3]=k;var z=L(4,B,4,D,C);I=m*s;p=T*m;v=p-(p-m);c=m-v;p=T*s;g=p-(p-s);d=s-g;_=c*d-(I-v*g-c*g-v*d);b=j*u;p=T*j;v=p-(p-j);c=j-v;p=T*u;g=p-(p-u);d=u-g;O=c*d-(b-v*g-c*g-v*d);y=_-O;h=_-y;D[0]=_-(y+h)+(h-O);w=I+y;h=w-I;E=I-(w-h)+(y-h);y=E-b;h=E-y;D[1]=E-(y+h)+(h-b);k=w+y;h=k-w;D[2]=w-(k-h)+(y-h);D[3]=k;var M=L(z,C,4,D,A);I=a*s;p=T*a;v=p-(p-a);c=a-v;p=T*s;g=p-(p-s);d=s-g;_=c*d-(I-v*g-c*g-v*d);b=l*u;p=T*l;v=p-(p-l);c=l-v;p=T*u;g=p-(p-u);d=u-g;O=c*d-(b-v*g-c*g-v*d);y=_-O;h=_-y;D[0]=_-(y+h)+(h-O);w=I+y;h=w-I;E=I-(w-h)+(y-h);y=E-b;h=E-y;D[1]=E-(y+h)+(h-b);k=w+y;h=k-w;D[2]=w-(k-h)+(y-h);D[3]=k;var P=L(M,A,4,D,q);return q[P-1]}function G(t,e,r,i,n,o){var f=(e-o)*(r-n);var a=(t-n)*(i-o);var l=f-a;if(f===0||a===0||f>0!==a>0){return l}var u=Math.abs(f+a);if(Math.abs(l)>=M*u){return l}return-P(t,e,r,i,n,o,u)}function I(t,e,r){var i=G(t[0],t[1],e[0],e[1],r[0],r[1]);if(i>0){return-1}if(i<0){return 1}return 0}function _(t,e){var r=t.point;var i=e.point;if(r[0]>i[0]){return 1}if(r[0]<i[0]){return-1}if(r[1]!==i[1]){return r[1]>i[1]?1:-1}return H(t,e,r)}function H(t,e,r,i){if(t.left!==e.left){return t.left?1:-1}if(I(r,t.otherEvent.point,e.otherEvent.point)!==0){return!t.isBelow(e.otherEvent.point)?1:-1}return!t.isSubject&&e.isSubject?1:-1}function b(t,e,r){var i=new c(e,false,t,t.isSubject);var n=new c(e,true,t.otherEvent,t.isSubject);if(g(t.point,t.otherEvent.point)){console.warn("what is that, a collapsed segment?",t)}i.contourId=n.contourId=t.contourId;if(_(n,t.otherEvent)>0){t.otherEvent.left=true;n.left=false}t.otherEvent.otherEvent=n;t.otherEvent=i;r.push(n);r.push(i);return r}function O(t,e){return t[0]*e[1]-t[1]*e[0]}function k(t,e){return t[0]*e[0]+t[1]*e[1]}function J(t,e,r,i,n){var o=[e[0]-t[0],e[1]-t[1]];var f=[i[0]-r[0],i[1]-r[1]];function a(t,e,r){return[t[0]+e*r[0],t[1]+e*r[1]]}var l=[r[0]-t[0],r[1]-t[1]];var u=O(o,f);var s=u*u;var h=k(o,o);if(s>0){var p=O(l,f)/u;if(p<0||p>1){return null}var v=O(l,o)/u;if(v<0||v>1){return null}if(p===0||p===1){return n?null:[a(t,p,o)]}if(v===0||v===1){return n?null:[a(r,v,f)]}return[a(t,p,o)]}u=O(l,o);s=u*u;if(s>0){return null}var c=k(o,l)/h;var g=c+k(o,f)/h;var d=Math.min(c,g);var y=Math.max(c,g);if(d<=1&&y>=0){if(d===1){return n?null:[a(t,d>0?d:0,o)]}if(y===0){return n?null:[a(t,y<1?y:1,o)]}if(n&&d===0&&y===1){return null}return[a(t,d>0?d:0,o),a(t,y<1?y:1,o)]}return null}function m(t,e,r){var i=J(t.point,t.otherEvent.point,e.point,e.otherEvent.point);var n=i?i.length:0;if(n===0){return 0}if(n===1&&(g(t.point,e.point)||g(t.otherEvent.point,e.otherEvent.point))){return 0}if(n===2&&t.isSubject===e.isSubject){return 0}if(n===1){if(!g(t.point,i[0])&&!g(t.otherEvent.point,i[0])){b(t,i[0],r)}if(!g(e.point,i[0])&&!g(e.otherEvent.point,i[0])){b(e,i[0],r)}return 1}var o=[];var f=false;var a=false;if(g(t.point,e.point)){f=true}else if(_(t,e)===1){o.push(e,t)}else{o.push(t,e)}if(g(t.otherEvent.point,e.otherEvent.point)){a=true}else if(_(t.otherEvent,e.otherEvent)===1){o.push(e.otherEvent,t.otherEvent)}else{o.push(t.otherEvent,e.otherEvent)}if(f&&a||f){e.type=l;t.type=e.inOut===t.inOut?h:p;if(f&&!a){b(o[1].otherEvent,o[0].point,r)}return 2}if(a){b(o[0],o[1].point,r);return 3}if(o[0]!==o[3].otherEvent){b(o[0],o[1].point,r);b(o[1],o[2].point,r);return 3}b(o[0],o[1].point,r);b(o[3].otherEvent,o[2].point,r);return 3}function K(t,e){if(t===e){return 0}if(I(t.point,t.otherEvent.point,e.point)!==0||I(t.point,t.otherEvent.point,e.otherEvent.point)!==0){if(g(t.point,e.point)){return t.isBelow(e.otherEvent.point)?-1:1}if(t.point[0]===e.point[0]){return t.point[1]<e.point[1]?-1:1}if(_(t,e)===1){return e.isAbove(t.point)?-1:1}return t.isBelow(e.point)?-1:1}if(t.isSubject===e.isSubject){var r=t.point,i=e.point;if(r[0]===i[0]&&r[1]===i[1]){r=t.otherEvent.point;i=e.otherEvent.point;if(r[0]===i[0]&&r[1]===i[1]){return 0}else{return t.contourId>e.contourId?1:-1}}}else{return t.isSubject?-1:1}return _(t,e)===1?1:-1}function Q(t,e,r,i,n,o){var f=new d(K);var a=[];var l=Math.min(i[2],n[2]);var u,s,h;while(t.length!==0){var p=t.pop();a.push(p);if(o===y&&p.point[0]>l||o===w&&p.point[0]>i[2]){break}if(p.left){s=u=f.insert(p);h=f.minNode();if(u!==h){u=f.prev(u)}else{u=null}s=f.next(s);var v=u?u.key:null;var c=void 0;E(p,v,o);if(s){if(m(p,s.key,t)===2){E(p,v,o);E(s.key,p,o)}}if(u){if(m(u.key,p,t)===2){var g=u;if(g!==h){g=f.prev(g)}else{g=null}c=g?g.key:null;E(v,c,o);E(p,v,o)}}}else{p=p.otherEvent;s=u=f.find(p);if(u&&s){if(u!==h){u=f.prev(u)}else{u=null}s=f.next(s);f.remove(p);if(s&&u){m(u.key,s.key,t)}}}}return a}var W=function t(){this.points=[];this.holeIds=[];this.holeOf=null;this.depth=null};W.prototype.isExterior=function t(){return this.holeOf==null};function Y(t){var e,r,i,n;var o=[];for(r=0,i=t.length;r<i;r++){e=t[r];if(e.left&&e.inResult||!e.left&&e.otherEvent.inResult){o.push(e)}}var f=false;while(!f){f=true;for(r=0,i=o.length;r<i;r++){if(r+1<i&&_(o[r],o[r+1])===1){n=o[r];o[r]=o[r+1];o[r+1]=n;f=false}}}for(r=0,i=o.length;r<i;r++){e=o[r];e.otherPos=r}for(r=0,i=o.length;r<i;r++){e=o[r];if(!e.left){n=e.otherPos;e.otherPos=e.otherEvent.otherPos;e.otherEvent.otherPos=n}}return o}function Z(t,e,r,i){var n=t+1,o=e[t].point,f;var a=e.length;if(n<a){f=e[n].point}while(n<a&&f[0]===o[0]&&f[1]===o[1]){if(!r[n]){return n}else{n++}if(n<a){f=e[n].point}}n=t-1;while(r[n]&&n>i){n--}return n}function $(t,e,r){var i=new W;if(t.prevInResult!=null){var n=t.prevInResult;var o=n.outputContourId;var f=n.resultTransition;if(f>0){var a=e[o];if(a.holeOf!=null){var l=a.holeOf;e[l].holeIds.push(r);i.holeOf=l;i.depth=e[o].depth}else{e[o].holeIds.push(r);i.holeOf=o;i.depth=e[o].depth+1}}else{i.holeOf=null;i.depth=e[o].depth}}else{i.holeOf=null;i.depth=0}return i}function tt(t){var f,e;var a=Y(t);var l={};var u=[];var r=function(){if(l[f]){return}var e=u.length;var t=$(a[f],u,e);var r=function(t){l[t]=true;if(t<a.length&&a[t]){a[t].outputContourId=e}};var i=f;var n=f;var o=a[f].point;t.points.push(o);while(true){r(i);i=a[i].otherPos;r(i);t.points.push(a[i].point);i=Z(i,a,l,n);if(i==n||i>=a.length||!a[i]){break}}u.push(t)};for(f=0,e=a.length;f<e;f++)r();return u}var et=R;var rt=R;function R(t,e){if(!(this instanceof R)){return new R(t,e)}this.data=t||[];this.length=this.data.length;this.compare=e||it;if(this.length>0){for(var r=(this.length>>1)-1;r>=0;r--){this._down(r)}}}function it(t,e){return t<e?-1:t>e?1:0}R.prototype={push:function(t){this.data.push(t);this.length++;this._up(this.length-1)},pop:function(){if(this.length===0){return undefined}var t=this.data[0];this.length--;if(this.length>0){this.data[0]=this.data[this.length];this._down(0)}this.data.pop();return t},peek:function(){return this.data[0]},_up:function(t){var e=this.data;var r=this.compare;var i=e[t];while(t>0){var n=t-1>>1;var o=e[n];if(r(i,o)>=0){break}e[t]=o;t=n}e[t]=i},_down:function(t){var e=this.data;var r=this.compare;var i=this.length>>1;var n=e[t];while(t<i){var o=(t<<1)+1;var f=o+1;var a=e[o];if(f<this.length&&r(e[f],a)<0){o=f;a=e[f]}if(r(a,n)>=0){break}e[t]=a;t=o}e[t]=n}};et.default=rt;var nt=Math.max;var ot=Math.min;var j=0;function ft(t,e,r,i,n,o){var f,a,l,u,s,h;for(f=0,a=t.length-1;f<a;f++){l=t[f];u=t[f+1];s=new c(l,false,undefined,e);h=new c(u,false,s,e);s.otherEvent=h;if(l[0]===u[0]&&l[1]===u[1]){continue}s.contourId=h.contourId=r;if(!o){s.isExteriorRing=false;h.isExteriorRing=false}if(_(s,h)>0){h.left=true}else{s.left=true}var p=l[0],v=l[1];n[0]=ot(n[0],p);n[1]=ot(n[1],v);n[2]=nt(n[2],p);n[3]=nt(n[3],v);i.push(s);i.push(h)}}function at(t,e,r,i,n){var o=new et(null,_);var f,a,l,u,s,h;for(l=0,u=t.length;l<u;l++){f=t[l];for(s=0,h=f.length;s<h;s++){a=s===0;if(a){j++}ft(f[s],true,j,o,r,a)}}for(l=0,u=e.length;l<u;l++){f=e[l];for(s=0,h=f.length;s<h;s++){a=s===0;if(n===w){a=false}if(a){j++}ft(f[s],false,j,o,i,a)}}return o}var x=[];function lt(t,e,r){var i=null;if(t.length*e.length===0){if(r===y){i=x}else if(r===w){i=t}else if(r===a||r===v){i=t.length===0?e:t}}return i}function ut(t,e,r,i,n){var o=null;if(r[0]>i[2]||i[0]>r[2]||r[1]>i[3]||i[1]>r[3]){if(n===y){o=x}else if(n===w){o=t}else if(n===a||n===v){o=t.concat(e)}}return o}function S(t,e,r){if(typeof t[0][0][0]==="number"){t=[t]}if(typeof e[0][0][0]==="number"){e=[e]}var i=lt(t,e,r);if(i){return i===x?null:i}var n=[Infinity,Infinity,-Infinity,-Infinity];var o=[Infinity,Infinity,-Infinity,-Infinity];var f=at(t,e,n,o,r);i=ut(t,e,n,o,r);if(i){return i===x?null:i}var a=Q(f,t,e,n,o,r);var l=tt(a);var u=[];for(var s=0;s<l.length;s++){var h=l[s];if(h.isExterior()){var p=[h.points];for(var v=0;v<h.holeIds.length;v++){var c=h.holeIds[v];p.push(l[c].points)}u.push(p)}}return u}function st(t,e){return S(t,e,a)}function ht(t,e){return S(t,e,w)}function pt(t,e){return S(t,e,v)}function vt(t,e){return S(t,e,y)}var ct={UNION:a,DIFFERENCE:w,INTERSECTION:y,XOR:v};t.diff=ht;t.intersection=vt;t.operations=ct;t.union=st;t.xor=pt;Object.defineProperty(t,"__esModule",{value:true})});

dist/martinez.umd.js

 /**
- * martinez v0.7.2
+ * martinez v0.7.3
  * Martinez polygon clipping algorithm, does boolean operation on polygons (multipolygons, polygons with holes etc): intersection, union, difference, xor
@@ -1682,4 +1682,4 @@ *
     var newPos = pos + 1,
-        p = resultEvents[pos].point,
-        p1;
+      p = resultEvents[pos].point,
+      p1;
     var length = resultEvents.length;
@@ -1693,6 +1693,8 @@
         return newPos;
-      } else   {
+      } else {
         newPos++;
       }
-      p1 = resultEvents[newPos].point;
+      if (newPos < length) {
+        p1 = resultEvents[newPos].point;
+      }
     }
@@ -1775,3 +1777,5 @@
         processed[pos] = true;
-        resultEvents[pos].outputContourId = contourId;
+        if (pos < resultEvents.length && resultEvents[pos]) {
+          resultEvents[pos].outputContourId = contourId;
+        }
       };
@@ -1796,3 +1800,3 @@
 
-        if (pos == origPos) {
+        if (pos == origPos || pos >= resultEvents.length || !resultEvents[pos]) {
           break;
@@ -1799,0 +1803,0 @@ }

package.json

 {
   "name": "martinez-polygon-clipping",
-  "version": "0.7.2",
+  "version": "0.7.3",
   "description": "Martinez polygon clipping algorithm, does boolean operation on polygons (multipolygons, polygons with holes etc): intersection, union, difference, xor",
@@ -54,4 +54,4 @@ "main": "dist/martinez.umd.js",
     "geojson-project": "^1.0.0",
+    "http-server": "^0.12.1",
     "json-stringify-pretty-compact": "^2.0.0",
-    "http-server": "^0.12.1",
     "leaflet": "^1.2.0",
@@ -58,0 +58,0 @@ "leaflet-editable": "^1.1.0",

src/connect_edges.js

@@ -62,4 +62,4 @@ import compareEvents from './compare_events';
   let newPos = pos + 1,
-      p = resultEvents[pos].point,
-      p1;
+    p = resultEvents[pos].point,
+    p1;
   const length = resultEvents.length;
@@ -73,6 +73,8 @@
       return newPos;
-    } else   {
+    } else {
       newPos++;
     }
-    p1 = resultEvents[newPos].point;
+    if (newPos < length) {
+      p1 = resultEvents[newPos].point;
+    }
   }
@@ -155,3 +157,5 @@
       processed[pos] = true;
-      resultEvents[pos].outputContourId = contourId;
+      if (pos < resultEvents.length && resultEvents[pos]) {
+        resultEvents[pos].outputContourId = contourId;
+      }
     };
@@ -176,3 +180,3 @@
 
-      if (pos == origPos) {
+      if (pos == origPos || pos >= resultEvents.length || !resultEvents[pos]) {
         break;
@@ -179,0 +183,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

247435

increased by0.28%

Lines of code

2868

increased by0.28%

No dependency changes