How to use myQs method in wpt

Best JavaScript code snippet using wpt

TrapezoiderTest.js

Source:TrapezoiderTest.js

1/**2 * @author jahting / http://www.ameco.tv/3 */4function test_Trapezoid() {5 function test_new_Trapezoid() {6 //7 // empty trapezoid8 var myTrap = new PNLTRI.Trapezoid();9 equal( myTrap.vHigh.x, Number.POSITIVE_INFINITY, "new_Trapezoid: high.x = POSITIVE_INFINITY" );10 equal( myTrap.vHigh.y, Number.POSITIVE_INFINITY, "new_Trapezoid: high.y = POSITIVE_INFINITY" );11 equal( myTrap.vLow.x, Number.NEGATIVE_INFINITY, "new_Trapezoid: low.x = NEGATIVE_INFINITY" );12 equal( myTrap.vLow.y, Number.NEGATIVE_INFINITY, "new_Trapezoid: low.y = NEGATIVE_INFINITY" );13 equal( myTrap.lseg, null, "new_Trapezoid: no left segment" );14 equal( myTrap.rseg, null, "new_Trapezoid: no right segment" );15 equal( myTrap.uL, null, "new_Trapezoid: no upper left neighbor" );16 equal( myTrap.uR, null, "new_Trapezoid: no upper right neighbor" );17 equal( myTrap.dL, null, "new_Trapezoid: no lower left neighbor" );18 equal( myTrap.dR, null, "new_Trapezoid: no lower right neighbor" );19 equal( myTrap.sink, null, "new_Trapezoid: no QueryStructure node attached" );20 equal( myTrap.usave, null, "new_Trapezoid: usave == null" );21 equal( myTrap.uleft, null, "new_Trapezoid: uleft == null" );22 equal( myTrap.depth, -1, "new_Trapezoid: depth not yet assigned" );23 equal( myTrap.monoDone, false, "new_Trapezoid: not yet monotonized" );24 //25 // filled trapezoid26 var highPt = { x: 1, y: 4 };27 var lowPt = { x: 3, y: 1 };28 var leftSeg = { vFrom: highPt, vTo: { x: 2, y: 0 }, upward: false };29 var rightSeg = { vFrom: lowPt, vTo: { x: 2, y: 5 }, upward: true };30 //31 myTrap = new PNLTRI.Trapezoid( highPt, lowPt, leftSeg, rightSeg );32 equal( myTrap.vHigh, highPt, "new_Trapezoid: high point" );33 equal( myTrap.vLow, lowPt, "new_Trapezoid: low point" );34 equal( myTrap.lseg, leftSeg, "new_Trapezoid: left segment" );35 equal( myTrap.rseg, rightSeg, "new_Trapezoid: right segment" );36 equal( myTrap.uL, null, "new_Trapezoid: no upper left neighbor" );37 equal( myTrap.uR, null, "new_Trapezoid: no upper right neighbor" );38 equal( myTrap.dL, null, "new_Trapezoid: no lower left neighbor" );39 equal( myTrap.dR, null, "new_Trapezoid: no lower right neighbor" );40 equal( myTrap.sink, null, "new_Trapezoid: no QueryStructure node attached" );41 equal( myTrap.usave, null, "new_Trapezoid: usave == null" );42 equal( myTrap.uleft, null, "new_Trapezoid: uleft == null" );43 equal( myTrap.depth, -1, "new_Trapezoid: depth not yet assigned" );44 equal( myTrap.monoDone, false, "new_Trapezoid: not yet monotonized" );45 }46 function test_clone() {47 //48 // empty trapezoid49 var myTrap = new PNLTRI.Trapezoid().clone();50 equal( myTrap.vHigh.x, Number.POSITIVE_INFINITY, "clone_Trapezoid: high.x = POSITIVE_INFINITY" );51 equal( myTrap.vHigh.y, Number.POSITIVE_INFINITY, "clone_Trapezoid: high.y = POSITIVE_INFINITY" );52 equal( myTrap.vLow.x, Number.NEGATIVE_INFINITY, "clone_Trapezoid: low.x = NEGATIVE_INFINITY" );53 equal( myTrap.vLow.y, Number.NEGATIVE_INFINITY, "clone_Trapezoid: low.y = NEGATIVE_INFINITY" );54 equal( myTrap.lseg, null, "clone_Trapezoid: no left segment" );55 equal( myTrap.rseg, null, "clone_Trapezoid: no right segment" );56 equal( myTrap.uL, null, "clone_Trapezoid: no upper left neighbor" );57 equal( myTrap.uR, null, "clone_Trapezoid: no upper right neighbor" );58 equal( myTrap.dL, null, "clone_Trapezoid: no lower left neighbor" );59 equal( myTrap.dR, null, "clone_Trapezoid: no lower right neighbor" );60 equal( myTrap.sink, null, "clone_Trapezoid: no QueryStructure node attached" );61 equal( myTrap.usave, null, "clone_Trapezoid: usave == null" );62 equal( myTrap.uleft, null, "clone_Trapezoid: uleft == null" );63 equal( myTrap.depth, -1, "clone_Trapezoid: depth not yet assigned" );64 equal( myTrap.monoDone, false, "clone_Trapezoid: not yet monotonized" );65 //66 // filled trapezoid67 var highPt = { x: 1, y: 4 };68 var lowPt = { x: 3, y: 1 };69 var leftSeg = { vFrom: highPt, vTo: { x: 2, y: 0 }, upward: false };70 var rightSeg = { vFrom: lowPt, vTo: { x: 2, y: 5 }, upward: true };71 var upperLeft = new PNLTRI.Trapezoid( highPt );72 var upperRight = new PNLTRI.Trapezoid( null, lowPt );73 var lowerLeft = new PNLTRI.Trapezoid( null, null, leftSeg );74 var lowerRight = new PNLTRI.Trapezoid( null, null, null, rightSeg );75 var dummySink = { trap: myTrap };76 //77 myTrap = new PNLTRI.Trapezoid( highPt, lowPt, leftSeg, rightSeg );78 myTrap.uL = upperLeft;79 myTrap.uR = upperRight;80 myTrap.dL = lowerLeft;81 myTrap.dR = lowerRight;82 myTrap.sink = dummySink;83 //84 var myTrap2 = myTrap.clone();85 equal( myTrap2.vHigh, highPt, "clone_Trapezoid: high point" );86 equal( myTrap2.vLow, lowPt, "clone_Trapezoid: low point" );87 equal( myTrap2.lseg, leftSeg, "clone_Trapezoid: left segment" );88 equal( myTrap2.rseg, rightSeg, "clone_Trapezoid: right segment" );89 equal( myTrap2.uL, upperLeft, "clone_Trapezoid: upper left neighbor" );90 equal( myTrap2.uR, upperRight, "clone_Trapezoid: upper right neighbor" );91 equal( myTrap2.dL, lowerLeft, "clone_Trapezoid: lower left neighbor" );92 equal( myTrap2.dR, lowerRight, "clone_Trapezoid: lower right neighbor" );93 equal( myTrap2.sink, dummySink, "clone_Trapezoid: dummy QueryStructure node attached" );94 equal( myTrap2.usave, null, "clone_Trapezoid: usave == null" );95 equal( myTrap2.uleft, null, "clone_Trapezoid: uleft == null" );96 equal( myTrap2.depth, -1, "clone_Trapezoid: depth not yet assigned" );97 equal( myTrap2.monoDone, false, "clone_Trapezoid: not yet monotonized" );98 }99 function test_splitOffLower() {100 //101 // empty trapezoid102 var myTrap = new PNLTRI.Trapezoid();103 var splitPt = { x: 2, y: 3 };104 var myLower = myTrap.splitOffLower( splitPt );105 equal( myTrap.vHigh.x, Number.POSITIVE_INFINITY, "splitOffLower: high.x = POSITIVE_INFINITY" );106 equal( myTrap.vHigh.y, Number.POSITIVE_INFINITY, "splitOffLower: high.y = POSITIVE_INFINITY" );107 equal( myTrap.vLow, splitPt, "splitOffLower: low = splitPt" );108 equal( myTrap.lseg, null, "splitOffLower: no left segment" );109 equal( myTrap.rseg, null, "splitOffLower: no right segment" );110 equal( myTrap.uL, null, "splitOffLower: no upper left neighbor" );111 equal( myTrap.uR, null, "splitOffLower: no upper right neighbor" );112 equal( myTrap.dL, myLower, "splitOffLower: new lower left neighbor" );113 equal( myTrap.dR, null, "splitOffLower: no lower right neighbor" );114 equal( myTrap.sink, null, "splitOffLower: no QueryStructure node attached" );115 equal( myTrap.usave, null, "splitOffLower: usave == null" );116 equal( myTrap.uleft, null, "splitOffLower: uleft == null" );117 equal( myTrap.depth, -1, "splitOffLower: depth not yet assigned" );118 equal( myTrap.monoDone, false, "splitOffLower: not yet monotonized" );119 //120 equal( myLower.vHigh, splitPt, "splitOffLower: high = splitPt" );121 equal( myLower.vLow.x, Number.NEGATIVE_INFINITY, "splitOffLower: low.x = NEGATIVE_INFINITY" );122 equal( myLower.vLow.y, Number.NEGATIVE_INFINITY, "splitOffLower: low.y = NEGATIVE_INFINITY" );123 equal( myLower.lseg, null, "splitOffLower: no left segment" );124 equal( myLower.rseg, null, "splitOffLower: no right segment" );125 equal( myLower.uL, myTrap, "splitOffLower: new upper left neighbor" );126 equal( myLower.uR, null, "splitOffLower: no upper right neighbor" );127 equal( myLower.dL, null, "splitOffLower: no lower left neighbor" );128 equal( myLower.dR, null, "splitOffLower: no lower right neighbor" );129 equal( myLower.sink, null, "splitOffLower: no QueryStructure node attached" );130 equal( myLower.usave, null, "splitOffLower: usave == null" );131 equal( myLower.uleft, null, "splitOffLower: uleft == null" );132 equal( myLower.depth, -1, "splitOffLower: depth not yet assigned" );133 equal( myLower.monoDone, false, "splitOffLower: not yet monotonized" );134 //135 // filled trapezoid136 var highPt = { x: 1, y: 4 };137 var lowPt = { x: 3, y: 1 };138 var leftSeg = { vFrom: highPt, vTo: { x: 2, y: 0 }, upward: false };139 var rightSeg = { vFrom: lowPt, vTo: { x: 2, y: 5 }, upward: true };140 var upperLeft = new PNLTRI.Trapezoid( highPt );141 var upperRight = new PNLTRI.Trapezoid( null, lowPt );142 var lowerLeft = new PNLTRI.Trapezoid( null, null, leftSeg );143 var lowerLeftUR = new PNLTRI.Trapezoid( null, null, rightSeg );144 var lowerRight = new PNLTRI.Trapezoid( null, null, null, rightSeg );145 var lowerRightUL = new PNLTRI.Trapezoid( null, null, null, leftSeg );146 var dummySink = { trap: myTrap };147 //148 myTrap = new PNLTRI.Trapezoid( highPt, lowPt, leftSeg, rightSeg );149 myTrap.uL = upperLeft; upperLeft.dL = myTrap;150 myTrap.uR = upperRight; upperRight.dR = myTrap;151 myTrap.dL = lowerLeft; lowerLeft.uL = myTrap; lowerLeft.uR = lowerLeftUR;152 myTrap.dR = lowerRight; lowerRight.uR = myTrap; lowerRight.uL = lowerRightUL;153 myTrap.sink = dummySink;154 //155 myLower = myTrap.splitOffLower( splitPt );156 equal( myTrap.vHigh, highPt, "splitOffLower: high point" );157 equal( myTrap.vLow, splitPt, "splitOffLower: low = split point" );158 equal( myTrap.lseg, leftSeg, "splitOffLower: left segment" );159 equal( myTrap.rseg, rightSeg, "splitOffLower: right segment" );160 equal( myTrap.uL, upperLeft, "splitOffLower: upper left neighbor unchanged" );161 equal( myTrap.uR, upperRight, "splitOffLower: upper right neighbor unchanged" );162 equal( myTrap.dL, myLower, "splitOffLower: new lower left neighbor" );163 equal( myTrap.dR, null, "splitOffLower: no lower right neighbor" );164 equal( myTrap.sink, dummySink, "splitOffLower: dummy QueryStructure node attached" );165 equal( myTrap.usave, null, "splitOffLower: usave == null" );166 equal( myTrap.uleft, null, "splitOffLower: uleft == null" );167 equal( myTrap.depth, -1, "splitOffLower: depth not yet assigned" );168 equal( myTrap.monoDone, false, "splitOffLower: not yet monotonized" );169 //170 equal( myLower.vHigh, splitPt, "splitOffLower: high = split point" );171 equal( myLower.vLow, lowPt, "splitOffLower: low point" );172 equal( myLower.lseg, leftSeg, "splitOffLower: left segment" );173 equal( myLower.rseg, rightSeg, "splitOffLower: right segment" );174 equal( myLower.uL, myTrap, "splitOffLower: new upper left neighbor" );175 equal( myLower.uR, null, "splitOffLower: no upper right neighbor" );176 equal( myLower.dL, lowerLeft, "splitOffLower: lower left neighbor unchanged" );177 equal( myLower.dR, lowerRight, "splitOffLower: lower right neighbor unchanged" );178 equal( myLower.sink, dummySink, "splitOffLower: dummy QueryStructure node attached" );179 equal( myLower.usave, null, "splitOffLower: usave == null" );180 equal( myLower.uleft, null, "splitOffLower: uleft == null" );181 equal( myLower.depth, -1, "splitOffLower: depth not yet assigned" );182 equal( myLower.monoDone, false, "splitOffLower: not yet monotonized" );183 //184 equal( upperLeft.dL, myTrap, "splitOffLower: upperLeft.dL unchanged" );185 equal( upperRight.dR, myTrap, "splitOffLower: upperRight.dR unchanged" );186 equal( lowerLeft.uL, myLower, "splitOffLower: lowerLeft.uL -> new lower" );187 equal( lowerLeft.uR, lowerLeftUR, "splitOffLower: lowerLeft.uR unchanged" );188 equal( lowerRight.uL, lowerRightUL, "splitOffLower: lowerRight.uL unchanged" );189 equal( lowerRight.uR, myLower, "splitOffLower: lowerRight.uR -> new lower" );190 }191 test( "Trapezoid", function() {192 test_new_Trapezoid();193 test_clone();194 test_splitOffLower();195 });196}197/*==============================================================================198 *199 *============================================================================*/200/* Base class extensions - for testing only */201PNLTRI.QueryStructure.prototype.setup_segments = function ( inSeg ) {202 var myQsRoot = this.getRoot();203 var currSeg = inSeg;204 do {205 currSeg.rootFrom = currSeg.rootTo = myQsRoot;206 currSeg.is_inserted = false;207 currSeg = currSeg.snext;208 } while ( currSeg != inSeg );209 this.add_segment( inSeg );210 return this.root;211};212PNLTRI.QueryStructure.prototype.nbTrapezoids = function () {213 return this.trapArray.length;214};215PNLTRI.QueryStructure.prototype.getTrapByIdx = function ( inIdx ) {216 return this.trapArray[inIdx];217};218// Check depth of the trapezoids219PNLTRI.QueryStructure.prototype.minDepth = function () {220 var myMinDepth = 1000;221 for (var i=0,j=this.trapArray.length; i<j; i++) {222 if ( this.trapArray[i].depth < myMinDepth ) {223 myMinDepth = this.trapArray[i].depth;224 }225 }226 return myMinDepth;227};228PNLTRI.QueryStructure.prototype.maxDepth = function () {229 var myMaxDepth = -2;230 for (var i=0,j=this.trapArray.length; i<j; i++) {231 if ( this.trapArray[i].depth > myMaxDepth ) {232 myMaxDepth = this.trapArray[i].depth;233 }234 }235 return myMaxDepth;236};237// check all trapezoids for link consistency238PNLTRI.QueryStructure.prototype.check_trapezoids_link_consistency = function () {239 var bugList = [];240 var currTrap;241 for (var i=0, j=this.trapArray.length; i<j; i++) {242 currTrap = this.trapArray[i];243 if ( currTrap.uL ) {244 if ( currTrap.uL == currTrap ) { bugList.push( "ID#"+currTrap.trapID+".uL: self-link" ); };245 if ( currTrap.uL == currTrap.uR ) { bugList.push( "ID#"+currTrap.trapID+".uL == uR" ); };246 if ( currTrap.uL == currTrap.dL ) { bugList.push( "ID#"+currTrap.trapID+".uL == dL" ); };247 if ( currTrap.uL == currTrap.dR ) { bugList.push( "ID#"+currTrap.trapID+".uL == dR" ); };248 if ( ( currTrap.uL.dL != currTrap ) &&249 ( currTrap.uL.dR != currTrap ) ) {250 bugList.push( "ID#"+currTrap.trapID+".uL: reverse dN-Link missing in ID#" + currTrap.uL.trapID );251 }252 }253 if ( currTrap.uR ) {254 if ( currTrap.uR == currTrap ) { bugList.push( "ID#"+currTrap.trapID+".uR: self-link" ); };255 if ( currTrap.uR == currTrap.dL ) { bugList.push( "ID#"+currTrap.trapID+".uR == dL" ); };256 if ( currTrap.uR == currTrap.dR ) { bugList.push( "ID#"+currTrap.trapID+".uR == dR" ); };257 if ( ( currTrap.uR.dL != currTrap ) &&258 ( currTrap.uR.dR != currTrap ) ) {259 bugList.push( "ID#"+currTrap.trapID+".uR: reverse dN-Link missing in ID#" + currTrap.uR.trapID );260 }261 }262 if ( currTrap.dL ) {263 if ( currTrap.dL == currTrap ) { bugList.push( "ID#"+currTrap.trapID+".dL: self-link" ); };264 if ( currTrap.dL == currTrap.dR ) { bugList.push( "ID#"+currTrap.trapID+".dL == dR" ); };265 if ( ( currTrap.dL.uL != currTrap ) &&266 ( currTrap.dL.uR != currTrap ) ) {267 bugList.push( "ID#"+currTrap.trapID+".dL: reverse uN-Link missing in ID#" + currTrap.dL.trapID );268 }269 }270 if ( currTrap.dR ) {271 if ( currTrap.dR == currTrap ) { bugList.push( "ID#"+currTrap.trapID+".dR: self-link" ); };272 if ( ( currTrap.dR.uL != currTrap ) &&273 ( currTrap.dR.uR != currTrap ) ) {274 bugList.push( "ID#"+currTrap.trapID+".dR: reverse uN-Link missing in ID#" + currTrap.dR.trapID );275 }276 }277 }278 return ( bugList.length == 0 ) ? null : bugList;279};280PNLTRI.QueryStructure.prototype.add_segment_consistently = function ( inSegment, inTestID ) {281 // integrated Unit-Test !!282 this.add_segment( inSegment );283 var buglist, bugStr = ( ( inSegment.is_inserted ) ? '' : 'NOT inserted; ' );284 if ( buglist = this.check_trapezoids_link_consistency() ) bugStr += buglist.join(", ");285 if ( bugStr.length > 0 ) {286 ok( false, "add_segment_consistently #"+inTestID+": " + bugStr );287 }288}289// check if trapezoid has specific neighbors290PNLTRI.QueryStructure.prototype.check_trapezoid_neighbors = function ( inTrapId, inChkUL, inChkUR, inChkDL, inChkDR, inTestName ) {291 var trapezoid = this.getTrapByIdx(inTrapId);292 if ( trapezoid ) {293 var uL_ID = trapezoid.uL ? trapezoid.uL.trapID : null;294 var uR_ID = trapezoid.uR ? trapezoid.uR.trapID : null;295 var dL_ID = trapezoid.dL ? trapezoid.dL.trapID : null;296 var dR_ID = trapezoid.dR ? trapezoid.dR.trapID : null;297 //298 equal( uL_ID, inChkUL, inTestName + ": uL == " + inChkUL );299 equal( uR_ID, inChkUR, inTestName + ": uR == " + inChkUR );300 equal( dL_ID, inChkDL, inTestName + ": dL == " + inChkDL );301 equal( dR_ID, inChkDR, inTestName + ": dR == " + inChkDR );302 } else {303 ok( trapezoid, inTestName + ": trapezoid exists" );304 }305}306// #############################################################################307function test_QueryStructure() {308 /* TODO: Tests for PNLTRI.QueryStructure.cloneTrap, trLeft, trRight */309 function test_is_left_of() {310 var myQs = new PNLTRI.QueryStructure();311 // going UPwards312 var segment = { vFrom: { x: 10, y: 10 }, vTo: { x: 17, y: 13 }, upward: true };313 // y equal314 ok( myQs.is_left_of(segment, { x: 0, y: 10 } ) > 0, "is_left_of: 0, 10 (yes)" );315 ok( myQs.is_left_of(segment, { x: 0, y: 13 } ) > 0, "is_left_of: 0, 13 (yes)" );316 ok( myQs.is_left_of(segment, { x: 20, y: 10 } ) < 0, "is_left_of: 20, 10 (no)" );317 ok( myQs.is_left_of(segment, { x: 20, y: 13 } ) < 0, "is_left_of: 20, 13 (no)" );318 //319 ok( myQs.is_left_of(segment, { x: 0, y: 10 }, true ) > 0, "is_left_of: 0, 10 (yes, between Y)" );320 ok( myQs.is_left_of(segment, { x: 0, y: 13 }, true ) > 0, "is_left_of: 0, 13 (yes, between Y)" );321 ok( myQs.is_left_of(segment, { x: 20, y: 10 }, true ) < 0, "is_left_of: 20, 10 (no, between Y)" );322 ok( myQs.is_left_of(segment, { x: 20, y: 13 }, true ) < 0, "is_left_of: 20, 13 (no, between Y)" );323 // on the line324 ok( myQs.is_left_of(segment, { x: 13.5, y: 11.5 } ) == 0, "is_left_of: 13.5, 11.5 (co-linear)" );325 ok( myQs.is_left_of(segment, { x: 13.5, y: 11.5 }, true ) == 0, "is_left_of: 13.5, 11.5 (co-linear, between Y)" );326 ok( myQs.is_left_of(segment, { x: 3, y: 7 } ) == 0, "is_left_of: 3, 7 (co-linear)" );327 ok( myQs.is_left_of(segment, { x: 24, y: 16 } ) == 0, "is_left_of: 24, 16 (co-linear)" );328 // general case329 // < x0330 ok( myQs.is_left_of(segment, { x: 0, y: 0 } ) < 0, "is_left_of: 0, 0 (no)" );331 ok( myQs.is_left_of(segment, { x: 4, y: 8 } ) > 0, "is_left_of: 4, 8 (yes)" );332 ok( myQs.is_left_of(segment, { x: 7, y: 11 } ) > 0, "is_left_of: 7, 11 (yes)" );333 ok( myQs.is_left_of(segment, { x: 7, y: 11 }, true ) > 0, "is_left_of: 7, 11 (yes, between Y)" );334 ok( myQs.is_left_of(segment, { x: 6, y: 15 } ) > 0, "is_left_of: 6, 15 (yes)" );335 // x0 < < x1336 ok( myQs.is_left_of(segment, { x: 12, y: 8 } ) < 0, "is_left_of: 12, 8 (no)" );337 ok( myQs.is_left_of(segment, { x: 15, y: 12 } ) < 0, "is_left_of: 15, 12 (no)" );338 ok( myQs.is_left_of(segment, { x: 15, y: 12 }, true ) < 0, "is_left_of: 15, 12 (no, between Y)" );339 ok( myQs.is_left_of(segment, { x: 12, y: 11 } ) > 0, "is_left_of: 12, 11 (yes)" );340 ok( myQs.is_left_of(segment, { x: 12, y: 11 }, true ) > 0, "is_left_of: 12, 11 (yes, between Y)" );341 ok( myQs.is_left_of(segment, { x: 14, y: 15 } ) > 0, "is_left_of: 14, 15 (yes)" );342 // > x1343 ok( myQs.is_left_of(segment, { x: 25, y: 8 } ) < 0, "is_left_of: 12, 8 (no)" );344 ok( myQs.is_left_of(segment, { x: 23, y: 12 } ) < 0, "is_left_of: 15, 12 (no)" );345 ok( myQs.is_left_of(segment, { x: 23, y: 12 }, true ) < 0, "is_left_of: 15, 12 (no, between Y)" );346 ok( myQs.is_left_of(segment, { x: 20, y: 14 } ) < 0, "is_left_of: 12, 11 (no)" );347 ok( myQs.is_left_of(segment, { x: 21, y: 15 } ) > 0, "is_left_of: 21, 15 (yes)" );348 //349 // going DOWNwards350 var segment = { vFrom: { x: 17, y: 13 }, vTo: { x: 10, y: 10 }, upward: false };351 // y equal352 ok( myQs.is_left_of(segment, { x: 0, y: 10 } ) > 0, "is_left_of: 0, 10 (yes)" );353 ok( myQs.is_left_of(segment, { x: 0, y: 13 } ) > 0, "is_left_of: 0, 13 (yes)" );354 ok( myQs.is_left_of(segment, { x: 20, y: 10 } ) < 0, "is_left_of: 20, 10 (no)" );355 ok( myQs.is_left_of(segment, { x: 20, y: 13 } ) < 0, "is_left_of: 20, 13 (no)" );356 //357 ok( myQs.is_left_of(segment, { x: 0, y: 10 }, true ) > 0, "is_left_of: 0, 10 (yes, between Y)" );358 ok( myQs.is_left_of(segment, { x: 0, y: 13 }, true ) > 0, "is_left_of: 0, 13 (yes, between Y)" );359 ok( myQs.is_left_of(segment, { x: 20, y: 10 }, true ) < 0, "is_left_of: 20, 10 (no, between Y)" );360 ok( myQs.is_left_of(segment, { x: 20, y: 13 }, true ) < 0, "is_left_of: 20, 13 (no, between Y)" );361 // on the line362 ok( myQs.is_left_of(segment, { x: 13.5, y: 11.5 } ) == 0, "is_left_of: 13.5, 11.5 (co-linear)" );363 ok( myQs.is_left_of(segment, { x: 13.5, y: 11.5 }, true ) == 0, "is_left_of: 13.5, 11.5 (co-linear, between Y)" );364 ok( myQs.is_left_of(segment, { x: 3, y: 7 } ) == 0, "is_left_of: 3, 7 (co-linear)" );365 ok( myQs.is_left_of(segment, { x: 24, y: 16 } ) == 0, "is_left_of: 24, 16 (co-linear)" );366 // general case367 // < x0368 ok( myQs.is_left_of(segment, { x: 0, y: 0 } ) < 0, "is_left_of: 0, 0 (no)" );369 ok( myQs.is_left_of(segment, { x: 4, y: 8 } ) > 0, "is_left_of: 4, 8 (yes)" );370 ok( myQs.is_left_of(segment, { x: 7, y: 11 } ) > 0, "is_left_of: 7, 11 (yes)" );371 ok( myQs.is_left_of(segment, { x: 7, y: 11 }, true ) > 0, "is_left_of: 7, 11 (yes, between Y)" );372 ok( myQs.is_left_of(segment, { x: 6, y: 15 } ) > 0, "is_left_of: 6, 15 (yes)" );373 // x0 < < x1374 ok( myQs.is_left_of(segment, { x: 12, y: 8 } ) < 0, "is_left_of: 12, 8 (no)" );375 ok( myQs.is_left_of(segment, { x: 15, y: 12 } ) < 0, "is_left_of: 15, 12 (no)" );376 ok( myQs.is_left_of(segment, { x: 15, y: 12 }, true ) < 0, "is_left_of: 15, 12 (no, between Y)" );377 ok( myQs.is_left_of(segment, { x: 12, y: 11 } ) > 0, "is_left_of: 12, 11 (yes)" );378 ok( myQs.is_left_of(segment, { x: 12, y: 11 }, true ) > 0, "is_left_of: 12, 11 (yes, between Y)" );379 ok( myQs.is_left_of(segment, { x: 14, y: 15 } ) > 0, "is_left_of: 14, 15 (yes)" );380 // > x1381 ok( myQs.is_left_of(segment, { x: 25, y: 8 } ) < 0, "is_left_of: 12, 8 (no)" );382 ok( myQs.is_left_of(segment, { x: 23, y: 12 } ) < 0, "is_left_of: 15, 12 (no)" );383 ok( myQs.is_left_of(segment, { x: 23, y: 12 }, true ) < 0, "is_left_of: 15, 12 (no, between Y)" );384 ok( myQs.is_left_of(segment, { x: 20, y: 14 } ) < 0, "is_left_of: 12, 11 (no)" );385 ok( myQs.is_left_of(segment, { x: 21, y: 15 } ) > 0, "is_left_of: 21, 15 (yes)" );386 }387 /* 0388 * ------------*----------------------389 * /390 * 1 / 3391 * /392 * --------*--------------------------393 * 2394 */395 function test_init_query_structure_up() {396 // going UPwards397 var base_segment = { vFrom: { x: 1, y: 1 }, vTo: { x: 3, y: 4 }, upward: true };398 // segment chain399 var thirdVertex = { x: 2, y: 4 };400 base_segment.snext = { vFrom: base_segment.vTo, vTo: thirdVertex, upward: false };401 base_segment.sprev = { vFrom: thirdVertex, vTo: base_segment.vFrom, upward: false };402 base_segment.snext.sprev = base_segment.sprev.snext = base_segment;403 base_segment.snext.snext = base_segment.sprev;404 base_segment.sprev.sprev = base_segment.snext;405 //406 var myQs = new PNLTRI.QueryStructure();407 var myQsRoot = myQs.setup_segments( base_segment );408// showDataStructure( myQsRoot );409 ok( base_segment.is_inserted, "init_query_structure_up: Segment inserted" );410 // segMax(vTo): root-Node411 equal( myQsRoot.yval, base_segment.vTo, "init_query_structure_up: root: yval = vTo" );412 ok( !myQsRoot.trap, "init_query_structure_up: root: no trapezoid" );413 ok( !myQsRoot.seg, "init_query_structure_up: root: no segment" );414 // top(tr0): above root415 var tr0, qsNode2 = myQsRoot.right;416 ok( ( tr0 = qsNode2.trap ), "init_query_structure_up: root.above: has trapezoid" );417 ok( !qsNode2.yval, "init_query_structure_up: root.above: no horizontal line" );418 ok( !qsNode2.seg, "init_query_structure_up: root.above: no segment" );419 // tr0420 equal( tr0.sink, qsNode2, "init_query_structure_up: root.above->tr.sink: this qsNode" );421 equal( tr0.vHigh.y, Number.POSITIVE_INFINITY, "init_query_structure_up: root.above->tr.vHigh.y: +INFINITY" );422 equal( tr0.vLow, base_segment.vTo, "init_query_structure_up: root.above->tr.vLow: vTo" );423 // segMin(vFrom): below root424 var qsNode3 = myQsRoot.left;425 equal( qsNode3.yval, base_segment.vFrom, "init_query_structure_up: root.below: yval = vFrom" );426 ok( !qsNode3.trap, "init_query_structure_up: root.below: no trapezoid" );427 ok( !qsNode3.seg, "init_query_structure_up: root.below: no segment" );428 //429 // bottom(tr2): below segMin(qsNode3)430 var tr2, qsNode4 = qsNode3.left;431 ok( ( tr2 = qsNode4.trap ), "init_query_structure_up: segMin.below: has trapezoid" );432 ok( !qsNode4.yval, "init_query_structure_up: segMin.below: no horizontal line" );433 ok( !qsNode4.seg, "init_query_structure_up: segMin.below: no segment" );434 // tr2435 equal( tr2.sink, qsNode4, "init_query_structure_up: segMin.below->tr.sink: this qsNode" );436 equal( tr2.vLow.y, Number.NEGATIVE_INFINITY, "init_query_structure_up: segMin.below->tr.vLow.y: -INFINITY" );437 equal( tr2.vHigh, base_segment.vFrom, "init_query_structure_up: segMin.below->tr.vHigh: vFrom" );438 //439 // Segment - below segMax, above segMin440 var qsNode5 = qsNode3.right;441 equal( qsNode5.seg, base_segment, "init_query_structure_up: segment.seg -> inSegment" );442 ok( !qsNode5.trap, "init_query_structure_up: segment: no trapezoid" );443 ok( !qsNode5.yval, "init_query_structure_up: segment: no horizontal line" );444 //445 // left(tr1): segment.left(qsNode5)446 var tr1, qsNode6 = qsNode5.left;447 ok( ( tr1 = qsNode6.trap ), "init_query_structure_up: segment.left: has trapezoid" );448 ok( !qsNode6.yval, "init_query_structure_up: segment.left: no horizontal line" );449 ok( !qsNode6.seg, "init_query_structure_up: segment.left: no segment" );450 // tr1451 equal( tr1.sink, qsNode6, "init_query_structure_up: segment.left->tr.sink: this qsNode" );452 equal( tr1.rseg, base_segment, "init_query_structure_up: segment.left->tr.rseg: inSegment" );453 equal( tr1.vHigh, base_segment.vTo, "init_query_structure_up: segment.left->tr.vHigh: vTo" );454 equal( tr1.vLow, base_segment.vFrom, "init_query_structure_up: segment.left->tr.vLow: vFrom" );455 //456 // right(tr3): segment.right(qsNode5)457 var tr3, qsNode7 = qsNode5.right;458 ok( ( tr3 = qsNode7.trap ), "init_query_structure_up: segment.right: has trapezoid" );459 ok( !qsNode7.yval, "init_query_structure_up: segment.right: no horizontal line" );460 ok( !qsNode7.seg, "init_query_structure_up: segment.right: no segment" );461 // tr3462 equal( tr3.sink, qsNode7, "init_query_structure_up: segment.right->tr.sink: this qsNode" );463 equal( tr3.lseg, base_segment, "init_query_structure_up: segment.right->tr.lseg: inSegment" );464 equal( tr3.vHigh, base_segment.vTo, "init_query_structure_up: segment.right->tr.vHigh: vTo" );465 equal( tr3.vLow, base_segment.vFrom, "init_query_structure_up: segment.right->tr.vLow: vFrom" );466 //467 // Trapezoid-Neighborhood468 myQs.check_trapezoid_neighbors( 0, null, null, 1, 3, "init_query_structure_up: top" );469 myQs.check_trapezoid_neighbors( 1, 0, null, 2, null, "init_query_structure_up: left" );470 myQs.check_trapezoid_neighbors( 2, 1, 3, null, null, "init_query_structure_up: bottom" );471 myQs.check_trapezoid_neighbors( 3, null, 0, null, 2, "init_query_structure_up: right" );472 //473 //474// showDataStructure( myQsRoot );475// drawTrapezoids( myQsRoot );476 }477 /* 0478 * --------*--------------------------479 * \480 * 1 \ 3481 * \482 * ------------*----------------------483 * 2484 */485 function test_init_query_structure_down() {486 // going DOWNwards487 var base_segment = { vFrom: { x: 1, y: 4 }, vTo: { x: 3, y: 1 }, upward: false };488 // segment chain489 var thirdVertex = { x: 3, y: 3 };490 base_segment.snext = { vFrom: base_segment.vTo, vTo: thirdVertex, upward: true };491 base_segment.sprev = { vFrom: thirdVertex, vTo: base_segment.vFrom, upward: true };492 base_segment.snext.sprev = base_segment.sprev.snext = base_segment;493 base_segment.snext.snext = base_segment.sprev;494 base_segment.sprev.sprev = base_segment.snext;495 //496 var myQs = new PNLTRI.QueryStructure();497 var myQsRoot = myQs.setup_segments( base_segment );498 ok( base_segment.is_inserted, "init_query_structure_down: Segment inserted" );499 // segMax(vFrom): root-Node500 equal( myQsRoot.yval, base_segment.vFrom, "init_query_structure_down: root: yval = vFrom" );501 // top(tr0): above root502 var tr0 = myQsRoot.right.trap;503 equal( tr0.vLow, base_segment.vFrom, "init_query_structure_down: root.above->tr.vLow: vFrom" );504 // segMin(vTo): below root505 var qsNode3 = myQsRoot.left;506 equal( qsNode3.yval, base_segment.vTo, "init_query_structure_down: root.below: yval = vTo" );507 //508 // bottom(tr2): below segMin(qsNode3)509 var tr2 = qsNode3.left.trap;510 equal( tr2.vHigh, base_segment.vTo, "init_query_structure_down: segMin.below->tr.vHigh: vTo" );511 //512 // Segment - below segMax, above segMin513 var qsNode5 = qsNode3.right;514 //515 // left(tr1): segment.left(qsNode5)516 var tr1 = qsNode5.left.trap;517 equal( tr1.vHigh, base_segment.vFrom, "init_query_structure_down: segment.left->tr.vHigh: vFrom" );518 equal( tr1.vLow, base_segment.vTo, "init_query_structure_down: segment.left->tr.vLow: vTo" );519 //520 // right(tr3): segment.right(qsNode5)521 var tr3 = qsNode5.right.trap;522 equal( tr3.vHigh, base_segment.vFrom, "init_query_structure_down: segment.right->tr.vHigh: vFrom" );523 equal( tr3.vLow, base_segment.vTo, "init_query_structure_down: segment.right->tr.vLow: vTo" );524 //525 //526// showDataStructure( myQsRoot );527// drawTrapezoids( myQsRoot );528 }529 /* 0530 * -------------*---------------------531 * /532 * 1 / 3533 * ----*-----/534 * 4 /535 * --------*--------------------------536 * 2537 * ------*----------------------------538 * 5539 */540 function test_splitNodeAtPoint1() {541 // going UPwards542 var base_segment = { vFrom: { x: 20, y: 20 }, vTo: { x: 30, y: 40 }, upward: true }543 // going DOWNwards - with exchanged coordinates544 var downward_segment = { vFrom: { x: 15, y: 10 }, vTo: { x: 10, y: 25 }, upward: true }545 // segment chain546 base_segment.snext = downward_segment.sprev = { vFrom: base_segment.vTo, vTo: downward_segment.vFrom, upward: false,547 sprev: base_segment, snext: downward_segment };548 base_segment.sprev = downward_segment.snext = { vFrom: downward_segment.vTo, vTo: base_segment.vFrom, upward: false,549 sprev: downward_segment, snext: base_segment };550 //551 var myQs = new PNLTRI.QueryStructure();552 var myQsRoot = myQs.setup_segments( base_segment );553 //554 // precheck of correct Trapezoids555 var tr1 = myQs.getTrapByIdx(1), qs_tr1 = tr1.sink;556 var tr2 = myQs.getTrapByIdx(2), qs_tr2 = tr2.sink;557 myQs.segNodes( downward_segment );558 ok( ( downward_segment.rootFrom == qs_tr2 ), "splitNodeAtPoint1: Seg.vFrom -> qs_tr2" );559 ok( ( downward_segment.rootTo == qs_tr1 ), "splitNodeAtPoint1: Seg.vTo -> qs_tr1" );560 //561// showDataStructure( myQsRoot );562// drawTrapezoids( myQsRoot );563 //564 // Main Test565 //566 // insert higher point into QueryStructure567 var qs_tr4 = myQs.splitNodeAtPoint( qs_tr1, downward_segment.vTo, false );568 //569 equal( qs_tr1.yval, downward_segment.vTo, "splitNodeAtPoint1: high.yval == splitPt" );570 ok( !qs_tr1.trap, "splitNodeAtPoint1: high: no trapezoid" );571 ok( !qs_tr1.seg, "splitNodeAtPoint1: high: no segment" );572 strictEqual( qs_tr1.right.trap, tr1, "splitNodeAtPoint1: high.right -> OrigTrap(tr1)" );573 strictEqual( qs_tr1.right, tr1.sink, "splitNodeAtPoint1: high.right == sink(OrigTrap(tr1))" );574 strictEqual( qs_tr1.left, qs_tr4, "splitNodeAtPoint1: high.left -> NewTrap(tr4)" );575 strictEqual( qs_tr1.left, qs_tr4.trap.sink, "splitNodeAtPoint1: high.left == sink(NewTrap(tr4))" );576 myQs.check_trapezoid_neighbors( 1, 0, null, 4, null, "splitNodeAtPoint1: OrigTrap(tr1) neighbors" );577 myQs.check_trapezoid_neighbors( 2, 4, 3, null, null, "splitNodeAtPoint1: tr2 neighbors" );578 myQs.check_trapezoid_neighbors( 4, 1, null, 2, null, "splitNodeAtPoint1: NewTrap(tr4) neighbors" );579 //580 // insert lower point into QueryStructure581 var qs_tr5 = myQs.splitNodeAtPoint( qs_tr2, downward_segment.vFrom, false );582 //583 equal( qs_tr2.yval, downward_segment.vFrom, "splitNodeAtPoint1: low.yval == splitPt" );584 ok( !qs_tr2.trap, "splitNodeAtPoint1: low: no trapezoid" );585 ok( !qs_tr2.seg, "splitNodeAtPoint1: low: no segment" );586 strictEqual( qs_tr2.right.trap, tr2, "splitNodeAtPoint1: low.right -> OrigTrap(tr2)" );587 strictEqual( qs_tr2.right, tr2.sink, "splitNodeAtPoint1: low.right == sink(OrigTrap(tr2))" );588 strictEqual( qs_tr2.left, qs_tr5, "splitNodeAtPoint1: low.left -> NewTrap(tr5)" );589 strictEqual( qs_tr2.left, qs_tr5.trap.sink, "splitNodeAtPoint1: low.left == sink(NewTrap(tr5))" );590 myQs.check_trapezoid_neighbors( 2, 4, 3, 5, null, "splitNodeAtPoint1: OrigTrap(tr2) neighbors" );591 myQs.check_trapezoid_neighbors( 5, 2, null, null, null, "splitNodeAtPoint1: NewTrap(tr5) neighbors" );592 //593 //594// showDataStructure( myQsRoot );595// drawTrapezoids( myQsRoot );596 }597 /* 0598 * -------------*---------------------599 * /600 * 1 / 3601 * /602 * /603 * --------*--------------------------604 * 2605 * ---*-------------------------------606 * 4607 */608 function test_splitNodeAtPoint2() {609 // going UPwards610 var base_segment = { vFrom: { x: 20, y: 20 }, vTo: { x: 30, y: 40 }, upward: true }611 // inside of tr2, connected !!612 var downward_segment = { vFrom: { x: 5, y: 15 }, vTo: base_segment.vFrom, upward: true }613 // segment chain614 var third_segment = { vFrom: base_segment.vTo, vTo: downward_segment.vFrom, upward: false,615 sprev: base_segment, snext: downward_segment };616 base_segment.sprev = downward_segment;617 downward_segment.snext = base_segment;618 base_segment.snext = downward_segment.sprev = third_segment;619 //620 var myQs = new PNLTRI.QueryStructure();621 var myQsRoot = myQs.setup_segments( base_segment );622 //623 // precheck of correct Trapezoids624 var tr2 = myQs.getTrapByIdx(2), qs_tr2 = tr2.sink;625 myQs.segNodes( downward_segment );626 ok( ( downward_segment.rootFrom == qs_tr2 ), "splitNodeAtPoint2: Seg.vFrom -> qs_tr2" );627 ok( ( downward_segment.rootTo == qs_tr2 ), "splitNodeAtPoint2: Seg.vTo -> qs_tr2" );628 //629// showDataStructure( myQsRoot );630// drawTrapezoids( myQsRoot );631 //632 // Main Test633 //634 // insert higher point into QueryStructure635 var qs_tr2b = myQs.splitNodeAtPoint( qs_tr2, downward_segment.vTo, false );636 equal( qs_tr2b, qs_tr2, "splitNodeAtPoint2: high: no split really happened, point already inserted" );637 //638 // insert lower point into QueryStructure639 var qs_tr4 = myQs.splitNodeAtPoint( qs_tr2, downward_segment.vFrom, false );640 //641 equal( qs_tr2.yval, downward_segment.vFrom, "splitNodeAtPoint2: low.yval == splitPt" );642 ok( !qs_tr2.trap, "splitNodeAtPoint2: low: no trapezoid" );643 ok( !qs_tr2.seg, "splitNodeAtPoint2: low: no segment" );644 strictEqual( qs_tr2.right.trap, tr2, "splitNodeAtPoint2: low.right -> OrigTrap(tr2)" );645 strictEqual( qs_tr2.right, tr2.sink, "splitNodeAtPoint2: low.right == sink(OrigTrap(tr2))" );646 strictEqual( qs_tr2.left, qs_tr4, "splitNodeAtPoint2: low.left -> NewTrap(tr4)" );647 strictEqual( qs_tr2.left, qs_tr4.trap.sink, "splitNodeAtPoint2: low.left == sink(NewTrap(tr4))" );648 myQs.check_trapezoid_neighbors( 2, 1, 3, 4, null, "splitNodeAtPoint2: OrigTrap(tr2) neighbors" );649 myQs.check_trapezoid_neighbors( 4, 2, null, null, null, "splitNodeAtPoint2: NewTrap(tr4) neighbors" );650 //651 //652// showDataStructure( myQsRoot );653// drawTrapezoids( myQsRoot );654 }655 function test_ptNode() {656 //657 // 0658 // ------------*---------------------- myQsRoot659 // /660 // 1 qsLR 3661 // /662 // --------*-------------------------- qsL663 // 2664 //665 // point objects666 var firstPoint = { x: 1, y: 1 };667 var secondPoint = { x: 3, y: 4 };668 var thirdPoint = { x: 2, y: 4 };669 // going UPwards670 var base_segment = { vFrom: firstPoint,671 vTo: secondPoint,672 upward: true,673 }674 // segment chain675 var thirdVertex = thirdPoint;676 base_segment.snext = { vFrom: base_segment.vTo, vTo: thirdVertex, upward: false };677 base_segment.sprev = { vFrom: thirdVertex, vTo: base_segment.vFrom, upward: false };678 base_segment.snext.sprev = base_segment.sprev.snext = base_segment;679 base_segment.snext.snext = base_segment.sprev;680 base_segment.sprev.sprev = base_segment.snext;681 //682 var myQs = new PNLTRI.QueryStructure();683 var myQsRoot = myQs.setup_segments( base_segment ); // Y-Node684// showDataStructure( myQsRoot );685 //686 var qs_tr0 = myQsRoot.right; // myQsRoot.right.trap: tr0;687 var qsL = myQsRoot.left; // Y-Node688 var qs_tr2 = qsL.left; // qsL.left.trap: tr2;689 var qsLR = qsL.right; // X-Node: base_segment690 var qs_tr1 = qsLR.left; // qsLR.left.trap: tr1;691 var qs_tr3 = qsLR.right; // qsLR.right.trap: tr3;692 // SINK-Node693 ok( ( myQs.ptNode( { vFrom: { x: 2, y: 5 }, vTo: { x: 3, y: 6 }, rootFrom: qsL.left }, true ) == qs_tr2 ), "ptNode A: Sink direct -> qs_tr2" );694 // Y-Node695 ok( ( myQs.ptNode( { vFrom: { x: 2, y: 5 }, vTo: { x: 3, y: 6 }, rootFrom: myQsRoot }, true ) == qs_tr0 ), "ptNode A: Y-Node(root), above -> qs_tr0" );696 ok( ( myQs.ptNode( { vFrom: { x: 2, y: 0 }, vTo: { x: 4, y: -1 }, rootFrom: qsL }, true ) == qs_tr2 ), "ptNode A: Y-Node(qsL), below -> qs_tr2" );697 // Y-Node: 1.end point hit698 ok( ( myQs.ptNode( { vFrom: firstPoint, vTo: { x: 4, y: 0 }, rootFrom: qsL }, true ) == qs_tr2 ), "ptNode A: Y-Node(qsL), =vFrom, below -> qs_tr2" );699 // Y-Node: 2.end point hit700 ok( ( myQs.ptNode( { vFrom: secondPoint, vTo: { x: 0, y: 5 }, rootFrom: myQsRoot }, true ) == qs_tr0 ), "ptNode A: Y-Node(root), =vTo, above -> qs_tr0" );701 // X-Node702 ok( ( myQs.ptNode( { vFrom: { x: 2, y: 3 }, vTo: { x: 3, y: 6 }, rootFrom: qsLR }, true ) == qs_tr1 ), "ptNode A: X-Node(qsLR) -> qs_tr1" );703 ok( ( myQs.ptNode( { vFrom: { x: 2, y: 2 }, vTo: { x: 3, y: 6 }, rootFrom: qsLR }, true ) == qs_tr3 ), "ptNode A: X-Node(qsLR) -> qs_tr3" );704 // X-Node: 1.end point hit - not horizontal705 ok( ( myQs.ptNode( { vFrom: firstPoint, vTo: { x: 0, y: 0 }, rootFrom: qsLR }, true ) == qs_tr1 ), "ptNode A: X-Node(qsLR), =vFrom -> qs_tr1" );706 ok( ( myQs.ptNode( { vFrom: { x: 2, y: 2 }, vTo: firstPoint, rootTo: qsLR }, false ) == qs_tr3 ), "ptNode A: X-Node(qsLR), =vFrom -> qs_tr3" );707 // X-Node: 2.end point hit - not horizontal708 ok( ( myQs.ptNode( { vFrom: secondPoint, vTo: { x: 3, y: 5 }, rootFrom: qsLR }, true ) == qs_tr1 ), "ptNode A: X-Node(qsLR), =vTo -> qs_tr1" );709 ok( ( myQs.ptNode( { vFrom: { x: 4, y: 5 }, vTo: secondPoint, rootTo: qsLR }, false ) == qs_tr3 ), "ptNode A: X-Node(qsLR), =vTo -> qs_tr3" );710 // X-Node: 1.end point hit - horizontal711 ok( ( myQs.ptNode( { vFrom: firstPoint, vTo: { x: 0, y: 1 }, rootFrom: qsLR }, true ) == qs_tr1 ), "ptNode A: X-Node(qsLR), =vFrom, horiz -> qs_tr1" );712 ok( ( myQs.ptNode( { vFrom: firstPoint, vTo: { x: 2, y: 1 }, rootFrom: qsLR }, true ) == qs_tr3 ), "ptNode A: X-Node(qsLR), =vFrom, horiz -> qs_tr3" );713 // X-Node: 2.end point hit - horizontal714 ok( ( myQs.ptNode( { vFrom: secondPoint, vTo: { x: 2.5, y: 4 }, rootFrom: qsLR }, true ) == qs_tr1 ), "ptNode A: X-Node(qsLR), =vTo, horiz -> qs_tr1" );715 ok( ( myQs.ptNode( { vFrom: secondPoint, vTo: { x: 4, y: 4 }, rootFrom: qsLR }, true ) == qs_tr3 ), "ptNode A: X-Node(qsLR), =vTo, horiz -> qs_tr3" );716 //717 // 0718 // --------*-------------------------- myQsRoot719 // \720 // 1 qsLR 3721 // \722 // ------------*---------------------- qsL723 // 2724 //725 // point objects726 firstPoint = { x: 1, y: 4 };727 secondPoint = { x: 3, y: 1 };728 thirdPoint = { x: 3, y: 3 };729 // DOWNward segment730 base_segment = { vFrom: firstPoint,731 vTo: secondPoint,732 }733 // segment chain734 thirdVertex = thirdPoint;735 base_segment.snext = { vFrom: base_segment.vTo, vTo: thirdVertex };736 base_segment.sprev = { vFrom: thirdVertex, vTo: base_segment.vFrom };737 base_segment.snext.sprev = base_segment.sprev.snext = base_segment;738 base_segment.snext.snext = base_segment.sprev;739 base_segment.sprev.sprev = base_segment.snext;740 //741 myQs = new PNLTRI.QueryStructure();742 myQsRoot = myQs.setup_segments( base_segment ); // Y-Node743// showDataStructure( myQsRoot );744 //745 qs_tr0 = myQsRoot.right; // myQsRoot.right.trap: tr0;746 qsL = myQsRoot.left; // Y-Node747 qs_tr2 = qsL.left; // qsL.left.trap: tr2;748 qsLR = qsL.right; // X-Node: base_segment749 qs_tr1 = qsLR.left; // qsLR.left.trap: tr1;750 qs_tr3 = qsLR.right; // qsLR.right.trap: tr3;751 // SINK-Node752 ok( ( myQs.ptNode( { vFrom: { x: 2, y: 5 }, vTo: { x: 3, y: 6 }, rootFrom: qsL.left }, true ) == qs_tr2 ), "ptNode B: Sink direct -> qs_tr2" );753 // Y-Node754 ok( ( myQs.ptNode( { vFrom: { x: 2, y: 5 }, vTo: { x: 3, y: 6 }, rootFrom: myQsRoot }, true ) == qs_tr0 ), "ptNode B: Y-Node(root), above -> qs_tr0" );755 ok( ( myQs.ptNode( { vFrom: { x: 2, y: 0 }, vTo: { x: 4, y: -1 }, rootFrom: qsL }, true ) == qs_tr2 ), "ptNode B: Y-Node(qsL), below -> qs_tr2" );756 // Y-Node: 1.end point hit757 ok( ( myQs.ptNode( { vFrom: firstPoint, vTo: { x: 0, y: 5 }, rootFrom: myQsRoot }, true ) == qs_tr0 ), "ptNode B: Y-Node(root), =vFrom, above -> qs_tr0" );758 // Y-Node: 2.end point hit759 ok( ( myQs.ptNode( { vFrom: secondPoint, vTo: { x: 4, y: 0 }, rootFrom: qsL }, true ) == qs_tr2 ), "ptNode B: Y-Node(qsL), =vTo, below -> qs_tr2" );760 // X-Node761 ok( ( myQs.ptNode( { vFrom: { x: 2, y: 2 }, vTo: { x: 3, y: 6 }, rootFrom: qsLR }, true ) == qs_tr1 ), "ptNode B: X-Node(qsLR) -> qs_tr1" );762 ok( ( myQs.ptNode( { vFrom: { x: 2, y: 3 }, vTo: { x: 3, y: 6 }, rootFrom: qsLR }, true ) == qs_tr3 ), "ptNode B: X-Node(qsLR) -> qs_tr3" );763 // X-Node: 1.end point hit - not horizontal764 ok( ( myQs.ptNode( { vFrom: firstPoint, vTo: { x: 0, y: 5 }, rootFrom: qsLR }, true ) == qs_tr1 ), "ptNode B: X-Node(qsLR), =vFrom -> qs_tr1" );765 ok( ( myQs.ptNode( { vFrom: firstPoint, vTo: { x: 0, y: 6 }, rootFrom: qsLR }, true ) == qs_tr3 ), "ptNode B: X-Node(qsLR), =vFrom -> qs_tr3" );766 // X-Node: 2.end point hit - not horizontal767 ok( ( myQs.ptNode( { vFrom: secondPoint, vTo: { x: 4, y: -1 }, rootFrom: qsLR }, true ) == qs_tr1 ), "ptNode B: X-Node(qsLR), =vTo -> qs_tr1" );768 ok( ( myQs.ptNode( { vFrom: secondPoint, vTo: { x: 4, y: 0 }, rootFrom: qsLR }, true ) == qs_tr3 ), "ptNode B: X-Node(qsLR), =vTo -> qs_tr3" );769 // X-Node: 1.end point hit - horizontal770 ok( ( myQs.ptNode( { vFrom: firstPoint, vTo: { x: 0, y: 4 }, rootFrom: qsLR }, true ) == qs_tr1 ), "ptNode B: X-Node(qsLR), =vFrom, horiz -> qs_tr1" );771 ok( ( myQs.ptNode( { vFrom: firstPoint, vTo: { x: 2, y: 4 }, rootFrom: qsLR }, true ) == qs_tr3 ), "ptNode B: X-Node(qsLR), =vFrom, horiz -> qs_tr3" );772 // X-Node: 2.end point hit - horizontal773 ok( ( myQs.ptNode( { vFrom: secondPoint, vTo: { x: 2, y: 1 }, rootFrom: qsLR }, true ) == qs_tr1 ), "ptNode B: X-Node(qsLR), =vTo, horiz -> qs_tr1" );774 ok( ( myQs.ptNode( { vFrom: secondPoint, vTo: { x: 4, y: 1 }, rootFrom: qsLR }, true ) == qs_tr3 ), "ptNode B: X-Node(qsLR), =vTo, horiz -> qs_tr3" );775 }776 /**************************************************************************/777 //778 // Cases of endpoints touching other segments779 // The touched segment is already inserted, now the endpoint of another segment,780 // which lies ON the first segment shall be located with ptNode()781 // This is the opposite case to "test_add_segment_touching_N"782 //783 function test_ptNode_touching() {784 var testPolygon = [ { x: 10, y: 30 }, { x: 20, y: 10 }, { x: 30, y: 40 } ];785 var myPolygonData = new PNLTRI.PolygonData( [ testPolygon ] );786 var segListArray = myPolygonData.getSegments();787 var myQs = new PNLTRI.QueryStructure( myPolygonData );788 var myQsRoot = myQs.getRoot();789 myQs.add_segment( segListArray[1] ); // touch line; touch point: 25,25790 var qs_tr1 = myQs.getTrapByIdx(1).sink;791 var qs_tr3 = myQs.getTrapByIdx(3).sink;792// showDataStructure( myQsRoot );793// drawTrapezoids( myQsRoot, false );794 var testSegment;795 // DOWNward segments796 myQs.segNodes( testSegment = { vFrom: { x: 25, y: 25 }, vTo: { x: 15, y: 15 }, rootFrom: myQsRoot, rootTo: myQsRoot } );797 ok( ( testSegment.rootFrom == qs_tr1 ), "ptNode_touching: down from, left -> qs_tr1" );798 ok( ( testSegment.rootTo == qs_tr1 ), "ptNode_touching: down to, left -> qs_tr1" );799 myQs.segNodes( testSegment = { vFrom: { x: 25, y: 25 }, vTo: { x: 35, y: 15 }, rootFrom: myQsRoot, rootTo: myQsRoot } );800 ok( ( testSegment.rootFrom == qs_tr3 ), "ptNode_touching: down from, right -> qs_tr3" );801 ok( ( testSegment.rootTo == qs_tr3 ), "ptNode_touching: down to, right -> qs_tr3" );802 // UPward segments803 myQs.segNodes( testSegment = { vFrom: { x: 25, y: 25 }, vTo: { x: 15, y: 35 }, rootFrom: myQsRoot, rootTo: myQsRoot } );804 ok( ( testSegment.rootFrom == qs_tr1 ), "ptNode_touching: up from, left -> qs_tr1" );805 ok( ( testSegment.rootTo == qs_tr1 ), "ptNode_touching: up to, left -> qs_tr1" );806 myQs.segNodes( testSegment = { vFrom: { x: 25, y: 25 }, vTo: { x: 35, y: 35 }, rootFrom: myQsRoot, rootTo: myQsRoot } );807 ok( ( testSegment.rootFrom == qs_tr3 ), "ptNode_touching: up from, right -> qs_tr3" );808 ok( ( testSegment.rootTo == qs_tr3 ), "ptNode_touching: up to, right -> qs_tr3" );809 }810 //811 // Helper function:812 // Checks where segment endpoints get located for all segments813 // after the insertion of one "base" segment814 //815 function check_one_ptNode_case( inTestName, inTestPolygon, inBaseSeg, inResults ) {816 var myPolygonData = new PNLTRI.PolygonData( [ inTestPolygon ] );817 var segListArray = myPolygonData.getSegments();818 var myQs = new PNLTRI.QueryStructure( myPolygonData );819 var myQsRoot = myQs.getRoot();820 myQs.add_segment( segListArray[inBaseSeg] ); // start touch line821 var qs_tr = [ myQs.getTrapByIdx(0).sink, myQs.getTrapByIdx(1).sink,822 myQs.getTrapByIdx(2).sink, myQs.getTrapByIdx(3).sink ];823// showDataStructure( myQsRoot );824// drawTrapezoids( myQsRoot, false );825 // check other segments endpoints826 for ( var segId = 0; segId < inResults.length; segId++ ) {827 if ( !inResults[segId] ) continue; // skip base segment828 myQs.segNodes( segListArray[segId] );829 var qsFrom = inResults[segId][0], qsTo = inResults[segId][1];830 ok( ( segListArray[segId].rootFrom == qs_tr[qsFrom] ), inTestName + ": Seg#"+segId+" from -> qs_tr" + qsFrom );831 ok( ( segListArray[segId].rootTo == qs_tr[qsTo] ), inTestName + ": Seg#"+segId+" to -> qs_tr" + qsTo );832 }833 }834 //835 // Cases of segments being co-linear and fully inside of other segments836 //837 function test_ptNode_colinear_inside() {838 function check_one_case( inTestName, inTestPolygon, inBaseSeg, inResults ) {839 check_one_ptNode_case( "ptNode_colinear_inside " + inTestName, inTestPolygon, inBaseSeg, inResults );840 }841 // fully left side, CCW // TODO: CW842 //843 // 0844 // ------------*-------------- myQsRoot845 // + /846 // 1 +/ 3847 // ++/848 // /849 // -------*------------------- qsL850 // 2851 //852 var testPolygon = [ { x: 5, y: 14 }, { x: 10, y: 10 }, { x: 40, y: 40 },853 { x: 35, y: 37 }, { x: 30, y: 30 }, { x: 20, y: 20 } ];854// drawPolygonLayers( { "poly": [ testPolygon ] } );855 check_one_case( "lg", testPolygon, 1,856 [ null, null, null, [ 1, 1 ], [ 1, 1 ], [ 1, 1 ] ] ); // 0:-, 1: base, 2:-, 3, 4: co-linear, 5857 // horizontal lines858 var testPolygon = [ { x: 15, y: 15 }, { x: 10, y: 10 }, { x: 40, y: 10 },859 { x: 35, y: 20 }, { x: 30, y: 10 }, { x: 20, y: 10 } ];860 check_one_case( "lh", testPolygon, 1,861 [ [ 0, 1 ], null, [ 0, 0 ], [ 0, 1 ], [ 1, 1 ], [ 1, 0 ] ] ); // 0, 1: base, 2, 3, 4: co-linear, 5862 // vertical lines863 var testPolygon = [ { x: 15, y: 15 }, { x: 30, y: 10 }, { x: 30, y: 40 },864 { x: 25, y: 35 }, { x: 30, y: 30 }, { x: 30, y: 20 } ];865 check_one_case( "lv", testPolygon, 1,866 [ [ 1, 1 ], null, [ 1, 1 ], [ 1, 1 ], [ 1, 1 ], [ 1, 1 ] ] ); // 0, 1: base, 2, 3, 4: co-linear, 5867 // fully right side, CW // TODO: CCW868 //869 // 0870 // ------------*-------------- myQsRoot871 // /872 // 1 /++ 3873 // /+874 // ´ / +875 // -------*------------------- qsL876 // 2877 //878 var testPolygon = [ { x: 25, y: 14 }, { x: 10, y: 10 }, { x: 40, y: 40 },879 { x: 45, y: 37 }, { x: 30, y: 30 }, { x: 20, y: 20 } ];880// drawPolygonLayers( { "poly": [ testPolygon ] } );881 check_one_case( "rg", testPolygon, 1,882 [ null, null, null, [ 3, 3 ], [ 3, 3 ], [ 3, 3 ] ] ); // 0:-, 1: base, 2:-, 3, 4: co-linear, 5883 // horizontal lines884 var testPolygon = [ { x: 15, y: 30 }, { x: 10, y: 40 }, { x: 40, y: 40 },885 { x: 35, y: 35 }, { x: 30, y: 40 }, { x: 20, y: 40 } ];886 check_one_case( "rh", testPolygon, 1,887 [ [ 2, 2 ], null, [ 3, 2 ], [ 2, 3 ], [ 3, 3 ], [ 3, 2 ] ] ); // 0, 1: base, 2, 3, 4: co-linear, 5888 // vertical lines889 var testPolygon = [ { x: 45, y: 15 }, { x: 30, y: 10 }, { x: 30, y: 40 },890 { x: 35, y: 35 }, { x: 30, y: 30 }, { x: 30, y: 20 } ];891 check_one_case( "rv", testPolygon, 1,892 [ [ 3, 3 ], null, [ 3, 3 ], [ 3, 3 ], [ 3, 3 ], [ 3, 3 ] ] ); // 0, 1: base, 2, 3, 4: co-linear, 5893 }894 //895 // Cases of segments being co-linear and overlapping other segments896 //897 function test_ptNode_colinear_overlapping() {898 function check_one_case( inTestName, inTestPolygon, inBaseSeg, inResults ) {899 check_one_ptNode_case( "ptNode_colinear_overlapping " + inTestName, inTestPolygon, inBaseSeg, inResults );900 }901 // overlapping left low, right high, CCW902 //903 // 0904 // -----------*--------------- myQsRoot905 // + /906 // 1 +/ 3907 // +*------------------- qsL908 // +__ 2909 //910 var testPolygon = [ { x: 25, y: 14 }, { x: 20, y: 20 }, { x: 40, y: 40 },911 { x: 29, y: 37 }, { x: 30, y: 30 }, { x: 10, y: 10 } ];912// drawPolygonLayers( { "poly": [ testPolygon ] } );913 check_one_case( "la", testPolygon, 1,914 [ null, null, null, [ 1, 1 ], [ 1, 2 ], [ 2, 2 ] ] ); // 0:-, 1: base, 2:-, 3, 4: co-linear, 5915 check_one_case( "lb", testPolygon, 4,916 [ [ 3, 3 ], [ 3, 0 ], [ 0, 0 ] ] ); // 0, 1: co-linear, 2, 3:-, 4: base, 5:-917 // overlapping right low, left high, CW918 //919 // 0920 // ------------*-------------- myQsRoot921 // /922 // 1 /++ 3923 // ---------*+ qsL924 // + 2925 // +926 var testPolygon = [ { x: 5, y: 14 }, { x: 20, y: 20 }, { x: 40, y: 40 },927 { x: 45, y: 37 }, { x: 30, y: 30 }, { x: 10, y: 10 } ];928// drawPolygonLayers( { "poly": [ testPolygon ] } );929 check_one_case( "ra", testPolygon, 1,930 [ null, null, null, [ 3, 3 ], [ 3, 2 ], [ 2, 2 ] ] ); // 0:-, 1: base, 2:-, 3, 4: co-linear, 5931 check_one_case( "rb", testPolygon, 4,932 [ [ 1, 1 ], [ 1, 0 ], [ 0, 0 ] ] ); // 0, 1: co-linear, 2, 3:-, 4: base, 5:-933 }934 //935 // Cases of segments reversing direction co-linear with the prev/next segment936 //937 function test_ptNode_colinear_reversal() {938 function check_one_case( inTestName, inTestPolygon, inBaseSeg, inResults ) {939 check_one_ptNode_case( "ptNode_colinear_reversal " + inTestName, inTestPolygon, inBaseSeg, inResults );940 }941 // reversal low, left triang high942 //943 // 0944 // -----------*--------------- myQsRoot945 // + /946 // 1 +/ 3947 // +/948 // -------*------------------- qsL949 // 2950 // CCW951 var testPolygon = [ { x: 20, y: 20 }, { x: 40, y: 40 },952 { x: 23, y: 28 }, { x: 30, y: 30 } ];953// drawPolygonLayers( { "poly": [ testPolygon ] } );954 check_one_case( "llCCWa", testPolygon, 0,955 [ null, [ 1, 1 ], [ 1, 1 ], [ 1, 1 ] ] ); // 0: base, 1, 2, 3: co-linear956 check_one_case( "llCCWb", testPolygon, 3,957 [ [ 3, 0 ], [ 0, 1 ], [ 1, 1 ], null ] ); // 0: co-linear, 1, 2, 3: base958 // CW959 var testPolygon = [ { x: 40, y: 40 }, { x: 20, y: 20 },960 { x: 30, y: 30 }, { x: 23, y: 28 } ];961 check_one_case( "llCWa", testPolygon, 0,962 [ null, [ 1, 1 ], [ 1, 1 ], [ 1, 1 ] ] ); // 0: base, 1: co-linear, 2, 3963 check_one_case( "llCWb", testPolygon, 1,964 [ [ 0, 3 ], null, [ 1, 1 ], [ 1, 0 ] ] ); // 0: co-linear, 1: base, 2, 3965 // reversal low, right triang high966 //967 // 0968 // ------------*-------------- myQsRoot969 // / +970 // 1 /+ 3971 // /+972 // --------*------------------ qsL973 // 2974 // CCW975 var testPolygon = [ { x: 40, y: 40 }, { x: 20, y: 20 },976 { x: 30, y: 30 }, { x: 41, y: 29 } ];977// drawPolygonLayers( { "poly": [ testPolygon ] } );978 check_one_case( "lrCCWa", testPolygon, 0,979 [ null, [ 3, 3 ], [ 3, 3 ], [ 3, 3 ] ] ); // 0: base, 1: co-linear, 2, 3980 check_one_case( "lrCCWb", testPolygon, 1,981 [ [ 0, 1 ], null, [ 3, 3 ], [ 3, 0 ] ] ); // 0: co-linear, 1: base, 2, 3982 // CW983 var testPolygon = [ { x: 40, y: 40 }, { x: 41, y: 29 },984 { x: 30, y: 30 }, { x: 20, y: 20 } ];985 check_one_case( "lrCWa", testPolygon, 3,986 [ [ 3, 3 ], [ 3, 3 ], [ 3, 3 ], null ] ); // 0, 1, 2: co-linear, 3: base987 check_one_case( "lrCWb", testPolygon, 2,988 [ [ 0, 3 ], [ 3, 3 ], null, [ 1, 0 ] ] ); // 0, 1, 2: base, 3: co-linear989 // reversal high, left triang low990 //991 // 0992 // -----------*--------------- myQsRoot993 // +/994 // 1 +/ 3995 // + /996 // -------*------------------- qsL997 // 2998 // CCW999 var testPolygon = [ { x: 30, y: 30 }, { x: 20, y: 20 },1000 { x: 8, y: 22 }, { x: 10, y: 10 } ];1001// drawPolygonLayers( { "poly": [ testPolygon ] } );1002 check_one_case( "hlCCWa", testPolygon, 3,1003 [ [ 1, 1 ], [ 1, 1], [ 1, 1 ], null ] ); // 0: co-linear, 1, 2, 3: base1004 check_one_case( "hlCCWb", testPolygon, 0,1005 [ null, [ 1, 1 ], [ 1, 2 ], [ 2, 3 ] ] ); // 0: base, 1, 2, 3: co-linear1006 // CW1007 var testPolygon = [ { x: 30, y: 30 }, { x: 10, y: 10 },1008 { x: 8, y: 22 }, { x: 20, y: 20 } ];1009 check_one_case( "hlCWa", testPolygon, 0,1010 [ null, [ 1, 1 ], [ 1, 1 ], [ 1, 1 ] ] ); // 0: base, 1, 2, 3: co-linear1011 check_one_case( "hlCWb", testPolygon, 3,1012 [ [ 3, 2 ], [ 2, 1 ], [ 1, 1 ], null ] ); // 0: co-linear, 1, 2, 3: base1013 // reversal high, right triang low1014 //1015 // 01016 // ------------*-------------- myQsRoot1017 // /+1018 // 1 /+ 31019 // / +1020 // --------*------------------ qsL1021 // 21022 // CCW1023 var testPolygon = [ { x: 30, y: 30 }, { x: 10, y: 10 },1024 { x: 28, y: 23 }, { x: 20, y: 20 } ];1025// drawPolygonLayers( { "poly": [ testPolygon ] } );1026 check_one_case( "hrCCWa", testPolygon, 0,1027 [ null, [ 3, 3 ], [ 3, 3 ], [ 3, 3 ] ] ); // 0: base, 1, 2, 3: co-linear1028 check_one_case( "hrCCWb", testPolygon, 3,1029 [ [ 1, 2 ], [ 2, 3 ], [ 3, 3 ], null ] ); // 0: co-linear, 1, 2, 3: base1030 // CW1031 var testPolygon = [ { x: 30, y: 30 }, { x: 20, y: 20 },1032 { x: 28, y: 23 }, { x: 10, y: 10 } ];1033 check_one_case( "hrCWa", testPolygon, 3,1034 [ [ 3, 3 ], [ 3, 3 ], [ 3, 3 ], null ] ); // 0: co-linear, 1, 2, 3: base1035 check_one_case( "hrCWb", testPolygon, 0,1036 [ null, [ 3, 3 ], [ 3, 2 ], [ 2, 1 ] ] ); // 0: base, 1, 2, 3: co-linear1037 }1038 /**************************************************************************/1039 function test_assign_depths() {1040 var testPolygon = [ { x: 5, y: 5 }, { x: 45, y: 20 }, { x: 15, y: 40 } ];1041 var myPolygonData = new PNLTRI.PolygonData( [ testPolygon ] );1042 var segListArray = myPolygonData.getSegments();1043 //1044 var myQs = new PNLTRI.QueryStructure( myPolygonData );1045 var myQsRoot = myQs.getRoot();1046 //1047 myQs.add_segment_consistently( segListArray[0], 'assign_depths #0' );1048 myQs.add_segment_consistently( segListArray[1], 'assign_depths #1' );1049 myQs.add_segment_consistently( segListArray[2], 'assign_depths #2' );1050 ok( myPolygonData.allSegsInQueryStructure(), "assign_depths: all segments inserted" );1051 //1052 // Main test: standard case1053 //1054 equal( myQs.minDepth(), -1, "assign_depths: Min depth: -1" );1055 equal( myQs.maxDepth(), -1, "assign_depths: Max depth: -1" );1056 myQs.assignDepths(myPolygonData); // marks outside trapezoids1057 equal( myQs.minDepth(), 0, "assign_depths: Min depth: 0" );1058 equal( myQs.maxDepth(), 1, "assign_depths: Max depth: 1" );1059 //1060// showDataStructure( myQsRoot );1061// drawTrapezoids( myQsRoot, false, 1 );1062 //1063 //1064 var myPolygonData = new PNLTRI.PolygonData( [ testPolygon ] );1065 var segListArray = myPolygonData.getSegments();1066 //1067 var myQs = new PNLTRI.QueryStructure( myPolygonData );1068 var myQsRoot = myQs.getRoot();1069 // not closed !!1070 myQs.add_segment_consistently( segListArray[0], 'assign_depths #0' );1071 myQs.add_segment_consistently( segListArray[1], 'assign_depths #1' );1072 //1073 // Main test: all outside1074 //1075 myQs.assignDepths(myPolygonData); // marks all trapezoids as outside1076 equal( myQs.minDepth(), 0, "assign_depths: Min depth: 0" );1077 equal( myQs.maxDepth(), 0, "assign_depths: Max depth: 0" );1078 //1079// showDataStructure( myQsRoot );1080// drawTrapezoids( myQsRoot, false, 1 );1081 }1082 /**************************************************************************/1083 /* 01084 * --------------------------*-------- y=40 myQsRoot1085 * 1 qsLR1086 * ------*-----------------/ 3 y=25 qsLRL1087 * \ 6 /1088 * \-------------*------------ y=20 qsL1089 * 4 qsLRLL 21090 * ----------*------------------------ y=10 qsLL1091 * 51092 */1093 function test_add_segment_basic_1() {1094 var base_segment = { vFrom: { x: 30, y: 40 }, vTo: { x: 20, y: 20 }, upward: false }1095 var other_segment = { vFrom: { x: 15, y: 10 }, vTo: { x: 10, y: 25 }, upward: true }1096 // segment chain1097 base_segment.snext = other_segment.sprev = { vFrom: base_segment.vTo, vTo: other_segment.vFrom, upward: false,1098 sprev: base_segment, snext: other_segment };1099 base_segment.sprev = other_segment.snext = { vFrom: other_segment.vTo, vTo: base_segment.vFrom, upward: true,1100 sprev: other_segment, snext: base_segment };1101 //1102 var myQs = new PNLTRI.QueryStructure();1103 var myQsRoot = myQs.setup_segments( base_segment );1104 ok( base_segment.is_inserted, "Add#1: Base Segment inserted" );1105 equal( myQs.nbTrapezoids(), 4, "Add#1: Number of Trapezoids in Array (4)" );1106 // precheck of correct Trapezoids1107 var qs_tr1 = myQs.getTrapByIdx(1).sink;1108 var qs_tr2 = myQs.getTrapByIdx(2).sink;1109 myQs.segNodes( other_segment );1110 ok( ( other_segment.rootFrom == qs_tr2 ), "Add#1: Seg.vFrom -> qs_tr2" );1111 ok( ( other_segment.rootTo == qs_tr1 ), "Add#1: Seg.vTo -> qs_tr1" );1112 //1113// showDataStructure( myQsRoot );1114// drawTrapezoids( myQsRoot );1115 //1116 // Main Test1117 //1118 myQs.add_segment( other_segment );1119 ok( other_segment.is_inserted, "Add#1: 2.Segment inserted" );1120 equal( myQs.nbTrapezoids(), 7, "Add#1: Number of Trapezoids in Array (7)" );1121 //1122 myQs.check_trapezoid_neighbors( 0, null, null, 1, 3, "Add#1: neighbors trap0" );1123 myQs.check_trapezoid_neighbors( 1, 0, null, 4, 6, "Add#1: neighbors trap1" );1124 myQs.check_trapezoid_neighbors( 2, 6, 3, null, 5, "Add#1: neighbors trap2" );1125 myQs.check_trapezoid_neighbors( 3, null, 0, null, 2, "Add#1: neighbors trap3" );1126 myQs.check_trapezoid_neighbors( 4, 1, null, 5, null, "Add#1: neighbors trap4" );1127 myQs.check_trapezoid_neighbors( 5, 4, 2, null, null, "Add#1: neighbors trap5" );1128 myQs.check_trapezoid_neighbors( 6, null, 1, 2, null, "Add#1: neighbors trap6" );1129 //1130 ok( ( myQsRoot.right.trap == myQs.getTrapByIdx(0) ), "Add#1: trap0 == root.right" );1131 ok( ( myQsRoot.left.right.right.trap == myQs.getTrapByIdx(3) ), "Add#1: trap3 == root.left.right.right" );1132 ok( ( myQsRoot.left.right.left.right.trap == myQs.getTrapByIdx(1) ), "Add#1: trap1 == root.left.right.left.right" );1133 ok( ( myQsRoot.left.right.left.left.right.trap == myQs.getTrapByIdx(6) ), "Add#1: trap6 == root.left.right.left.left.right" );1134 ok( ( myQsRoot.left.right.left.left.left.trap == myQs.getTrapByIdx(4) ), "Add#1: trap4 == root.left.right.left.left.left" );1135 ok( ( myQsRoot.left.left.right.right.trap == myQs.getTrapByIdx(2) ), "Add#1: trap2 == root.left.left.right.right" );1136 ok( ( myQsRoot.left.left.right.left.trap == myQs.getTrapByIdx(4) ), "Add#1: trap4 == root.left.left.right.left" );1137 ok( ( myQsRoot.left.left.left.trap == myQs.getTrapByIdx(5) ), "Add#1: trap5 == root.left.left.left" );1138 //1139// showDataStructure( myQsRoot );1140// drawTrapezoids( myQsRoot );1141 }1142 /* 01143 * -----*------------------------- y=45 qsR1144 * \ 61145 * \------------*---------- y=40 myQsRoot1146 * 4 \ 1 qsLR 31147 * \--------*------------ y=20 qsL1148 * qsLLR 21149 * -----------*------------------- y=10 qsLL1150 * 51151 */1152 function test_add_segment_basic_2() {1153 var base_segment = { vFrom: { x: 20, y: 20 }, vTo: { x: 30, y: 40 }, upward: true }1154 // start in tr0, end in tr21155 var other_segment = { vFrom: { x: 10, y: 45 }, vTo: { x: 15, y: 10 }, upward: false }1156 // segment chain1157 base_segment.snext = other_segment.sprev = { vFrom: base_segment.vTo, vTo: other_segment.vFrom, upward: true,1158 sprev: base_segment, snext: other_segment };1159 base_segment.sprev = other_segment.snext = { vFrom: other_segment.vTo, vTo: base_segment.vFrom, upward: false,1160 sprev: other_segment, snext: base_segment };1161 //1162 var myQs = new PNLTRI.QueryStructure();1163 var myQsRoot = myQs.setup_segments( base_segment );1164 ok( base_segment.is_inserted, "Add#2: Base Segment inserted" );1165 // precheck of correct Trapezoids1166 var qs_tr0 = myQs.getTrapByIdx(0).sink;1167 var qs_tr2 = myQs.getTrapByIdx(2).sink;1168 myQs.segNodes( other_segment );1169 ok( ( other_segment.rootFrom == qs_tr0 ), "Add#2: Seg.vFrom -> qs_tr0" );1170 ok( ( other_segment.rootTo == qs_tr2 ), "Add#2: Seg.vTo -> qs_tr2" );1171 //1172// showDataStructure( myQsRoot );1173// drawTrapezoids( myQsRoot );1174 //1175 // Main Test1176 //1177 myQs.add_segment( other_segment );1178 ok( other_segment.is_inserted, "Add#2: 2.Segment inserted" );1179 equal( myQs.nbTrapezoids(), 7, "Add#2: Number of Trapezoids in Array (7)" );1180 //1181 myQs.check_trapezoid_neighbors( 0, null, null, 4, 6, "Add#2: neighbors trap0" );1182 myQs.check_trapezoid_neighbors( 1, 6, null, 2, null, "Add#2: neighbors trap1" );1183 myQs.check_trapezoid_neighbors( 2, 1, 3, null, 5, "Add#2: neighbors trap2" );1184 myQs.check_trapezoid_neighbors( 3, null, 6, null, 2, "Add#2: neighbors trap3" );1185 myQs.check_trapezoid_neighbors( 4, 0, null, 5, null, "Add#2: neighbors trap4" );1186 myQs.check_trapezoid_neighbors( 5, 4, 2, null, null, "Add#2: neighbors trap5" );1187 myQs.check_trapezoid_neighbors( 6, null, 0, 1, 3, "Add#2: neighbors trap6" );1188 //1189 ok( ( myQsRoot.right.right.trap == myQs.getTrapByIdx(0) ), "Add#2: trap0 == root.right.right" );1190 ok( ( myQsRoot.right.left.left.trap == myQs.getTrapByIdx(4) ), "Add#2: trap4 == root.right.left.left" );1191 ok( ( myQsRoot.right.left.right.trap == myQs.getTrapByIdx(6) ), "Add#2: trap6 == root.right.left.right" );1192 ok( ( myQsRoot.left.right.right.trap == myQs.getTrapByIdx(3) ), "Add#2: trap3 == root.left.right.right" );1193 ok( ( myQsRoot.left.right.left.right.trap == myQs.getTrapByIdx(1) ), "Add#2: trap1 == root.left.right.left.right" );1194 ok( ( myQsRoot.left.right.left.left.trap == myQs.getTrapByIdx(4) ), "Add#2: trap4 == root.left.right.left.left" );1195 ok( ( myQsRoot.left.left.right.right.trap == myQs.getTrapByIdx(2) ), "Add#2: trap2 == root.left.left.right.right" );1196 ok( ( myQsRoot.left.left.right.left.trap == myQs.getTrapByIdx(4) ), "Add#2: trap4 == root.left.left.right.left" );1197 ok( ( myQsRoot.left.left.left.trap == myQs.getTrapByIdx(5) ), "Add#2: trap5 == root.left.left.left" );1198 //1199// showDataStructure( myQsRoot );1200// drawTrapezoids( myQsRoot );1201 }1202 /* 01203 * ----------*-------------------- y=40 myQsRoot1204 * / 31205 * /-----------*---------- y=35 qsLRR1206 * 1 qsLR 4 qsLRRLR 61207 * /-----------*------------ y=25 qsLRRL1208 * / 51209 * ----*-------------------------- y=20 qsL1210 * 21211 */1212 function test_add_segment_basic_3() {1213 var base_segment = { vFrom: { x: 30, y: 40 }, vTo: { x: 20, y: 20 }, upward: false }1214 // inside of tr31215 var other_segment = { vFrom: { x: 25, y: 25 }, vTo: { x: 35, y: 35 }, upward: true }1216 // segment chain1217 base_segment.snext = other_segment.sprev = { vFrom: base_segment.vTo, vTo: other_segment.vFrom, upward: false,1218 sprev: base_segment, snext: other_segment };1219 base_segment.sprev = other_segment.snext = { vFrom: other_segment.vTo, vTo: base_segment.vFrom, upward: false,1220 sprev: other_segment, snext: base_segment };1221 //1222 var myQs = new PNLTRI.QueryStructure();1223 var myQsRoot = myQs.setup_segments( base_segment );1224 ok( base_segment.is_inserted, "Add#3: Base Segment inserted" );1225 // precheck of correct Trapezoids1226 var qs_tr3 = myQs.getTrapByIdx(3).sink;1227 myQs.segNodes( other_segment );1228 ok( ( other_segment.rootFrom == qs_tr3 ), "Add#3: Seg.vFrom -> qs_tr3" );1229 ok( ( other_segment.rootTo == qs_tr3 ), "Add#3: Seg.vTo -> qs_tr3" );1230 //1231// showDataStructure( myQsRoot );1232// drawTrapezoids( myQsRoot );1233 //1234 // Main Test1235 //1236 myQs.add_segment( other_segment );1237 ok( other_segment.is_inserted, "Add#3: 2.Segment inserted" );1238 equal( myQs.nbTrapezoids(), 7, "Add#3: Number of Trapezoids in Array (7)" );1239 //1240 myQs.check_trapezoid_neighbors( 0, null, null, 1, 3, "Add#3: neighbors trap0" );1241 myQs.check_trapezoid_neighbors( 1, 0, null, 2, null, "Add#3: neighbors trap1" );1242 myQs.check_trapezoid_neighbors( 2, 1, 5, null, null, "Add#3: neighbors trap2" );1243 myQs.check_trapezoid_neighbors( 3, null, 0, 4, 6, "Add#3: neighbors trap3" );1244 myQs.check_trapezoid_neighbors( 4, 3, null, 5, null, "Add#3: neighbors trap4" );1245 myQs.check_trapezoid_neighbors( 5, 4, 6, null, 2, "Add#3: neighbors trap5" );1246 myQs.check_trapezoid_neighbors( 6, null, 3, null, 5, "Add#3: neighbors trap6" );1247 //1248 ok( ( myQsRoot.right.trap == myQs.getTrapByIdx(0) ), "Add#3: trap0 == root.right" );1249 ok( ( myQsRoot.left.right.right.right.trap == myQs.getTrapByIdx(3) ), "Add#3: trap3 == root.left.right.right.right" );1250 ok( ( myQsRoot.left.right.right.left.right.right.trap == myQs.getTrapByIdx(6) ), "Add#3: trap6 == root.left.right.right.left.right.right" );1251 ok( ( myQsRoot.left.right.right.left.right.left.trap == myQs.getTrapByIdx(4) ), "Add#3: trap4 == root.left.right.right.left.right.left" );1252 ok( ( myQsRoot.left.right.right.left.left.trap == myQs.getTrapByIdx(5) ), "Add#3: trap5 == root.left.right.right.left.left" );1253 ok( ( myQsRoot.left.right.left.trap == myQs.getTrapByIdx(1) ), "Add#3: trap1 == root.left.right.left" );1254 ok( ( myQsRoot.left.left.trap == myQs.getTrapByIdx(2) ), "Add#3: trap2 == root.left.left" );1255 //1256// showDataStructure( myQsRoot );1257// drawTrapezoids( myQsRoot );1258 }1259 /* 01260 * ----------*-------------------- y=40 myQsRoot1261 * 1 qsLR 31262 * --------*---------------------- y=20 qsL1263 * 21264 * ------*------------------------ y=15 qsLL1265 * 4 qsLLLR 61266 * --------*---------------------- y= 5 qsLLL1267 * 51268 */1269 function test_add_segment_basic_4() {1270 var base_segment = { vFrom: { x: 30, y: 40 }, vTo: { x: 20, y: 20 }, upward: false }1271 // inside of tr21272 var other_segment = { vFrom: { x: 5, y: 15 }, vTo: { x: 35, y: 5 }, upward: false }1273 // segment chain1274 base_segment.snext = other_segment.sprev = { vFrom: base_segment.vTo, vTo: other_segment.vFrom, upward: false,1275 sprev: base_segment, snext: other_segment };1276 base_segment.sprev = other_segment.snext = { vFrom: other_segment.vTo, vTo: base_segment.vFrom, upward: true,1277 sprev: other_segment, snext: base_segment };1278 //1279 var myQs = new PNLTRI.QueryStructure();1280 var myQsRoot = myQs.setup_segments( base_segment );1281 ok( base_segment.is_inserted, "Add#4: Base Segment inserted" );1282 // precheck of correct Trapezoids1283 var qs_tr2 = myQs.getTrapByIdx(2).sink;1284 myQs.segNodes( other_segment );1285 ok( ( other_segment.rootFrom == qs_tr2 ), "Add#4: Seg.vFrom -> qs_tr2" );1286 ok( ( other_segment.rootTo == qs_tr2 ), "Add#4: Seg.vTo -> qs_tr2" );1287 //1288// showDataStructure( myQsRoot );1289// drawTrapezoids( myQsRoot );1290 //1291 // Main Test1292 //1293 myQs.add_segment( other_segment );1294 ok( other_segment.is_inserted, "Add#4: 2.Segment inserted" );1295 equal( myQs.nbTrapezoids(), 7, "Add#4: Number of Trapezoids in Array (7)" );1296 //1297 myQs.check_trapezoid_neighbors( 0, null, null, 1, 3, "Add#4: neighbors trap0" );1298 myQs.check_trapezoid_neighbors( 1, 0, null, 2, null, "Add#4: neighbors trap1" );1299 myQs.check_trapezoid_neighbors( 2, 1, 3, 4, 6, "Add#4: neighbors trap2" );1300 myQs.check_trapezoid_neighbors( 3, null, 0, null, 2, "Add#4: neighbors trap3" );1301 myQs.check_trapezoid_neighbors( 4, 2, null, 5, null, "Add#4: neighbors trap4" );1302 myQs.check_trapezoid_neighbors( 5, 4, 6, null, null, "Add#4: neighbors trap5" );1303 myQs.check_trapezoid_neighbors( 6, null, 2, null, 5, "Add#4: neighbors trap6" );1304 //1305 ok( ( myQsRoot.right.trap == myQs.getTrapByIdx(0) ), "Add#4: trap0 == root.right" );1306 ok( ( myQsRoot.left.right.right.trap == myQs.getTrapByIdx(3) ), "Add#4: trap3 == root.left.right.right" );1307 ok( ( myQsRoot.left.right.left.trap == myQs.getTrapByIdx(1) ), "Add#4: trap1 == root.left.right.left" );1308 ok( ( myQsRoot.left.left.right.trap == myQs.getTrapByIdx(2) ), "Add#4: trap2 == root.left.left.right" );1309 ok( ( myQsRoot.left.left.left.right.right.trap == myQs.getTrapByIdx(6) ), "Add#4: trap6 == root.left.left.left.right.right" );1310 ok( ( myQsRoot.left.left.left.right.left.trap == myQs.getTrapByIdx(4) ), "Add#4: trap4 == root.left.left.left.right.left" );1311 ok( ( myQsRoot.left.left.left.left.trap == myQs.getTrapByIdx(5) ), "Add#4: trap5 == root.left.left.left.left" );1312 //1313// showDataStructure( myQsRoot );1314// drawTrapezoids( myQsRoot );1315 }1316 //1317 // Cases of segments touching other endpoints1318 // A segment endpoint is already inserted, now another segment,1319 // which includes the endpoint as well shall be added on the correct side1320 // These cases are handled in two_trap_below()1321 // This is the opposite case to "test_ptNode_touching"1322 //1323 // TODO: test all mirrored cases !!!1324 // if going back co-linear direction1325 // should be checked with the preceding segment1326 // ATTENTION: this needs to be looped since the1327 // preceeding segment can also be co-linear ...1328 /* 01329 * -----------*----------- y=401330 * / |1331 * --------*--| y=301332 * \ |1333 * ----------*| y=251334 * / |1335 * --------*--| y=151336 * \ |1337 * -----------*----------- y=101338 *1339 */1340 function test_add_segment_touching_1() {1341 // Test A1342 var testPolygon = [1343 { x: 25, y: 25 }, // touch point1344 { x: 15, y: 15 }, { x: 20, y: 10 }, { x: 30, y: 40 }, // touch line (right of point)1345 { x: 10, y: 30 },1346 ];1347 var myPolygonData = new PNLTRI.PolygonData( [ testPolygon ] );1348 var segListArray = myPolygonData.getSegments();1349 var myQs = new PNLTRI.QueryStructure( myPolygonData );1350 var myQsRoot = myQs.getRoot();1351 myQs.add_segment_consistently( segListArray[0], 'Touch#1 A #1' );1352 myQs.add_segment_consistently( segListArray[2], 'Touch#1 A #2' );1353 myQs.check_trapezoid_neighbors( 0, null, null, 4, 6, "Touch#1 A: neighbors trap0" );1354 myQs.check_trapezoid_neighbors( 1, 4, null, 2, null, "Touch#1 A: neighbors trap1" );1355 myQs.check_trapezoid_neighbors( 2, 1, 3, 5, null, "Touch#1 A: neighbors trap2" );1356 myQs.check_trapezoid_neighbors( 3, null, 4, null, 2, "Touch#1 A: neighbors trap3" );1357 myQs.check_trapezoid_neighbors( 4, 0, null, 1, 3, "Touch#1 A: neighbors trap4" );1358 myQs.check_trapezoid_neighbors( 5, 2, 6, null, null, "Touch#1 A: neighbors trap5" );1359 myQs.check_trapezoid_neighbors( 6, null, 0, null, 5, "Touch#1 A: neighbors trap6" );1360 //1361// showDataStructure( myQsRoot );1362// drawTrapezoids( myQsRoot, false );1363 // Test B1364 var testPolygon = [1365 { x: 25, y: 25 }, // touch point1366 { x: 40, y: 15 }, { x: 20, y: 10 }, { x: 30, y: 40 }, // touch line (left of point)1367 { x: 35, y: 30 },1368 ];1369 var myPolygonData = new PNLTRI.PolygonData( [ testPolygon ] );1370 var segListArray = myPolygonData.getSegments();1371 var myQs = new PNLTRI.QueryStructure( myPolygonData );1372 var myQsRoot = myQs.getRoot();1373 myQs.add_segment_consistently( segListArray[0], 'Touch#1 B #1' );1374 myQs.add_segment_consistently( segListArray[2], 'Touch#1 B #2' );1375 myQs.check_trapezoid_neighbors( 0, null, null, 4, 6, "Touch#1 B: neighbors trap0" );1376 myQs.check_trapezoid_neighbors( 1, 6, null, 2, null, "Touch#1 B: neighbors trap1" );1377 myQs.check_trapezoid_neighbors( 2, 1, 3, null, 5, "Touch#1 B: neighbors trap2" );1378 myQs.check_trapezoid_neighbors( 3, null, 6, null, 2, "Touch#1 B: neighbors trap3" );1379 myQs.check_trapezoid_neighbors( 4, 0, null, 5, null, "Touch#1 B: neighbors trap4" );1380 myQs.check_trapezoid_neighbors( 5, 4, 2, null, null, "Touch#1 B: neighbors trap5" );1381 myQs.check_trapezoid_neighbors( 6, null, 0, 1, 3, "Touch#1 B: neighbors trap6" );1382 //1383// showDataStructure( myQsRoot );1384// drawTrapezoids( myQsRoot, false );1385 }1386 //1387 // Complete Polygons1388 //1389 /* 01390 * -----------*----------- y=40 myQsRoot1391 * /|1392 * qsLR |1393 * 1 /3 qsLRR1394 * -------*---| 6 y=20 qsL1395 * 2 \5 qsLLRR1396 * qsLLR |1397 * \|1398 * -----------*----------- y=10 qsLL1399 * 41400 */1401 function test_add_segment_polygon_1() {1402 var myPolygonData = new PNLTRI.PolygonData( [ [1403 { x: 30, y: 40 }, { x: 20, y: 20 }, { x: 25, y:10 },1404 ] ] );1405 var segListArray = myPolygonData.getSegments();1406 var myQs = new PNLTRI.QueryStructure( myPolygonData );1407 var myQsRoot = myQs.getRoot();1408 myQs.add_segment_consistently( segListArray[0], 'Poly#1 #1' );1409 myQs.add_segment_consistently( segListArray[1], 'Poly#1 #2' );1410 myQs.add_segment_consistently( segListArray[2], 'Poly#1 #3' );1411 equal( myQs.nbTrapezoids(), 7, "Poly#1: Number of Trapezoids" );1412 myQs.check_trapezoid_neighbors( 0, null, null, 1, 6, "Poly#1: neighbors trap0" );1413 myQs.check_trapezoid_neighbors( 1, 0, null, 2, null, "Poly#1: neighbors trap1" );1414 myQs.check_trapezoid_neighbors( 2, 1, null, 4, null, "Poly#1: neighbors trap2" );1415 myQs.check_trapezoid_neighbors( 3, null, null, null, 5, "Poly#1: neighbors trap3" );1416 myQs.check_trapezoid_neighbors( 4, 2, 6, null, null, "Poly#1: neighbors trap4" );1417 myQs.check_trapezoid_neighbors( 5, null, 3, null, null, "Poly#1: neighbors trap5" );1418 myQs.check_trapezoid_neighbors( 6, null, 0, null, 4, "Poly#1: neighbors trap6" );1419 ok( ( myQsRoot.right.trap == myQs.getTrapByIdx(0) ), "Poly#1: trap0 == root.right" );1420 ok( myQsRoot.left.yval, "Poly#1: root.left: Y-Node" );1421 ok( myQsRoot.left.right.seg, "Poly#1: root.left.right: X-Node" );1422 ok( myQsRoot.left.right.right.seg, "Poly#1: root.left.right.right: X-Node" );1423 ok( ( myQsRoot.left.right.right.right.trap == myQs.getTrapByIdx(6) ), "Poly#1: trap6 == root.left.right.right.right" );1424 ok( ( myQsRoot.left.right.right.left.trap == myQs.getTrapByIdx(3) ), "Poly#1: trap3 == root.left.right.right.left" );1425 ok( ( myQsRoot.left.right.left.trap == myQs.getTrapByIdx(1) ), "Poly#1: trap1 == root.left.right.left" );1426 ok( myQsRoot.left.left.yval, "Poly#1: root.left.left: Y-Node" );1427 ok( myQsRoot.left.left.right.seg, "Poly#1: root.left.left.right: X-Node" );1428 ok( myQsRoot.left.left.right.right.seg, "Poly#1: root.left.left.right.right: X-Node" );1429 ok( ( myQsRoot.left.left.right.right.right.trap == myQs.getTrapByIdx(6) ), "Poly#1: trap6 == root.left.left.right.right.right" );1430 ok( ( myQsRoot.left.left.right.right.left.trap == myQs.getTrapByIdx(5) ), "Poly#1: trap5 == root.left.left.right.right.left" );1431 ok( ( myQsRoot.left.left.right.left.trap == myQs.getTrapByIdx(2) ), "Poly#1: trap2 == root.left.left.right.left" );1432 ok( ( myQsRoot.left.left.left.trap == myQs.getTrapByIdx(4) ), "Poly#1: trap4 == root.left.left.left" );1433// showDataStructure( myQsRoot );1434// drawTrapezoids( myQsRoot );1435 }1436 function test_add_segment_polygon_2ccw() {1437 // CCW-Ordering (Shapes)1438 var myPolygonData = new PNLTRI.PolygonData( [ [1439 { x: 30, y: 40 }, { x: 20, y: 20 }, { x: 10, y: 15 }, { x: 60, y: 22 }1440 ] ] );1441 var segListArray = myPolygonData.getSegments();1442 var myQs = new PNLTRI.QueryStructure( myPolygonData );1443 //1444 // Main Test1445 //1446 myQs.add_segment_consistently( segListArray[0], 'Poly#2ccw #1' );1447 myQs.add_segment_consistently( segListArray[1], 'Poly#2ccw #2' );1448 myQs.add_segment_consistently( segListArray[3], 'Poly#2ccw #3' );1449 myQs.add_segment_consistently( segListArray[2], 'Poly#2ccw #4' );1450 equal( myQs.nbTrapezoids(), 9, "Poly#2ccw: Number of Trapezoids" );1451 myQs.check_trapezoid_neighbors( 0, null, null, 1, 7, "Poly#2ccw: neighbors trap0" );1452 myQs.check_trapezoid_neighbors( 1, 0, null, 2, null, "Poly#2ccw: neighbors trap1" );1453 myQs.check_trapezoid_neighbors( 2, 1, null, 4, null, "Poly#2ccw: neighbors trap2" );1454 myQs.check_trapezoid_neighbors( 3, null, null, 6, null, "Poly#2ccw: neighbors trap3" );1455 myQs.check_trapezoid_neighbors( 4, 2, 8, null, null, "Poly#2ccw: neighbors trap4" );1456 myQs.check_trapezoid_neighbors( 5, null, 6, null, null, "Poly#2ccw: neighbors trap5" );1457 myQs.check_trapezoid_neighbors( 6, 3, null, null, 5, "Poly#2ccw: neighbors trap6" );1458 myQs.check_trapezoid_neighbors( 7, null, 0, null, 8, "Poly#2ccw: neighbors trap7" );1459 myQs.check_trapezoid_neighbors( 8, null, 7, null, 4, "Poly#2ccw: neighbors trap8" );1460// var myQsRoot = myQs.getRoot();1461// showDataStructure( myQsRoot );1462// drawTrapezoids( myQsRoot );1463 }1464 function test_add_segment_polygon_2cw() {1465 // CW-Ordering (Holes)1466 var myPolygonData = new PNLTRI.PolygonData( [ [1467 { x: 10, y: 15 }, { x: 20, y: 20 }, { x: 30, y: 40 }, { x: 60, y: 22 }1468 // segment_left, segment_top, segment_right, segment_bottom1469 ] ] );1470 var segListArray = myPolygonData.getSegments();1471 var myQs = new PNLTRI.QueryStructure( myPolygonData );1472 //1473 // Main Test1474 //1475 myQs.add_segment_consistently( segListArray[0], 'Poly#2cw #1' );1476 myQs.add_segment_consistently( segListArray[3], 'Poly#2cw #2' );1477 myQs.add_segment_consistently( segListArray[2], 'Poly#2cw #3' );1478 myQs.add_segment_consistently( segListArray[1], 'Poly#2cw #4' );1479 equal( myQs.nbTrapezoids(), 9, "Poly#2cw: Number of Trapezoids" );1480 myQs.check_trapezoid_neighbors( 0, null, null, 6, 7, "Poly#2cw: neighbors trap0" );1481 myQs.check_trapezoid_neighbors( 1, 6, null, 2, null, "Poly#2cw: neighbors trap1" );1482 myQs.check_trapezoid_neighbors( 2, 1, 5, null, null, "Poly#2cw: neighbors trap2" );1483 myQs.check_trapezoid_neighbors( 3, null, 4, null, null, "Poly#2cw: neighbors trap3" );1484 myQs.check_trapezoid_neighbors( 4, 8, null, null, 3, "Poly#2cw: neighbors trap4" );1485 myQs.check_trapezoid_neighbors( 5, null, 7, null, 2, "Poly#2cw: neighbors trap5" );1486 myQs.check_trapezoid_neighbors( 6, 0, null, 1, null, "Poly#2cw: neighbors trap6" );1487 myQs.check_trapezoid_neighbors( 7, null, 0, null, 5, "Poly#2cw: neighbors trap7" );1488 myQs.check_trapezoid_neighbors( 8, null, null, 4, null, "Poly#2cw: neighbors trap8" );1489// var myQsRoot = myQs.getRoot();1490// showDataStructure( myQsRoot );1491// drawTrapezoids( myQsRoot );1492 }1493 function test_add_segment_polygon_3nonmono() {1494 // CCW-Ordering (Shapes)1495 var myPolygonData = new PNLTRI.PolygonData( [ [1496 { x: 28, y: 33 }, { x: 20, y: 20 }, { x: 10, y: 10 }, { x: 60, y: 22 }, { x: 35, y: 40 }, { x: 26, y: 36 },1497 { x: 30, y: 45 }, { x: 15, y: 30 },1498 // segment_lefttop, segment_leftbot, segment_bottom, segment_right, segment_indebot, segment_indetop,1499 // segment_nosetop, segment_nosebot1500 ] ] );1501 var segListArray = myPolygonData.getSegments();1502 var myQs = new PNLTRI.QueryStructure( myPolygonData );1503 //1504 // Main Test1505 //1506 myQs.add_segment_consistently( segListArray[0], 'Poly#3nonmono #1' );1507 myQs.add_segment_consistently( segListArray[2], 'Poly#3nonmono #2' );1508 myQs.add_segment_consistently( segListArray[7], 'Poly#3nonmono #3' );1509 myQs.add_segment_consistently( segListArray[4], 'Poly#3nonmono #4' );1510 myQs.add_segment_consistently( segListArray[3], 'Poly#3nonmono #5' );1511 myQs.add_segment_consistently( segListArray[6], 'Poly#3nonmono #6' );1512 myQs.add_segment_consistently( segListArray[1], 'Poly#3nonmono #7' );1513 myQs.add_segment_consistently( segListArray[5], 'Poly#3nonmono #8' );1514 equal( myQs.nbTrapezoids(), 17, "Poly#3nonmono: Number of Trapezoids" );1515 myQs.check_trapezoid_neighbors( 0, null, null, 13, 16, "Poly#3nonmono: neighbors trap0" );1516 myQs.check_trapezoid_neighbors( 1, 10, null, null, null, "Poly#3nonmono: neighbors trap1" );1517 myQs.check_trapezoid_neighbors( 2, 7, null, 5, null, "Poly#3nonmono: neighbors trap2" );1518 myQs.check_trapezoid_neighbors( 3, null, 10, 4, null, "Poly#3nonmono: neighbors trap3" );1519 myQs.check_trapezoid_neighbors( 4, 3, null, null, 15, "Poly#3nonmono: neighbors trap4" );1520 myQs.check_trapezoid_neighbors( 5, 2, 6, null, null, "Poly#3nonmono: neighbors trap5" );1521 myQs.check_trapezoid_neighbors( 6, null, 12, null, 5, "Poly#3nonmono: neighbors trap6" );1522 myQs.check_trapezoid_neighbors( 7, 13, 8, 2, null, "Poly#3nonmono: neighbors trap7" );1523 myQs.check_trapezoid_neighbors( 8, null, null, null, 7, "Poly#3nonmono: neighbors trap8" );1524 myQs.check_trapezoid_neighbors( 9, 16, null, null, null, "Poly#3nonmono: neighbors trap9" );1525 myQs.check_trapezoid_neighbors( 10, 14, 11, 1, 3, "Poly#3nonmono: neighbors trap10" );1526 myQs.check_trapezoid_neighbors( 11, null, null, null, 10, "Poly#3nonmono: neighbors trap11" );1527 myQs.check_trapezoid_neighbors( 12, null, 16, null, 6, "Poly#3nonmono: neighbors trap12" );1528 myQs.check_trapezoid_neighbors( 13, 0, null, 7, null, "Poly#3nonmono: neighbors trap13" );1529 myQs.check_trapezoid_neighbors( 14, null, null, 10, null, "Poly#3nonmono: neighbors trap14" );1530 myQs.check_trapezoid_neighbors( 15, null, 4, null, null, "Poly#3nonmono: neighbors trap15" );1531 myQs.check_trapezoid_neighbors( 16, null, 0, 9, 12, "Poly#3nonmono: neighbors trap16" );1532// var myQsRoot = myQs.getRoot();1533// showDataStructure( myQsRoot );1534// drawTrapezoids( myQsRoot );1535 }1536 //1537 // Complex special cases, extracted from ERRORs1538 // during trapezoidation of real world examples1539 //1540 function test_add_segment_special_1() {1541 var myPolygonData = new PNLTRI.PolygonData( [ [1542 { x:1, y:1 }, { x:4, y:3 }, { x:6, y:2 }, { x:7, y:5 },1543 { x:5, y:6 }, { x:2, y:4 }, { x:1, y:7 },1544 ] ] );1545 var segListArray = myPolygonData.getSegments();1546// showDataStructure( myPolygonData.getVertices(), [ 'sprev', 'snext', 'vertTo', 'segOut' ] );1547// showDataStructure( myPolygonData.getSegments(), [ 'sprev', 'snext', 'mprev', 'mnext' ] );1548 var myQs = new PNLTRI.QueryStructure( myPolygonData );1549 myQs.add_segment_consistently( segListArray[0], 'Spec_1 #1' );1550 myQs.add_segment_consistently( segListArray[2], 'Spec_1 #2' );1551 myQs.add_segment_consistently( segListArray[4], 'Spec_1 #3' );1552 // complex case concerning "only_one_trap_below"1553 myQs.add_segment_consistently( segListArray[6], 'Spec_1 Main' );1554 equal( myQs.nbTrapezoids(), 12, "Spec_1: Number of Trapezoids" );1555 myQs.check_trapezoid_neighbors( 0, null, null, 10, 11, "Spec_1: neighbors trap0" );1556 myQs.check_trapezoid_neighbors( 1, 8, null, null, null, "Spec_1: neighbors trap1" );1557 myQs.check_trapezoid_neighbors( 2, 10, 5, null, null, "Spec_1: neighbors trap2" );1558 myQs.check_trapezoid_neighbors( 3, null, 8, 5, null, "Spec_1: neighbors trap3" );1559 myQs.check_trapezoid_neighbors( 4, 9, null, null, 8, "Spec_1: neighbors trap4" );1560 myQs.check_trapezoid_neighbors( 5, 3, 6, null, 2, "Spec_1: neighbors trap5" );1561 myQs.check_trapezoid_neighbors( 6, null, 9, null, 5, "Spec_1: neighbors trap6" );1562 myQs.check_trapezoid_neighbors( 7, 11, null, 8, null, "Spec_1: neighbors trap7" );1563 myQs.check_trapezoid_neighbors( 8, 7, 4, 1, 3, "Spec_1: neighbors trap8" );1564 myQs.check_trapezoid_neighbors( 9, null, 11, 4, 6, "Spec_1: neighbors trap9" );1565 myQs.check_trapezoid_neighbors( 10, 0, null, 2, null, "Spec_1: neighbors trap10" );1566 myQs.check_trapezoid_neighbors( 11, null, 0, 7, 9, "Spec_1: neighbors trap11" );1567// var myQsRoot = myQs.getRoot();1568// showDataStructure( myQsRoot );1569// drawTrapezoids( myQsRoot, false, 5 );1570 }1571 function test_add_segment_special_2() {1572 var myPolygonData = new PNLTRI.PolygonData( [ [1573 { x:1, y:1 }, { x:5, y:5.1 }, { x:6, y:8 }, { x:4, y:6 },1574 { x:2, y:3 }, { x:1, y:5 },1575 ] ] );1576 var segListArray = myPolygonData.getSegments();1577// showDataStructure( myPolygonData.getVertices(), [ 'sprev', 'snext', 'vertTo', 'segOut' ] );1578// showDataStructure( myPolygonData.getSegments(), [ 'sprev', 'snext', 'mprev', 'mnext' ] );1579 //1580 var myQs = new PNLTRI.QueryStructure( myPolygonData );1581 //1582 myQs.add_segment_consistently( segListArray[0], 'Spec_2 #1' );1583 myQs.add_segment_consistently( segListArray[1], 'Spec_2 #2' );1584 myQs.add_segment_consistently( segListArray[5], 'Spec_2 #3' );1585 // complex case: extending first on the left then right1586 myQs.add_segment_consistently( segListArray[3], 'Spec_2 Main' );1587 //1588 myQs.add_segment_consistently( segListArray[2], 'Spec_2 #4' );1589 myQs.add_segment_consistently( segListArray[4], 'Spec_2 #5' );1590 equal( myQs.nbTrapezoids(), 13, "Spec_2: Number of Trapezoids" );1591 //1592// var myQsRoot = myQs.getRoot();1593// showDataStructure( myQsRoot );1594// drawTrapezoids( myQsRoot, false, 5 );1595 }1596 function test_add_segment_special_3() {1597 var myPolygonData = new PNLTRI.PolygonData( [ [1598 { x: 19.3395, y: 7.15 }, { x: 19.228, y: 7.150000000000001 },1599 { x: 5.03, y: 6.9715 }, { x: 5.17, y: 6.046 },1600 ] ] );1601 var segListArray = myPolygonData.getSegments();1602// showDataStructure( myPolygonData.getVertices(), [ 'sprev', 'snext', 'vertTo', 'segOut' ] );1603// showDataStructure( myPolygonData.getSegments(), [ 'sprev', 'snext', 'mprev', 'mnext' ] );1604 //1605 var myQs = new PNLTRI.QueryStructure( myPolygonData );1606 //1607 myQs.add_segment_consistently( segListArray[2], 'Spec_3 #1' );1608 // complex case: 3.Segment goes upwards and downwards => always use EPSILON1609 myQs.add_segment_consistently( segListArray[0], 'Spec_3 Main' );1610 equal( myQs.nbTrapezoids(), 7, "Spec_3: Number of Trapezoids" );1611 myQs.check_trapezoid_neighbors( 0, null, null, 4, 6, "Spec_3: neighbors trap0" );1612 myQs.check_trapezoid_neighbors( 1, 5, null, 2, null, "Spec_3: neighbors trap1" );1613 myQs.check_trapezoid_neighbors( 2, 1, 3, null, null, "Spec_3: neighbors trap2" );1614 myQs.check_trapezoid_neighbors( 3, null, 5, null, 2, "Spec_3: neighbors trap3" );1615 myQs.check_trapezoid_neighbors( 4, 0, null, 5, null, "Spec_3: neighbors trap4" );1616 myQs.check_trapezoid_neighbors( 5, 4, 6, 1, 3, "Spec_3: neighbors trap5" );1617 myQs.check_trapezoid_neighbors( 6, null, 0, null, 5, "Spec_3: neighbors trap6" );1618// var myQsRoot = myQs.getRoot();1619// showDataStructure( myQsRoot );1620// drawTrapezoids( myQsRoot, false, 2 );1621 }1622 function test_add_segment_special_4() { // TODO: replace with direct tests1623 var testPolygon = [ [1624 { x: 2, y: 1 },1625 { x: 1, y: 3 }, { x: 1, y: 2 }, { x: 1, y: 4 }, // goes back on same x-line1626 { x: 0, y: 0 },1627 ] ];1628// drawPolygonLayers( { "poly": testPolygon }, 10 );1629 //1630 // Test A1631 var myPolygonData = new PNLTRI.PolygonData( testPolygon );1632 var segListArray = myPolygonData.getSegments();1633// showDataStructure( myPolygonData.getVertices(), [ 'sprev', 'snext', 'vertTo', 'segOut' ] );1634// showDataStructure( myPolygonData.getSegments(), [ 'sprev', 'snext', 'mprev', 'mnext' ] );1635 var myQs = new PNLTRI.QueryStructure( myPolygonData );1636 var myQsRoot = myQs.getRoot();1637 myQs.add_segment_consistently( segListArray[0], 'Spec_4a #1' );1638 myQs.add_segment_consistently( segListArray[1], 'Spec_4a #2' );1639 myQs.check_trapezoid_neighbors( 0, null, null, 1, 3, "Spec_4a #2, trap0" );1640 myQs.check_trapezoid_neighbors( 1, 0, null, 4, null, "Spec_4a #2, trap1" );1641 myQs.check_trapezoid_neighbors( 2, 4, 3, null, null, "Spec_4a #2, trap2" );1642 myQs.check_trapezoid_neighbors( 3, null, 0, null, 2, "Spec_4a #2, trap3" );1643 myQs.check_trapezoid_neighbors( 4, 1, 5, 2, null, "Spec_4a #2, trap4" );1644 myQs.check_trapezoid_neighbors( 5, null, null, null, 4, "Spec_4a #2, trap5" );1645 // complex case: goes back on same x-line1646 myQs.add_segment_consistently( segListArray[2], 'Spec_4a Main' );1647 equal( myQs.nbTrapezoids(), 8, "Spec_4a: Number of Trapezoids" );1648// showDataStructure( myQsRoot );1649// drawTrapezoids( myQsRoot, false, 10 );1650 }1651 function test_add_segment_special_5() {1652 var myPolygonData = new PNLTRI.PolygonData( [ [1653 { x:43, y:31 }, { x:41, y:29 },1654 { x:42, y:40 }, { x:36, y:24 },1655 { x:34, y:16 }, { x:23, y:34 },1656 { x: 8, y:32 }, { x: 1, y:28 },1657 { x:14, y:38 }, { x:10, y: 6 },1658 { x:63, y:26 }, { x:58, y:18 },1659 ] ] );1660 var segListArray = myPolygonData.getSegments();1661// showDataStructure( myPolygonData.getVertices(), [ 'sprev', 'snext', 'vertTo', 'segOut' ] );1662// showDataStructure( myPolygonData.getSegments(), [ 'sprev', 'snext', 'mprev', 'mnext' ] );1663 //1664 var myQs = new PNLTRI.QueryStructure( myPolygonData );1665 var myQsRoot = myQs.getRoot();1666 //1667 myQs.add_segment_consistently( segListArray[ 0], 'Spec_5 #1' );1668 myQs.add_segment_consistently( segListArray[10], 'Spec_5 #2' );1669 myQs.add_segment_consistently( segListArray[ 6], 'Spec_5 #3' );1670 myQs.add_segment_consistently( segListArray[ 8], 'Spec_5 #4' );1671 myQs.add_segment_consistently( segListArray[ 2], 'Spec_5 #5' );1672 // endless loop, if in only_one_trap_below.1B_1UN_END inTrNext.uL and trNewLeft is not set1673 myQs.add_segment_consistently( segListArray[ 4], 'Spec_5 Main' );1674 //1675// showDataStructure( myQsRoot );1676// drawTrapezoids( myQsRoot, false, 1 );1677 }1678 function test_add_segment_special_6() {1679 var myPolygonData = new PNLTRI.PolygonData( [ [1680 { x:10, y:34 }, { x:36, y:12 }, { x:32, y:20 }, { x:28, y:24 },1681 { x:27, y:30 }, { x:38, y: 8 }, { x:40, y:32 },1682 ] ] );1683 var segListArray = myPolygonData.getSegments();1684// showDataStructure( myPolygonData.getVertices(), [ 'sprev', 'snext', 'vertTo', 'segOut' ] );1685// showDataStructure( myPolygonData.getSegments(), [ 'sprev', 'snext', 'mprev', 'mnext' ] );1686 //1687 var myQs = new PNLTRI.QueryStructure( myPolygonData );1688 var myQsRoot = myQs.getRoot();1689 myQs.add_segment_consistently( segListArray[4], 'Spec_6 #1' );1690 myQs.add_segment_consistently( segListArray[2], 'Spec_6 #2' );1691 // selects wrong trapezoid for upper point, if tmpPoint overrides inPtOther1692 myQs.add_segment_consistently( segListArray[1], 'Spec_6 Main' );1693 myQs.check_trapezoid_neighbors( 0, null, null, 1, 3, "Spec_6: neighbors trap0" );1694 myQs.check_trapezoid_neighbors( 1, 0, null, 4, 6, "Spec_6: neighbors trap1" );1695 myQs.check_trapezoid_neighbors( 2, 7, 3, null, null, "Spec_6: neighbors trap2" );1696 myQs.check_trapezoid_neighbors( 3, null, 0, null, 2, "Spec_6: neighbors trap3" );1697 myQs.check_trapezoid_neighbors( 4, 1, null, 5, null, "Spec_6: neighbors trap4" );1698 myQs.check_trapezoid_neighbors( 5, 4, null, 7, null, "Spec_6: neighbors trap5" );1699 myQs.check_trapezoid_neighbors( 6, null, 1, null, 8, "Spec_6: neighbors trap6" );1700 myQs.check_trapezoid_neighbors( 7, 5, 8, 2, null, "Spec_6: neighbors trap7" );1701 myQs.check_trapezoid_neighbors( 8, null, 6, null, 7, "Spec_6: neighbors trap8" );1702 //1703// showDataStructure( myQsRoot );1704// drawTrapezoids( myQsRoot, false, 1 );1705 }1706 function test_add_segment_special_7() {1707 // co-linear horizontal direction reversals1708 // reverse on high point1709 var myPolygonData = new PNLTRI.PolygonData( [ [1710 { x:15, y:20 }, { x:10, y:20 }, { x:30, y: 5 },1711 { x:35, y:40 }, { x: 5, y:20 },1712 ] ] );1713 //1714 var myQs = new PNLTRI.QueryStructure( myPolygonData );1715 var myQsRoot = myQs.getRoot();1716 var segListArray = myPolygonData.getSegments();1717 //1718 myQs.add_segment_consistently( segListArray[3], 'Spec_7a1 #1' );1719 myQs.add_segment_consistently( segListArray[4], 'Spec_7a1 #2' );1720 myQs.check_trapezoid_neighbors( 0, null, null, 1, 3, "Spec_7a1: neighbors trap0" );1721 myQs.check_trapezoid_neighbors( 1, 0, null, 2, null, "Spec_7a1: neighbors trap1" );1722 myQs.check_trapezoid_neighbors( 2, 1, 5, null, null, "Spec_7a1: neighbors trap2" );1723 myQs.check_trapezoid_neighbors( 3, null, 0, 4, 5, "Spec_7a1: neighbors trap3" );1724 myQs.check_trapezoid_neighbors( 4, 3, null, null, null, "Spec_7a1: neighbors trap4" );1725 myQs.check_trapezoid_neighbors( 5, null, 3, null, 2, "Spec_7a1: neighbors trap5" );1726 // horizontal co-linear segment: connected at qsNode.seg.vTo, inSeg: short & up1727 myQs.add_segment_consistently( segListArray[0], 'Spec_7a1 Main' );1728 //1729// showDataStructure( myQsRoot );1730// drawTrapezoids( myQsRoot, false, 1 );1731 // other sequence1732 myQs = new PNLTRI.QueryStructure( myPolygonData );1733 myQsRoot = myQs.getRoot();1734 segListArray = myPolygonData.getSegments();1735 //1736 myQs.add_segment_consistently( segListArray[0], 'Spec_7a2 #1' );1737 myQs.add_segment_consistently( segListArray[1], 'Spec_7a2 #2' );1738 // horizontal co-linear segment: connected at qsNode.seg.vFrom, inSegLong, qsSegDown1739 myQs.add_segment_consistently( segListArray[4], 'Spec_7a2 Main' );1740 //1741// showDataStructure( myQsRoot );1742// drawTrapezoids( myQsRoot, false, 1 );1743 // reverse on high point1744 // exchanged length of horizontal segments1745 myPolygonData = new PNLTRI.PolygonData( [ [1746 { x:15, y:20 }, { x: 5, y:20 }, { x:30, y: 5 },1747 { x:35, y:40 }, { x:10, y:20 },1748 ] ] );1749 //1750 myQs = new PNLTRI.QueryStructure( myPolygonData );1751 myQsRoot = myQs.getRoot();1752 segListArray = myPolygonData.getSegments();1753 //1754 myQs.add_segment_consistently( segListArray[3], 'Spec_7b1 #1' );1755 myQs.add_segment_consistently( segListArray[4], 'Spec_7b1 #2' );1756 // horizontal co-linear segment: connected at qsNode.seg.vTo, inSegLong, qsSegDown1757 myQs.add_segment_consistently( segListArray[0], 'Spec_7b1 Main' );1758 //1759// showDataStructure( myQsRoot );1760// drawTrapezoids( myQsRoot, false, 1 );1761 // other sequence1762 myQs = new PNLTRI.QueryStructure( myPolygonData );1763 myQsRoot = myQs.getRoot();1764 segListArray = myPolygonData.getSegments();1765 //1766 myQs.add_segment_consistently( segListArray[3], 'Spec_7b2 #1' );1767 myQs.add_segment_consistently( segListArray[0], 'Spec_7b2 #2' );1768 // horizontal co-linear segment: connected at qsNode.seg.vFrom, inSeg: short & down1769 myQs.add_segment_consistently( segListArray[4], 'Spec_7b2 Main' );1770 //1771// showDataStructure( myQsRoot );1772// drawTrapezoids( myQsRoot, false, 1 );1773 // reverse on low point1774 myPolygonData = new PNLTRI.PolygonData( [ [1775 { x:20, y:20 }, { x:35, y:20 }, { x:15, y:40 },1776 { x:10, y: 5 }, { x:40, y:20 },1777 ] ] );1778 //1779 myQs = new PNLTRI.QueryStructure( myPolygonData );1780 myQsRoot = myQs.getRoot();1781 segListArray = myPolygonData.getSegments();1782 //1783 myQs.add_segment_consistently( segListArray[3], 'Spec_7c1 #1' );1784 myQs.add_segment_consistently( segListArray[4], 'Spec_7c1 #2' );1785 // horizontal co-linear segment: connected at qsNode.seg.vTo, inSeg: short & down1786 myQs.add_segment_consistently( segListArray[0], 'Spec_7c1 Main' );1787 //1788// showDataStructure( myQsRoot );1789// drawTrapezoids( myQsRoot, false, 1 );1790 // other sequence1791 myQs = new PNLTRI.QueryStructure( myPolygonData );1792 myQsRoot = myQs.getRoot();1793 segListArray = myPolygonData.getSegments();1794 //1795 myQs.add_segment_consistently( segListArray[3], 'Spec_7c2 #1' );1796 myQs.add_segment_consistently( segListArray[0], 'Spec_7c2 #2' );1797 // horizontal co-linear segment: connected at qsNode.seg.vFrom, inSegLong, qsSegUp1798 myQs.add_segment_consistently( segListArray[4], 'Spec_7c2 Main' );1799 //1800// showDataStructure( myQsRoot );1801// drawTrapezoids( myQsRoot, false, 1 );1802 // reverse on low point1803 // exchanged length of horizontal segments1804 myPolygonData = new PNLTRI.PolygonData( [ [1805 { x:20, y:20 }, { x:40, y:20 }, { x:15, y:40 },1806 { x:10, y: 5 }, { x:35, y:20 },1807 ] ] );1808 //1809 myQs = new PNLTRI.QueryStructure( myPolygonData );1810 myQsRoot = myQs.getRoot();1811 segListArray = myPolygonData.getSegments();1812 //1813 myQs.add_segment_consistently( segListArray[3], 'Spec_7d1 #1' );1814 myQs.add_segment_consistently( segListArray[4], 'Spec_7d1 #2' );1815 // horizontal co-linear segment: connected at qsNode.seg.vTo, inSegLong, qsSegUp1816 myQs.add_segment_consistently( segListArray[0], 'Spec_7d1 Main' );1817 //1818// showDataStructure( myQsRoot );1819// drawTrapezoids( myQsRoot, false, 1 );1820 // other sequence1821 myQs = new PNLTRI.QueryStructure( myPolygonData );1822 myQsRoot = myQs.getRoot();1823 segListArray = myPolygonData.getSegments();1824 //1825 myQs.add_segment_consistently( segListArray[3], 'Spec_7d2 #1' );1826 myQs.add_segment_consistently( segListArray[0], 'Spec_7d2 #2' );1827 // horizontal co-linear segment: connected at qsNode.seg.vFrom, inSeg: short & up1828 myQs.add_segment_consistently( segListArray[4], 'Spec_7d2 Main' );1829 //1830// showDataStructure( myQsRoot );1831// drawTrapezoids( myQsRoot, false, 1 );1832 //1833 // both horizontal segments continue in same direction: up1834 myPolygonData = new PNLTRI.PolygonData( [ [1835 { x:15, y:20 }, { x:10, y:20 }, { x:30, y:35 }, { x: 5, y:20 },1836 ] ] );1837 //1838 myQs = new PNLTRI.QueryStructure( myPolygonData );1839 myQsRoot = myQs.getRoot();1840 segListArray = myPolygonData.getSegments();1841 //1842 myQs.add_segment_consistently( segListArray[2], 'Spec_7e1 #1' );1843 myQs.add_segment_consistently( segListArray[3], 'Spec_7e1 #2' );1844 // horizontal co-linear segment: connected at qsNode.seg.vTo, inSeg: short & up1845 myQs.add_segment_consistently( segListArray[0], 'Spec_7e1 Main' );1846 //1847// showDataStructure( myQsRoot );1848// drawTrapezoids( myQsRoot, false, 1 );1849 // other sequence1850 myQs = new PNLTRI.QueryStructure( myPolygonData );1851 myQsRoot = myQs.getRoot();1852 segListArray = myPolygonData.getSegments();1853 //1854 myQs.add_segment_consistently( segListArray[0], 'Spec_7e2 #1' );1855 myQs.add_segment_consistently( segListArray[1], 'Spec_7e2 #2' );1856 // horizontal co-linear segment: connected at qsNode.seg.vFrom, inSegLong, qsSegUp1857 myQs.add_segment_consistently( segListArray[3], 'Spec_7e2 Main' );1858 //1859// showDataStructure( myQsRoot );1860// drawTrapezoids( myQsRoot, false, 1 );1861 // both horizontal segments continue in same direction: up, CW1862 myPolygonData = new PNLTRI.PolygonData( [ [1863 { x:15, y:20 }, { x: 5, y:20 }, { x:30, y:35 }, { x:10, y:20 },1864 ] ] );1865 //1866 myQs = new PNLTRI.QueryStructure( myPolygonData );1867 myQsRoot = myQs.getRoot();1868 segListArray = myPolygonData.getSegments();1869 //1870 myQs.add_segment_consistently( segListArray[2], 'Spec_7e1cw #1' );1871 myQs.add_segment_consistently( segListArray[3], 'Spec_7e1cw #2' );1872 // horizontal co-linear segment: connected at qsNode.seg.vTo, inSegLong, qsSegDown1873 myQs.add_segment_consistently( segListArray[0], 'Spec_7e1cw Main' );1874 //1875// showDataStructure( myQsRoot );1876// drawTrapezoids( myQsRoot, false, 1 );1877 // other sequence1878 myQs = new PNLTRI.QueryStructure( myPolygonData );1879 myQsRoot = myQs.getRoot();1880 segListArray = myPolygonData.getSegments();1881 //1882 myQs.add_segment_consistently( segListArray[0], 'Spec_7e2cw #1' );1883 myQs.add_segment_consistently( segListArray[1], 'Spec_7e2cw #2' );1884 // horizontal co-linear segment: connected at qsNode.seg.vFrom, inSeg: short & down1885 myQs.add_segment_consistently( segListArray[3], 'Spec_7e2cw Main' );1886 //1887// showDataStructure( myQsRoot );1888// drawTrapezoids( myQsRoot, false, 1 );1889 // both horizontal segments continue in same direction: down1890 myPolygonData = new PNLTRI.PolygonData( [ [1891 { x:15, y:20 }, { x:10, y:20 }, { x:30, y: 5 }, { x: 5, y:20 },1892 ] ] );1893 //1894 myQs = new PNLTRI.QueryStructure( myPolygonData );1895 myQsRoot = myQs.getRoot();1896 segListArray = myPolygonData.getSegments();1897 //1898 myQs.add_segment_consistently( segListArray[2], 'Spec_7f1 #1' );1899 myQs.add_segment_consistently( segListArray[3], 'Spec_7f1 #2' );1900 // horizontal co-linear segment: connected at qsNode.seg.vTo, inSeg: short & up1901 myQs.add_segment_consistently( segListArray[0], 'Spec_7f1 Main' );1902 //1903// showDataStructure( myQsRoot );1904// drawTrapezoids( myQsRoot, false, 1 );1905 // other sequence1906 myQs = new PNLTRI.QueryStructure( myPolygonData );1907 myQsRoot = myQs.getRoot();1908 segListArray = myPolygonData.getSegments();1909 //1910 myQs.add_segment_consistently( segListArray[0], 'Spec_7f2 #1' );1911 myQs.add_segment_consistently( segListArray[1], 'Spec_7f2 #2' );1912 // horizontal co-linear segment: connected at qsNode.seg.vFrom, inSegLong, qsSegDown1913 myQs.add_segment_consistently( segListArray[3], 'Spec_7f2 Main' );1914 //1915// showDataStructure( myQsRoot );1916// drawTrapezoids( myQsRoot, false, 1 );1917 // both horizontal segments continue in same direction: down, CW1918 myPolygonData = new PNLTRI.PolygonData( [ [1919 { x:15, y:20 }, { x: 5, y:20 }, { x:30, y: 5 }, { x:10, y:20 },1920 ] ] );1921 //1922 myQs = new PNLTRI.QueryStructure( myPolygonData );1923 myQsRoot = myQs.getRoot();1924 segListArray = myPolygonData.getSegments();1925 //1926 myQs.add_segment_consistently( segListArray[2], 'Spec_7f1cw #1' );1927 myQs.add_segment_consistently( segListArray[3], 'Spec_7f1cw #2' );1928 // horizontal co-linear segment: connected at qsNode.seg.vTo, inSegLong, qsSegUp1929 myQs.add_segment_consistently( segListArray[0], 'Spec_7f1cw Main' );1930 //1931// showDataStructure( myQsRoot );1932// drawTrapezoids( myQsRoot, false, 1 );1933 // other sequence1934 myQs = new PNLTRI.QueryStructure( myPolygonData );1935 myQsRoot = myQs.getRoot();1936 segListArray = myPolygonData.getSegments();1937 //1938 myQs.add_segment_consistently( segListArray[0], 'Spec_7f2cw #1' );1939 myQs.add_segment_consistently( segListArray[1], 'Spec_7f2cw #2' );1940 // horizontal co-linear segment: connected at qsNode.seg.vFrom, inSeg: short & up1941 myQs.add_segment_consistently( segListArray[3], 'Spec_7f2cw Main' );1942 //1943// showDataStructure( myQsRoot );1944// drawTrapezoids( myQsRoot, false, 1 );1945 }1946 // temporary method to test polygons-chains before adding them1947 // to the PolygonTestdata1948 function test_add_segment_NEW() {1949 var inDebug = 1;1950// var testData = new PolygonTestdata();1951// var myPolygonData = new PNLTRI.PolygonData( testData.get_polygon_with_holes( "three_error#3" ) );1952 var myPolygonData = new PNLTRI.PolygonData( [ [1953 { x: 16.5, y: 30 }, { x: 10, y: 23.5 }, { x: 15, y: 20 },1954 { x: 10, y: 16.5 }, { x: 22.5, y: 10 }, { x: 30, y: 16.5 },1955 { x: 25, y: 20 }, { x: 30, y: 23.5 },1956 ] ] );1957 console.log("add_segment_NEW: Number of Segments: ", myPolygonData.nbSegments() );1958// showDataStructure( myPolygonData.getVertices(), [ 'sprev', 'snext', 'vertTo', 'segOut' ] );1959// showDataStructure( myPolygonData.getSegments(), [ 'sprev', 'snext', 'mprev', 'mnext' ] );1960 //1961 var myQs = new PNLTRI.QueryStructure( myPolygonData );1962 var myQsRoot = myQs.getRoot();1963 var segListArray = myPolygonData.getSegments().concat();1964 //1965/* PNLTRI.Math.myRandom( 1 ); // set specific random seed for finding random errors1966 PNLTRI.Math.random = PNLTRI.Math.myRandom; */1967/* PNLTRI.Math.randomTestSetup(); // set specific random seed for repeatable testing1968 PNLTRI.Math.array_shuffle( segListArray );1969// showDataStructure( segListArray, [ 'sprev', 'snext', 'mprev', 'mnext' ] ); */1970/* var idxList = [ 27, 60, 32, 40, 64, 44, 57, 45, 30, 85, 22, 29, ];1971// myPolygonData.map_segments_and_vertices( segListArray, idxList );1972 segListArray = idxList.map( function (val) { return segListArray[val] } ); */1973 //1974 for (var i=0; i<segListArray.length; i++) {1975 myQs.add_segment_consistently( segListArray[i], 'New#'+i );1976/* var info = document.createElement( 'div' );1977 info.innerHTML = i;1978 document.body.appendChild( info );1979 drawTrapezoids( myQsRoot, false, inDebug ); */1980 }1981 ok( myPolygonData.allSegsInQueryStructure(), "add_segment_NEW: all segments inserted" );1982 console.log("add_segment_NEW: Number of Trapezoids: ", myQs.nbTrapezoids() );1983 myQs.assignDepths(myPolygonData); // marks outside trapezoids1984 equal( myQs.minDepth(), 0, "add_segment_NEW: Min depth == 0 (closed polygon)" );1985 //1986// showDataStructure( myQsRoot );1987 drawTrapezoids( myQsRoot, false, inDebug );1988 //1989 // check following steps - OPTIONAL1990/* var myMono = new PNLTRI.MonoSplitter( myPolygonData );1991 myMono.create_mono_chains();1992 myPolygonData.unique_monotone_chains_max();1993 console.log( "MonoChains after normalization: ", testData.polygons_to_str( myPolygonData.monotone_chains_2_polygons() ) );1994 console.log( "MonoChains after normalization: ", myPolygonData.polygons_2_vertexIndexLists( myPolygonData.monotone_chains_2_polygons() ) );1995 console.log( "MonoChains after normalization: ", myPolygonData.monoChainStarts_2_vertexIndexLists() );1996 var checkResult;1997 if ( checkResult = myPolygonData.check_normedMonoChains_consistency() ) console.log("add_segment_NEW: " + checkResult );1998 drawPolygonLayers( { "mono": myPolygonData.monotone_chains_2_polygons() }, inDebug );1999 //2000 var myTriangulator = new PNLTRI.MonoTriangulator( myPolygonData );2001 myTriangulator.triangulate_all_polygons();2002 var triangList = myPolygonData.getTriangles(); // sorted results !!2003 drawPolygonLayers( { "poly": example_data, "triang": myPolygonData.triangles_2_polygons() }, inDebug ); */2004 }2005 test( "QueryStructure", function() {2006 test_is_left_of();2007 //2008 test_init_query_structure_up();2009 test_init_query_structure_down();2010 test_splitNodeAtPoint1();2011 test_splitNodeAtPoint2();2012 //2013 test_ptNode();2014 test_ptNode_touching();2015 test_ptNode_colinear_inside();2016 test_ptNode_colinear_overlapping();2017 test_ptNode_colinear_reversal();2018 //2019 test_assign_depths();2020 //2021 // 2 unconnected segments2022 test_add_segment_basic_1();2023 test_add_segment_basic_2();2024 test_add_segment_basic_3();2025 test_add_segment_basic_4();2026 // touching segments2027 test_add_segment_touching_1();2028// test_add_segment_touching_2();2029 // polygons2030 test_add_segment_polygon_1();2031 test_add_segment_polygon_2ccw();2032 test_add_segment_polygon_2cw();2033 test_add_segment_polygon_3nonmono();2034 // special segment constellations2035 test_add_segment_special_1();2036 test_add_segment_special_2();2037 test_add_segment_special_3();2038 test_add_segment_special_4();2039 test_add_segment_special_5();2040 test_add_segment_special_6();2041 test_add_segment_special_7();2042 // for testing new polygons2043// test_add_segment_NEW();2044// test_add_segment_Error();2045 });2046}2047/*==============================================================================2048 *2049 *============================================================================*/2050/* Base class extensions - for testing only */2051PNLTRI.Trapezoider.prototype.getQsRoot = function () {2052 return this.queryStructure.getRoot();2053};2054PNLTRI.Trapezoider.prototype.nbTrapezoids = function () {2055 return this.queryStructure.nbTrapezoids();2056};2057PNLTRI.Trapezoider.prototype.minDepth = function () {2058 return this.queryStructure.minDepth();2059};2060PNLTRI.Trapezoider.prototype.maxDepth = function () {2061 return this.queryStructure.maxDepth();2062};2063PNLTRI.Trapezoider.prototype.check_trapezoid_neighbors = function ( inTrapId, inChkU0, inChkU1, inChkD0, inChkD1, inTestName ) {2064 return this.queryStructure.check_trapezoid_neighbors( inTrapId, inChkU0, inChkU1, inChkD0, inChkD1, inTestName );2065};2066//2067// The CENTRAL method for the near-linear performance !!!2068// Was inlined into trapezoide_polygon for performance.2069//2070PNLTRI.Trapezoider.prototype.math_logstar_stops = function ( inNbSegs ) {2071 var logStarSections = [ 0 ];2072 var idx, logstar;2073 for ( idx = 1, logstar = inNbSegs; logstar > 1; idx++ ) {2074 logstar = Math.log(logstar)/Math.LN2; // == log2(logstar)2075 logStarSections[idx] = ( logstar > 1 ) ? Math.floor( inNbSegs / logstar ) : inNbSegs;2076 }2077// console.log( "GesamtListe: ", logStarSections.join(", ") );2078 return logStarSections;2079};2080function test_Trapezoider() {2081 var testData = new PolygonTestdata();2082 function test_math_logstar_stops() {2083 var trap = new PNLTRI.Trapezoider();2084 //2085 deepEqual( trap.math_logstar_stops( 6 ), [ 0, 2, 4, 6 ], "math_logstar_stops: 6" );2086 deepEqual( trap.math_logstar_stops( 16 ), [ 0, 4, 8, 16 ], "math_logstar_stops: 16" );2087 deepEqual( trap.math_logstar_stops( 17 ), [ 0, 4, 8, 16, 17 ], "math_logstar_stops: 17" );2088 deepEqual( trap.math_logstar_stops( 314 ), [ 0, 37, 102, 195, 314 ], "math_logstar_stops: 314" );2089 deepEqual( trap.math_logstar_stops( 6404 ), [ 0, 506, 1749, 3420, 6404 ], "math_logstar_stops: 6404" );2090 deepEqual( trap.math_logstar_stops( 100000 ), [ 0, 6020, 24667, 49521, 98631, 100000 ], "math_logstar_stops: 100000" );2091 //2092 // "0, 2, 4, 7", "0, 2, 5, 8", "0, 3, 5, 10", "0, 3, 6, 12", "0, 3, 6, 13", "0, 3, 7, 15"2093 // "0, 4, 8, 17, 18", "0, 4, 9, 17, 19", "0, 4, 9, 18, 20", "0, 4, 9, 19, 21"2094 // "0, 5, 11, 22, 26", "0, 5, 12, 23, 28", "0, 6, 13, 25, 31", "0, 7, 16, 30, 39"2095 // "0, 7, 16, 31, 40", "0, 8, 20, 38, 51", "0, 13, 33, 63, 91", "0, 14, 34, 64, 92"2096 // "0, 15, 37, 70, 102", "0, 92, 274, 525, 904"2097 }2098 function test_optimise_randomlist() {2099 PNLTRI.Math.randomTestSetup(); // set specific random seed for repeatable testing2100 //2101 var myPolygonData = new PNLTRI.PolygonData( testData.get_polygon_with_holes( "square_3triangholes" ) );2102 var myTrapezoider = new PNLTRI.Trapezoider( myPolygonData );2103 //2104 // Main Test2105 //2106 var myQs = myTrapezoider.queryStructure; // TODO2107 var randSegListArray = myPolygonData.getSegments().concat();2108 PNLTRI.Math.array_shuffle( randSegListArray ); // "10, 4, 3, 11, 8, 5, 12, 1, 7, 2, 0, 9, 6"2109// console.log( "Old Random Segment Sequence: ", dumpRandomSequence( randSegListArray ) );2110 myTrapezoider.optimise_randomlist( randSegListArray ); // "10, 4, 3, 8, 11, 5, 12, 1, 7, 2, 0, 9, 6"2111// console.log( "New Random Segment Sequence: ", dumpRandomSequence( randSegListArray ) );2112 var expectedSequence = [10, 4, 3, 8, 11, 5, 12, 1, 7, 2, 0, 9, 6];2113 equal( randSegListArray.length, expectedSequence.length, "optimise_randomlist: new sequence length" );2114 var expectedSequenceOK = true;2115 for (var i=0; i<expectedSequence.length; i++) {2116 expectedSequenceOK &= ( randSegListArray[i].vFrom.id == expectedSequence[i] );2117 }2118 ok( expectedSequenceOK, "optimise_randomlist: new sequence elements" );2119 }2120 function test_trapezoide_polygon_structure() {2121 PNLTRI.Math.randomTestSetup(); // set specific random seed for repeatable testing2122 //2123 var inPolygonChainList = testData.get_polygon_with_holes("article_poly"); // from article [Sei91]2124 //2125 var myPolygonData = new PNLTRI.PolygonData( inPolygonChainList );2126// showDataStructure( myPolygonData.getVertices(), [ 'sprev', 'snext', 'vertTo', 'segOut' ] );2127 //2128 var myTrapezoider = new PNLTRI.Trapezoider( myPolygonData );2129 myTrapezoider.trapezoide_polygon();2130 ok( myPolygonData.allSegsInQueryStructure(), "trapezoide_polygon_structure: all segments inserted" );2131 equal( myTrapezoider.nbTrapezoids(), 41, "trapezoide_polygon_structure: Number of generated Trapezoids" );2132 //2133 myTrapezoider.check_trapezoid_neighbors( 0, null, null, 13, 36, "trapezoide_polygon_structure #0" );2134 myTrapezoider.check_trapezoid_neighbors( 1, 7, null, null, null, "trapezoide_polygon_structure #1" );2135 myTrapezoider.check_trapezoid_neighbors( 2, 25, 3, 8, null, "trapezoide_polygon_structure #2" );2136 myTrapezoider.check_trapezoid_neighbors( 3, null, null, null, 2, "trapezoide_polygon_structure #3" );2137 myTrapezoider.check_trapezoid_neighbors( 4, 30, null, null, 29, "trapezoide_polygon_structure #4" );2138 myTrapezoider.check_trapezoid_neighbors( 5, 37, null, 16, 24, "trapezoide_polygon_structure #5" );2139 myTrapezoider.check_trapezoid_neighbors( 6, null, 40, null, 27, "trapezoide_polygon_structure #6" );2140 myTrapezoider.check_trapezoid_neighbors( 7, 29, null, 1, 38, "trapezoide_polygon_structure #7" );2141 myTrapezoider.check_trapezoid_neighbors( 8, 2, 17, null, null, "trapezoide_polygon_structure #8" );2142 myTrapezoider.check_trapezoid_neighbors( 9, null, null, 21, null, "trapezoide_polygon_structure #9" );2143 myTrapezoider.check_trapezoid_neighbors( 10, 36, null, null, null, "trapezoide_polygon_structure #10" );2144 myTrapezoider.check_trapezoid_neighbors( 11, 39, null, null, 30, "trapezoide_polygon_structure #11" );2145 myTrapezoider.check_trapezoid_neighbors( 12, null, 36, null, 40, "trapezoide_polygon_structure #12" );2146 myTrapezoider.check_trapezoid_neighbors( 13, 0, null, 14, null, "trapezoide_polygon_structure #13" );2147 myTrapezoider.check_trapezoid_neighbors( 14, 13, null, 19, null, "trapezoide_polygon_structure #14" );2148 myTrapezoider.check_trapezoid_neighbors( 15, null, null, null, 20, "trapezoide_polygon_structure #15" );2149 myTrapezoider.check_trapezoid_neighbors( 16, 5, null, null, 22, "trapezoide_polygon_structure #16" );2150 myTrapezoider.check_trapezoid_neighbors( 17, 21, 23, null, 8, "trapezoide_polygon_structure #17" );2151 myTrapezoider.check_trapezoid_neighbors( 18, null, null, 23, null, "trapezoide_polygon_structure #18" );2152 myTrapezoider.check_trapezoid_neighbors( 19, 14, null, 25, 34, "trapezoide_polygon_structure #19" );2153 myTrapezoider.check_trapezoid_neighbors( 20, null, 15, 31, null, "trapezoide_polygon_structure #20" );2154 myTrapezoider.check_trapezoid_neighbors( 21, 9, null, 17, null, "trapezoide_polygon_structure #21" );2155 myTrapezoider.check_trapezoid_neighbors( 22, null, 16, null, null, "trapezoide_polygon_structure #22" );2156 myTrapezoider.check_trapezoid_neighbors( 23, 18, 27, null, 17, "trapezoide_polygon_structure #23" );2157 myTrapezoider.check_trapezoid_neighbors( 24, null, 5, null, null, "trapezoide_polygon_structure #24" );2158 myTrapezoider.check_trapezoid_neighbors( 25, 19, null, 2, null, "trapezoide_polygon_structure #25" );2159 myTrapezoider.check_trapezoid_neighbors( 26, null, null, 33, null, "trapezoide_polygon_structure #26" );2160 myTrapezoider.check_trapezoid_neighbors( 27, null, 6, null, 23, "trapezoide_polygon_structure #27" );2161 myTrapezoider.check_trapezoid_neighbors( 28, 34, null, null, 35, "trapezoide_polygon_structure #28" );2162 myTrapezoider.check_trapezoid_neighbors( 29, 33, 4, 7, 37, "trapezoide_polygon_structure #29" );2163 myTrapezoider.check_trapezoid_neighbors( 30, null, 11, 4, null, "trapezoide_polygon_structure #30" );2164 myTrapezoider.check_trapezoid_neighbors( 31, 20, 32, null, 39, "trapezoide_polygon_structure #31" );2165 myTrapezoider.check_trapezoid_neighbors( 32, null, null, null, 31, "trapezoide_polygon_structure #32" );2166 myTrapezoider.check_trapezoid_neighbors( 33, 26, null, 29, null, "trapezoide_polygon_structure #33" );2167 myTrapezoider.check_trapezoid_neighbors( 34, null, 19, 28, null, "trapezoide_polygon_structure #34" );2168 myTrapezoider.check_trapezoid_neighbors( 35, null, 28, null, null, "trapezoide_polygon_structure #35" );2169 myTrapezoider.check_trapezoid_neighbors( 36, null, 0, 10, 12, "trapezoide_polygon_structure #36" );2170 myTrapezoider.check_trapezoid_neighbors( 37, null, 29, 5, null, "trapezoide_polygon_structure #37" );2171 myTrapezoider.check_trapezoid_neighbors( 38, null, 7, null, null, "trapezoide_polygon_structure #38" );2172 myTrapezoider.check_trapezoid_neighbors( 39, null, 31, 11, null, "trapezoide_polygon_structure #39" );2173 myTrapezoider.check_trapezoid_neighbors( 40, null, 12, null, 6, "trapezoide_polygon_structure #40" );2174 //2175 //2176// var myQsRoot = myTrapezoider.getQsRoot();2177// showDataStructure( myQsRoot );2178// drawTrapezoids( myQsRoot, false, 1.5 );2179 }2180 function test_trapezoide_polygon( inDataName, inExpectedSegs, inExpectedTraps, inExpectedStartTrap,2181 inExpectedMaxDepth, inPolyLeftArr, inDebug ) {2182 PNLTRI.Math.randomTestSetup(); // set specific random seed for repeatable testing2183 //2184 var myPolygonData = new PNLTRI.PolygonData( testData.get_polygon_with_holes( inDataName ) );2185 equal( myPolygonData.nbSegments(), inExpectedSegs, "trapezoide_polygon ("+inDataName+"): originalSize" );2186 if ( inDebug > 0 ) {2187// showDataStructure( myPolygonData.getSegments(), [ 'sprev', 'snext', 'mprev', 'mnext' ] );2188 }2189 //2190 // Main Test2191 //2192 var myTrapezoider = new PNLTRI.Trapezoider( myPolygonData );2193 myTrapezoider.trapezoide_polygon();2194 var buglist = [];2195 //2196 ok( myPolygonData.allSegsInQueryStructure(), "trapezoide_polygon ("+inDataName+"): all segments inserted" );2197 equal( myTrapezoider.nbTrapezoids(), inExpectedTraps, "trapezoide_polygon ("+inDataName+"): Number of generated Trapezoids" );2198 equal( myTrapezoider.minDepth(), 0, "trapezoide_polygon ("+inDataName+"): depths assigned to all" );2199 equal( myTrapezoider.maxDepth(), inExpectedMaxDepth, "trapezoide_polygon ("+inDataName+"): Max depth" );2200 //2201 if ( buglist = myPolygonData.check_segments_consistency() )2202 ok( !buglist, "trapezoide_polygon ("+inDataName+") segment consistency: " + buglist.join(", ") );2203 //2204 if ( inPolyLeftArr ) {2205 deepEqual( myPolygonData.get_PolyLeftArr(), inPolyLeftArr, "trapezoide_polygon ("+inDataName+"): PolyLeftArr OK?" );2206 }2207 //2208 if ( inDebug > 0 ) {2209 var myQsRoot = myTrapezoider.getQsRoot();2210// showDataStructure( myQsRoot );2211// drawTrapezoids( myQsRoot, true, inDebug );2212 drawTrapezoids( myQsRoot, false, inDebug );2213 }2214 }2215 function test_visibility_map( inDataName, inDebug ) {2216 PNLTRI.Math.randomTestSetup(); // set specific random seed for repeatable testing2217 //2218 var myPolygonData = new PNLTRI.PolygonData( testData.get_polygon_with_holes( inDataName ) );2219 var myTrapezoider = new PNLTRI.Trapezoider( myPolygonData );2220 myTrapezoider.trapezoide_polygon();2221 //2222 if ( inDebug > 0 ) {2223 var myQsRoot = myTrapezoider.getQsRoot();2224// showDataStructure( myQsRoot );2225// drawTrapezoids( myQsRoot, true, inDebug );2226 drawTrapezoids( myQsRoot, false, inDebug );2227 }2228 //2229 // Main Test2230 //2231 myTrapezoider.create_visibility_map( myPolygonData );2232 //2233 var myVertices = myPolygonData.getVertices();2234 var vMapIdxs = [], curOutDiag;2235 for ( var i = 0; i < myVertices.length; i++ ) {2236 vMapIdxs[i] = [];2237 var vertex = myVertices[i];2238 if ( curOutDiag = vertex.firstOutDiag ) {2239 do {2240 vMapIdxs[i].push( curOutDiag.vTo.id );2241 curOutDiag = curOutDiag.revDiag.mnext;2242 } while ( curOutDiag && ( curOutDiag.vFrom == vertex ) );2243 }2244 }2245 var sollVisibilityMap = testData.get_visibilityMap( inDataName );2246 deepEqual( vMapIdxs, sollVisibilityMap, "visibility_map ("+inDataName+")" );2247 }2248 test( "Trapezoider for (Simple) Polygons", function() {2249 test_math_logstar_stops();2250 test_optimise_randomlist();2251 //2252 test_trapezoide_polygon_structure(); // detailed trapezoid structure2253 //2254 test_trapezoide_polygon( "article_poly", 20, 41, 1, 1, [ true ], 0 ); // 1.5: from article [Sei91]2255 test_trapezoide_polygon( "square_3triangholes", 13, 27, 19, 2, [ true, true, true, true ], 0 ); // 5; from "Narkhede A. and Manocha D.", data_12256 test_trapezoide_polygon( "trap_2up_2down", 6, 13, 3, 1, [ true ], 0 ); // 4: trapezoid with 2 upper and 2 lower neighbors2257 test_trapezoide_polygon( "pt_3_diag_max", 7, 15, 10, 1, [ true ], 0 ); // 4: vertex (6,6) with 3 additional diagonals (max)2258 test_trapezoide_polygon( "xy_bad_saw", 39, 79, 14, 1, [ true ], 0 ); // 2: very inconvenient contour in X- and Y-direction2259 //2260 test_trapezoide_polygon( "hole_short_path", 10, 21, 6, 2, [ false, false ], 0 ); // 0.8; shortest path to hole is outside polygon2261 test_trapezoide_polygon( "colinear#1", 13, 27, 6, 1, [ true ], 0 ); // 1; 4 touching co-linear lines2262 test_trapezoide_polygon( "colinear#2", 26, 53, 2, 2, [ true, true, true, true, true ], 0 ); // 1; 4 touching co-linear lines & 4 touching colinear holes2263 test_trapezoide_polygon( "colinear#3", 24, 49, 8, 2, [ true, true, true, true, true ], 0 ); // 1; touching co-linear horizontal lines2264 //2265 test_trapezoide_polygon( "three_error#1", 73, 147, 72, 1, [ false ], 0 ); // 1; 1.Error, integrating into Three.js (letter "t")2266 test_trapezoide_polygon( "three_error#2", 51, 103, 5, 1, [ false ], 0 ); // 0.7; 2.Error, integrating into Three.js (letter "1")2267 test_trapezoide_polygon( "three_error#3", 91, 183, 41, 1, [ false ], 0 ); // 3000; 3.Error, integrating into Three.js (logbuffer)2268 test_trapezoide_polygon( "three_error#4", 91, 183, 51, 1, [ true ], 0 ); // 1; 4.Error, integrating into Three.js (USA Maine)2269 test_trapezoide_polygon( "three_error#4b", 91, 183, 9, 1, [ false ], 0 ); // 0.04; 4.Error, integrating into Three.js (USA Maine)2270 test_trapezoide_polygon( "hole_first", 19, 39, 13, 2, [ false, false ], 0 ); // 0.5; 5.Error, integrating into Three.js ("R")2271 test_trapezoide_polygon( "two_polygons#1", 20, 41, 3, 1, [ true, false ], 0 ); // 0.5; 6.Error, integrating into Three.js ("i")2272 test_trapezoide_polygon( "two_polygons#2", 6, 13, 3, 1, [ true, false ], 0 ); // 1; my#6: two trivial polygons2273 test_trapezoide_polygon( "polygons_inside_hole", 19, 39, 7, 3, [ true, true, true, false ], 0 ); // 0.7; my#7: square with unregular hole with two polygons inside2274 //2275// console.perform();2276 test_trapezoide_polygon( "squares_perftest_mid", 904, 1809, 399, 2, null, 0 ); // 1: 15x15 Squares in Squares Performance Test2277// console.performEnd();2278 test_visibility_map( "article_poly", 0 ); // 1.5: from article [Sei91]2279 test_visibility_map( "square_3triangholes", 0 ); // 5; from "Narkhede A. and Manocha D.", data_12280 test_visibility_map( "trap_2up_2down", 0 ); // 4: trapezoid with 2 upper and 2 lower neighbors2281 test_visibility_map( "pt_3_diag_max", 0 ); // 4: vertex (6,6) with 3 additional diagonals (max)2282 test_visibility_map( "colinear#2", 0 ); // 1; 4 touching co-linear lines & 4 touching colinear holes2283 test_visibility_map( "three_error#1", 0 ); // 1; 1.Error, integrating into Three.js2284 });2285}2286function compute_Trapezoider( inResultTarget ) {2287 var myPolygonData = new PNLTRI.PolygonData( [ [2288 { x:10, y:35 }, { x:15, y: 5 }, { x:22, y:15 },2289 { x:25, y:10 }, { x:35, y:30 }, { x:20, y:25 },2290 ] ] );2291 //2292 var myTrapezoider = new PNLTRI.Trapezoider( myPolygonData );2293 myTrapezoider.trapezoide_polygon();2294 //2295 var myQsRoot = myTrapezoider.getQsRoot();2296// showDataStructure( myQsRoot );2297 drawTrapezoids( myQsRoot, false, 1 );...

abc.js

Source:abc.js

1$("#firstBu").click(function(){2//desplaying my main page untill we bress lets go3 $("#quiz").css("display", "block");4 $("#end").css("display", "block");5 $("#startdiv").css("display", "none");6 //changing the inner bacground7 $("body").css("background-image","url(images/yal.jpg)")8 })9 10//hear i stored my data wiche is the questions and the selectors and the answers inside an array of objects, 11// and the selectors inside an array cause they have multiple choices and i need to reach each one of them12var myQs = [{Q:"1.which letter does the word 'apple' starts with?:",13 A:"choice3",14 S : ["1.C","2.B","3.A","4.M"]},15 {Q:"2.which letter does the word 'butterfly' starts with?:",16 A:"choice1",17 S : [ "1.B", "2.K","3.O","4.P"]},18 {Q:"3.which letter does the word 'corn' starts with?:",19 A:"choice4",20 S : ["1.F","2.Z","3.I","4.C"]},21 {Q:"4.which letter does the word 'donuts' starts with?",22 A:"choice3",23 S : ["1.C","2.U","3.D","4.Z"]},24 {Q:"5.which letter does the word 'elephants' starts with?:",25 A:"choice3",26 S : ["1.B","2.N","3.E","4.Q"]}27 ];28$("#mistakes").click(function(){29 // blocking my main div wich is the div that contains the questions from my welcoming page30 $("#quiz").css("display", "block");31 //displaying the user's answers untill they bress the results button32 $("#form1 .cc").css("display", "block");33 $("#form2 .cc").css("display", "block");34 $("#form3 .cc").css("display", "block");35 $("#form4 .cc").css("display", "block");36 $("#form5 .cc").css("display", "block");37 //displaying the right answers untill the user bress the results button38 $(".correct").css("display", "block");39 40//hiding the starting messege41 $("#P1").css("display", "none");42 $("#mistakes").css("display", "none")43 44})45// getting each question with its options46$("#q1").text(myQs[0].Q);47$("#labelsId1").text((myQs[0].S)[0]);48$("#labelsId2").text((myQs[0].S)[1]);49$("#labelsId3").text((myQs[0].S)[2]);50$("#labelsId4").text((myQs[0].S)[3]);51$("#q2").text(myQs[1].Q);52$("#labelsId5").text((myQs[1].S)[0]);53$("#labelsId6").text((myQs[1].S)[1]);54$("#labelsId7").text((myQs[1].S)[2]);55$("#labelsId8").text((myQs[1].S)[3]);56$("#q3").text(myQs[2].Q);57$("#labelsId9").text((myQs[2].S)[0]);58$("#labelsId10").text((myQs[2].S)[1]);59$("#labelsId11").text((myQs[2].S)[2]);60$("#labelsId12").text((myQs[2].S)[3]);61$("#q4").text(myQs[3].Q);62$("#labelsId13").text((myQs[3].S)[0]);63$("#labelsId14").text((myQs[3].S)[1]);64$("#labelsId15").text((myQs[3].S)[2]);65$("#labelsId16").text((myQs[3].S)[3]);66$("#q5").text(myQs[4].Q);67$("#labelsId17").text((myQs[4].S)[0]);68$("#labelsId18").text((myQs[4].S)[1]);69$("#labelsId19").text((myQs[4].S)[2]);70$("#labelsId20").text((myQs[4].S)[3]);71$("#finish").click(function resultsCounter(){72 var choice1=$("#form1 :checked").val();73 var choice2=$("#form2 :checked").val();74 var choice3=$("#form3 :checked").val();75 var choice4=$("#form4 :checked").val();76 var choice5=$("#form5 :checked").val();77 //counting an storing my results78 var c = 0;79 var results;80//alert in case of a missing choice81 if(!choice1||!choice2||!choice3||!choice4||!choice5)82 alert('Oopsie, it seems like you forgot to answer a question, check again!');83 else { 84 //if the user solved all questions the main div will be displayed85 $("#quiz").css("display", "none");86 $("#startdiv").css("display", "none");87 $("#end").css("display", "none");88 //blockeing the result and the mistakes untill the user bress the button89 $("#result").css("display", "block");90 $("#mistakes").css("display", "block");91 //counting results .. it worked at the end92 for (var i = 0; i<5;i++){93 if ($(`#form${i+1} :checked`).val() === myQs[i].A){94 c++;95 $(`#form${i+1} .cc`).css("background-color", " #00cc00");96 }97 }98 //result ecuation99 results = (c/5)*100;100 // counting my results101 if(results === 100 || results >= 90){102 $('#result').text("your results:"+ results + '%, Awsome, You did great.');}103 else if(results >= 70 && results < 90){104 $('#result').text('your results:' + results + "%, That's very good.");} 105 else if(results >= 40 && results < 70){ 106 $('#result').text('your results:' + results + "%, That's good.");107 $('a').css("display", "inline");}108 //if they got lesser than 40 they will get the message from element a from the html109 else{110 $('#result').text('your results:' + results + '%, Hmmm!, you need some pract');111 $('a').css("display", "inline");} 112 // getting choice one corrected answer113 $("#form1 .cc").text("Your answer is :"+($("#form1 label[for="+choice1+"]").text())); 114 // getting choice two corrected answer115 $("#form2 .cc").text("Your answer is :"+($("#form2 label[for="+ choice2+"]").text()));116 // getting choice three corrected answer117 $("#form3 .cc").text("Your answer is :"+($("#form3 label[for="+choice3+"]").text()));118 // getting choice four corrected answer119 $("#form4 .cc").text("Your answer is :"+($("#form4 label[for="+choice4+"]").text()));120 // getting choice five corrected answer121 $("#form5 .cc").text("Your answer is :"+($("#form5 label[for="+choice5+"]").text()));122 }...

QuestionStorage.spec.js

Source:QuestionStorage.spec.js

1const { isArguments } = require("lodash");2const qs = require("./QuestionStorage");3describe("question Interface test", () => {4 it("question storage creation", () => {5 const myQs = new qs.QuestionStorage();6 expect(myQs.getQuestions()).toEqual([]);7 });8 it("adding a question", () => {9 const myQs = new qs.QuestionStorage();10 myQs.addQuestion({ fragenid: 1, titel: "me and my friends" });11 expect(myQs.getQuestions()).toEqual([12 {13 fragenid: 1,14 titel: "me and my friends",15 antworten: [],16 tags: [],17 },18 ]);19 });20 it("removes additional information", () => {21 const myQs = new qs.QuestionStorage();22 myQs.addQuestion({23 fragenid: 2,24 antworten: [{ text: "nice", nom: "nom", correct: true }],25 });26 expect(myQs.getQuestions()).toEqual([27 {28 fragenid: 2,29 titel: "default",30 antworten: [{ text: "nice", correct: true }],31 tags: [],32 },33 ]);34 });35 it("recognizes wrong format", () => {36 const myQs = new qs.QuestionStorage();37 expect(() =>38 myQs.addQuestion({39 fragenid: 2,40 antworten: [{ text: "nice", nom: "nom", correct: "hi" }],41 })42 ).toThrow();43 expect(() =>44 myQs.addQuestion({45 fragenid: "sad",46 antworten: [{ text: "nice", nom: "nom", correct: true }],47 })48 ).toThrow();49 expect(() =>50 myQs.addQuestion({51 fragenid: 2,52 antworten: [{ text: "nice", nom: "nom", correct: true }],53 tags: [1, 23, "hi"],54 })55 ).toThrow();56 });57 it("add answer interface", () => {58 const myQs = new qs.QuestionStorage();59 myQs.addQuestion({60 fragenid: 7,61 antworten: [{ text: "nice", correct: true }],62 });63 myQs.updateQuestion(7, qs.addAnswer());64 expect(myQs.getQuestions()[0].antworten.length).toBe(2);65 });66 it("remove answer interface", () => {67 const myQs = new qs.QuestionStorage();68 myQs.addQuestion({69 fragenid: 7,70 antworten: [{ text: "nice", correct: true }],71 });72 myQs.updateQuestion(7, qs.removeAnswer(0));73 expect(myQs.getQuestions()[0].antworten.length).toBe(0);74 });75 it("update answer interface", () => {76 const myQs = new qs.QuestionStorage();77 myQs.addQuestion({78 fragenid: 7,79 antworten: [80 { text: "nice", correct: true },81 { text: "old", correct: true },82 ],83 });84 myQs.updateQuestion(85 7,86 qs.updateAnswer(1, { text: "updated", correct: false, hi: "ho" })87 );88 expect(myQs.getQuestions()[0].antworten).toEqual([89 { text: "nice", correct: true },90 { text: "updated", correct: false },91 ]);92 });93 it("hstory travel back", () => {94 const myQs = new qs.QuestionStorage();95 myQs.addQuestion({96 fragenid: 7,97 antworten: [98 { text: "nice", correct: true },99 { text: "old", correct: true },100 ],101 });102 myQs.updateQuestion(103 7,104 qs.updateAnswer(1, { text: "updated", correct: false, hi: "ho" })105 );106 myQs.travelBack();107 expect(myQs.getQuestions()[0].antworten[1]).toEqual({108 text: "old",109 correct: true,110 });111 });112 it("hstory travel back and forward", () => {113 const myQs = new qs.QuestionStorage();114 myQs.addQuestion({115 fragenid: 7,116 antworten: [117 { text: "nice", correct: true },118 { text: "old", correct: true },119 ],120 });121 myQs.updateQuestion(122 7,123 qs.updateAnswer(1, { text: "updated", correct: false, hi: "ho" })124 );125 myQs.travelBack();126 expect(myQs.getQuestions()[0].antworten[1]).toEqual({127 text: "old",128 correct: true,129 });130 myQs.travelForward();131 expect(myQs.getQuestions()[0].antworten[1]).toEqual({132 text: "updated",133 correct: false,134 });135 });136 it("not adding to history when answer doesnt change", () => {137 const myQs = new qs.QuestionStorage();138 myQs.addQuestion({139 fragenid: 7,140 antworten: [141 { text: "nice", correct: true },142 { text: "old", correct: true },143 ],144 });145 myQs.updateQuestion(146 7,147 qs.updateAnswer(1, { text: "old", correct: true, hi: "ho" })148 );149 expect(() => myQs.travelBack()).toThrow(150 "cant go back to this point in time"151 );152 });...

Using AI Code Generation

1var wpt = require('webpagetest');2var wpt = new WebPageTest('www.webpagetest.org', 'A.1a2b3c4d5e6f7g8h9i0j1k2l3m4n5o6p');3var options = {4};5wpt.runTest(options, function(err, data) {6 if (err) return console.error(err);7 console.log(data);8});

Using AI Code Generation

1var wpt = require('webpagetest');2var wpt = new WebPageTest('www.webpagetest.org');3}, function(err, data) {4 if (err) return console.error(err);5 console.log(data);6});7var wpt = require('webpagetest');8var wpt = new WebPageTest('www.webpagetest.org');9 myQs: {10 }11}, function(err, data) {12 if (err) return console.error(err);13 console.log(data);14});15var wpt = require('webpagetest');16var wpt = new WebPageTest('www.webpagetest.org');17 myQs: {18 }19}, function(err, data) {20 if (err) return console.error(err);21 console.log(data);22}, function(err, data) {23 if (err) return console.error(err);24 console.log(data);25});

Using AI Code Generation

1var wpt = require('webpagetest');2var options = {3};4var wpt = new WebPageTest('www.webpagetest.org', options.key);5wpt.runTest(testURL, options, function(err, data) {6 if (err) return console.error(err);7 console.log(data);8});9var wpt = require('webpagetest');10var options = {11};12var wpt = new WebPageTest('www.webpagetest.org', options.key);13wpt.runTest(testURL, options, function(err, data) {14 if (err) return console.error(err);15 console.log(data);16});

Using AI Code Generation

1var wpt = require('webpagetest');2var options = {3};4var wpt = new WebPageTest('www.webpagetest.org', options.key);5 if (err) return console.error(err);6 console.log('Test status:', data.statusText);7 if (data.statusCode == 200) {8 console.log('Test completed in', data.data.average.firstView.loadTime, 'ms');9 }10});11var WebPageTest = require('webpagetest');12var wpt = new WebPageTest('www.webpagetest.org', 'A.5a3a3f9b9d1a5e5a3a3f9b9d1a5e5e5');13wpt.getLocations(function(err, data) {14 if (err) return console.error(err);15 console.log(data);16});17var WebPageTest = require('webpagetest');18var wpt = new WebPageTest('www.webpagetest.org', 'A.5a3a3f9b9d1a5e5a3a3f9b9d1a5e5e5');19wpt.getTesters(function(err, data) {20 if (err) return console.error(err);21 console.log(data);22});23var WebPageTest = require('webpagetest');24var wpt = new WebPageTest('www.webpagetest.org', 'A.5a3a3f9b9d1a5e5a3a3f9b9d1a5e5e5');25wpt.getTestStatus('170322_7G_1b1e8b0f1f1d7d0c2c2e', function(err, data) {26 if (err) return console.error(err);27 console.log(data);28});

Using AI Code Generation

1var wpt = require('webpagetest');2var options = {3};4var wpt = new WebPageTest('www.webpagetest.org', options.key);5 if (err) return console.error(err);6 console.log(data.data.median.firstView);7});8{ [Error: connect ECONNREFUSED

Automation Testing Tutorials

Learn to execute automation testing from scratch with LambdaTest Learning Hub. Right from setting up the prerequisites to run your first automation test, to following best practices and diving deeper into advanced test scenarios. LambdaTest Learning Hubs compile a list of step-by-step guides to help you be proficient with different test automation frameworks i.e. Selenium, Cypress, TestNG etc.

LambdaTest Learning Hubs:

• JUnit Tutorial
• TestNG Tutorial
• Webdriver Tutorial
• WebDriverIO Tutorial
• Protractor Tutorial
• Selenium 4 Tutorial
• Jenkins Tutorial
• NUnit Tutorial
• Jest Tutorial
• Playwright Tutorial
• Cypress Tutorial
• PyTest Tutorial

YouTube

You could also refer to video tutorials over LambdaTest YouTube channel to get step by step demonstration from industry experts.

Run wpt automation tests on LambdaTest cloud grid

Perform automation testing on 3000+ real desktop and mobile devices online.

View sample repo View DocumentationSign up Free

›

_