This repository has been archived by the owner on May 16, 2018. It is now read-only.
/
clipper.js
executable file
·209 lines (206 loc) · 75.8 KB
/
clipper.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
/*******************************************************************************
* *
* Author : Angus Johnson *
* Version : 5.0.2 *
* Date : 30 December 2012 *
* Website : http://www.angusj.com *
* Copyright : Angus Johnson 2010-2012 *
* *
* License: *
* Use, modification & distribution is subject to Boost Software License Ver 1. *
* http://www.boost.org/LICENSE_1_0.txt *
* *
* Attributions: *
* The code in this library is an extension of Bala Vatti's clipping algorithm: *
* "A generic solution to polygon clipping" *
* Communications of the ACM, Vol 35, Issue 7 (July 1992) pp 56-63. *
* http://portal.acm.org/citation.cfm?id=129906 *
* *
* Computer graphics and geometric modeling: implementation and algorithms *
* By Max K. Agoston *
* Springer; 1 edition (January 4, 2005) *
* http://books.google.com/books?q=vatti+clipping+agoston *
* *
* See also: *
* "Polygon Offsetting by Computing Winding Numbers" *
* Paper no. DETC2005-85513 pp. 565-575 *
* ASME 2005 International Design Engineering Technical Conferences *
* and Computers and Information in Engineering Conference (IDETC/CIE2005) *
* September 24–28, 2005 , Long Beach, California, USA *
* http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf *
* *
*******************************************************************************/
/*******************************************************************************
* *
* Author : Timo *
* Version : 5.0.2.1 *
* Date : 12 January 2013 *
* *
* This is a translation of the C# Clipper library to Javascript. *
* Int128 struct of C# is implemented using JSBN of Tom Wu. *
* Because Javascript lacks support for 64-bit integers, the space *
* is a little more restricted than in C# version. *
* *
* C# version has support for coordinate space: *
* +-4611686018427387903 ( sqrt(2^127 -1)/2 ) *
* while Javascript version has support for space: *
* +-4503599627370495 ( sqrt(2^106 -1)/2 ) *
* *
* Tom Wu's JSBN proved to be the fastest big integer library: *
* http://jsperf.com/big-integer-library-test *
* *
* This class can be made simpler when (if ever) 64-bit integer support comes. *
* *
*******************************************************************************/
/*******************************************************************************
* *
* Basic JavaScript BN library - subset useful for RSA encryption. *
* http://www-cs-students.stanford.edu/~tjw/jsbn/ *
* Copyright (c) 2005 Tom Wu *
* All Rights Reserved. *
* See "LICENSE" for details: *
* http://www-cs-students.stanford.edu/~tjw/jsbn/LICENSE *
* *
*******************************************************************************/
(function(Q){function j(a,b){d.biginteger_used=1;null!=a&&("number"==typeof a?this.fromString(Math.floor(a).toString(),10):null==b&&"string"!=typeof a?this.fromString(a,256):(-1!=a.indexOf(".")&&(a=a.substring(0,a.indexOf("."))),this.fromString(a,b)))}function n(){return new j(null)}function R(a,b,c,e,d,f){for(;0<=--f;){var h=b*this[a++]+c[e]+d;d=Math.floor(h/67108864);c[e++]=h&67108863}return d}function S(a,b,c,e,d,f){var h=b&32767;for(b>>=15;0<=--f;){var k=this[a]&32767,j=this[a++]>>15,l=b*k+j*
h,k=h*k+((l&32767)<<15)+c[e]+(d&1073741823);d=(k>>>30)+(l>>>15)+b*j+(d>>>30);c[e++]=k&1073741823}return d}function T(a,b,c,e,d,f){var h=b&16383;for(b>>=14;0<=--f;){var k=this[a]&16383,j=this[a++]>>14,l=b*k+j*h,k=h*k+((l&16383)<<14)+c[e]+d;d=(k>>28)+(l>>14)+b*j;c[e++]=k&268435455}return d}function L(a,b){var c=F[a.charCodeAt(b)];return null==c?-1:c}function A(a){var b=n();b.fromInt(a);return b}function G(a){var b=1,c;if(0!=(c=a>>>16))a=c,b+=16;if(0!=(c=a>>8))a=c,b+=8;if(0!=(c=a>>4))a=c,b+=4;if(0!=
(c=a>>2))a=c,b+=2;0!=a>>1&&(b+=1);return b}function B(a){this.m=a}function C(a){this.m=a;this.mp=a.invDigit();this.mpl=this.mp&32767;this.mph=this.mp>>15;this.um=(1<<a.DB-15)-1;this.mt2=2*a.t}function U(a,b){return a&b}function K(a,b){return a|b}function M(a,b){return a^b}function N(a,b){return a&~b}function E(){}function O(a){return a}function D(a){this.r2=n();this.q3=n();j.ONE.dlShiftTo(2*a.t,this.r2);this.mu=this.r2.divide(a);this.m=a}var p=navigator.userAgent.toString().toLowerCase(),y,u,x,H,
I,J,P;y=-1!=p.indexOf("chrome")&&-1==p.indexOf("chromium")?1:0;u=-1!=p.indexOf("chromium")?1:0;x=-1!=p.indexOf("safari")&&-1==p.indexOf("chrome")&&-1==p.indexOf("chromium")?1:0;H=-1!=p.indexOf("firefox")?1:0;p.indexOf("firefox/17");p.indexOf("firefox/15");p.indexOf("firefox/3");I=-1!=p.indexOf("opera")?1:0;p.indexOf("msie 10");p.indexOf("msie 9");J=-1!=p.indexOf("msie 8")?1:0;P=-1!=p.indexOf("msie 7")?1:0;var p=-1!=p.indexOf("msie ")?1:0,d={biginteger_used:null},t;"Microsoft Internet Explorer"==navigator.appName?
(j.prototype.am=S,t=30):"Netscape"!=navigator.appName?(j.prototype.am=R,t=26):(j.prototype.am=T,t=28);j.prototype.DB=t;j.prototype.DM=(1<<t)-1;j.prototype.DV=1<<t;j.prototype.FV=Math.pow(2,52);j.prototype.F1=52-t;j.prototype.F2=2*t-52;var F=[],v;t=48;for(v=0;9>=v;++v)F[t++]=v;t=97;for(v=10;36>v;++v)F[t++]=v;t=65;for(v=10;36>v;++v)F[t++]=v;B.prototype.convert=function(a){return 0>a.s||0<=a.compareTo(this.m)?a.mod(this.m):a};B.prototype.revert=function(a){return a};B.prototype.reduce=function(a){a.divRemTo(this.m,
null,a)};B.prototype.mulTo=function(a,b,c){a.multiplyTo(b,c);this.reduce(c)};B.prototype.sqrTo=function(a,b){a.squareTo(b);this.reduce(b)};C.prototype.convert=function(a){var b=n();a.abs().dlShiftTo(this.m.t,b);b.divRemTo(this.m,null,b);0>a.s&&0<b.compareTo(j.ZERO)&&this.m.subTo(b,b);return b};C.prototype.revert=function(a){var b=n();a.copyTo(b);this.reduce(b);return b};C.prototype.reduce=function(a){for(;a.t<=this.mt2;)a[a.t++]=0;for(var b=0;b<this.m.t;++b){var c=a[b]&32767,e=c*this.mpl+((c*this.mph+
(a[b]>>15)*this.mpl&this.um)<<15)&a.DM,c=b+this.m.t;for(a[c]+=this.m.am(0,e,a,b,0,this.m.t);a[c]>=a.DV;)a[c]-=a.DV,a[++c]++}a.clamp();a.drShiftTo(this.m.t,a);0<=a.compareTo(this.m)&&a.subTo(this.m,a)};C.prototype.mulTo=function(a,b,c){a.multiplyTo(b,c);this.reduce(c)};C.prototype.sqrTo=function(a,b){a.squareTo(b);this.reduce(b)};j.prototype.copyTo=function(a){for(var b=this.t-1;0<=b;--b)a[b]=this[b];a.t=this.t;a.s=this.s};j.prototype.fromInt=function(a){this.t=1;this.s=0>a?-1:0;0<a?this[0]=a:-1>a?
this[0]=a+DV:this.t=0};j.prototype.fromString=function(a,b){var c;if(16==b)c=4;else if(8==b)c=3;else if(256==b)c=8;else if(2==b)c=1;else if(32==b)c=5;else if(4==b)c=2;else{this.fromRadix(a,b);return}this.s=this.t=0;for(var e=a.length,d=!1,f=0;0<=--e;){var h=8==c?a[e]&255:L(a,e);0>h?"-"==a.charAt(e)&&(d=!0):(d=!1,0==f?this[this.t++]=h:f+c>this.DB?(this[this.t-1]|=(h&(1<<this.DB-f)-1)<<f,this[this.t++]=h>>this.DB-f):this[this.t-1]|=h<<f,f+=c,f>=this.DB&&(f-=this.DB))}8==c&&0!=(a[0]&128)&&(this.s=-1,
0<f&&(this[this.t-1]|=(1<<this.DB-f)-1<<f));this.clamp();d&&j.ZERO.subTo(this,this)};j.prototype.clamp=function(){for(var a=this.s&this.DM;0<this.t&&this[this.t-1]==a;)--this.t};j.prototype.dlShiftTo=function(a,b){var c;for(c=this.t-1;0<=c;--c)b[c+a]=this[c];for(c=a-1;0<=c;--c)b[c]=0;b.t=this.t+a;b.s=this.s};j.prototype.drShiftTo=function(a,b){for(var c=a;c<this.t;++c)b[c-a]=this[c];b.t=Math.max(this.t-a,0);b.s=this.s};j.prototype.lShiftTo=function(a,b){var c=a%this.DB,e=this.DB-c,d=(1<<e)-1,f=Math.floor(a/
this.DB),h=this.s<<c&this.DM,k;for(k=this.t-1;0<=k;--k)b[k+f+1]=this[k]>>e|h,h=(this[k]&d)<<c;for(k=f-1;0<=k;--k)b[k]=0;b[f]=h;b.t=this.t+f+1;b.s=this.s;b.clamp()};j.prototype.rShiftTo=function(a,b){b.s=this.s;var c=Math.floor(a/this.DB);if(c>=this.t)b.t=0;else{var e=a%this.DB,d=this.DB-e,f=(1<<e)-1;b[0]=this[c]>>e;for(var h=c+1;h<this.t;++h)b[h-c-1]|=(this[h]&f)<<d,b[h-c]=this[h]>>e;0<e&&(b[this.t-c-1]|=(this.s&f)<<d);b.t=this.t-c;b.clamp()}};j.prototype.subTo=function(a,b){for(var c=0,e=0,d=Math.min(a.t,
this.t);c<d;)e+=this[c]-a[c],b[c++]=e&this.DM,e>>=this.DB;if(a.t<this.t){for(e-=a.s;c<this.t;)e+=this[c],b[c++]=e&this.DM,e>>=this.DB;e+=this.s}else{for(e+=this.s;c<a.t;)e-=a[c],b[c++]=e&this.DM,e>>=this.DB;e-=a.s}b.s=0>e?-1:0;-1>e?b[c++]=this.DV+e:0<e&&(b[c++]=e);b.t=c;b.clamp()};j.prototype.multiplyTo=function(a,b){var c=this.abs(),e=a.abs(),d=c.t;for(b.t=d+e.t;0<=--d;)b[d]=0;for(d=0;d<e.t;++d)b[d+c.t]=c.am(0,e[d],b,d,0,c.t);b.s=0;b.clamp();this.s!=a.s&&j.ZERO.subTo(b,b)};j.prototype.squareTo=function(a){for(var b=
this.abs(),c=a.t=2*b.t;0<=--c;)a[c]=0;for(c=0;c<b.t-1;++c){var e=b.am(c,b[c],a,2*c,0,1);if((a[c+b.t]+=b.am(c+1,2*b[c],a,2*c+1,e,b.t-c-1))>=b.DV)a[c+b.t]-=b.DV,a[c+b.t+1]=1}0<a.t&&(a[a.t-1]+=b.am(c,b[c],a,2*c,0,1));a.s=0;a.clamp()};j.prototype.divRemTo=function(a,b,c){var e=a.abs();if(!(0>=e.t)){var d=this.abs();if(d.t<e.t)null!=b&&b.fromInt(0),null!=c&&this.copyTo(c);else{null==c&&(c=n());var f=n(),h=this.s;a=a.s;var k=this.DB-G(e[e.t-1]);0<k?(e.lShiftTo(k,f),d.lShiftTo(k,c)):(e.copyTo(f),d.copyTo(c));
e=f.t;d=f[e-1];if(0!=d){var m=d*(1<<this.F1)+(1<e?f[e-2]>>this.F2:0),l=this.FV/m,m=(1<<this.F1)/m,w=1<<this.F2,q=c.t,p=q-e,s=null==b?n():b;f.dlShiftTo(p,s);0<=c.compareTo(s)&&(c[c.t++]=1,c.subTo(s,c));j.ONE.dlShiftTo(e,s);for(s.subTo(f,f);f.t<e;)f[f.t++]=0;for(;0<=--p;){var r=c[--q]==d?this.DM:Math.floor(c[q]*l+(c[q-1]+w)*m);if((c[q]+=f.am(0,r,c,p,0,e))<r){f.dlShiftTo(p,s);for(c.subTo(s,c);c[q]<--r;)c.subTo(s,c)}}null!=b&&(c.drShiftTo(e,b),h!=a&&j.ZERO.subTo(b,b));c.t=e;c.clamp();0<k&&c.rShiftTo(k,
c);0>h&&j.ZERO.subTo(c,c)}}}};j.prototype.invDigit=function(){if(1>this.t)return 0;var a=this[0];if(0==(a&1))return 0;var b=a&3,b=b*(2-(a&15)*b)&15,b=b*(2-(a&255)*b)&255,b=b*(2-((a&65535)*b&65535))&65535,b=b*(2-a*b%this.DV)%this.DV;return 0<b?this.DV-b:-b};j.prototype.isEven=function(){return 0==(0<this.t?this[0]&1:this.s)};j.prototype.exp=function(a,b){if(4294967295<a||1>a)return j.ONE;var c=n(),e=n(),d=b.convert(this),f=G(a)-1;for(d.copyTo(c);0<=--f;)if(b.sqrTo(c,e),0<(a&1<<f))b.mulTo(e,d,c);else var h=
c,c=e,e=h;return b.revert(c)};j.prototype.toString=function(a){if(0>this.s)return"-"+this.negate().toString(a);if(16==a)a=4;else if(8==a)a=3;else if(2==a)a=1;else if(32==a)a=5;else if(4==a)a=2;else return this.toRadix(a);var b=(1<<a)-1,c,e=!1,d="",f=this.t,h=this.DB-f*this.DB%a;if(0<f--){if(h<this.DB&&0<(c=this[f]>>h))e=!0,d="0123456789abcdefghijklmnopqrstuvwxyz".charAt(c);for(;0<=f;)h<a?(c=(this[f]&(1<<h)-1)<<a-h,c|=this[--f]>>(h+=this.DB-a)):(c=this[f]>>(h-=a)&b,0>=h&&(h+=this.DB,--f)),0<c&&(e=
!0),e&&(d+="0123456789abcdefghijklmnopqrstuvwxyz".charAt(c))}return e?d:"0"};j.prototype.negate=function(){var a=n();j.ZERO.subTo(this,a);return a};j.prototype.abs=function(){return 0>this.s?this.negate():this};j.prototype.compareTo=function(a){var b=this.s-a.s;if(0!=b)return b;var c=this.t,b=c-a.t;if(0!=b)return 0>this.s?-b:b;for(;0<=--c;)if(0!=(b=this[c]-a[c]))return b;return 0};j.prototype.bitLength=function(){return 0>=this.t?0:this.DB*(this.t-1)+G(this[this.t-1]^this.s&this.DM)};j.prototype.mod=
function(a){var b=n();this.abs().divRemTo(a,null,b);0>this.s&&0<b.compareTo(j.ZERO)&&a.subTo(b,b);return b};j.prototype.modPowInt=function(a,b){var c;c=256>a||b.isEven()?new B(b):new C(b);return this.exp(a,c)};j.ZERO=A(0);j.ONE=A(1);E.prototype.convert=O;E.prototype.revert=O;E.prototype.mulTo=function(a,b,c){a.multiplyTo(b,c)};E.prototype.sqrTo=function(a,b){a.squareTo(b)};D.prototype.convert=function(a){if(0>a.s||a.t>2*this.m.t)return a.mod(this.m);if(0>a.compareTo(this.m))return a;var b=n();a.copyTo(b);
this.reduce(b);return b};D.prototype.revert=function(a){return a};D.prototype.reduce=function(a){a.drShiftTo(this.m.t-1,this.r2);a.t>this.m.t+1&&(a.t=this.m.t+1,a.clamp());this.mu.multiplyUpperTo(this.r2,this.m.t+1,this.q3);for(this.m.multiplyLowerTo(this.q3,this.m.t+1,this.r2);0>a.compareTo(this.r2);)a.dAddOffset(1,this.m.t+1);for(a.subTo(this.r2,a);0<=a.compareTo(this.m);)a.subTo(this.m,a)};D.prototype.mulTo=function(a,b,c){a.multiplyTo(b,c);this.reduce(c)};D.prototype.sqrTo=function(a,b){a.squareTo(b);
this.reduce(b)};var r=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,
719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997],V=67108864/r[r.length-1];j.prototype.chunkSize=function(a){return Math.floor(Math.LN2*this.DB/Math.log(a))};j.prototype.toRadix=function(a){null==a&&(a=10);if(0==this.signum()||2>a||36<a)return"0";var b=this.chunkSize(a),b=Math.pow(a,b),c=A(b),e=n(),d=n(),f="";for(this.divRemTo(c,e,d);0<e.signum();)f=(b+d.intValue()).toString(a).substr(1)+
f,e.divRemTo(c,e,d);return d.intValue().toString(a)+f};j.prototype.fromRadix=function(a,b){this.fromInt(0);null==b&&(b=10);for(var c=this.chunkSize(b),e=Math.pow(b,c),d=!1,f=0,h=0,k=0;k<a.length;++k){var m=L(a,k);0>m?"-"==a.charAt(k)&&0==this.signum()&&(d=!0):(h=b*h+m,++f>=c&&(this.dMultiply(e),this.dAddOffset(h,0),h=f=0))}0<f&&(this.dMultiply(Math.pow(b,f)),this.dAddOffset(h,0));d&&j.ZERO.subTo(this,this)};j.prototype.fromNumber=function(a,b,c){if("number"==typeof b)if(2>a)this.fromInt(1);else{this.fromNumber(a,
c);this.testBit(a-1)||this.bitwiseTo(j.ONE.shiftLeft(a-1),K,this);for(this.isEven()&&this.dAddOffset(1,0);!this.isProbablePrime(b);)this.dAddOffset(2,0),this.bitLength()>a&&this.subTo(j.ONE.shiftLeft(a-1),this)}else{c=[];var e=a&7;c.length=(a>>3)+1;b.nextBytes(c);c[0]=0<e?c[0]&(1<<e)-1:0;this.fromString(c,256)}};j.prototype.bitwiseTo=function(a,b,c){var e,d,f=Math.min(a.t,this.t);for(e=0;e<f;++e)c[e]=b(this[e],a[e]);if(a.t<this.t){d=a.s&this.DM;for(e=f;e<this.t;++e)c[e]=b(this[e],d);c.t=this.t}else{d=
this.s&this.DM;for(e=f;e<a.t;++e)c[e]=b(d,a[e]);c.t=a.t}c.s=b(this.s,a.s);c.clamp()};j.prototype.changeBit=function(a,b){var c=j.ONE.shiftLeft(a);this.bitwiseTo(c,b,c);return c};j.prototype.addTo=function(a,b){for(var c=0,e=0,d=Math.min(a.t,this.t);c<d;)e+=this[c]+a[c],b[c++]=e&this.DM,e>>=this.DB;if(a.t<this.t){for(e+=a.s;c<this.t;)e+=this[c],b[c++]=e&this.DM,e>>=this.DB;e+=this.s}else{for(e+=this.s;c<a.t;)e+=a[c],b[c++]=e&this.DM,e>>=this.DB;e+=a.s}b.s=0>e?-1:0;0<e?b[c++]=e:-1>e&&(b[c++]=this.DV+
e);b.t=c;b.clamp()};j.prototype.dMultiply=function(a){this[this.t]=this.am(0,a-1,this,0,0,this.t);++this.t;this.clamp()};j.prototype.dAddOffset=function(a,b){if(0!=a){for(;this.t<=b;)this[this.t++]=0;for(this[b]+=a;this[b]>=this.DV;)this[b]-=this.DV,++b>=this.t&&(this[this.t++]=0),++this[b]}};j.prototype.multiplyLowerTo=function(a,b,c){var e=Math.min(this.t+a.t,b);c.s=0;for(c.t=e;0<e;)c[--e]=0;var d;for(d=c.t-this.t;e<d;++e)c[e+this.t]=this.am(0,a[e],c,e,0,this.t);for(d=Math.min(a.t,b);e<d;++e)this.am(0,
a[e],c,e,0,b-e);c.clamp()};j.prototype.multiplyUpperTo=function(a,b,c){--b;var e=c.t=this.t+a.t-b;for(c.s=0;0<=--e;)c[e]=0;for(e=Math.max(b-this.t,0);e<a.t;++e)c[this.t+e-b]=this.am(b-e,a[e],c,0,0,this.t+e-b);c.clamp();c.drShiftTo(1,c)};j.prototype.modInt=function(a){if(0>=a)return 0;var b=this.DV%a,c=0>this.s?a-1:0;if(0<this.t)if(0==b)c=this[0]%a;else for(var e=this.t-1;0<=e;--e)c=(b*c+this[e])%a;return c};j.prototype.millerRabin=function(a){var b=this.subtract(j.ONE),c=b.getLowestSetBit();if(0>=
c)return!1;var e=b.shiftRight(c);a=a+1>>1;a>r.length&&(a=r.length);for(var d=n(),f=0;f<a;++f){d.fromInt(r[Math.floor(Math.random()*r.length)]);var h=d.modPow(e,this);if(0!=h.compareTo(j.ONE)&&0!=h.compareTo(b)){for(var k=1;k++<c&&0!=h.compareTo(b);)if(h=h.modPowInt(2,this),0==h.compareTo(j.ONE))return!1;if(0!=h.compareTo(b))return!1}}return!0};j.prototype.clone=function(){var a=n();this.copyTo(a);return a};j.prototype.intValue=function(){if(0>this.s){if(1==this.t)return this[0]-this.DV;if(0==this.t)return-1}else{if(1==
this.t)return this[0];if(0==this.t)return 0}return(this[1]&(1<<32-this.DB)-1)<<this.DB|this[0]};j.prototype.byteValue=function(){return 0==this.t?this.s:this[0]<<24>>24};j.prototype.shortValue=function(){return 0==this.t?this.s:this[0]<<16>>16};j.prototype.signum=function(){return 0>this.s?-1:0>=this.t||1==this.t&&0>=this[0]?0:1};j.prototype.toByteArray=function(){var a=this.t,b=[];b[0]=this.s;var c=this.DB-a*this.DB%8,e,d=0;if(0<a--){if(c<this.DB&&(e=this[a]>>c)!=(this.s&this.DM)>>c)b[d++]=e|this.s<<
this.DB-c;for(;0<=a;)if(8>c?(e=(this[a]&(1<<c)-1)<<8-c,e|=this[--a]>>(c+=this.DB-8)):(e=this[a]>>(c-=8)&255,0>=c&&(c+=this.DB,--a)),0!=(e&128)&&(e|=-256),0==d&&(this.s&128)!=(e&128)&&++d,0<d||e!=this.s)b[d++]=e}return b};j.prototype.equals=function(a){return 0==this.compareTo(a)};j.prototype.min=function(a){return 0>this.compareTo(a)?this:a};j.prototype.max=function(a){return 0<this.compareTo(a)?this:a};j.prototype.and=function(a){var b=n();this.bitwiseTo(a,U,b);return b};j.prototype.or=function(a){var b=
n();this.bitwiseTo(a,K,b);return b};j.prototype.xor=function(a){var b=n();this.bitwiseTo(a,M,b);return b};j.prototype.andNot=function(a){var b=n();this.bitwiseTo(a,N,b);return b};j.prototype.not=function(){for(var a=n(),b=0;b<this.t;++b)a[b]=this.DM&~this[b];a.t=this.t;a.s=~this.s;return a};j.prototype.shiftLeft=function(a){var b=n();0>a?this.rShiftTo(-a,b):this.lShiftTo(a,b);return b};j.prototype.shiftRight=function(a){var b=n();0>a?this.lShiftTo(-a,b):this.rShiftTo(a,b);return b};j.prototype.getLowestSetBit=
function(){for(var a=0;a<this.t;++a)if(0!=this[a]){var b=a*this.DB;a=this[a];if(0==a)a=-1;else{var c=0;0==(a&65535)&&(a>>=16,c+=16);0==(a&255)&&(a>>=8,c+=8);0==(a&15)&&(a>>=4,c+=4);0==(a&3)&&(a>>=2,c+=2);0==(a&1)&&++c;a=c}return b+a}return 0>this.s?this.t*this.DB:-1};j.prototype.bitCount=function(){for(var a=0,b=this.s&this.DM,c=0;c<this.t;++c){for(var d=this[c]^b,g=0;0!=d;)d&=d-1,++g;a+=g}return a};j.prototype.testBit=function(a){var b=Math.floor(a/this.DB);return b>=this.t?0!=this.s:0!=(this[b]&
1<<a%this.DB)};j.prototype.setBit=function(a){return this.changeBit(a,K)};j.prototype.clearBit=function(a){return this.changeBit(a,N)};j.prototype.flipBit=function(a){return this.changeBit(a,M)};j.prototype.add=function(a){var b=n();this.addTo(a,b);return b};j.prototype.subtract=function(a){var b=n();this.subTo(a,b);return b};j.prototype.multiply=function(a){var b=n();this.multiplyTo(a,b);return b};j.prototype.divide=function(a){var b=n();this.divRemTo(a,b,null);return b};j.prototype.remainder=function(a){var b=
n();this.divRemTo(a,null,b);return b};j.prototype.divideAndRemainder=function(a){var b=n(),c=n();this.divRemTo(a,b,c);return[b,c]};j.prototype.modPow=function(a,b){var c=a.bitLength(),d,g=A(1),f;if(0>=c)return g;d=18>c?1:48>c?3:144>c?4:768>c?5:6;f=8>c?new B(b):b.isEven()?new D(b):new C(b);var h=[],k=3,j=d-1,l=(1<<d)-1;h[1]=f.convert(this);if(1<d){c=n();for(f.sqrTo(h[1],c);k<=l;)h[k]=n(),f.mulTo(c,h[k-2],h[k]),k+=2}for(var w=a.t-1,q,p=!0,s=n(),c=G(a[w])-1;0<=w;){c>=j?q=a[w]>>c-j&l:(q=(a[w]&(1<<c+1)-
1)<<j-c,0<w&&(q|=a[w-1]>>this.DB+c-j));for(k=d;0==(q&1);)q>>=1,--k;if(0>(c-=k))c+=this.DB,--w;if(p)h[q].copyTo(g),p=!1;else{for(;1<k;)f.sqrTo(g,s),f.sqrTo(s,g),k-=2;0<k?f.sqrTo(g,s):(k=g,g=s,s=k);f.mulTo(s,h[q],g)}for(;0<=w&&0==(a[w]&1<<c);)f.sqrTo(g,s),k=g,g=s,s=k,0>--c&&(c=this.DB-1,--w)}return f.revert(g)};j.prototype.modInverse=function(a){var b=a.isEven();if(this.isEven()&&b||0==a.signum())return j.ZERO;for(var c=a.clone(),d=this.clone(),g=A(1),f=A(0),h=A(0),k=A(1);0!=c.signum();){for(;c.isEven();){c.rShiftTo(1,
c);if(b){if(!g.isEven()||!f.isEven())g.addTo(this,g),f.subTo(a,f);g.rShiftTo(1,g)}else f.isEven()||f.subTo(a,f);f.rShiftTo(1,f)}for(;d.isEven();){d.rShiftTo(1,d);if(b){if(!h.isEven()||!k.isEven())h.addTo(this,h),k.subTo(a,k);h.rShiftTo(1,h)}else k.isEven()||k.subTo(a,k);k.rShiftTo(1,k)}0<=c.compareTo(d)?(c.subTo(d,c),b&&g.subTo(h,g),f.subTo(k,f)):(d.subTo(c,d),b&&h.subTo(g,h),k.subTo(f,k))}if(0!=d.compareTo(j.ONE))return j.ZERO;if(0<=k.compareTo(a))return k.subtract(a);if(0>k.signum())k.addTo(a,k);
else return k;return 0>k.signum()?k.add(a):k};j.prototype.pow=function(a){return this.exp(a,new E)};j.prototype.gcd=function(a){var b=0>this.s?this.negate():this.clone();a=0>a.s?a.negate():a.clone();if(0>b.compareTo(a)){var c=b,b=a;a=c}var c=b.getLowestSetBit(),d=a.getLowestSetBit();if(0>d)return b;c<d&&(d=c);0<d&&(b.rShiftTo(d,b),a.rShiftTo(d,a));for(;0<b.signum();)0<(c=b.getLowestSetBit())&&b.rShiftTo(c,b),0<(c=a.getLowestSetBit())&&a.rShiftTo(c,a),0<=b.compareTo(a)?(b.subTo(a,b),b.rShiftTo(1,b)):
(a.subTo(b,a),a.rShiftTo(1,a));0<d&&a.lShiftTo(d,a);return a};j.prototype.isProbablePrime=function(a){var b,c=this.abs();if(1==c.t&&c[0]<=r[r.length-1]){for(b=0;b<r.length;++b)if(c[0]==r[b])return!0;return!1}if(c.isEven())return!1;for(b=1;b<r.length;){for(var d=r[b],g=b+1;g<r.length&&d<V;)d*=r[g++];for(d=c.modInt(d);b<g;)if(0==d%r[b++])return!1}return c.millerRabin(a)};j.prototype.square=function(){var a=n();this.squareTo(a);return a};d.Math_Abs_Int64=d.Math_Abs_Int32=d.Math_Abs_Double=function(a){return Math.abs(a)};
d.Math_Max_Int32_Int32=function(a,b){return Math.max(a,b)};d.Cast_Int32=p||I||x?function(a){return a|0}:function(a){return~~a};d.Cast_Int64=y?function(a){return-2147483648>a||2147483647<a?0>a?Math.ceil(a):Math.floor(a):~~a}:H&&"function"==typeof Number.toInteger?function(a){return Number.toInteger(a)}:P||J?function(a){return parseInt(a,10)}:p?function(a){return-2147483648>a||2147483647<a?0>a?Math.ceil(a):Math.floor(a):a|0}:function(a){return 0>a?Math.ceil(a):Math.floor(a)};d.Clear=function(a){a.length=
0};d.MaxSteps=64;d.PI=3.141592653589793;d.PI2=6.283185307179586;d.IntPoint=function(){var a=arguments;1==a.length&&(this.X=a[0].X,this.Y=a[0].Y);2==a.length&&(this.X=a[0],this.Y=a[1])};d.IntRect=function(){var a=arguments;if(4==a.length){var b=a[1],c=a[2],d=a[3];this.left=a[0];this.top=b;this.right=c;this.bottom=d}else this.bottom=this.right=this.top=this.left=0};d.Polygon=function(){return[]};d.Polygons=function(){return[[]]};d.ExPolygon=function(){this.holes=this.outer=null};d.ClipType={ctIntersection:0,
ctUnion:1,ctDifference:2,ctXor:3};d.PolyType={ptSubject:0,ptClip:1};d.PolyFillType={pftEvenOdd:0,pftNonZero:1,pftPositive:2,pftNegative:3};d.JoinType={jtSquare:0,jtRound:1,jtMiter:2};d.EdgeSide={esLeft:1,esRight:2};d.Protects={ipNone:0,ipLeft:1,ipRight:2,ipBoth:3};d.Direction={dRightToLeft:0,dLeftToRight:1};d.TEdge=function(){this.tmpX=this.deltaY=this.deltaX=this.dx=this.ytop=this.xtop=this.ycurr=this.xcurr=this.ybot=this.xbot=0;this.polyType=d.PolyType.ptSubject;this.side=null;this.outIdx=this.windCnt2=
this.windCnt=this.windDelta=0;this.prevInSEL=this.nextInSEL=this.prevInAEL=this.nextInAEL=this.nextInLML=this.prev=this.next=null};d.IntersectNode=function(){this.next=this.pt=this.edge2=this.edge1=null};d.LocalMinima=function(){this.Y=0;this.next=this.rightBound=this.leftBound=null};d.Scanbeam=function(){this.Y=0;this.next=null};d.OutRec=function(){this.idx=0;this.isHole=!1;this.bottomPt=this.pts=this.AppendLink=this.FirstLeft=null};d.OutPt=function(){this.idx=0;this.prev=this.next=this.pt=null};
d.JoinRec=function(){this.pt1b=this.pt1a=null;this.poly1Idx=0;this.pt2b=this.pt2a=null;this.poly2Idx=0};d.HorzJoinRec=function(){this.edge=null;this.savedIdx=0};d.ClipperBase=function(){this.m_CurrentLM=this.m_MinimaList=null;this.m_edges=[[]];this.m_UseFullRange=!1};d.ClipperBase.horizontal=-9007199254740992;d.ClipperBase.loRange=47453132;d.ClipperBase.hiRange=0xfffffffffffff;d.ClipperBase.PointsEqual=function(a,b){return a.X==b.X&&a.Y==b.Y};d.ClipperBase.prototype.PointIsVertex=function(a,b){var c=
b;do{if(d.ClipperBase.PointsEqual(c.pt,a))return!0;c=c.next}while(c!=b);return!1};d.ClipperBase.prototype.PointInPolygon=function(a,b,c){var d=b,g=!1;if(c){do{if((d.pt.Y<=a.Y&&a.Y<d.prev.pt.Y||d.prev.pt.Y<=a.Y&&a.Y<d.pt.Y)&&0>(new j(a.X-d.pt.X)).compareTo((new j(d.prev.pt.X-d.pt.X)).multiply(new j(a.Y-d.pt.Y)).divide(new j(d.prev.pt.Y-d.pt.Y))))g=!g;d=d.next}while(d!=b)}else{do{if((d.pt.Y<=a.Y&&a.Y<d.prev.pt.Y||d.prev.pt.Y<=a.Y&&a.Y<d.pt.Y)&&a.X-d.pt.X<(d.prev.pt.X-d.pt.X)*(a.Y-d.pt.Y)/(d.prev.pt.Y-
d.pt.Y))g=!g;d=d.next}while(d!=b)}return g};d.ClipperBase.prototype.SlopesEqual=function(){var a=arguments,b,c,d,g;if(3==a.length)return b=a[0],c=a[1],(a=a[2])?(new j(b.deltaY)).multiply(new j(c.deltaX)).toString()==(new j(b.deltaX)).multiply(new j(c.deltaY)).toString():b.deltaY*c.deltaX==b.deltaX*c.deltaY;if(4==a.length)return b=a[0],c=a[1],d=a[2],(a=a[3])?(new j(b.Y-c.Y)).multiply(new j(c.X-d.X)).toString()==(new j(b.X-c.X)).multiply(new j(c.Y-d.Y)).toString():0==(b.Y-c.Y)*(c.X-d.X)-(b.X-c.X)*(c.Y-
d.Y);if(5==a.length)return b=a[0],c=a[1],d=a[2],g=a[3],(a=a[4])?(new j(b.Y-c.Y)).multiply(new j(d.X-g.X)).toString()==(new j(b.X-c.X)).multiply(new j(d.Y-g.Y)).toString():0==(b.Y-c.Y)*(d.X-g.X)-(b.X-c.X)*(d.Y-g.Y)};d.ClipperBase.prototype.Clear=function(){this.DisposeLocalMinimaList();for(var a=0;a<this.m_edges.length;++a){for(var b=0;b<this.m_edges[a].length;++b)this.m_edges[a][b]=null;d.Clear(this.m_edges[a])}d.Clear(this.m_edges);this.m_UseFullRange=!1};d.ClipperBase.prototype.DisposeLocalMinimaList=
function(){for(;null!=this.m_MinimaList;){var a=this.m_MinimaList.next;this.m_MinimaList=null;this.m_MinimaList=a}this.m_CurrentLM=null};d.ClipperBase.prototype.AddPolygons=function(a,b){var c=!1,e=!1;if(!(a instanceof Array))return c;for(var g=0;g<a.length;++g)if((e=this.AddPolygon(a[g],b,!0))&&"exceed"!=e)c=!0;else if("exceed"==e)break;"exceed"==e&&d.Error("Coordinate exceeds range bounds in AddPolygons().");return c};d.ClipperBase.prototype.AddPolygon=function(a,b,c){if(!(a instanceof Array))return!1;
var e=a.length;if(3>e)return!1;var g=new d.Polygon;g.push(new d.IntPoint(a[0].X,a[0].Y));var f=0,h,k=!1;for(h=1;h<e;++h){var j;j=this.m_UseFullRange?d.ClipperBase.hiRange:d.ClipperBase.loRange;if(d.Math_Abs_Int64(a[h].X)>j||d.Math_Abs_Int64(a[h].Y)>j){if(d.Math_Abs_Int64(a[h].X)>d.ClipperBase.hiRange||d.Math_Abs_Int64(a[h].Y)>d.ClipperBase.hiRange){if("undefined"!=typeof c)return"exceed";k=!0;break}this.m_UseFullRange=!0}d.ClipperBase.PointsEqual(g[f],a[h])||(0<f&&this.SlopesEqual(g[f-1],g[f],a[h],
this.m_UseFullRange)?d.ClipperBase.PointsEqual(g[f-1],a[h])&&f--:f++,f<g.length?g[f]=a[h]:g.push(new d.IntPoint(a[h].X,a[h].Y)))}k&&"undefined"==typeof c&&d.Error("Coordinate exceeds range bounds in AddPolygon()");if(2>f)return!1;for(e=f+1;2<e;){if(d.ClipperBase.PointsEqual(g[f],g[0]))f--;else if(d.ClipperBase.PointsEqual(g[0],g[1])||this.SlopesEqual(g[f],g[0],g[1],this.m_UseFullRange))g[0]=g[f--];else if(this.SlopesEqual(g[f-1],g[f],g[0],this.m_UseFullRange))f--;else if(this.SlopesEqual(g[0],g[1],
g[2],this.m_UseFullRange)){for(h=2;h<=f;++h)g[h-1]=g[h];f--}else break;e--}if(3>e)return!1;a=[];for(h=0;h<e;h++)a.push(new d.TEdge);this.m_edges.push(a);a[0].xcurr=g[0].X;a[0].ycurr=g[0].Y;this.InitEdge(a[e-1],a[0],a[e-2],g[e-1],b);for(h=e-2;0<h;--h)this.InitEdge(a[h],a[h+1],a[h-1],g[h],b);this.InitEdge(a[0],a[1],a[e-1],g[0],b);e=b=a[0];do b.xcurr=b.xbot,b.ycurr=b.ybot,b.ytop<e.ytop&&(e=b),b=b.next;while(b!=a[0]);0<e.windDelta&&(e=e.next);e.dx==d.ClipperBase.horizontal&&(e=e.next);b=e;do b=this.AddBoundsToLML(b);
while(b!=e);return!0};d.ClipperBase.prototype.InitEdge=function(a,b,c,d,g){a.next=b;a.prev=c;a.xcurr=d.X;a.ycurr=d.Y;a.ycurr>=a.next.ycurr?(a.xbot=a.xcurr,a.ybot=a.ycurr,a.xtop=a.next.xcurr,a.ytop=a.next.ycurr,a.windDelta=1):(a.xtop=a.xcurr,a.ytop=a.ycurr,a.xbot=a.next.xcurr,a.ybot=a.next.ycurr,a.windDelta=-1);this.SetDx(a);a.polyType=g;a.outIdx=-1};d.ClipperBase.prototype.SetDx=function(a){a.deltaX=a.xtop-a.xbot;a.deltaY=a.ytop-a.ybot;a.dx=0==a.deltaY?d.ClipperBase.horizontal:a.deltaX/a.deltaY};
d.ClipperBase.prototype.AddBoundsToLML=function(a){a.nextInLML=null;for(a=a.next;;){if(a.dx==d.ClipperBase.horizontal){if(a.next.ytop<a.ytop&&a.next.xbot>a.prev.xbot)break;a.xtop!=a.prev.xbot&&this.SwapX(a);a.nextInLML=a.prev}else if(a.ycurr==a.prev.ycurr)break;else a.nextInLML=a.prev;a=a.next}var b=new d.LocalMinima;b.next=null;b.Y=a.prev.ybot;a.dx==d.ClipperBase.horizontal?(a.xbot!=a.prev.xbot&&this.SwapX(a),b.leftBound=a.prev,b.rightBound=a):a.dx<a.prev.dx?(b.leftBound=a.prev,b.rightBound=a):(b.leftBound=
a,b.rightBound=a.prev);b.leftBound.side=d.EdgeSide.esLeft;b.rightBound.side=d.EdgeSide.esRight;for(this.InsertLocalMinima(b);!(a.next.ytop==a.ytop&&a.next.dx!=d.ClipperBase.horizontal);)a=a.nextInLML=a.next,a.dx==d.ClipperBase.horizontal&&a.xbot!=a.prev.xtop&&this.SwapX(a);return a.next};d.ClipperBase.prototype.InsertLocalMinima=function(a){if(null==this.m_MinimaList)this.m_MinimaList=a;else if(a.Y>=this.m_MinimaList.Y)a.next=this.m_MinimaList,this.m_MinimaList=a;else{for(var b=this.m_MinimaList;null!=
b.next&&a.Y<b.next.Y;)b=b.next;a.next=b.next;b.next=a}};d.ClipperBase.prototype.PopLocalMinima=function(){null!=this.m_CurrentLM&&(this.m_CurrentLM=this.m_CurrentLM.next)};d.ClipperBase.prototype.SwapX=function(a){a.xcurr=a.xtop;a.xtop=a.xbot;a.xbot=a.xcurr};d.ClipperBase.prototype.Reset=function(){for(var a=this.m_CurrentLM=this.m_MinimaList;null!=a;){for(var b=a.leftBound;null!=b;)b.xcurr=b.xbot,b.ycurr=b.ybot,b.side=d.EdgeSide.esLeft,b.outIdx=-1,b=b.nextInLML;for(b=a.rightBound;null!=b;)b.xcurr=
b.xbot,b.ycurr=b.ybot,b.side=d.EdgeSide.esRight,b.outIdx=-1,b=b.nextInLML;a=a.next}};d.ClipperBase.prototype.GetBounds=function(){var a=new d.IntRect,b=this.m_MinimaList;if(null==b)return a;a.left=b.leftBound.xbot;a.top=b.leftBound.ybot;a.right=b.leftBound.xbot;for(a.bottom=b.leftBound.ybot;null!=b;){b.leftBound.ybot>a.bottom&&(a.bottom=b.leftBound.ybot);for(var c=b.leftBound;;){for(var e=c;null!=c.nextInLML;)c.xbot<a.left&&(a.left=c.xbot),c.xbot>a.right&&(a.right=c.xbot),c=c.nextInLML;c.xbot<a.left&&
(a.left=c.xbot);c.xbot>a.right&&(a.right=c.xbot);c.xtop<a.left&&(a.left=c.xtop);c.xtop>a.right&&(a.right=c.xtop);c.ytop<a.top&&(a.top=c.ytop);if(e==b.leftBound)c=b.rightBound;else break}b=b.next}return a};d.Clipper=function(){this.m_PolyOuts=null;this.m_ClipType=d.ClipType.ctIntersection;this.m_IntersectNodes=this.m_SortedEdges=this.m_ActiveEdges=this.m_Scanbeam=null;this.m_ExecuteLocked=!1;this.m_SubjFillType=this.m_ClipFillType=d.PolyFillType.pftEvenOdd;this.m_HorizJoins=this.m_Joins=null;this.m_UsingExPolygons=
this.m_ReverseOutput=!1;d.ClipperBase.call(this);this.m_IntersectNodes=this.m_SortedEdges=this.m_ActiveEdges=this.m_Scanbeam=null;this.m_ExecuteLocked=!1;this.m_PolyOuts=[];this.m_Joins=[];this.m_HorizJoins=[];this.m_UsingExPolygons=this.m_ReverseOutput=!1};d.Clipper.prototype.Clear=function(){0!=this.m_edges.length&&(this.DisposeAllPolyPts(),d.ClipperBase.prototype.Clear.call(this))};d.Clipper.prototype.DisposeScanbeamList=function(){for(;null!=this.m_Scanbeam;){var a=this.m_Scanbeam.next;this.m_Scanbeam=
null;this.m_Scanbeam=a}};d.Clipper.prototype.Reset=function(){d.ClipperBase.prototype.Reset.call(this);this.m_SortedEdges=this.m_ActiveEdges=this.m_Scanbeam=null;this.DisposeAllPolyPts();for(var a=this.m_MinimaList;null!=a;)this.InsertScanbeam(a.Y),this.InsertScanbeam(a.leftBound.ytop),a=a.next};d.Clipper.prototype.get_ReverseSolution=function(){return this.m_ReverseOutput};d.Clipper.prototype.set_ReverseSolution=function(a){this.m_ReverseOutput=a};d.Clipper.prototype.InsertScanbeam=function(a){var b;
if(null==this.m_Scanbeam)this.m_Scanbeam=new d.Scanbeam,this.m_Scanbeam.next=null,this.m_Scanbeam.Y=a;else if(a>this.m_Scanbeam.Y)b=new d.Scanbeam,b.Y=a,b.next=this.m_Scanbeam,this.m_Scanbeam=b;else{for(var c=this.m_Scanbeam;null!=c.next&&a<=c.next.Y;)c=c.next;a!=c.Y&&(b=new d.Scanbeam,b.Y=a,b.next=c.next,c.next=b)}};d.Clipper.prototype.Execute=function(a,b,c,e){var g;2==arguments.length&&(e=c=d.PolyFillType.pftEvenOdd);if(b.hasOwnProperty("outer")){if(this.m_ExecuteLocked)return!1;this.m_ExecuteLocked=
!0;d.Clear(b);this.m_SubjFillType=c;this.m_ClipFillType=e;this.m_ClipType=a;this.m_UsingExPolygons=!0;(g=this.ExecuteInternal())&&this.BuildResultEx(b)}else{if(this.m_ExecuteLocked)return!1;this.m_ExecuteLocked=!0;d.Clear(b);this.m_SubjFillType=c;this.m_ClipFillType=e;this.m_ClipType=a;this.m_UsingExPolygons=!1;(g=this.ExecuteInternal())&&this.BuildResult(b)}this.m_ExecuteLocked=!1;return g};d.Clipper.prototype.PolySort=function(a,b){if(a==b)return 0;if(null==a.pts||null==b.pts)return null==a.pts!=
(null==b.pts)?null==a.pts?1:-1:0;var c=(a.isHole?a.FirstLeft.idx:a.idx)-(b.isHole?b.FirstLeft.idx:b.idx);return 0==c&&a.isHole!=b.isHole?a.isHole?1:-1:c};d.Clipper.prototype.FindAppendLinkEnd=function(a){for(;null!=a.AppendLink;)a=a.AppendLink;return a};d.Clipper.prototype.FixHoleLinkage=function(a){var b;b=null!=a.bottomPt?this.m_PolyOuts[a.bottomPt.idx].FirstLeft:a.FirstLeft;a==b&&d.Error("HoleLinkage error");null!=b&&(null!=b.AppendLink&&(b=this.FindAppendLinkEnd(b)),b==a?b=null:b.isHole&&(this.FixHoleLinkage(b),
b=b.FirstLeft));a.FirstLeft=b;null==b&&(a.isHole=!1);a.AppendLink=null};d.Clipper.prototype.ExecuteInternal=function(){var a;try{this.Reset();if(null==this.m_CurrentLM)return!0;var b=this.PopScanbeam();do{this.InsertLocalMinimaIntoAEL(b);d.Clear(this.m_HorizJoins);this.ProcessHorizontals();var c=this.PopScanbeam();a=this.ProcessIntersections(b,c);if(!a)break;this.ProcessEdgesAtTopOfScanbeam(c);b=c}while(null!=this.m_Scanbeam)}catch(e){a=!1}if(a){for(c=0;c<this.m_PolyOuts.length;c++)b=this.m_PolyOuts[c],
null!=b.pts&&(this.FixupOutPolygon(b),null!=b.pts&&(b.isHole&&this.m_UsingExPolygons&&this.FixHoleLinkage(b),(b.isHole^this.m_ReverseOutput)==0<this.Area(b,this.m_UseFullRange)&&this.ReversePolyPtLinks(b.pts)));this.JoinCommonEdges();this.m_UsingExPolygons&&this.m_PolyOuts.sort(this.PolySort)}d.Clear(this.m_Joins);d.Clear(this.m_HorizJoins);return a};d.Clipper.prototype.PopScanbeam=function(){var a=this.m_Scanbeam.Y;this.m_Scanbeam=this.m_Scanbeam.next;return a};d.Clipper.prototype.DisposeAllPolyPts=
function(){for(var a=0;a<this.m_PolyOuts.length;++a)this.DisposeOutRec(a);d.Clear(this.m_PolyOuts)};d.Clipper.prototype.DisposeOutRec=function(a){var b=this.m_PolyOuts[a];null!=b.pts&&this.DisposeOutPts(b.pts);this.m_PolyOuts[a]=null};d.Clipper.prototype.DisposeOutPts=function(a){if(null!=a)for(a.prev.next=null;null!=a;)a=a.next};d.Clipper.prototype.AddJoin=function(a,b,c,e){var g=new d.JoinRec;g.poly1Idx=0<=c?c:a.outIdx;g.pt1a=new d.IntPoint(a.xcurr,a.ycurr);g.pt1b=new d.IntPoint(a.xtop,a.ytop);
g.poly2Idx=0<=e?e:b.outIdx;g.pt2a=new d.IntPoint(b.xcurr,b.ycurr);g.pt2b=new d.IntPoint(b.xtop,b.ytop);this.m_Joins.push(g)};d.Clipper.prototype.AddHorzJoin=function(a,b){var c=new d.HorzJoinRec;c.edge=a;c.savedIdx=b;this.m_HorizJoins.push(c)};d.Clipper.prototype.InsertLocalMinimaIntoAEL=function(a){for(var b,c;null!=this.m_CurrentLM&&this.m_CurrentLM.Y==a;){var e=this.m_CurrentLM.leftBound,g=this.m_CurrentLM.rightBound;this.InsertEdgeIntoAEL(e);this.InsertScanbeam(e.ytop);this.InsertEdgeIntoAEL(g);
this.IsEvenOddFillType(e)?(e.windDelta=1,g.windDelta=1):g.windDelta=-e.windDelta;this.SetWindingCount(e);g.windCnt=e.windCnt;g.windCnt2=e.windCnt2;g.dx==d.ClipperBase.horizontal?(this.AddEdgeToSEL(g),this.InsertScanbeam(g.nextInLML.ytop)):this.InsertScanbeam(g.ytop);this.IsContributing(e)&&this.AddLocalMinPoly(e,g,new d.IntPoint(e.xcurr,this.m_CurrentLM.Y));if(0<=g.outIdx&&g.dx==d.ClipperBase.horizontal)for(var f=0;f<this.m_HorizJoins.length;f++){b=new d.IntPoint;c=new d.IntPoint;var h=this.m_HorizJoins[f];
b={Value:b};c={Value:c};this.GetOverlapSegment(new d.IntPoint(h.edge.xbot,h.edge.ybot),new d.IntPoint(h.edge.xtop,h.edge.ytop),new d.IntPoint(g.xbot,g.ybot),new d.IntPoint(g.xtop,g.ytop),b,c)&&this.AddJoin(h.edge,g,h.savedIdx,-1)}if(e.nextInAEL!=g){0<=g.outIdx&&(0<=g.prevInAEL.outIdx&&this.SlopesEqual(g.prevInAEL,g,this.m_UseFullRange))&&this.AddJoin(g,g.prevInAEL,-1,-1);c=e.nextInAEL;for(b=new d.IntPoint(e.xcurr,e.ycurr);c!=g;)null==c&&d.Error("InsertLocalMinimaIntoAEL: missing rightbound!"),this.IntersectEdges(g,
c,b,d.Protects.ipNone),c=c.nextInAEL}this.PopLocalMinima()}};d.Clipper.prototype.InsertEdgeIntoAEL=function(a){a.prevInAEL=null;a.nextInAEL=null;if(null==this.m_ActiveEdges)this.m_ActiveEdges=a;else if(this.E2InsertsBeforeE1(this.m_ActiveEdges,a))a.nextInAEL=this.m_ActiveEdges,this.m_ActiveEdges=this.m_ActiveEdges.prevInAEL=a;else{for(var b=this.m_ActiveEdges;null!=b.nextInAEL&&!this.E2InsertsBeforeE1(b.nextInAEL,a);)b=b.nextInAEL;a.nextInAEL=b.nextInAEL;null!=b.nextInAEL&&(b.nextInAEL.prevInAEL=
a);a.prevInAEL=b;b.nextInAEL=a}};d.Clipper.prototype.E2InsertsBeforeE1=function(a,b){return b.xcurr==a.xcurr?b.dx>a.dx:b.xcurr<a.xcurr};d.Clipper.prototype.IsEvenOddFillType=function(a){return a.polyType==d.PolyType.ptSubject?this.m_SubjFillType==d.PolyFillType.pftEvenOdd:this.m_ClipFillType==d.PolyFillType.pftEvenOdd};d.Clipper.prototype.IsEvenOddAltFillType=function(a){return a.polyType==d.PolyType.ptSubject?this.m_ClipFillType==d.PolyFillType.pftEvenOdd:this.m_SubjFillType==d.PolyFillType.pftEvenOdd};
d.Clipper.prototype.IsContributing=function(a){var b,c;a.polyType==d.PolyType.ptSubject?(b=this.m_SubjFillType,c=this.m_ClipFillType):(b=this.m_ClipFillType,c=this.m_SubjFillType);switch(b){case d.PolyFillType.pftEvenOdd:case d.PolyFillType.pftNonZero:if(1!=d.Math_Abs_Int32(a.windCnt))return!1;break;case d.PolyFillType.pftPositive:if(1!=a.windCnt)return!1;break;default:if(-1!=a.windCnt)return!1}switch(this.m_ClipType){case d.ClipType.ctIntersection:switch(c){case d.PolyFillType.pftEvenOdd:case d.PolyFillType.pftNonZero:return 0!=
a.windCnt2;case d.PolyFillType.pftPositive:return 0<a.windCnt2;default:return 0>a.windCnt2}case d.ClipType.ctUnion:switch(c){case d.PolyFillType.pftEvenOdd:case d.PolyFillType.pftNonZero:return 0==a.windCnt2;case d.PolyFillType.pftPositive:return 0>=a.windCnt2;default:return 0<=a.windCnt2}case d.ClipType.ctDifference:if(a.polyType==d.PolyType.ptSubject)switch(c){case d.PolyFillType.pftEvenOdd:case d.PolyFillType.pftNonZero:return 0==a.windCnt2;case d.PolyFillType.pftPositive:return 0>=a.windCnt2;
default:return 0<=a.windCnt2}else switch(c){case d.PolyFillType.pftEvenOdd:case d.PolyFillType.pftNonZero:return 0!=a.windCnt2;case d.PolyFillType.pftPositive:return 0<a.windCnt2;default:return 0>a.windCnt2}}return!0};d.Clipper.prototype.SetWindingCount=function(a){for(var b=a.prevInAEL;null!=b&&b.polyType!=a.polyType;)b=b.prevInAEL;null==b?(a.windCnt=a.windDelta,a.windCnt2=0,b=this.m_ActiveEdges):(a.windCnt=this.IsEvenOddFillType(a)?1:0>b.windCnt*b.windDelta?1<d.Math_Abs_Int32(b.windCnt)?0>b.windDelta*
a.windDelta?b.windCnt:b.windCnt+a.windDelta:b.windCnt+b.windDelta+a.windDelta:1<d.Math_Abs_Int32(b.windCnt)&&0>b.windDelta*a.windDelta?b.windCnt:0==b.windCnt+a.windDelta?b.windCnt:b.windCnt+a.windDelta,a.windCnt2=b.windCnt2,b=b.nextInAEL);if(this.IsEvenOddAltFillType(a))for(;b!=a;)a.windCnt2=0==a.windCnt2?1:0,b=b.nextInAEL;else for(;b!=a;)a.windCnt2+=b.windDelta,b=b.nextInAEL};d.Clipper.prototype.AddEdgeToSEL=function(a){null==this.m_SortedEdges?(this.m_SortedEdges=a,a.prevInSEL=null,a.nextInSEL=
null):(a.nextInSEL=this.m_SortedEdges,a.prevInSEL=null,this.m_SortedEdges=this.m_SortedEdges.prevInSEL=a)};d.Clipper.prototype.CopyAELToSEL=function(){var a=this.m_ActiveEdges;this.m_SortedEdges=a;if(null!=this.m_ActiveEdges){this.m_SortedEdges.prevInSEL=null;for(a=a.nextInAEL;null!=a;)a.prevInSEL=a.prevInAEL,a.prevInSEL.nextInSEL=a,a.nextInSEL=null,a=a.nextInAEL}};d.Clipper.prototype.SwapPositionsInAEL=function(a,b){var c,d;!(null==a.nextInAEL&&null==a.prevInAEL)&&!(null==b.nextInAEL&&null==b.prevInAEL)&&
(a.nextInAEL==b?(c=b.nextInAEL,null!=c&&(c.prevInAEL=a),d=a.prevInAEL,null!=d&&(d.nextInAEL=b),b.prevInAEL=d,b.nextInAEL=a,a.prevInAEL=b,a.nextInAEL=c):b.nextInAEL==a?(c=a.nextInAEL,null!=c&&(c.prevInAEL=b),d=b.prevInAEL,null!=d&&(d.nextInAEL=a),a.prevInAEL=d,a.nextInAEL=b,b.prevInAEL=a,b.nextInAEL=c):(c=a.nextInAEL,d=a.prevInAEL,a.nextInAEL=b.nextInAEL,null!=a.nextInAEL&&(a.nextInAEL.prevInAEL=a),a.prevInAEL=b.prevInAEL,null!=a.prevInAEL&&(a.prevInAEL.nextInAEL=a),b.nextInAEL=c,null!=b.nextInAEL&&
(b.nextInAEL.prevInAEL=b),b.prevInAEL=d,null!=b.prevInAEL&&(b.prevInAEL.nextInAEL=b)),null==a.prevInAEL?this.m_ActiveEdges=a:null==b.prevInAEL&&(this.m_ActiveEdges=b))};d.Clipper.prototype.SwapPositionsInSEL=function(a,b){var c,d;!(null==a.nextInSEL&&null==a.prevInSEL)&&!(null==b.nextInSEL&&null==b.prevInSEL)&&(a.nextInSEL==b?(c=b.nextInSEL,null!=c&&(c.prevInSEL=a),d=a.prevInSEL,null!=d&&(d.nextInSEL=b),b.prevInSEL=d,b.nextInSEL=a,a.prevInSEL=b,a.nextInSEL=c):b.nextInSEL==a?(c=a.nextInSEL,null!=c&&
(c.prevInSEL=b),d=b.prevInSEL,null!=d&&(d.nextInSEL=a),a.prevInSEL=d,a.nextInSEL=b,b.prevInSEL=a,b.nextInSEL=c):(c=a.nextInSEL,d=a.prevInSEL,a.nextInSEL=b.nextInSEL,null!=a.nextInSEL&&(a.nextInSEL.prevInSEL=a),a.prevInSEL=b.prevInSEL,null!=a.prevInSEL&&(a.prevInSEL.nextInSEL=a),b.nextInSEL=c,null!=b.nextInSEL&&(b.nextInSEL.prevInSEL=b),b.prevInSEL=d,null!=b.prevInSEL&&(b.prevInSEL.nextInSEL=b)),null==a.prevInSEL?this.m_SortedEdges=a:null==b.prevInSEL&&(this.m_SortedEdges=b))};d.Clipper.prototype.AddLocalMaxPoly=
function(a,b,c){this.AddOutPt(a,c);a.outIdx==b.outIdx?(a.outIdx=-1,b.outIdx=-1):a.outIdx<b.outIdx?this.AppendPolygon(a,b):this.AppendPolygon(b,a)};d.Clipper.prototype.AddLocalMinPoly=function(a,b,c){var e;b.dx==d.ClipperBase.horizontal||a.dx>b.dx?(this.AddOutPt(a,c),b.outIdx=a.outIdx,a.side=d.EdgeSide.esLeft,b.side=d.EdgeSide.esRight,e=a,a=e.prevInAEL==b?b.prevInAEL:e.prevInAEL):(this.AddOutPt(b,c),a.outIdx=b.outIdx,a.side=d.EdgeSide.esRight,b.side=d.EdgeSide.esLeft,e=b,a=e.prevInAEL==a?a.prevInAEL:
e.prevInAEL);null!=a&&(0<=a.outIdx&&d.Clipper.TopX(a,c.Y)==d.Clipper.TopX(e,c.Y)&&this.SlopesEqual(e,a,this.m_UseFullRange))&&this.AddJoin(e,a,-1,-1)};d.Clipper.prototype.CreateOutRec=function(){var a=new d.OutRec;a.idx=-1;a.isHole=!1;a.FirstLeft=null;a.AppendLink=null;a.pts=null;a.bottomPt=null;return a};d.Clipper.prototype.AddOutPt=function(a,b){var c,e,g=a.side==d.EdgeSide.esLeft;if(0>a.outIdx)c=this.CreateOutRec(),this.m_PolyOuts.push(c),c.idx=this.m_PolyOuts.length-1,a.outIdx=c.idx,e=new d.OutPt,
c.pts=e,c.bottomPt=e,e.pt=b,e.idx=c.idx,e.next=e,e.prev=e,this.SetHoleState(a,c);else{c=this.m_PolyOuts[a.outIdx];e=c.pts;var f;g&&d.ClipperBase.PointsEqual(b,e.pt)||!g&&d.ClipperBase.PointsEqual(b,e.prev.pt)||(f=new d.OutPt,f.pt=b,f.idx=c.idx,f.pt.Y==c.bottomPt.pt.Y&&f.pt.X<c.bottomPt.pt.X&&(c.bottomPt=f),f.next=e,f.prev=e.prev,f.prev.next=f,e.prev=f,g&&(c.pts=f))}};d.Clipper.prototype.SwapPoints=function(a,b){var c=a.Value;a.Value=b.Value;b.Value=c};d.Clipper.prototype.GetOverlapSegment=function(a,
b,c,e,g,f){if(d.Math_Abs_Int64(a.X-b.X)>d.Math_Abs_Int64(a.Y-b.Y))return a.X>b.X&&(a={Value:a},b={Value:b},this.SwapPoints(a,b),a=a.Value,b=b.Value),c.X>e.X&&(c={Value:c},e={Value:e},this.SwapPoints(c,e),c=c.Value,e=e.Value),g.Value=a.X>c.X?a:c,f.Value=b.X<e.X?b:e,g.Value.X<f.Value.X;a.Y<b.Y&&(a={Value:a},b={Value:b},this.SwapPoints(a,b),a=a.Value,b=b.Value);c.Y<e.Y&&(c={Value:c},e={Value:e},this.SwapPoints(c,e),c=c.Value,e=e.Value);g.Value=a.Y<c.Y?a:c;f.Value=b.Y>e.Y?b:e;return g.Value.Y>f.Value.Y};
d.Clipper.prototype.FindSegment=function(a,b,c){if(null==a.Value)return!1;var e=a.Value,g=new d.IntPoint(b.Value),f=new d.IntPoint(c.Value);do{if(this.SlopesEqual(g,f,a.Value.pt,a.Value.prev.pt,!0)&&this.SlopesEqual(g,f,a.Value.pt,!0)&&this.GetOverlapSegment(g,f,a.Value.pt,a.Value.prev.pt,b,c))return!0;a.Value=a.Value.next}while(a.Value!=e);return!1};d.Clipper.prototype.Pt3IsBetweenPt1AndPt2=function(a,b,c){return d.ClipperBase.PointsEqual(a,c)||d.ClipperBase.PointsEqual(b,c)?!0:a.X!=b.X?a.X<c.X==
c.X<b.X:a.Y<c.Y==c.Y<b.Y};d.Clipper.prototype.InsertPolyPtBetween=function(a,b,c){var e=new d.OutPt;e.pt=c;b==a.next?(a.next=e,b.prev=e,e.next=b,e.prev=a):(b.next=e,a.prev=e,e.next=a,e.prev=b);return e};d.Clipper.prototype.SetHoleState=function(a,b){for(var c=!1,d=a.prevInAEL;null!=d;)0<=d.outIdx&&(c=!c,null==b.FirstLeft&&(b.FirstLeft=this.m_PolyOuts[d.outIdx])),d=d.prevInAEL;c&&(b.isHole=!0)};d.Clipper.prototype.GetDx=function(a,b){return a.Y==b.Y?d.ClipperBase.horizontal:(b.X-a.X)/(b.Y-a.Y)};d.Clipper.prototype.FirstIsBottomPt=
function(a,b){for(var c=a.prev;d.ClipperBase.PointsEqual(c.pt,a.pt)&&c!=a;)c=c.prev;for(var e=d.Math_Abs_Double(this.GetDx(a.pt,c.pt)),c=a.next;d.ClipperBase.PointsEqual(c.pt,a.pt)&&c!=a;)c=c.next;for(var g=d.Math_Abs_Double(this.GetDx(a.pt,c.pt)),c=b.prev;d.ClipperBase.PointsEqual(c.pt,b.pt)&&c!=b;)c=c.prev;for(var f=d.Math_Abs_Double(this.GetDx(b.pt,c.pt)),c=b.next;d.ClipperBase.PointsEqual(c.pt,b.pt)&&c!=b;)c=c.next;c=d.Math_Abs_Double(this.GetDx(b.pt,c.pt));return e>=f&&e>=c||g>=f&&g>=c};d.Clipper.prototype.GetBottomPt=
function(a){for(var b=null,c=a.next;c!=a;)c.pt.Y>a.pt.Y?(a=c,b=null):c.pt.Y==a.pt.Y&&c.pt.X<=a.pt.X&&(c.pt.X<a.pt.X?(b=null,a=c):c.next!=a&&c.prev!=a&&(b=c)),c=c.next;if(null!=b)for(;b!=c;){this.FirstIsBottomPt(c,b)||(a=b);for(b=b.next;!d.ClipperBase.PointsEqual(b.pt,a.pt);)b=b.next}return a};d.Clipper.prototype.GetLowermostRec=function(a,b){var c=a.bottomPt,d=b.bottomPt;return c.pt.Y>d.pt.Y?a:c.pt.Y<d.pt.Y?b:c.pt.X<d.pt.X?a:c.pt.X>d.pt.X?b:c.next==c?b:d.next==d?a:this.FirstIsBottomPt(c,d)?a:b};d.Clipper.prototype.Param1RightOfParam2=
function(a,b){do if(a=a.FirstLeft,a==b)return!0;while(null!=a);return!1};d.Clipper.prototype.AppendPolygon=function(a,b){var c=this.m_PolyOuts[a.outIdx],e=this.m_PolyOuts[b.outIdx],g;g=this.Param1RightOfParam2(c,e)?e:this.Param1RightOfParam2(e,c)?c:this.GetLowermostRec(c,e);var f=c.pts,h=f.prev,k=e.pts,j=k.prev;a.side==d.EdgeSide.esLeft?(b.side==d.EdgeSide.esLeft?(this.ReversePolyPtLinks(k),k.next=f,f.prev=k,h.next=j,j.prev=h,c.pts=j):(j.next=f,f.prev=j,k.prev=h,h.next=k,c.pts=k),f=d.EdgeSide.esLeft):
(b.side==d.EdgeSide.esRight?(this.ReversePolyPtLinks(k),h.next=j,j.prev=h,k.next=f,f.prev=k):(h.next=k,k.prev=h,f.prev=j,j.next=f),f=d.EdgeSide.esRight);g==e&&(c.bottomPt=e.bottomPt,c.bottomPt.idx=c.idx,e.FirstLeft!=c&&(c.FirstLeft=e.FirstLeft),c.isHole=e.isHole);e.pts=null;e.bottomPt=null;e.AppendLink=c;c=a.outIdx;e=b.outIdx;a.outIdx=-1;b.outIdx=-1;for(g=this.m_ActiveEdges;null!=g;){if(g.outIdx==e){g.outIdx=c;g.side=f;break}g=g.nextInAEL}for(g=0;g<this.m_Joins.length;++g)this.m_Joins[g].poly1Idx==
e&&(this.m_Joins[g].poly1Idx=c),this.m_Joins[g].poly2Idx==e&&(this.m_Joins[g].poly2Idx=c);for(g=0;g<this.m_HorizJoins.length;++g)this.m_HorizJoins[g].savedIdx==e&&(this.m_HorizJoins[g].savedIdx=c)};d.Clipper.prototype.ReversePolyPtLinks=function(a){if(null!=a){var b,c;b=a;do c=b.next,b.next=b.prev,b=b.prev=c;while(b!=a)}};d.Clipper.SwapSides=function(a,b){var c=a.side;a.side=b.side;b.side=c};d.Clipper.SwapPolyIndexes=function(a,b){var c=a.outIdx;a.outIdx=b.outIdx;b.outIdx=c};d.Clipper.prototype.DoEdge1=
function(a,b,c){this.AddOutPt(a,c);d.Clipper.SwapSides(a,b);d.Clipper.SwapPolyIndexes(a,b)};d.Clipper.prototype.DoEdge2=function(a,b,c){this.AddOutPt(b,c);d.Clipper.SwapSides(a,b);d.Clipper.SwapPolyIndexes(a,b)};d.Clipper.prototype.DoBothEdges=function(a,b,c){this.AddOutPt(a,c);this.AddOutPt(b,c);d.Clipper.SwapSides(a,b);d.Clipper.SwapPolyIndexes(a,b)};d.Clipper.prototype.IntersectEdges=function(a,b,c,e){var g=0==(d.Protects.ipLeft&e)&&null==a.nextInLML&&a.xtop==c.X&&a.ytop==c.Y;e=0==(d.Protects.ipRight&
e)&&null==b.nextInLML&&b.xtop==c.X&&b.ytop==c.Y;var f=0<=a.outIdx,h=0<=b.outIdx;if(a.polyType==b.polyType)if(this.IsEvenOddFillType(a)){var j=a.windCnt;a.windCnt=b.windCnt;b.windCnt=j}else a.windCnt=0==a.windCnt+b.windDelta?-a.windCnt:a.windCnt+b.windDelta,b.windCnt=0==b.windCnt-a.windDelta?-b.windCnt:b.windCnt-a.windDelta;else a.windCnt2=this.IsEvenOddFillType(b)?0==a.windCnt2?1:0:a.windCnt2+b.windDelta,b.windCnt2=this.IsEvenOddFillType(a)?0==b.windCnt2?1:0:b.windCnt2-a.windDelta;var m,l,n;a.polyType==
d.PolyType.ptSubject?(m=this.m_SubjFillType,n=this.m_ClipFillType):(m=this.m_ClipFillType,n=this.m_SubjFillType);b.polyType==d.PolyType.ptSubject?(l=this.m_SubjFillType,j=this.m_ClipFillType):(l=this.m_ClipFillType,j=this.m_SubjFillType);switch(m){case d.PolyFillType.pftPositive:m=a.windCnt;break;case d.PolyFillType.pftNegative:m=-a.windCnt;break;default:m=d.Math_Abs_Int32(a.windCnt)}switch(l){case d.PolyFillType.pftPositive:l=b.windCnt;break;case d.PolyFillType.pftNegative:l=-b.windCnt;break;default:l=
d.Math_Abs_Int32(b.windCnt)}if(f&&h)g||e||0!=m&&1!=m||0!=l&&1!=l||a.polyType!=b.polyType&&this.m_ClipType!=d.ClipType.ctXor?this.AddLocalMaxPoly(a,b,c):this.DoBothEdges(a,b,c);else if(f)(0==l||1==l)&&(this.m_ClipType!=d.ClipType.ctIntersection||b.polyType==d.PolyType.ptSubject||0!=b.windCnt2)&&this.DoEdge1(a,b,c);else if(h)(0==m||1==m)&&(this.m_ClipType!=d.ClipType.ctIntersection||a.polyType==d.PolyType.ptSubject||0!=a.windCnt2)&&this.DoEdge2(a,b,c);else if((0==m||1==m)&&(0==l||1==l)&&!g&&!e){switch(n){case d.PolyFillType.pftPositive:f=
a.windCnt2;break;case d.PolyFillType.pftNegative:f=-a.windCnt2;break;default:f=d.Math_Abs_Int32(a.windCnt2)}switch(j){case d.PolyFillType.pftPositive:h=b.windCnt2;break;case d.PolyFillType.pftNegative:h=-b.windCnt2;break;default:h=d.Math_Abs_Int32(b.windCnt2)}if(a.polyType!=b.polyType)this.AddLocalMinPoly(a,b,c);else if(1==m&&1==l)switch(this.m_ClipType){case d.ClipType.ctIntersection:0<f&&0<h&&this.AddLocalMinPoly(a,b,c);break;case d.ClipType.ctUnion:0>=f&&0>=h&&this.AddLocalMinPoly(a,b,c);break;
case d.ClipType.ctDifference:(a.polyType==d.PolyType.ptClip&&0<f&&0<h||a.polyType==d.PolyType.ptSubject&&0>=f&&0>=h)&&this.AddLocalMinPoly(a,b,c);break;case d.ClipType.ctXor:this.AddLocalMinPoly(a,b,c)}else d.Clipper.SwapSides(a,b)}if(g!=e&&(g&&0<=a.outIdx||e&&0<=b.outIdx))d.Clipper.SwapSides(a,b),d.Clipper.SwapPolyIndexes(a,b);g&&this.DeleteFromAEL(a);e&&this.DeleteFromAEL(b)};d.Clipper.prototype.DeleteFromAEL=function(a){var b=a.prevInAEL,c=a.nextInAEL;null==b&&null==c&&a!=this.m_ActiveEdges||(null!=
b?b.nextInAEL=c:this.m_ActiveEdges=c,null!=c&&(c.prevInAEL=b),a.nextInAEL=null,a.prevInAEL=null)};d.Clipper.prototype.DeleteFromSEL=function(a){var b=a.prevInSEL,c=a.nextInSEL;null==b&&null==c&&a!=this.m_SortedEdges||(null!=b?b.nextInSEL=c:this.m_SortedEdges=c,null!=c&&(c.prevInSEL=b),a.nextInSEL=null,a.prevInSEL=null)};d.Clipper.prototype.UpdateEdgeIntoAEL=function(a){null==a.Value.nextInLML&&d.Error("UpdateEdgeIntoAEL: invalid call");var b=a.Value.prevInAEL,c=a.Value.nextInAEL;a.Value.nextInLML.outIdx=
a.Value.outIdx;null!=b?b.nextInAEL=a.Value.nextInLML:this.m_ActiveEdges=a.Value.nextInLML;null!=c&&(c.prevInAEL=a.Value.nextInLML);a.Value.nextInLML.side=a.Value.side;a.Value.nextInLML.windDelta=a.Value.windDelta;a.Value.nextInLML.windCnt=a.Value.windCnt;a.Value.nextInLML.windCnt2=a.Value.windCnt2;a.Value=a.Value.nextInLML;a.Value.prevInAEL=b;a.Value.nextInAEL=c;a.Value.dx!=d.ClipperBase.horizontal&&this.InsertScanbeam(a.Value.ytop)};d.Clipper.prototype.ProcessHorizontals=function(){for(var a=this.m_SortedEdges;null!=
a;)this.DeleteFromSEL(a),this.ProcessHorizontal(a),a=this.m_SortedEdges};d.Clipper.prototype.ProcessHorizontal=function(a){var b,c,e;a.xcurr<a.xtop?(c=a.xcurr,e=a.xtop,b=d.Direction.dLeftToRight):(c=a.xtop,e=a.xcurr,b=d.Direction.dRightToLeft);var g;g=null!=a.nextInLML?null:this.GetMaximaPair(a);for(var f=this.GetNextInAEL(a,b);null!=f;){var h=this.GetNextInAEL(f,b);if(null!=g||b==d.Direction.dLeftToRight&&f.xcurr<=e||b==d.Direction.dRightToLeft&&f.xcurr>=c){if(f.xcurr==a.xtop&&null==g)if(this.SlopesEqual(f,
a.nextInLML,this.m_UseFullRange)){0<=a.outIdx&&0<=f.outIdx&&this.AddJoin(a.nextInLML,f,a.outIdx,-1);break}else if(f.dx<a.nextInLML.dx)break;if(f==g){b==d.Direction.dLeftToRight?this.IntersectEdges(a,f,new d.IntPoint(f.xcurr,a.ycurr),0):this.IntersectEdges(f,a,new d.IntPoint(f.xcurr,a.ycurr),0);0<=g.outIdx&&d.Error("ProcessHorizontal error");return}f.dx==d.ClipperBase.horizontal&&this.IsMinima(f);b==d.Direction.dLeftToRight?this.IntersectEdges(a,f,new d.IntPoint(f.xcurr,a.ycurr),this.IsTopHorz(a,f.xcurr)?
d.Protects.ipLeft:d.Protects.ipBoth):this.IntersectEdges(f,a,new d.IntPoint(f.xcurr,a.ycurr),this.IsTopHorz(a,f.xcurr)?d.Protects.ipRight:d.Protects.ipBoth);this.SwapPositionsInAEL(a,f)}else if(b==d.Direction.dLeftToRight&&f.xcurr>e&&null==a.nextInSEL||b==d.Direction.dRightToLeft&&f.xcurr<c&&null==a.nextInSEL)break;f=h}null!=a.nextInLML?(0<=a.outIdx&&this.AddOutPt(a,new d.IntPoint(a.xtop,a.ytop)),a={Value:a},this.UpdateEdgeIntoAEL(a)):(0<=a.outIdx&&this.IntersectEdges(a,g,new d.IntPoint(a.xtop,a.ycurr),
d.Protects.ipBoth),this.DeleteFromAEL(g),this.DeleteFromAEL(a))};d.Clipper.prototype.IsTopHorz=function(a,b){for(var c=this.m_SortedEdges;null!=c;){if(b>=Math.min(c.xcurr,c.xtop)&&b<=Math.max(c.xcurr,c.xtop))return!1;c=c.nextInSEL}return!0};d.Clipper.prototype.GetNextInAEL=function(a,b){return b==d.Direction.dLeftToRight?a.nextInAEL:a.prevInAEL};d.Clipper.prototype.IsMinima=function(a){return null!=a&&a.prev.nextInLML!=a&&a.next.nextInLML!=a};d.Clipper.prototype.IsMaxima=function(a,b){return null!=
a&&a.ytop==b&&null==a.nextInLML};d.Clipper.prototype.IsIntermediate=function(a,b){return a.ytop==b&&null!=a.nextInLML};d.Clipper.prototype.GetMaximaPair=function(a){return!this.IsMaxima(a.next,a.ytop)||a.next.xtop!=a.xtop?a.prev:a.next};d.Clipper.prototype.ProcessIntersections=function(a,b){if(null==this.m_ActiveEdges)return!0;try{this.BuildIntersectList(a,b);if(null==this.m_IntersectNodes)return!0;if(this.FixupIntersections())this.ProcessIntersectList();else return!1}catch(c){this.m_SortedEdges=
null,this.DisposeIntersectNodes(),d.Error("ProcessIntersections error")}return!0};d.Clipper.prototype.BuildIntersectList=function(a,b){if(null!=this.m_ActiveEdges){var c=this.m_ActiveEdges;c.tmpX=d.Clipper.TopX(c,b);this.m_SortedEdges=c;this.m_SortedEdges.prevInSEL=null;for(c=c.nextInAEL;null!=c;)c.prevInSEL=c.prevInAEL,c.prevInSEL.nextInSEL=c,c.nextInSEL=null,c.tmpX=d.Clipper.TopX(c,b),c=c.nextInAEL;for(var e=!0;e&&null!=this.m_SortedEdges;){e=!1;for(c=this.m_SortedEdges;null!=c.nextInSEL;){var g=
c.nextInSEL,f=new d.IntPoint,h;if(h=c.tmpX>g.tmpX)f={Value:f},h=this.IntersectPoint(c,g,f),f=f.Value;h?(f.Y>a&&(f.Y=a,f.X=d.Clipper.TopX(c,f.Y)),this.AddIntersectNode(c,g,f),this.SwapPositionsInSEL(c,g),e=!0):c=g}if(null!=c.prevInSEL)c.prevInSEL.nextInSEL=null;else break}this.m_SortedEdges=null}};d.Clipper.prototype.FixupIntersections=function(){if(null==this.m_IntersectNodes.next)return!0;this.CopyAELToSEL();for(var a=this.m_IntersectNodes,b=this.m_IntersectNodes.next;null!=b;){var c=a.edge1;if(c.prevInSEL==
a.edge2)b=c.prevInSEL;else if(c.nextInSEL==a.edge2)b=c.nextInSEL;else{for(;null!=b&&!(b.edge1.nextInSEL==b.edge2||b.edge1.prevInSEL==b.edge2);)b=b.next;if(null==b)return!1;this.SwapIntersectNodes(a,b);c=a.edge1;b=a.edge2}this.SwapPositionsInSEL(c,b);a=a.next;b=a.next}this.m_SortedEdges=null;return a.edge1.prevInSEL==a.edge2||a.edge1.nextInSEL==a.edge2};d.Clipper.prototype.ProcessIntersectList=function(){for(;null!=this.m_IntersectNodes;){var a=this.m_IntersectNodes.next;this.IntersectEdges(this.m_IntersectNodes.edge1,
this.m_IntersectNodes.edge2,this.m_IntersectNodes.pt,d.Protects.ipBoth);this.SwapPositionsInAEL(this.m_IntersectNodes.edge1,this.m_IntersectNodes.edge2);this.m_IntersectNodes=null;this.m_IntersectNodes=a}};y=function(a){return 0>a?Math.ceil(a-0.5):Math.round(a)};H=function(a){return 0>a?Math.ceil(a-0.5):Math.floor(a+0.5)};I=function(a){return 0>a?-Math.round(Math.abs(a)):Math.round(a)};J=function(a){if(0>a)return a-=0.5,-2147483648>a?Math.ceil(a):a|0;a+=0.5;return 2147483647<a?Math.floor(a):a|0};
d.Clipper.Round=p?y:u?I:x?J:H;d.Clipper.TopX=function(a,b){return b==a.ytop?a.xtop:a.xbot+d.Clipper.Round(a.dx*(b-a.ybot))};d.Clipper.prototype.AddIntersectNode=function(a,b,c){var e=new d.IntersectNode;e.edge1=a;e.edge2=b;e.pt=c;e.next=null;if(null==this.m_IntersectNodes)this.m_IntersectNodes=e;else if(this.ProcessParam1BeforeParam2(e,this.m_IntersectNodes))e.next=this.m_IntersectNodes,this.m_IntersectNodes=e;else{for(a=this.m_IntersectNodes;null!=a.next&&this.ProcessParam1BeforeParam2(a.next,e);)a=
a.next;e.next=a.next;a.next=e}};d.Clipper.prototype.ProcessParam1BeforeParam2=function(a,b){var c;return a.pt.Y==b.pt.Y?a.edge1==b.edge1||a.edge2==b.edge1?(c=b.pt.X>a.pt.X,0<b.edge1.dx?!c:c):a.edge1==b.edge2||a.edge2==b.edge2?(c=b.pt.X>a.pt.X,0<b.edge2.dx?!c:c):b.pt.X>a.pt.X:a.pt.Y>b.pt.Y};d.Clipper.prototype.SwapIntersectNodes=function(a,b){var c=a.edge1,d=a.edge2,g=a.pt;a.edge1=b.edge1;a.edge2=b.edge2;a.pt=b.pt;b.edge1=c;b.edge2=d;b.pt=g};d.Clipper.prototype.IntersectPoint=function(a,b,c){var e,
g;if(this.SlopesEqual(a,b,this.m_UseFullRange))return!1;if(0==a.dx)c.Value.X=a.xbot,b.dx==d.ClipperBase.horizontal?c.Value.Y=b.ybot:(g=b.ybot-b.xbot/b.dx,c.Value.Y=d.Clipper.Round(c.Value.X/b.dx+g));else if(0==b.dx)c.Value.X=b.xbot,a.dx==d.ClipperBase.horizontal?c.Value.Y=a.ybot:(e=a.ybot-a.xbot/a.dx,c.Value.Y=d.Clipper.Round(c.Value.X/a.dx+e));else{e=a.xbot-a.ybot*a.dx;g=b.xbot-b.ybot*b.dx;var f=(g-e)/(a.dx-b.dx);c.Value.Y=d.Clipper.Round(f);c.Value.X=d.Math_Abs_Double(a.dx)<d.Math_Abs_Double(b.dx)?
d.Clipper.Round(a.dx*f+e):d.Clipper.Round(b.dx*f+g)}if(c.Value.Y<a.ytop||c.Value.Y<b.ytop){if(a.ytop>b.ytop)return c.Value.X=a.xtop,c.Value.Y=a.ytop,d.Clipper.TopX(b,a.ytop)<a.xtop;c.Value.X=b.xtop;c.Value.Y=b.ytop;return d.Clipper.TopX(a,b.ytop)>b.xtop}return!0};d.Clipper.prototype.DisposeIntersectNodes=function(){for(;null!=this.m_IntersectNodes;){var a=this.m_IntersectNodes.next;this.m_IntersectNodes=null;this.m_IntersectNodes=a}};d.Clipper.prototype.ProcessEdgesAtTopOfScanbeam=function(a){for(var b=
this.m_ActiveEdges,c;null!=b;)if(this.IsMaxima(b,a)&&this.GetMaximaPair(b).dx!=d.ClipperBase.horizontal)c=b.prevInAEL,this.DoMaxima(b,a),b=null==c?this.m_ActiveEdges:c.nextInAEL;else{if(this.IsIntermediate(b,a)&&b.nextInLML.dx==d.ClipperBase.horizontal){if(0<=b.outIdx){this.AddOutPt(b,new d.IntPoint(b.xtop,b.ytop));for(c=0;c<this.m_HorizJoins.length;++c){var e=new d.IntPoint,g=new d.IntPoint,f=this.m_HorizJoins[c],e={Value:e},g={Value:g};this.GetOverlapSegment(new d.IntPoint(f.edge.xbot,f.edge.ybot),
new d.IntPoint(f.edge.xtop,f.edge.ytop),new d.IntPoint(b.nextInLML.xbot,b.nextInLML.ybot),new d.IntPoint(b.nextInLML.xtop,b.nextInLML.ytop),e,g)&&this.AddJoin(f.edge,b.nextInLML,f.savedIdx,b.outIdx)}this.AddHorzJoin(b.nextInLML,b.outIdx)}b={Value:b};this.UpdateEdgeIntoAEL(b);b=b.Value;this.AddEdgeToSEL(b)}else b.xcurr=d.Clipper.TopX(b,a),b.ycurr=a;b=b.nextInAEL}this.ProcessHorizontals();for(b=this.m_ActiveEdges;null!=b;)this.IsIntermediate(b,a)&&(0<=b.outIdx&&this.AddOutPt(b,new d.IntPoint(b.xtop,
b.ytop)),b={Value:b},this.UpdateEdgeIntoAEL(b),b=b.Value,c=b.prevInAEL,e=b.nextInAEL,null!=c&&c.xcurr==b.xbot&&c.ycurr==b.ybot&&0<=b.outIdx&&0<=c.outIdx&&c.ycurr>c.ytop&&this.SlopesEqual(b,c,this.m_UseFullRange)?(this.AddOutPt(c,new d.IntPoint(b.xbot,b.ybot)),this.AddJoin(b,c,-1,-1)):null!=e&&(e.xcurr==b.xbot&&e.ycurr==b.ybot&&0<=b.outIdx&&0<=e.outIdx&&e.ycurr>e.ytop&&this.SlopesEqual(b,e,this.m_UseFullRange))&&(this.AddOutPt(e,new d.IntPoint(b.xbot,b.ybot)),this.AddJoin(b,e,-1,-1))),b=b.nextInAEL};
d.Clipper.prototype.DoMaxima=function(a,b){for(var c=this.GetMaximaPair(a),e=a.xtop,g=a.nextInAEL;g!=c;)null==g&&d.Error("DoMaxima error"),this.IntersectEdges(a,g,new d.IntPoint(e,b),d.Protects.ipBoth),g=g.nextInAEL;0>a.outIdx&&0>c.outIdx?(this.DeleteFromAEL(a),this.DeleteFromAEL(c)):0<=a.outIdx&&0<=c.outIdx?this.IntersectEdges(a,c,new d.IntPoint(e,b),d.Protects.ipNone):d.Error("DoMaxima error")};d.Clipper.ReversePolygons=function(a){for(var b=a.length,c=0;c<b;c++)a[c]instanceof Array&&a[c].reverse()};
d.Clipper.Orientation=function(a){return 0<=this.Area(a)};d.Clipper.prototype.PointCount=function(a){if(null==a)return 0;var b=0,c=a;do b++,c=c.next;while(c!=a);return b};d.Clipper.prototype.BuildResult=function(a){d.Clear(a);for(var b,c=this.m_PolyOuts.length,e=0;e<c;e++)if(b=this.m_PolyOuts[e],null!=b.pts){b=b.pts;var g=this.PointCount(b);if(!(3>g)){for(var f=new d.Polygon(g),h=0;h<g;h++)f.push(b.pt),b=b.prev;a.push(f)}}};d.Clipper.prototype.BuildResultEx=function(a){d.Clear(a);for(var b=0;b<this.m_PolyOuts.length;){var c=
this.m_PolyOuts[b++];if(null==c.pts)break;var e=c.pts,c=this.PointCount(e);if(!(3>c)){var g=new d.ExPolygon;g.outer=new d.Polygon;g.holes=new d.Polygons;for(var f=0;f<c;f++)g.outer.push(e.pt),e=e.prev;for(;b<this.m_PolyOuts.length;){c=this.m_PolyOuts[b];if(null==c.pts||!c.isHole)break;f=new d.Polygon;e=c.pts;do f.push(e.pt),e=e.prev;while(e!=c.pts);g.holes.push(f);b++}a.push(g)}}};d.Clipper.prototype.FixupOutPolygon=function(a){for(var b=null,c=a.pts=a.bottomPt;;){if(c.prev==c||c.prev==c.next){this.DisposeOutPts(c);
a.pts=null;a.bottomPt=null;return}if(d.ClipperBase.PointsEqual(c.pt,c.next.pt)||this.SlopesEqual(c.prev.pt,c.pt,c.next.pt,this.m_UseFullRange))b=null,c==a.bottomPt&&(a.bottomPt=null),c.prev.next=c.next,c=c.next.prev=c.prev;else if(c==b)break;else null==b&&(b=c),c=c.next}null==a.bottomPt&&(a.bottomPt=this.GetBottomPt(c),a.bottomPt.idx=a.idx,a.pts=a.bottomPt)};d.Clipper.prototype.JoinPoints=function(a,b,c){b.Value=null;c.Value=null;var e=this.m_PolyOuts[a.poly1Idx],g=this.m_PolyOuts[a.poly2Idx];if(null==
e||null==g)return!1;var f=e.pts,h=g.pts,j=a.pt2a,m=a.pt2b,l=a.pt1a;a=a.pt1b;var f={Value:f},j={Value:j},m={Value:m},n=this.FindSegment(f,j,m),f=f.Value,j=j.Value,m=m.Value;if(!n)return!1;if(e==g){if(h=f.next,h={Value:h},l={Value:l},a={Value:a},e=this.FindSegment(h,l,a),h=h.Value,l=l.Value,a=a.Value,!e||h==f)return!1}else if(h={Value:h},l={Value:l},a={Value:a},e=this.FindSegment(h,l,a),h=h.Value,l=l.Value,a=a.Value,!e)return!1;j={Value:j};m={Value:m};l=this.GetOverlapSegment(j.Value,m.Value,l,a,j,
m);j=j.Value;m=m.Value;if(!l)return!1;l=f.prev;b.Value=d.ClipperBase.PointsEqual(f.pt,j)?f:d.ClipperBase.PointsEqual(l.pt,j)?l:this.InsertPolyPtBetween(f,l,j);c.Value=d.ClipperBase.PointsEqual(f.pt,m)?f:d.ClipperBase.PointsEqual(l.pt,m)?l:b.Value==f||b.Value==l?this.InsertPolyPtBetween(f,l,m):this.Pt3IsBetweenPt1AndPt2(f.pt,b.Value.pt,m)?this.InsertPolyPtBetween(f,b.Value,m):this.InsertPolyPtBetween(b.Value,l,m);l=h.prev;f=d.ClipperBase.PointsEqual(h.pt,j)?h:d.ClipperBase.PointsEqual(l.pt,j)?l:this.InsertPolyPtBetween(h,
l,j);h=d.ClipperBase.PointsEqual(h.pt,m)?h:d.ClipperBase.PointsEqual(l.pt,m)?l:f==h||f==l?this.InsertPolyPtBetween(h,l,m):this.Pt3IsBetweenPt1AndPt2(h.pt,f.pt,m)?this.InsertPolyPtBetween(h,f,m):this.InsertPolyPtBetween(f,l,m);return b.Value.next==c.Value&&f.prev==h?(b.Value.next=f,f.prev=b.Value,c.Value.prev=h,h.next=c.Value,!0):b.Value.prev==c.Value&&f.next==h?(b.Value.prev=f,f.next=b.Value,c.Value.next=h,h.prev=c.Value,!0):!1};d.Clipper.prototype.FixupJoinRecs=function(a,b,c){for(;c<this.m_Joins.length;c++){var d=
this.m_Joins[c];d.poly1Idx==a.poly1Idx&&this.PointIsVertex(d.pt1a,b)&&(d.poly1Idx=a.poly2Idx);d.poly2Idx==a.poly1Idx&&this.PointIsVertex(d.pt2a,b)&&(d.poly2Idx=a.poly2Idx)}};d.Clipper.prototype.JoinCommonEdges=function(){for(var a,b,c=0;c<this.m_Joins.length;c++){a=this.m_Joins[c];var d,g;d={Value:d};g={Value:g};var f=this.JoinPoints(a,d,g);d=d.Value;g=g.Value;if(f){var f=this.m_PolyOuts[a.poly1Idx],h=this.m_PolyOuts[a.poly2Idx];if(f==h)if(f.pts=this.GetBottomPt(d),f.bottomPt=f.pts,f.bottomPt.idx=
f.idx,h=this.CreateOutRec(),this.m_PolyOuts.push(h),h.idx=this.m_PolyOuts.length-1,a.poly2Idx=h.idx,h.pts=this.GetBottomPt(g),h.bottomPt=h.pts,h.bottomPt.idx=h.idx,this.PointInPolygon(h.pts.pt,f.pts,this.m_UseFullRange))h.isHole=!f.isHole,h.FirstLeft=f,this.FixupJoinRecs(a,g,c+1),this.FixupOutPolygon(f),this.FixupOutPolygon(h),(h.isHole^this.m_ReverseOutput)==0<this.Area(h,this.m_UseFullRange)&&this.ReversePolyPtLinks(h.pts);else if(this.PointInPolygon(f.pts.pt,h.pts,this.m_UseFullRange)){if(h.isHole=
f.isHole,f.isHole=!h.isHole,h.FirstLeft=f.FirstLeft,f.FirstLeft=h,this.FixupJoinRecs(a,g,c+1),this.FixupOutPolygon(f),this.FixupOutPolygon(h),(f.isHole^this.m_ReverseOutput)==0<this.Area(f,this.m_UseFullRange)&&this.ReversePolyPtLinks(f.pts),this.m_UsingExPolygons&&f.isHole)for(a=0;a<this.m_PolyOuts.length;++a)b=this.m_PolyOuts[a],b.isHole&&(null!=b.bottomPt&&b.FirstLeft==f)&&(b.FirstLeft=h)}else{if(h.isHole=f.isHole,h.FirstLeft=f.FirstLeft,this.FixupJoinRecs(a,g,c+1),this.FixupOutPolygon(f),this.FixupOutPolygon(h),
this.m_UsingExPolygons&&null!=h.pts)for(a=0;a<this.m_PolyOuts.length;++a)b=this.m_PolyOuts[a],b.isHole&&(null!=b.bottomPt&&b.FirstLeft==f&&this.PointInPolygon(b.bottomPt.pt,h.pts,this.m_UseFullRange))&&(b.FirstLeft=h)}else{if(this.m_UsingExPolygons)for(a=0;a<this.m_PolyOuts.length;++a)this.m_PolyOuts[a].isHole&&(null!=this.m_PolyOuts[a].bottomPt&&this.m_PolyOuts[a].FirstLeft==h)&&(this.m_PolyOuts[a].FirstLeft=f);this.FixupOutPolygon(f);null!=f.pts&&(f.isHole=0>this.Area(f,this.m_UseFullRange),f.isHole&&
null==f.FirstLeft&&(f.FirstLeft=h.FirstLeft));b=f.idx;var j=h.idx;h.pts=null;h.bottomPt=null;h.AppendLink=f;for(a=c+1;a<this.m_Joins.length;a++)f=this.m_Joins[a],f.poly1Idx==j&&(f.poly1Idx=b),f.poly2Idx==j&&(f.poly2Idx=b)}}}};d.Clipper.FullRangeNeeded=function(a){for(var b=!1,c=0;c<a.length;c++)if(d.Math_Abs_Int64(a[c].X)>d.ClipperBase.hiRange||d.Math_Abs_Int64(a[c].Y)>d.ClipperBase.hiRange)d.Error("Coordinate exceeds range bounds in FullRangeNeeded().");else if(d.Math_Abs_Int64(a[c].X)>d.ClipperBase.loRange||
d.Math_Abs_Int64(a[c].Y)>d.ClipperBase.loRange)b=!0;return b};d.Clipper.prototype.Area=d.Clipper.Area=function(){var a=arguments,b;if(1==a.length){var c=a[0],e=c.length-1;if(2>e)return 0;if(d.Clipper.FullRangeNeeded(c)){a=(new j(c[e].X+c[0].X)).multiply(new j(c[0].Y-c[e].Y));for(b=1;b<=e;++b)a=a.add((new j(c[b-1].X+c[b].X)).multiply(new j(c[b].Y-c[b-1].Y)));return parseFloat(a.toString())/2}a=(c[e].X+c[0].X)*(c[0].Y-c[e].Y);for(b=1;b<=e;++b)a+=(c[b-1].X+c[b].X)*(c[b].Y-c[b-1].Y);return a/2}if(2==
a.length){b=a[0];c=b.pts;if(null==c)return 0;if(a[1]){a=new j(j.ZERO);do a=a.add((new j(c.pt.X+c.prev.pt.X)).multiply(new j(c.prev.pt.Y-c.pt.Y))),c=c.next;while(c!=b.pts);return parseFloat(a.toString())/2}a=0;do a+=(c.pt.X+c.prev.pt.X)*(c.prev.pt.Y-c.pt.Y),c=c.next;while(c!=b.pts);return a/2}};d.Clipper.BuildArc=function(a,b,c,e){var g=Math.sqrt(d.Math_Abs_Double(e))*d.Math_Abs_Double(c-b),g=g/4;6>g&&(g=6);64<g&&(g=d.MaxSteps);var g=d.Cast_Int32(g),f=new d.Polygon;c=(c-b)/(g-1);for(var h=0;h<g;++h)f.push(new d.IntPoint(a.X+
d.Clipper.Round(Math.cos(b)*e),a.Y+d.Clipper.Round(Math.sin(b)*e))),b+=c;return f};d.Clipper.GetUnitNormal=function(a,b){var c=b.X-a.X,e=b.Y-a.Y;if(0==c&&0==e)return new d.Clipper.DoublePoint(0,0);var g=1/Math.sqrt(c*c+e*e);return new d.Clipper.DoublePoint(e*g,-(c*g))};d.Clipper.prototype.OffsetPolygons=function(a,b,c,e,g){var f=arguments;4==f.length?g=!0:3==f.length?(e=2,g=!0):2==f.length&&(c=d.JoinType.jtSquare,e=2,g=!0);isNaN(b)?d.Error("Delta is not a number"):isNaN(e)&&d.Error("MiterLimit is not a number");
f={};new d.Clipper.PolyOffsetBuilder(a,f,b,c,e,g);return f=f.Value?f.Value:[[]]};d.Clipper.prototype.SimplifyPolygon=function(a,b){var c=new d.Polygons,e=new d.Clipper;e.AddPolygon(a,d.PolyType.ptSubject)&&e.Execute(d.ClipType.ctUnion,c,b,b);return c};d.Clipper.prototype.SimplifyPolygons=function(a,b){var c=new d.Polygons,e=new d.Clipper;e.AddPolygons(a,d.PolyType.ptSubject)&&e.Execute(d.ClipType.ctUnion,c,b,b);return c};u=d.Clipper;x=d.ClipperBase;var z;if("undefined"==typeof Object.getOwnPropertyNames)for(z in x.prototype){if("undefined"==
typeof u.prototype[z]||u.prototype[z]==Object.prototype[z])u.prototype[z]=x.prototype[z]}else{p=Object.getOwnPropertyNames(x.prototype);for(y=0;y<p.length;y++)"undefined"==typeof Object.getOwnPropertyDescriptor(u.prototype,p[y])&&Object.defineProperty(u.prototype,p[y],Object.getOwnPropertyDescriptor(x.prototype,p[y]))}for(z in x)"undefined"==typeof u[z]&&(u[z]=x[z]);u.$baseCtor=x;d.Clipper.DoublePoint=function(a,b){this.X=a;this.Y=b};d.Clipper.PolyOffsetBuilder=function(a,b,c,e,g,f){this.normals=
this.currentPoly=this.pts=null;this.m_k=this.m_j=this.m_i=this.m_R=this.delta=0;this.botPt=null;if(0==c)b.Value=a;else{this.pts=a;this.delta=c;if(f){for(var h=this.pts.length,j=0;j<h&&0==this.pts[j].length;)j++;if(j==h)return;this.botPt=this.pts[j][0];for(f=j;f<h;++f){this.UpdateBotPt(this.pts[f][0])&&(j=f);for(a=this.pts[f].length-1;0<a;a--)d.ClipperBase.PointsEqual(this.pts[f][a],this.pts[f][a-1])?this.pts[f].splice(a,1):this.UpdateBotPt(this.pts[f][a])&&(j=f)}d.Clipper.Orientation(this.pts[j])||
d.Clipper.ReversePolygons(this.pts)}1>=g&&(g=1);f=2/(g*g);this.normals=[];b.Value=new d.Polygons;d.Clear(b.Value);for(this.m_i=0;this.m_i<this.pts.length;this.m_i++)if(h=this.pts[this.m_i].length,1<h&&(this.pts[this.m_i][0].X==this.pts[this.m_i][h-1].X&&this.pts[this.m_i][0].Y==this.pts[this.m_i][h-1].Y)&&h--,!(0==h||3>h&&0>=c))if(1==h)a=d.Clipper.BuildArc(this.pts[this.m_i][h-1],0,d.PI2,c),b.Value.push(a);else{d.Clear(this.normals);for(a=0;a<h-1;++a)this.normals.push(d.Clipper.GetUnitNormal(this.pts[this.m_i][a],
this.pts[this.m_i][a+1]));this.normals.push(d.Clipper.GetUnitNormal(this.pts[this.m_i][h-1],this.pts[this.m_i][0]));this.currentPoly=new d.Polygon;this.m_k=h-1;for(this.m_j=0;this.m_j<h;++this.m_j){switch(e){case d.JoinType.jtMiter:this.m_R=1+(this.normals[this.m_j].X*this.normals[this.m_k].X+this.normals[this.m_j].Y*this.normals[this.m_k].Y);this.m_R>=f?this.DoMiter():this.DoSquare(g);break;case d.JoinType.jtRound:this.DoRound();break;case d.JoinType.jtSquare:this.DoSquare(1)}this.m_k=this.m_j}b.Value.push(this.currentPoly)}e=
new d.Clipper;e.AddPolygons(b.Value,d.PolyType.ptSubject);if(0<c)e.Execute(d.ClipType.ctUnion,b.Value,d.PolyFillType.pftPositive,d.PolyFillType.pftPositive);else if(c=e.GetBounds(),g=new d.Polygon,g.push(new d.IntPoint(c.left-10,c.bottom+10)),g.push(new d.IntPoint(c.right+10,c.bottom+10)),g.push(new d.IntPoint(c.right+10,c.top-10)),g.push(new d.IntPoint(c.left-10,c.top-10)),e.AddPolygon(g,d.PolyType.ptSubject),e.Execute(d.ClipType.ctUnion,b.Value,d.PolyFillType.pftNegative,d.PolyFillType.pftNegative),
0<b.Value.length){b.Value.splice(0,1);for(f=0;f<b.Value.length;f++)b.Value[f].reverse()}}};d.Clipper.PolyOffsetBuilder.prototype.UpdateBotPt=function(a){return a.Y>this.botPt.Y||a.Y==this.botPt.Y&&a.X<this.botPt.X?(this.botPt=a,!0):!1};d.Clipper.PolyOffsetBuilder.prototype.AddPoint=function(a){this.currentPoly.push(a)};d.Clipper.PolyOffsetBuilder.prototype.DoSquare=function(a){var b=new d.IntPoint(d.Cast_Int64(d.Clipper.Round(this.pts[this.m_i][this.m_j].X+this.normals[this.m_k].X*this.delta)),d.Cast_Int64(d.Clipper.Round(this.pts[this.m_i][this.m_j].Y+
this.normals[this.m_k].Y*this.delta))),c=new d.IntPoint(d.Cast_Int64(d.Clipper.Round(this.pts[this.m_i][this.m_j].X+this.normals[this.m_j].X*this.delta)),d.Cast_Int64(d.Clipper.Round(this.pts[this.m_i][this.m_j].Y+this.normals[this.m_j].Y*this.delta)));if(0<=(this.normals[this.m_k].X*this.normals[this.m_j].Y-this.normals[this.m_j].X*this.normals[this.m_k].Y)*this.delta){var e=Math.atan2(this.normals[this.m_k].Y,this.normals[this.m_k].X),g=Math.atan2(-this.normals[this.m_j].Y,-this.normals[this.m_j].X),
e=Math.abs(g-e);e>d.PI&&(e=d.PI2-e);a=Math.tan((d.PI-e)/4)*Math.abs(this.delta*a);b=new d.IntPoint(d.Cast_Int64(b.X-this.normals[this.m_k].Y*a),d.Cast_Int64(b.Y+this.normals[this.m_k].X*a));this.AddPoint(b);c=new d.IntPoint(d.Cast_Int64(c.X+this.normals[this.m_j].Y*a),d.Cast_Int64(c.Y-this.normals[this.m_j].X*a))}else this.AddPoint(b),this.AddPoint(this.pts[this.m_i][this.m_j]);this.AddPoint(c)};d.Clipper.PolyOffsetBuilder.prototype.DoMiter=function(){if(0<=(this.normals[this.m_k].X*this.normals[this.m_j].Y-
this.normals[this.m_j].X*this.normals[this.m_k].Y)*this.delta){var a=this.delta/this.m_R;this.AddPoint(new d.IntPoint(d.Cast_Int64(d.Clipper.Round(this.pts[this.m_i][this.m_j].X+(this.normals[this.m_k].X+this.normals[this.m_j].X)*a)),d.Cast_Int64(d.Clipper.Round(this.pts[this.m_i][this.m_j].Y+(this.normals[this.m_k].Y+this.normals[this.m_j].Y)*a))))}else{var a=new d.IntPoint(d.Cast_Int64(d.Clipper.Round(this.pts[this.m_i][this.m_j].X+this.normals[this.m_k].X*this.delta)),d.Cast_Int64(d.Clipper.Round(this.pts[this.m_i][this.m_j].Y+
this.normals[this.m_k].Y*this.delta))),b=new d.IntPoint(d.Cast_Int64(d.Clipper.Round(this.pts[this.m_i][this.m_j].X+this.normals[this.m_j].X*this.delta)),d.Cast_Int64(d.Clipper.Round(this.pts[this.m_i][this.m_j].Y+this.normals[this.m_j].Y*this.delta)));this.AddPoint(a);this.AddPoint(this.pts[this.m_i][this.m_j]);this.AddPoint(b)}};d.Clipper.PolyOffsetBuilder.prototype.DoRound=function(){var a=new d.IntPoint(d.Clipper.Round(this.pts[this.m_i][this.m_j].X+this.normals[this.m_k].X*this.delta),d.Clipper.Round(this.pts[this.m_i][this.m_j].Y+
this.normals[this.m_k].Y*this.delta)),b=new d.IntPoint(d.Clipper.Round(this.pts[this.m_i][this.m_j].X+this.normals[this.m_j].X*this.delta),d.Clipper.Round(this.pts[this.m_i][this.m_j].Y+this.normals[this.m_j].Y*this.delta));this.AddPoint(a);if(0<=(this.normals[this.m_k].X*this.normals[this.m_j].Y-this.normals[this.m_j].X*this.normals[this.m_k].Y)*this.delta){if(0.985>this.normals[this.m_j].X*this.normals[this.m_k].X+this.normals[this.m_j].Y*this.normals[this.m_k].Y){var a=Math.atan2(this.normals[this.m_k].Y,
this.normals[this.m_k].X),c=Math.atan2(this.normals[this.m_j].Y,this.normals[this.m_j].X);0<this.delta&&c<a?c+=d.PI2:0>this.delta&&c>a&&(c-=d.PI2);a=d.Clipper.BuildArc(this.pts[this.m_i][this.m_j],a,c,this.delta);for(c=0;c<a.length;c++)this.AddPoint(a[c])}}else this.AddPoint(this.pts[this.m_i][this.m_j]);this.AddPoint(b)};d.Error=function(a){try{throw Error(a);}catch(b){alert(b.message)}};d.Clone=function(a){if(!(a instanceof Array)||0==a.length)return[];if(1==a.length&&0==a[0].length)return[[]];
var b=a[0]instanceof Array;b||(a=[a]);var c=a.length,d,g,f,h,j=[];for(g=0;g<c;g++){d=a[g].length;h=[];for(f=0;f<d;f++)h.push({X:a[g][f].X,Y:a[g][f].Y});j.push(h)}b||(j=j[0]);return j};d.Clean=function(a,b){if(!(a instanceof Array))return[];var c=a[0]instanceof Array;a=d.Clone(a);if("number"!=typeof b||null===b)return d.Error("Delta is not a number in Clean()."),a;if(0==a.length||1==a.length&&0==a[0].length||0>b)return a;c||(a=[a]);for(var e=a.length,g,f,h,j,m,l,n,q=[],p=0;p<e;p++)if(f=a[p],g=f.length,
0!=g)if(3>g)h=f,q.push(h);else{h=f;j=b*b;m=f[0];for(n=l=1;n<g;n++)(f[n].X-m.X)*(f[n].X-m.X)+(f[n].Y-m.Y)*(f[n].Y-m.Y)<=j||(h[l]=f[n],m=f[n],l++);m=f[l-1];(f[0].X-m.X)*(f[0].X-m.X)+(f[0].Y-m.Y)*(f[0].Y-m.Y)<=j&&l--;l<g&&h.splice(l,g-l);h.length&&q.push(h)}!c&&q.length?q=q[0]:!c&&0==q.length?q=[]:c&&0==q.length&&(q=[[]]);return q};d.Lighten=function(a,b){if(!(a instanceof Array))return[];if("number"!=typeof b||null===b)return d.Error("Tolerance is not a number in Lighten()."),d.Clone(a);if(0===a.length||
1==a.length&&0===a[0].length||0>b)return d.Clone(a);a[0]instanceof Array||(a=[a]);var c,e,g,f,h,j,m,l,n,p,r,s,t,v=a.length,u=[];for(c=0;c<v;c++){g=a[c];for(f=0;1E6>f;f++){h=[];j=g.length;g[j-1].X!=g[0].X||g[j-1].Y!=g[0].Y?(s=1,g.push({X:g[0].X,Y:g[0].Y}),j=g.length):s=0;r=[];for(e=0;e<j-2;e++){m=g[e];n=g[e+1];l=g[e+2];t=l.X-m.X;l=l.Y-m.Y;p=0;if(0!==t||0!==l)p=Math.sqrt(t*t+l*l),p=Math.abs((n.X-m.X)*l-(n.Y-m.Y)*t)/p;p<=b&&(r[e+1]=1,e++)}h.push({X:g[0].X,Y:g[0].Y});for(e=1;e<j-1;e++)r[e]||h.push({X:g[e].X,
Y:g[e].Y});h.push({X:g[j-1].X,Y:g[j-1].Y});s&&g.pop();if(r.length)g=h;else break}j=h.length;h[j-1].X==h[0].X&&h[j-1].Y==h[0].Y&&h.pop();2<h.length&&u.push(h)}!a[0]instanceof Array&&(u=u[0]);"undefined"==typeof u&&(u=[[]]);return u};Q.ClipperLib=d})(window);