https://www.sweethome3d.com/wp-content/plugins/sh3d-lib-scripts/vendor/triangulator.min.js?ver=7.5

1/*
2 * triangulator.min.js  version 7.5.2
3 * 
4 * Copyright (c) 2024 Space Mushrooms <[email protected]>
5 * 
6 * Copyright (c) 2007 Sun Microsystems, Inc. All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * - Redistribution of source code must retain the above copyright
13 *   notice, this list of conditions and the following disclaimer.
14 *
15 * - Redistribution in binary form must reproduce the above copyright
16 *   notice, this list of conditions and the following disclaimer in
17 *   the documentation and/or other materials provided with the
18 *   distribution.
19 *
20 * Neither the name of Sun Microsystems, Inc. or the names of
21 * contributors may be used to endorse or promote products derived
22 * from this software without specific prior written permission.
23 *
24 * This software is provided "AS IS," without a warranty of any
25 * kind. ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND
26 * WARRANTIES, INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY,
27 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY
28 * EXCLUDED. SUN MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL
29 * NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF
30 * USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS
31 * DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR
32 * ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL,
33 * CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND
34 * REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF THE USE OF OR
35 * INABILITY TO USE THIS SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE
36 * POSSIBILITY OF SUCH DAMAGES.
37 *
38 * You acknowledge that this software is not designed, licensed or
39 * intended for use in the design, construction, operation or
40 * maintenance of any nuclear facility.
41 */
42function Triangulator(){this.loops=null;this.chains=null;this.points=null;this.numPoints=0;this.triangles=null;this.list=null;this.firstNode=0;this.pointsUnsorted=null;this.maxNumPUnsorted=0;this.noHashingEdges=false;this.noHashingPnts=false;this.loopMin=0;this.loopMax=0;this.vertexList=null;this.reflexVertices=0;this.numReflex=0;this.distances=null;this.maxNumDist=0;this.heap=null;this.numHeap=0;this.numZero=0;this.polyArea=null;this.ccwLoop=true;this.identCntr;this.epsilon=1e-12}Triangulator.ZERO=1e-8;Triangulator.prototype.triangulate=function(c,g,b,i,f,q,m,t){this.vertices=c;this.maxNumDist=0;this.maxNumPUnsorted=0;this.loops=[];this.list=[];this.numReflex=0;this.numPoints=0;var d=0;if(f===null){f=[g.length]}for(var p=0;p<f.length;p++){var e=this.makeLoopHeader();var s=this.loops[e];for(var o=0;o<f[p];o++){var h=this.list.length;this.list.push(new Triangulator.ListNode(g[d]));this.insertAfter(s,h);this.list[h].setCommonIndex(d);s=h;d++}this.deleteHook(e)}this.triangles=[];this.epsilon=Triangulator.ZERO;var u=false,a=false;var l=[false];var n=[false];for(var p=0;p<f.length;p++){this.ccwLoop=true;if(!this.simpleFace(this.loops[p])){this.preProcessList(p);this.projectFace(p,p+1);var r=this.cleanPolyhedralFace(p,p+1);this.determineOrientation(this.loops[p]);this.noHashingEdges=false;this.noHashingPnts=false;this.classifyAngles(this.loops[p]);this.resetPolyList(this.loops[p]);this.prepareNoHashPoints(p);this.classifyEars(this.loops[p]);l[0]=false;while(!l[0]){if(!this.clipEar(l)){if(u){var h=this.getNode();this.resetPolyList(h);this.loops[p]=h;if(this.desperate(h,p,l)){if(!this.letsHope(h)){return}}else{u=false}}else{a=true;var h=this.getNode();this.resetPolyList(h);this.classifyEars(h);u=true}}else{u=false}if(l[0]){var h=this.getNextChain(n);if(n[0]){this.resetPolyList(h);this.loops[p]=h;this.noHashingPnts=false;this.prepareNoHashPoints(p);this.classifyEars(h);u=false;l[0]=false}}}}}this.copyToTriangles(g,b,i,q,m,t)};Triangulator.prototype.preProcessList=function(b){this.resetPolyList(this.loops[b]);var c=this.loops[b];var a=c;var d=this.list[a].next;while(d!==c){if(this.list[a].index===this.list[d].index){if(d===this.loops[b]){this.loops[b]=this.list[d].next}this.deleteLinks(d)}a=this.list[a].next;d=this.list[a].next}};Triangulator.prototype.copyToTriangles=function(f,g,c,e,b,h){for(var d=0;d<this.triangles.length;d++){var a=this.list[this.triangles[d].v1].getCommonIndex();e.push(f[a]);a=this.list[this.triangles[d].v2].getCommonIndex();e.push(f[a]);a=this.list[this.triangles[d].v3].getCommonIndex();e.push(f[a])}if(g!==null&&g.length>0){for(var d=0;d<this.triangles.length;d++){var a=this.list[this.triangles[d].v1].getCommonIndex();b.push(g[a]);a=this.list[this.triangles[d].v2].getCommonIndex();b.push(g[a]);a=this.list[this.triangles[d].v3].getCommonIndex();b.push(g[a])}}if(c!==null&&c.length){currIndex=0;for(var d=0;d<this.triangles.length;d++){var a=this.list[this.triangles[d].v1].getCommonIndex();h.push(c[a]);a=this.list[this.triangles[d].v2].getCommonIndex();h.push(c[a]);a=this.list[this.triangles[d].v3].getCommonIndex();h.push(c[a])}}};

42Triangulator.prototype.isInPolyList=function(a){return(a>=0)&&(a<this.list.length)};Triangulator.prototype.updateIndex=function(b,a){this.list[b].index=a};Triangulator.prototype.getAngle=function(a){return this.list[a].convex};Triangulator.prototype.setAngle=function(b,a){this.list[b].convex=a};Triangulator.prototype.resetPolyList=function(a){this.firstNode=a};Triangulator.prototype.getNode=function(){return this.firstNode};Triangulator.prototype.deleteHook=function(b){var a=this.loops[b];var c=this.list[a].next;if(this.isInPolyList(a)&&this.isInPolyList(c)){this.deleteLinks(a);this.loops[b]=c}};Triangulator.prototype.deleteLinks=function(a){if(this.isInPolyList(a)&&this.isInPolyList(this.list[a].prev)&&this.isInPolyList(this.list[a].next)){if(this.firstNode===a){this.firstNode=this.list[a].next}this.list[this.list[a].next].prev=this.list[a].prev;this.list[this.list[a].prev].next=this.list[a].next;this.list[a].prev=this.list[a].next=a}};Triangulator.prototype.rotateLinks=function(a,e){var b=this.list[a].next;var d=this.list[e].next;var c=this.list[a].next;this.list[a].next=this.list[e].next;this.list[e].next=c;this.list[b].prev=e;this.list[d].prev=a};Triangulator.prototype.storeChain=function(a){if(this.chains===null){this.chains=[]}this.chains.push(a)};Triangulator.prototype.getNextChain=function(a){if(this.chains!==null&&this.chains.length>0){a[0]=true;return this.chains.pop()}else{a[0]=false;this.chains=null;return 0}};Triangulator.prototype.splitSplice=function(a,d,c,b){this.list[a].next=b;this.list[b].prev=a;this.list[d].prev=c;this.list[c].next=d};Triangulator.prototype.makeHook=function(){var a=new Triangulator.ListNode(-1);a.prev=this.list.length;a.next=this.list.length;this.list.push(a);return this.list.length-1};Triangulator.prototype.makeLoopHeader=function(){this.loops.push(this.makeHook());return this.loops.length-1};Triangulator.prototype.makeNode=function(a){this.list.push(new Triangulator.ListNode(a));return this.list.length-1};Triangulator.prototype.insertAfter=function(a,c){if(this.isInPolyList(a)&&this.isInPolyList(c)){this.list[c].next=this.list[a].next;this.list[c].prev=a;this.list[a].next=c;var b=this.list[c].next;if(this.isInPolyList(b)){this.list[b].prev=c}}};Triangulator.prototype.fetchNextData=function(a){return this.list[a].next};Triangulator.prototype.fetchData=function(a){return this.list[a].index};Triangulator.prototype.fetchPrevData=function(a){return this.list[a].prev};Triangulator.prototype.swapLinks=function(a){var c=this.list[a].next;this.list[a].next=this.list[a].prev;this.list[a].prev=c;var b=c;while(c!==a){b=this.list[c].next;this.list[c].next=this.list[c].prev;this.list[c].prev=b;c=b}};Triangulator.prototype.storeTriangle=function(c,b,a){if(this.ccwLoop){this.triangles.push(new Triangulator.Triangle(c,b,a))}else{this.triangles.push(new Triangulator.Triangle(b,c,a))}};Triangulator.prototype.initPoints=function(b){this.points=[];for(var a=0;a<b;a++){this.points[a]=[0,0]}this.numPoints=0};Triangulator.prototype.inPointsList=function(a){return a>=0&&a<this.numPoints};Triangulator.prototype.storePoint=function(a,b){if(this.points===null){this.points=[]}this.points[this.numPoints]=[a,b];return this.numPoints++};Triangulator.prototype.simpleFace=function(j){var k=this.fetchPrevData(j);var q=this.fetchData(k);if(k===j){return true}var i=this.fetchNextData(j);var n=this.fetchData(i);if(k===i){return true}var h=this.fetchNextData(i);var m=this.fetchData(h);if(k===h){this.storeTriangle(j,i,h);return true}var f=this.fetchNextData(h);var l=this.fetchData(f);if(k===f){this.initPoints(5);var o=this.fetchData(j);var r=vec3.subtract(vec3.create(),this.vertices[o],this.vertices[n]);var p=vec3.subtract(vec3.create(),this.vertices[m],this.vertices[n]);var a=vec3.cross(vec3.create(),r,p);var g=Math.abs(a[0]);var e=Math.abs(a[1]);var d=Math.abs(a[2]);if(d>=g&&d>=e){this.points[1][0]=this.vertices[o][0];this.points[1][1]=this.vertices[o][1];this.points[2][0]=this.vertices[n][0];this.points[2][1]=this.vertices[n][1];this.points[3][0]=this.vertices[m][0];this.points[3][1]=this.vertices[m][1];this.points[4][0]=this.vertices[l][0];this.points[4][1]=this.vertices[l][1]}else{if(g>=e&&g>=d){this.points[1][0]=this.vertices[o][2];this.points[1][1]=this.vertices[o][1];this.points[2][0]=this.vertices[n][2];this.points[2][1]=this.vertices[n][1];this.points[3][0]=this.vertices[m][2];this.points[3][1]=this.vertices[m][1];this.points[4][0]=this.vertices[l][2];this.points[4][1]=this.vertices[l][1]}else{this.points[1][0]=this.vertices[o][0];this.points[1][1]=this.vertices[o][2];this.points[2][0]=this.vertices[n][0];this.points[2][1]=this.vertices[n][2];this.points[3][0]=this.vertices[m][0];this.points[3][1]=this.vertices[m][2];this.points[4][0]=this.vertices[l][0];this.points[4][1]=this.vertices[l][2]}}this.numPoints=5;var c=this.orientation(1,2,3);var b=this.orientation(1,3,4);if((c>0&&b>0)||(c<0&&b<0)){this.storeTriangle(j,i,h);this.storeTriangle(j,h,f)}else{this.storeTriangle(i,h,f);this.storeTriangle(i,f,j)}return true}return false};Triangulator.prototype.max3=function(e,d,f){return(e>d)?((e>f)?e:f):((d>f)?d:f)};Triangulator.prototype.min3=function(e,d,f){return(e<d)?((e<f)?e:f):((d<f)?d:f)};Triangulator.prototype.baseLength=function(b,a){return Math.abs(a[0]-b[0])+Math.abs(a[1]-b[1])};Triangulator.prototype.sideLength=function(c,b){var a=b[0]-c[0];var d=b[1]-c[1];return a*a+d*d};Triangulator.prototype.inBetween=function(c,b,a){return c<=a&&a<=b};Triangulator.prototype.strictlyInBetween=function(c,b,a){return c<a&&a<b};Triangulator.prototype.stableDet2D=function(g,e,d){var f;if(g===e||g===d||e===d){f=0}else{var c=this.points[g];var b=this.points[e];var a=this.points[d];if(g<e){if(e<d){f=this.det2D(c,b,a)}else{if(g<d){f=-this.det2D(c,a,b)}else{f=this.det2D(a,c,b)}}}else{if(g<d){f=-this.det2D(b,c,a)}else{if(e<d){f=this.det2D(b,a,c)}else{f=-this.det2D(a,b,c)}}}}return f};Triangulator.prototype.det2D=function(c,b,a){return(c[0]-b[0])*(b[1]-a[1])+(b[1]-c[1])*(b[0]-a[0])};Triangulator.prototype.orientation=function(c,b,a){var d=this.stableDet2D(c,b,a);if(d<-this.epsilon){return -1}else{if(!(d<=this.epsilon)){return 1}else{return 0}}};Triangulator.prototype.isInCone=function(e,d,c,a,b){if(b){if(e!==d){var g=this.orientation(e,d,a);if(g<0){return false}else{if(g===0){if(e<d){if(!this.inBetween(e,d,a)){return false}}else{if(!this.inBetween(d,e,a)){return false}}}}}if(d!==c){var f=this.orientation(d,c,a);if(f<0){return false}else{if(f===0){if(d<c){if(!this.inBetween(d,c,a)){return false}}else{if(!this.inBetween(c,d,a)){return false}}}}}}else{if(this.orientation(e,d,a)<=0&&this.orientation(d,c,a)<0){return false}}return true};Triangulator.prototype.isConvexAngle=function(e,d,c,g){if(e===d){if(d===c){return 1}else{return 1}}else{if(d===c){return -1}else{var h=this.orientation(e,d,c);if(h>0){return 1}else{if(h<0){return -1}else{var b=[this.points[e][0]-this.points[d][0],this.points[e][1]-this.points[d][1]];var a=[this.points[c][0]-this.points[d][0],this.points[c][1]-this.points[d][1]];var f=b[0]*a[0]+b[1]*a[1];if(f<0){return 0}else{return this.spikeAngle(e,d,c,g)}}}}}};Triangulator.prototype.isPointInTriangle=function(d,c,b,a){var e=this.orientation(c,b,a);if(e>=0){e=this.orientation(d,c,a);if(e>=0){e=this.orientation(b,d,a);if(e>=0){return true}}}return false};Triangulator.prototype.isVertexInTriangle=function(e,d,b,a,c){var f=this.orientation(d,b,a);if(f>=0){f=this.orientation(e,d,a);if(f>0){f=this.orientation(b,e,a);if(f>0){c[0]=0;return true}else{if(f===0){c[0]=1;return true}}}else{if(f===0){f=this.orientation(b,e,a);if(f>0){c[0]=2;return true}else{if(f===0){c[0]=3;return true}}}}}return false};Triangulator.prototype.segmentsIntersect=function(i,h,g,f,e){if(i===h||g===f){return false}if(i===g&&h===f){return true}if(g===e||f===e){++this.identCntr}var b=this.orientation(i,h,g);var a=this.orientation(i,h,f);

42if((b===1&&a===1)||(b===-1&&a===-1)){return false}if(b===0){if(this.strictlyInBetween(i,h,g)){return true}if(a===0){if(this.strictlyInBetween(i,h,f)){return true}}else{return false}}else{if(a===0){if(this.strictlyInBetween(i,h,f)){return true}else{return false}}}var d=this.orientation(g,f,i);var c=this.orientation(g,f,h);if((d<=0&&c<=0)||(d>=0&&c>=0)){return false}return true};Triangulator.prototype.getRatio=function(n,m,l){var h=this.points[n];var e=this.points[m];var d=this.points[l];var u=this.baseLength(h,e);var t=this.baseLength(h,d);var s=this.baseLength(d,e);var g=this.max3(u,t,s);if((10*u)<Math.min(t,s)){return 0.1}var f=this.stableDet2D(n,m,l);if(f<-this.epsilon){f=-f}else{if(f<=this.epsilon){if(g>u){return 0.1}else{return Number.MAX_VALUE}}}var o=g*g/f;if(o<10){return o}else{if(u<g){return 0.1}else{return o}}};Triangulator.prototype.spikeAngle=function(g,f,e,a){var l=a;var c=this.fetchData(l);var m=this.fetchPrevData(l);var d=this.fetchData(m);var h=this.fetchNextData(l);var b=this.fetchData(h);return this.recSpikeAngle(g,f,e,m,h)};Triangulator.prototype.recSpikeAngle=function(h,g,f,k,j){if(k===j){return -2}if(h!==f){var e;var d;if(h<g){e=h;d=g}else{e=g;d=h}if(this.inBetween(e,d,f)){g=f;j=this.fetchNextData(j);f=this.fetchData(j);if(k===j){return 2}var l=this.orientation(h,g,f);if(l>0){return 2}else{if(l<0){return -2}else{return this.recSpikeAngle(h,g,f,k,j)}}}else{g=h;k=this.fetchPrevData(k);h=this.fetchData(k);if(k===j){return 2}var l=this.orientation(h,g,f);if(l>0){return 2}else{if(l<0){return -2}else{return this.recSpikeAngle(h,g,f,k,j)}}}}else{var i=g;g=h;k=this.fetchPrevData(k);h=this.fetchData(k);if(k===j){return 2}j=this.fetchNextData(j);f=this.fetchData(j);if(k===j){return 2}l=this.orientation(h,g,f);if(l>0){if(this.orientation(h,g,i)>0&&this.orientation(g,f,i)>0){return -2}return 2}else{if(l<0){if(this.orientation(g,h,i)>0&&this.orientation(f,g,i)>0){return 2}return -2}else{var c=[this.points[h][0]-this.points[g][0],this.points[h][1]-this.points[g][1]];var b=[this.points[f][0]-this.points[g][0],this.points[f][1]-this.points[g][1]];var a=c[0]*b[0]+c[1]*b[1];if(a<0){if(this.orientation(g,h,i)>0){return 2}else{return -2}}else{return this.recSpikeAngle(h,g,f,k,j)}}}}};Triangulator.prototype.angle=function(a,j,i){var f=(i[0]-a[0])*(a[1]-j[1])+(a[1]-i[1])*(a[0]-j[0]);var b=f<=this.epsilon?(f<-this.epsilon?-1:0):1;if(b===0){return 0}var h=[j[0]-a[0],j[1]-a[1]];var g=[i[0]-a[0],i[1]-a[1]];var e=Math.atan2(h[1],h[0]);var d=Math.atan2(g[1],g[0]);if(e<0){e+=2*Math.PI}if(d<0){d+=2*Math.PI}var c=e-d;if(c>Math.PI){c=2*Math.PI-c}else{if(c<-Math.PI){c=2*Math.PI+c}}if(b===1){if(c<0){return -c}else{return c}}else{if(c>0){return -c}else{return c}}};Triangulator.prototype.projectFace=function(h,e){var f=vec3.create();var c=vec3.create();this.determineNormal(this.loops[h],f);var a=h+1;if(a<e){for(var b=a;b<e;b++){this.determineNormal(this.loops[b],c);if(vec3.dot(f,c)<0){vec3.negate(c,c)}vec3.add(f,c,f)}var g=vec3.length(f);if(!(g<=Triangulator.ZERO)){vec3.scale(f,f,1/g)}else{f[0]=f[1]=0;f[2]=1}}this.projectPoints(h,e,f)};Triangulator.prototype.determineNormal=function(c,i){var j=c;var f=this.fetchData(j);var l=this.fetchPrevData(j);var g=this.fetchData(l);var h=this.fetchNextData(j);var e=this.fetchData(h);var b=vec3.subtract(vec3.create(),this.vertices[g],this.vertices[f]);var a=vec3.subtract(vec3.create(),this.vertices[e],this.vertices[f]);var m=vec3.cross(vec3.create(),b,a);var k=vec3.length(m);if(!(k<=Triangulator.ZERO)){vec3.scale(i,m,1/k)}else{i[0]=i[1]=i[2]=0}vec3.copy(b,a);j=h;h=this.fetchNextData(j);e=this.fetchData(h);while(j!==c){vec3.subtract(a,this.vertices[e],this.vertices[f]);vec3.cross(m,b,a);k=vec3.length(m);if(!(k<=Triangulator.ZERO)){vec3.scale(m,m,1/k);if(vec3.dot(i,m)<0){vec3.negate(m,m)}vec3.add(i,m,i)}vec3.copy(b,a);j=h;h=this.fetchNextData(j);e=this.fetchData(h)}k=vec3.length(i);if(!(k<=Triangulator.ZERO)){vec3.scale(i,i,1/k)}else{i[0]=i[1]=0;i[2]=1}};Triangulator.prototype.projectPoints=function(c,b,g){var k=vec3.create();var h=vec3.create();if((Math.abs(g[0])>0.1)||(Math.abs(g[1])>0.1)){k[0]=-g[1];k[1]=g[0];k[2]=0}else{k[0]=g[2];k[2]=-g[0];k[1]=0}var l=vec3.length(k);vec3.scale(k,k,1/l);vec3.cross(h,k,g);l=vec3.length(h);vec3.scale(h,h,1/l);var m=mat4.create();m[0]=k[0];m[4]=k[1];m[8]=k[2];m[1]=h[0];m[5]=h[1];m[9]=h[2];m[2]=g[0];m[6]=g[1];m[10]=g[2];var f=vec3.create();this.initPoints(20);for(var e=c;e<b;e++){var a=this.loops[e];var j=a;var n=this.fetchData(j);vec3.transformMat4(f,this.vertices[n],m);n=this.storePoint(f[0],f[1]);this.updateIndex(j,n);j=this.fetchNextData(j);n=this.fetchData(j);while(j!==a){vec3.transformMat4(f,this.vertices[n],m);n=this.storePoint(f[0],f[1]);this.updateIndex(j,n);j=this.fetchNextData(j);n=this.fetchData(j)}}};Triangulator.prototype.initPointsUnsorted=function(b){if(b>this.maxNumPUnsorted){this.maxNumPUnsorted=b;this.pointsUnsorted=new Array(this.maxNumPUnsorted);for(var a=0;a<this.maxNumPUnsorted;a++){this.pointsUnsorted[a]=[0,0]}}};Triangulator.prototype.cleanPolyhedralFace=function(b,a){this.initPointsUnsorted(this.numPoints);for(var d=0;d<this.numPoints;d++){this.pointsUnsorted[d][0]=this.points[d][0];this.pointsUnsorted[d][1]=this.points[d][1]}this.sortPoints(this.points,this.numPoints);var d=0;var c;for(c=1;c<this.numPoints;c++){if(this.comparePoints(this.points[d],this.points[c])!==0){this.points[++d]=this.points[c]}}var e=d+1;var h=this.numPoints-e;for(d=b;d<a;++d){var k=this.loops[d];var g=this.fetchNextData(k);var f=this.fetchData(g);while(g!==k){c=this.findPointIndex(this.points,e,this.pointsUnsorted[f]);this.updateIndex(g,c);g=this.fetchNextData(g);f=this.fetchData(g)}c=this.findPointIndex(this.points,e,this.pointsUnsorted[f]);this.updateIndex(g,c)}this.numPoints=e;return h};Triangulator.prototype.sortPoints=function(e,d){for(var c=0;c<d;c++){for(var b=c+1;b<d;b++){if(this.comparePoints(e[c],e[b])>0){var a=e[c][0];var f=e[c][1];e[c][0]=e[b][0];e[c][1]=e[b][1];e[b][0]=a;e[b][1]=f}}}};Triangulator.prototype.findPointIndex=function(a,d,c){for(var b=0;b<d;b++){if(c[0]===a[b][0]&&c[1]===a[b][1]){return b}}return -1};Triangulator.prototype.comparePoints=function(d,c){if(d[0]<c[0]){return -1}else{if(d[0]>c[0]){return 1}else{if(d[1]<c[1]){return -1}else{if(d[1]>c[1]){return 1}else{return 0}}}}};Triangulator.prototype.polygonArea=function(f){var e=0;var a=f;var d=this.fetchData(a);var g=this.fetchNextData(a);var b=this.fetchData(g);var c=this.stableDet2D(e,d,b);a=g;d=b;while(a!==f){g=this.fetchNextData(a);b=this.fetchData(g);c+=this.stableDet2D(e,d,b);a=g;d=b}return c};

42Triangulator.prototype.determineOrientation=function(a){if(this.polygonArea(a)<0){this.swapLinks(a);this.ccwLoop=false}};Triangulator.prototype.classifyAngles=function(f){var a=f;var d=this.fetchData(a);var b=this.fetchPrevData(a);var e=this.fetchData(b);do{var h=this.fetchNextData(a);var c=this.fetchData(h);var g=this.isConvexAngle(e,d,c,a);this.setAngle(a,g);e=d;d=c;a=h}while(a!==f)};Triangulator.prototype.classifyEars=function(e){var b=[0];var f=[0];var c=[0];this.initHeap();var a=e;var d=this.fetchData(a);do{if((this.getAngle(a)>0)&&this.isEar(a,b,f,c)){this.dumpOnHeap(c[0],a,b[0],f[0])}a=this.fetchNextData(a);d=this.fetchData(a)}while(a!==e)};Triangulator.prototype.isEar=function(j,k,i,m){var c=this.fetchData(j);i[0]=this.fetchNextData(j);var b=this.fetchData(i[0]);var h=this.fetchNextData(i[0]);var a=this.fetchData(h);k[0]=this.fetchPrevData(j);var e=this.fetchData(k[0]);var l=this.fetchPrevData(k[0]);var f=this.fetchData(l);if(e===b||e===c||c===b||this.getAngle(j)===2){m[0]=0;return true}if(f===b){if(this.getAngle(l)<0||this.getAngle(i[0])<0){m[0]=0;return true}else{return false}}if(e===a){if((this.getAngle(k[0])<0)||(this.getAngle(h)<0)){m[0]=0;return true}else{return false}}var d=this.getAngle(k[0])>0;var n=this.isInCone(f,e,c,b,d);if(!n){return false}var d=this.getAngle(i[0])>0;var n=this.isInCone(c,b,a,e,d);if(n){var g=new Triangulator.BoundingBox(this,e,b);if(!this.noHashIntersectionExists(c,j,b,e,g)){m[0]=1;return true}}return false};Triangulator.prototype.clipEar=function(n){var f=[0];var d=[0];var l;var k=[0];var j;var r;var p;do{if(!this.deleteFromHeap(k,f,d)){return false}l=this.fetchPrevData(k[0]);r=this.fetchData(l);j=this.fetchNextData(k[0]);p=this.fetchData(j)}while(f[0]!==l||d[0]!==j);var q=this.fetchData(k[0]);this.deleteLinks(k[0]);this.storeTriangle(l,k[0],j);var m=this.fetchPrevData(l);var s=this.fetchData(m);if(m===j){n[0]=true;return true}var b=this.isConvexAngle(s,r,p,l);var i=this.fetchNextData(j);var o=this.fetchData(i);var a=this.isConvexAngle(r,p,o,j);if(r!==p){if(b>=0&&this.getAngle(l)<0){this.deleteReflexVertex(l)}if(a>=0&&this.getAngle(j)<0){this.deleteReflexVertex(j)}}else{if(b>=0&&this.getAngle(l)<0){this.deleteReflexVertex(l)}else{if(a>=0&&this.getAngle(j)<0){this.deleteReflexVertex(j)}}}this.setAngle(l,b);this.setAngle(j,a);var h=[0];var g=[0];var e=[0];if(b>0){if(this.isEar(l,g,e,h)){this.insertIntoHeap(h[0],l,g[0],e[0])}}var c=[0];if(a>0){if(this.isEar(j,e,c,h)){this.insertIntoHeap(h[0],j,e[0],c[0])}}m=this.fetchPrevData(l);s=this.fetchData(m);i=this.fetchNextData(j);o=this.fetchData(i);if(m===i){this.storeTriangle(l,j,i);n[0]=true}else{n[0]=false}return true};Triangulator.prototype.insertAfterVertex=function(a){if(this.vertexList===null){this.vertexList=[]}var b=new Triangulator.PointNode();b.pnt=a;b.next=this.reflexVertices;this.vertexList.push(b);this.reflexVertices=this.vertexList.length-1;++this.numReflex};Triangulator.prototype.deleteFromList=function(c){if(this.numReflex===0){return}var d=this.reflexVertices;var a=this.vertexList[d].pnt;if(a===c){this.reflexVertices=this.vertexList[d].next;--this.numReflex}else{var b=this.vertexList[d].next;while(b!==-1){a=this.vertexList[b].pnt;if(a===c){this.vertexList[d].next=this.vertexList[b].next;b=-1;--this.numReflex}else{d=b;b=this.vertexList[d].next}}}};Triangulator.prototype.freeNoHash=function(){this.noHashingEdges=false;this.noHashingPnts=false;this.vertexList=null};Triangulator.prototype.prepareNoHashEdges=function(a,b){this.loopMin=a;this.loopMax=b;this.noHashingEdges=true};Triangulator.prototype.prepareNoHashPoints=function(b){this.vertexList=null;this.reflexVertices=-1;var d=this.loops[b];var a=d;this.numReflex=0;var c=this.fetchData(a);do{if(this.getAngle(a)<0){this.insertAfterVertex(a)}a=this.fetchNextData(a);c=this.fetchData(a)}while(a!==d);this.noHashingPnts=true};Triangulator.prototype.noHashIntersectionExists=function(f,i,e,d,h){if(this.numReflex<=0){return false}if(f<h.imin){h.imin=f}else{if(f>h.imax){h.imax=f}}var l=this.points[f][1];if(l<h.ymin){h.ymin=l}else{if(l>h.ymax){h.ymax=l}}var c=this.reflexVertices;var k=[0];do{var j=this.vertexList[c].pnt;var b=this.fetchData(j);if(h.isInBoundingBox(this.points[b],b)){var g=this.fetchNextData(j);var a=this.fetchData(g);if(j!==i&&j!==g){if(b===f){if(this.handleDegeneracies(f,i,e,d,b,j)){return true}}else{if(b!==e&&b!==d){if(this.isVertexInTriangle(f,e,d,b,k)){return true}}}}}c=this.vertexList[c].next}while(c!==-1);return false};Triangulator.prototype.deleteReflexVertex=function(a){this.deleteFromList(

42a)};Triangulator.prototype.noHashEdgeIntersectionExists=function(j,f,e,g,a){this.identCntr=0;for(var h=this.loopMin;h<this.loopMax;h++){var c=this.loops[h];var k=c;var d=this.fetchData(k);do{k=this.fetchNextData(k);var b=this.fetchData(k);var l=new Triangulator.BoundingBox(this,d,b);if(j.overlaps(l)){if(this.segmentsIntersect(j.imin,j.imax,l.imin,l.imax,a)){return true}}d=b}while(k!==c)}if(this.identCntr>=4){return this.checkBottleNeck(a,f,e,g)}return false};Triangulator.prototype.handleDegeneracies=function(e,j,d,c,b,h){var g=this.fetchPrevData(h);var a=this.fetchData(g);if(a!==d&&a!==c){var m=[0];var l=this.isVertexInTriangle(e,d,c,a,m);if(l&&m[0]===0){return true}if(d<=c){if(b<=a){l=this.segmentsIntersect(d,c,b,a,-1)}else{l=this.segmentsIntersect(d,c,a,b,-1)}}else{if(b<=a){l=this.segmentsIntersect(c,d,b,a,-1)}else{l=this.segmentsIntersect(c,d,a,b,-1)}}if(l){return true}}g=this.fetchNextData(h);a=this.fetchData(g);if(a!==d&&a!==c){var m=[0];var l=this.isVertexInTriangle(e,d,c,a,m);if(l&&m[0]===0){return true}if(d<=c){if(b<=a){l=this.segmentsIntersect(d,c,b,a,-1)}else{l=this.segmentsIntersect(d,c,a,b,-1)}}else{if(b<=a){l=this.segmentsIntersect(c,d,b,a,-1)}else{l=this.segmentsIntersect(c,d,a,b,-1)}}if(l){return true}}var f=e;var k=j;var n=0;var p=0;j=this.fetchNextData(j);e=this.fetchData(j);while(j!==h){var i=this.fetchNextData(j);d=this.fetchData(i);area=this.stableDet2D(f,e,d);p+=area;j=i;e=d}var o=0;j=this.fetchPrevData(k);e=this.fetchData(j);while(j!==h){var i=this.fetchPrevData(j);d=this.fetchData(i);area=this.stableDet2D(f,e,d);o+=area;j=i;e=d}if(p<=this.ZERO&&o<=this.ZERO){return false}else{if(!(p<=-this.ZERO)&&!(o<=-this.ZERO)){return false}else{return true}}};Triangulator.prototype.desperate=function(a,f,l){var e=[0];var d=[0];var c=[0];var b=[0];var k=[0];var j=[0];var h=[0];var g=[0];l[0]=false;if(this.existsCrossOver(a,k,e,j,d,h,c,g,b)){this.handleCrossOver(k[0],e[0],j[0],d[0],h[0],c[0],g[0],b[0]);return false}this.prepareNoHashEdges(f,f+1);if(this.existsSplit(a,k,e,j,d)){this.handleSplit(k[0],e[0],j[0],d[0]);l[0]=true;return false}return true};Triangulator.prototype.existsCrossOver=function(b,i,e,h,d,g,c,f,a){i[0]=b;e[0]=this.fetchData(i[0]);h[0]=this.fetchNextData(i[0]);d[0]=this.fetchData(h[0]);g[0]=this.fetchNextData(h[0]);c[0]=this.fetchData(g[0]);f[0]=this.fetchNextData(g[0]);a[0]=this.fetchData(f[0]);do{var k=new Triangulator.BoundingBox(this,e[0],d[0]);var j=new Triangulator.BoundingBox(this,c[0],a[0]);if(k.overlaps(j)){if(this.segmentsIntersect(k.imin,k.imax,j.imin,j.imax,-1)){return true}}i[0]=h[0];e[0]=d[0];h[0]=g[0];d[0]=c[0];g[0]=f[0];c[0]=a[0];f[0]=this.fetchNextData(g[0]);a[0]=this.fetchData(f[0])}while(i[0]!==b);return false};Triangulator.prototype.handleCrossOver=function(k,d,j,c,h,b,g,a){var i=this.getAngle(k);var e=this.getAngle(g);var f;if(i<e){f=true}else{if(i>e){f=false}else{f=true}}if(f){this.deleteLinks(j);this.storeTriangle(k,j,h);this.setAngle(h,1);this.insertIntoHeap(0,h,k,g)}else{this.deleteLinks(h);this.storeTriangle(j,h,g);this.setAngle(j,1);this.insertIntoHeap(0,j,k,g)}};Triangulator.prototype.letsHope=function(c){var a=c;do{if(this.getAngle(a)>0){var b=this.fetchPrevData(a);var d=this.fetchNextData(a);this.insertIntoHeap(0,a,b,d);return true}a=this.fetchNextData(a)}while(a!==c);this.setAngle(c,1);var b=this.fetchPrevData(c);var d=this.fetchNextData(c);this.insertIntoHeap(0,c,b,d);return true};Triangulator.prototype.existsSplit=function(b,m,f,l,e){if(this.numPoints>this.maxNumDist){this.maxNumDist=this.numPoints;this.distances=new Array(this.maxNumDist);for(var g=0;g<this.maxNumDist;g++){this.distances[g]=new Triangulator.Distance()}}m[0]=b;f[0]=this.fetchData(m[0]);var i=this.fetchNextData(m[0]);var c=this.fetchData(i);var h=this.fetchNextData(i);var a=this.fetchData(h);var j=this.fetchPrevData(m[0]);var d=this.fetchData(j);if(this.foundSplit(h,a,j,m[0],f[0],d,c,l,e)){return true}d=f[0];m[0]=i;f[0]=c;i=h;c=a;h=this.fetchNextData(i);a=this.fetchData(h);while(h!==b){if(this.foundSplit(h,a,b,m[0],f[0],d,c,l,e)){return true}d=f[0];m[0]=i;f[0]=c;i=h;c=a;h=this.fetchNextData(i);a=this.fetchData(h)}return false};Triangulator.prototype.windingNumber=function(c,d){var b=this.fetchData(c);var f=this.fetchNextData(c);var a=this.fetchData(f);var e=this.angle(d,this.points[b],this.points[a]);while(f!==c){b=a;f=this.fetchNextData(f);a=this.fetchData(f);e+=this.angle(d,this.points[b],this.points[a])}e+=Math.PI;return Math.floor(e/(Math.PI*2))};

42Triangulator.prototype.foundSplit=function(d,m,f,i,q,o,n,h,p){var e=0;do{this.distances[e].dist=this.baseLength(this.points[q],this.points[m]);this.distances[e].ind=d;++e;d=this.fetchNextData(d);m=this.fetchData(d)}while(d!==f);this.sortDistance(this.distances,e);for(var r=0;r<e;r++){h[0]=this.distances[r].ind;p[0]=this.fetchData(h[0]);if(q!==p[0]){var c=this.fetchPrevData(h[0]);var l=this.fetchData(c);var b=this.fetchNextData(h[0]);var k=this.fetchData(b);var a=this.getAngle(h[0])>0;if(this.isInCone(l,p[0],k,q,a)){a=this.getAngle(i)>0;if(this.isInCone(o,q,n,p[0],a)){var g=new Triangulator.BoundingBox(this,q,p[0]);if(!this.noHashEdgeIntersectionExists(g,-1,-1,i,-1)){var s=[(this.points[q][0]+this.points[p[0]][0])*0.5,(this.points[q][1]+this.points[p[0]][1])*0.5];if(this.windingNumber(f,s)===1){return true}}}}}}return false};Triangulator.prototype.handleSplit=function(l,f,i,c){var k=this.makeNode(f);this.insertAfter(l,k);var b=this.list[l].getCommonIndex();this.list[k].setCommonIndex(b);var g=this.makeNode(c);this.insertAfter(i,g);b=this.list[i].getCommonIndex();this.list[g].setCommonIndex(b);this.splitSplice(l,k,i,g);this.storeChain(l);this.storeChain(i);var h=this.fetchNextData(l);var a=this.fetchData(h);var e=this.fetchPrevData(l);var j=this.fetchData(e);var d=this.isConvexAngle(j,f,a,l);this.setAngle(l,d);h=this.fetchNextData(k);a=this.fetchData(h);e=this.fetchPrevData(k);j=this.fetchData(e);d=this.isConvexAngle(j,f,a,k);this.setAngle(k,d);h=this.fetchNextData(i);a=this.fetchData(h);e=this.fetchPrevData(i);j=this.fetchData(e);d=this.isConvexAngle(j,c,a,i);this.setAngle(i,d);h=this.fetchNextData(g);a=this.fetchData(h);e=this.fetchPrevData(g);j=this.fetchData(e);d=this.isConvexAngle(j,c,a,g);this.setAngle(g,d)};Triangulator.prototype.initHeap=function(){this.heap=[];this.numHeap=0;this.numZero=0};Triangulator.prototype.storeHeapData=function(a,c,e,d,b){this.heap[a]=new Triangulator.HeapNode();this.heap[a].ratio=c;this.heap[a].index=e;this.heap[a].prev=d;this.heap[a].next=b};Triangulator.prototype.dumpOnHeap=function(c,e,d,b){var a;if(c===0){if(this.numZero<this.numHeap){if(this.heap[this.numHeap]===undefined){this.storeHeapData(this.numHeap,this.heap[this.numZero].ratio,this.heap[this.numZero].index,this.heap[this.numZero].prev,this.heap[this.numZero].next)}else{this.heap[this.numHeap].copy(this.heap[this.numZero])}}a=this.numZero;++this.numZero}else{a=this.numHeap}this.storeHeapData(a,c,e,d,b);++this.numHeap};Triangulator.prototype.insertIntoHeap=function(b,d,c,a){this.dumpOnHeap(b,d,c,a)};Triangulator.prototype.deleteFromHeap=function(c,b,a){if(this.numZero>0){--this.numZero;--this.numHeap;c[0]=this.heap[this.numZero].index;b[0]=this.heap[this.numZero].prev;a[0]=this.heap[this.numZero].next;if(this.numZero<this.numHeap){this.heap[this.numZero].copy(this.heap[this.numHeap])}return true}else{if(this.numHeap<=0){this.numHeap=0;return false}--this.numHeap;c[0]=this.heap[this.numHeap].index;b[0]=this.heap[this.numHeap].prev;a[0]=this.heap[this.numHeap].next;return true}};Triangulator.prototype.sortDistance=function(a,e){var d=new Triangulator.Distance();for(var c=0;c<e;c++){for(var b=c+1;b<e;b++){if(this.compareDistances(a[c],a[b])>0){d.copy(a[c]);a[c].copy(a[b]);a[b].copy(d)}}}};Triangulator.prototype.compareDistances=function(d,c){if(d.dist<c.dist){return -1}else{if(d.dist>c.dist){return 1}else{return 0}}};Triangulator.prototype.checkArea=function(f,e){var d=this.fetchData(f);var h=this.fetchNextData(f);var c=this.fetchData(h);var a=0;var j=0;while(h!=e){var g=this.fetchNextData(h);var b=this.fetchData(g);a=this.stableDet2D(d,c,b);j+=a;h=g;c=b}if(j<=this.ZERO){return false}h=this.fetchNextData(e);c=this.fetchData(h);var i=0;while(h!=f){var g=this.fetchNextData(h);var b=this.fetchData(g);a=this.stableDet2D(d,c,b);i+=a;h=g;c=b}return !(i<=this.ZERO)};Triangulator.prototype.checkBottleNeck=function(f,e,d,h){var c=f;var g=this.fetchPrevData(h);var b=this.fetchData(g);if(b!==e&&b!==d){if(this.isPointInTriangle(f,e,d,b)){return true}}var a;if(e<=d){if(c<=b){a=this.segmentsIntersect(e,d,c,b,-1)}else{a=this.segmentsIntersect(e,d,b,c,-1)}}else{if(c<=b){a=this.segmentsIntersect(d,e,c,b,-1)}else{a=this.segmentsIntersect(d,e,b,c,-1)}}if(a){return true}g=this.fetchNextData(h);b=this.fetchData(g);if(b!==e&&b!==d){if(this.isPointInTriangle(f,e,d,b)){return true}}

42if(e<=d){if(c<=b){a=this.segmentsIntersect(e,d,c,b,-1)}else{a=this.segmentsIntersect(e,d,b,c,-1)}}else{if(c<=b){a=this.segmentsIntersect(d,e,c,b,-1)}else{a=this.segmentsIntersect(d,e,b,c,-1)}}if(a){return true}g=this.fetchNextData(h);b=this.fetchData(g);while(g!==h){if(c===b){if(this.checkArea(h,g)){return true}}g=this.fetchNextData(g);b=this.fetchData(g)}return false};Triangulator.ListNode=function(a){this.index=a;this.prev=-1;this.next=-1;this.convex=0;this.vcntIndex=-1};Triangulator.ListNode.prototype.setCommonIndex=function(a){this.vcntIndex=a};Triangulator.ListNode.prototype.getCommonIndex=function(){return this.vcntIndex};Triangulator.Triangle=function(e,d,f){this.v1=e;this.v2=d;this.v3=f};Triangulator.BoundingBox=function(c,b,a){this.imin=Math.min(b,a);this.imax=Math.max(b,a);this.ymin=Math.min(c.points[this.imin][1],c.points[this.imax][1]);this.ymax=Math.max(c.points[this.imin][1],c.points[this.imax][1])};Triangulator.BoundingBox.prototype.isInBoundingBox=function(a,b){return this.imax>=b&&this.imin<=b&&this.ymax>=a[1]&&this.ymin<=a[1]};Triangulator.BoundingBox.prototype.overlaps=function(a){return this.imax>=a.imin&&this.imin<=a.imax&&this.ymax>=a.ymin&&this.ymin<=a.ymax};

42Triangulator.HeapNode=function(){this.index=0;this.prev=0;this.next=0;this.ratio=0};Triangulator.HeapNode.prototype.copy=function(a){this.index=a.index;this.prev=a.prev;this.next=a.next;this.ratio=a.ratio};Triangulator.Distance=function(){this.ind=0;this.dist=0};Triangulator.Distance.prototype.copy=function(a){this.ind=a.ind;this.dist=a.dist};Triangulator.PointNode=function(){this.pnt=0;this.next=0};