/**
 * Cesium - https://github.com/CesiumGS/cesium
 *
 * Copyright 2011-2020 Cesium Contributors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * Columbus View (Pat. Pend.)
 *
 * Portions licensed separately.
 * See https://github.com/CesiumGS/cesium/blob/master/LICENSE.md for full licensing details.
 */
define(["exports"],function(e){function n(e,n,t){t=t||2;var r,x,i,v,u,f,y,o=n&&n.length,p=o?n[0]*t:e.length,a=s(e,0,p,t,!0),h=[];if(!a||a.next===a.prev)return h;if(o&&(a=function(e,n,t,r){var x,i,v,u,f,y=[];for(x=0,i=n.length;x<i;x++)v=n[x]*r,u=x<i-1?n[x+1]*r:e.length,(f=s(e,v,u,r,!1))===f.next&&(f.steiner=!0),y.push(w(f));for(y.sort(g),x=0;x<y.length;x++)d(y[x],t),t=c(t,t.next);return t}(e,n,a,t)),e.length>80*t){r=i=e[0],x=v=e[1];for(var l=t;l<p;l+=t)(u=e[l])<r&&(r=u),(f=e[l+1])<x&&(x=f),i<u&&(i=u),v<f&&(v=f);y=0!==(y=Math.max(i-r,v-x))?1/y:0}return Z(a,h,t,r,x,y),h}function s(e,n,t,r,x){var i,v;if(x===0<A(e,n,t,r))for(i=n;i<t;i+=r)v=u(i,e[i],e[i+1],v);else for(i=t-r;n<=i;i-=r)v=u(i,e[i],e[i+1],v);return v&&l(v,v.next)&&(q(v),v=v.next),v}function c(e,n){if(!e)return e;n||(n=e);var t,r=e;do{if(t=!1,r.steiner||!l(r,r.next)&&0!==b(r.prev,r,r.next))r=r.next;else{if(q(r),(r=n=r.prev)===r.next)break;t=!0}}while(t||r!==n);return n}function Z(e,n,t,r,x,i,v){if(e){!v&&i&&function(e,n,t,r){var x=e;for(;null===x.z&&(x.z=M(x.x,x.y,n,t,r)),x.prevZ=x.prev,x.nextZ=x.next,x=x.next,x!==e;);x.prevZ.nextZ=null,x.prevZ=null,function(e){var n,t,r,x,i,v,u,f,y=1;do{for(t=e,i=e=null,v=0;t;){for(v++,r=t,n=u=0;n<y&&(u++,r=r.nextZ);n++);for(f=y;0<u||0<f&&r;)0!==u&&(0===f||!r||t.z<=r.z)?(t=(x=t).nextZ,u--):(r=(x=r).nextZ,f--),i?i.nextZ=x:e=x,x.prevZ=i,i=x;t=r}i.nextZ=null,y*=2}while(1<v)}(x)}(e,r,x,i);for(var u,f,y=e;e.prev!==e.next;)if(u=e.prev,f=e.next,i?p(e,r,x,i):o(e))n.push(u.i/t),n.push(e.i/t),n.push(f.i/t),q(e),e=f.next,y=f.next;else if((e=f)===y){v?1===v?Z(e=a(c(e),n,t),n,t,r,x,i,2):2===v&&h(e,n,t,r,x,i):Z(c(e),n,t,r,x,i,1);break}}}function o(e){var n=e.prev,t=e,r=e.next;if(0<=b(n,t,r))return!1;for(var x=e.next.next;x!==e.prev;){if(z(n.x,n.y,t.x,t.y,r.x,r.y,x.x,x.y)&&0<=b(x.prev,x,x.next))return!1;x=x.next}return!0}function p(e,n,t,r){var x=e.prev,i=e,v=e.next;if(0<=b(x,i,v))return!1;for(var u=x.x<i.x?x.x<v.x?x.x:v.x:i.x<v.x?i.x:v.x,f=x.y<i.y?x.y<v.y?x.y:v.y:i.y<v.y?i.y:v.y,y=x.x>i.x?x.x>v.x?x.x:v.x:i.x>v.x?i.x:v.x,o=x.y>i.y?x.y>v.y?x.y:v.y:i.y>v.y?i.y:v.y,p=M(u,f,n,t,r),a=M(y,o,n,t,r),h=e.prevZ,l=e.nextZ;h&&h.z>=p&&l&&l.z<=a;){if(h!==e.prev&&h!==e.next&&z(x.x,x.y,i.x,i.y,v.x,v.y,h.x,h.y)&&0<=b(h.prev,h,h.next))return!1;if(h=h.prevZ,l!==e.prev&&l!==e.next&&z(x.x,x.y,i.x,i.y,v.x,v.y,l.x,l.y)&&0<=b(l.prev,l,l.next))return!1;l=l.nextZ}for(;h&&h.z>=p;){if(h!==e.prev&&h!==e.next&&z(x.x,x.y,i.x,i.y,v.x,v.y,h.x,h.y)&&0<=b(h.prev,h,h.next))return!1;h=h.prevZ}for(;l&&l.z<=a;){if(l!==e.prev&&l!==e.next&&z(x.x,x.y,i.x,i.y,v.x,v.y,l.x,l.y)&&0<=b(l.prev,l,l.next))return!1;l=l.nextZ}return!0}function a(e,n,t){var r=e;do{var x=r.prev,i=r.next.next;!l(x,i)&&m(x,r,r.next,i)&&k(x,i)&&k(i,x)&&(n.push(x.i/t),n.push(r.i/t),n.push(i.i/t),q(r),q(r.next),r=e=i),r=r.next}while(r!==e);return c(r)}function h(e,n,t,r,x,i){var v,u,f=e;do{for(var y=f.next.next;y!==f.prev;){if(f.i!==y.i&&(u=y,(v=f).next.i!==u.i&&v.prev.i!==u.i&&!function(e,n){var t=e;do{if(t.i!==e.i&&t.next.i!==e.i&&t.i!==n.i&&t.next.i!==n.i&&m(t,t.next,e,n))return!0;t=t.next}while(t!==e);return!1}(v,u)&&(k(v,u)&&k(u,v)&&function(e,n){var t=e,r=!1,x=(e.x+n.x)/2,i=(e.y+n.y)/2;for(;t.y>i!=t.next.y>i&&t.next.y!==t.y&&x<(t.next.x-t.x)*(i-t.y)/(t.next.y-t.y)+t.x&&(r=!r),t=t.next,t!==e;);return r}(v,u)&&(b(v.prev,v,u.prev)||b(v,u.prev,u))||l(v,u)&&0<b(v.prev,v,v.next)&&0<b(u.prev,u,u.next)))){var o=j(f,y);return f=c(f,f.next),o=c(o,o.next),Z(f,n,t,r,x,i),void Z(o,n,t,r,x,i)}y=y.next}f=f.next}while(f!==e)}function g(e,n){return e.x-n.x}function d(e,n){if(n=function(e,n){var t,r=n,x=e.x,i=e.y,v=-1/0;do{if(i<=r.y&&i>=r.next.y&&r.next.y!==r.y){var u=r.x+(i-r.y)*(r.next.x-r.x)/(r.next.y-r.y);if(u<=x&&v<u){if((v=u)===x){if(i===r.y)return r;if(i===r.next.y)return r.next}t=r.x<r.next.x?r:r.next}}r=r.next}while(r!==n);if(!t)return null;if(x===v)return t;var f,y=t,o=t.x,p=t.y,a=1/0;r=t;for(;x>=r.x&&r.x>=o&&x!==r.x&&z(i<p?x:v,i,o,p,i<p?v:x,i,r.x,r.y)&&(f=Math.abs(i-r.y)/(x-r.x),k(r,e)&&(f<a||f===a&&(r.x>t.x||r.x===t.x&&(l=r,b((h=t).prev,h,l.prev)<0&&b(l.next,h,h.next)<0)))&&(t=r,a=f)),r=r.next,r!==y;);var h,l;return t}(e,n)){var t=j(n,e);c(t,t.next)}}function M(e,n,t,r,x){return(e=1431655765&((e=858993459&((e=252645135&((e=16711935&((e=32767*(e-t)*x)|e<<8))|e<<4))|e<<2))|e<<1))|(n=1431655765&((n=858993459&((n=252645135&((n=16711935&((n=32767*(n-r)*x)|n<<8))|n<<4))|n<<2))|n<<1))<<1}function w(e){for(var n=e,t=e;(n.x<t.x||n.x===t.x&&n.y<t.y)&&(t=n),(n=n.next)!==e;);return t}function z(e,n,t,r,x,i,v,u){return 0<=(x-v)*(n-u)-(e-v)*(i-u)&&0<=(e-v)*(r-u)-(t-v)*(n-u)&&0<=(t-v)*(i-u)-(x-v)*(r-u)}function b(e,n,t){return(n.y-e.y)*(t.x-n.x)-(n.x-e.x)*(t.y-n.y)}function l(e,n){return e.x===n.x&&e.y===n.y}function m(e,n,t,r){var x=y(b(e,n,t)),i=y(b(e,n,r)),v=y(b(t,r,e)),u=y(b(t,r,n));return x!==i&&v!==u||(!(0!==x||!f(e,t,n))||(!(0!==i||!f(e,r,n))||(!(0!==v||!f(t,e,r))||!(0!==u||!f(t,n,r)))))}function f(e,n,t){return n.x<=Math.max(e.x,t.x)&&n.x>=Math.min(e.x,t.x)&&n.y<=Math.max(e.y,t.y)&&n.y>=Math.min(e.y,t.y)}function y(e){return 0<e?1:e<0?-1:0}function k(e,n){return b(e.prev,e,e.next)<0?0<=b(e,n,e.next)&&0<=b(e,e.prev,n):b(e,n,e.prev)<0||b(e,e.next,n)<0}function j(e,n){var t=new v(e.i,e.x,e.y),r=new v(n.i,n.x,n.y),x=e.next,i=n.prev;return(e.next=n).prev=e,(t.next=x).prev=t,(r.next=t).prev=r,(i.next=r).prev=i,r}function u(e,n,t,r){var x=new v(e,n,t);return r?(x.next=r.next,(x.prev=r).next.prev=x,r.next=x):(x.prev=x).next=x,x}function q(e){e.next.prev=e.prev,e.prev.next=e.next,e.prevZ&&(e.prevZ.nextZ=e.nextZ),e.nextZ&&(e.nextZ.prevZ=e.prevZ)}function v(e,n,t){this.i=e,this.x=n,this.y=t,this.prev=null,this.next=null,this.z=null,this.prevZ=null,this.nextZ=null,this.steiner=!1}function A(e,n,t,r){for(var x=0,i=n,v=t-r;i<t;i+=r)x+=(e[v]-e[i])*(e[i+1]+e[v+1]),v=i;return x}n.deviation=function(e,n,t,r){var x=n&&n.length,i=x?n[0]*t:e.length,v=Math.abs(A(e,0,i,t));if(x)for(var u=0,f=n.length;u<f;u++){var y=n[u]*t,o=u<f-1?n[u+1]*t:e.length;v-=Math.abs(A(e,y,o,t))}var p=0;for(u=0;u<r.length;u+=3){var a=r[u]*t,h=r[u+1]*t,l=r[u+2]*t;p+=Math.abs((e[a]-e[l])*(e[h+1]-e[a+1])-(e[a]-e[h])*(e[l+1]-e[a+1]))}return 0===v&&0===p?0:Math.abs((p-v)/v)},n.flatten=function(e){for(var n=e[0][0].length,t={vertices:[],holes:[],dimensions:n},r=0,x=0;x<e.length;x++){for(var i=0;i<e[x].length;i++)for(var v=0;v<n;v++)t.vertices.push(e[x][i][v]);0<x&&(r+=e[x-1].length,t.holes.push(r))}return t},e.earcut=n});