1 /* 2 Copyright 2008-2022 3 Matthias Ehmann, 4 Michael Gerhaeuser, 5 Carsten Miller, 6 Alfred Wassermann 7 console.log("P:", P.coords.usrCoords, P.data.type) 8 9 This file is part of JSXGraph. 10 11 JSXGraph is free software dual licensed under the GNU LGPL or MIT License. 12 13 You can redistribute it and/or modify it under the terms of the 14 15 * GNU Lesser General Public License as published by 16 the Free Software Foundation, either version 3 of the License, or 17 (at your option) any later version 18 OR 19 * MIT License: https://github.com/jsxgraph/jsxgraph/blob/master/LICENSE.MIT 20 21 JSXGraph is distributed in the hope that it will be useful, 22 but WITHOUT ANY WARRANTY; without even the implied warranty of 23 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 24 GNU Lesser General Public License for more details. 25 26 You should have received a copy of the GNU Lesser General Public License and 27 the MIT License along with JSXGraph. If not, see <http://www.gnu.org/licenses/> 28 and <http://opensource.org/licenses/MIT/>. 29 */ 30 31 32 /*global JXG: true, define: true*/ 33 /*jslint nomen: true, plusplus: true*/ 34 35 /* depends: 36 jxg 37 base/constants 38 base/coords 39 math/math 40 math/numerics 41 math/geometry 42 utils/type 43 */ 44 45 /** 46 * @fileoverview This file contains the Math.Clip namespace for clipping and computing boolean operations 47 * on polygons and curves 48 * 49 * // TODO: 50 * * Check if input polygons are closed. If not, handle this case. 51 */ 52 53 define([ 54 'jxg', 'base/constants', 'base/coords', 'math/math', 'math/geometry', 'utils/type' 55 ], function (JXG, Const, Coords, Mat, Geometry, Type) { 56 57 "use strict"; 58 59 /** 60 * Math.Clip namespace definition. This namespace contains algorithms for Boolean operations on paths, i.e. 61 * intersection, union and difference of paths. Base is the Greiner-Hormann algorithm. 62 * @name JXG.Math.Clip 63 * @exports Mat.Clip as JXG.Math.Clip 64 * @namespace 65 */ 66 // Mat.Clip = function () { 67 // }; 68 69 // JXG.extend(Mat.Clip.prototype, /** @lends JXG.Curve.prototype */ { 70 71 Mat.Clip = { 72 73 _isSeparator: function(node) { 74 return isNaN(node.coords.usrCoords[1]) && isNaN(node.coords.usrCoords[2]); 75 }, 76 77 /** 78 * Add pointers to an array S such that it is a circular doubly-linked list. 79 * 80 * @private 81 * @param {Array} S Array 82 * @return {Array} return containing the starter indices of each component. 83 */ 84 makeDoublyLinkedList: function(S) { 85 var i, 86 first = null, 87 components = [], 88 le = S.length; 89 90 if (le > 0) { 91 for (i = 0; i < le; i++) { 92 // S[i]._next = S[(i + 1) % le]; 93 // S[i]._prev = S[(le + i - 1) % le]; 94 95 // If S[i] is component separator we proceed with the next node. 96 if (this._isSeparator(S[i])) { 97 S[i]._next = S[(i + 1) % le]; 98 S[i]._prev = S[(le + i - 1) % le]; 99 continue; 100 } 101 102 // Now we know that S[i] is a path component 103 if (first === null) { 104 // Start the component if it is not yet started. 105 first = i; 106 components.push(first); 107 } 108 if (this._isSeparator(S[(i + 1) % le]) || i === le - 1) { 109 // If the next node is a component separator or if the node is the last node, 110 // then we close the loop 111 112 S[i]._next = S[first]; 113 S[first]._prev = S[i]; 114 S[i]._end = true; 115 first = null; 116 } else { 117 // Here, we are not at the end of component 118 S[i]._next = S[(i + 1) % le]; 119 S[first]._prev = S[i]; 120 } 121 if (!this._isSeparator(S[(le + i - 1) % le])) { 122 S[i]._prev = S[(le + i - 1) % le]; 123 } 124 } 125 } 126 return components; 127 }, 128 129 /** 130 * JavaScript object containing the intersection of two paths. Every intersection point is on one path, but 131 * comes with a neighbour point having the same coordinates and being on the other path. 132 * 133 * The intersection point is inserted into the doubly linked list of the path. 134 * 135 * @private 136 * @param {JXG.Coords} coords JSXGraph Coords object conatining the coordinates of the intersection 137 * @param {Number} i Number of the segment of the subject path (first path) containing the intersection. 138 * @param {Number} alpha The intersection is a p_1 + alpha*(p_2 - p_1), where p_1 and p_2 are the end points 139 * of the i-th segment. 140 * @param {Array} path Pointer to the path containing the intersection point 141 * @param {String} pathname Name of the path: 'S' or 'C'. 142 */ 143 Vertex: function(coords, i, alpha, path, pathname, type) { 144 this.pos = i; 145 this.intersection = true; 146 this.coords = coords; 147 this.elementClass = Const.OBJECT_CLASS_POINT; 148 149 this.data = { 150 alpha: alpha, 151 path: path, 152 pathname: pathname, 153 done: false, 154 type: type, 155 idx: 0 156 }; 157 158 // Set after initialisation 159 this.neighbour = null; 160 this.entry_exit = false; 161 }, 162 163 _addToList: function(list, coords, pos) { 164 var len = list.length, 165 eps = Mat.eps * Mat.eps; 166 167 if (len > 0 && 168 Math.abs(list[len - 1].coords.usrCoords[0] - coords.usrCoords[0]) < eps && 169 Math.abs(list[len - 1].coords.usrCoords[1] - coords.usrCoords[1]) < eps && 170 Math.abs(list[len - 1].coords.usrCoords[2] - coords.usrCoords[2]) < eps) { 171 // Skip point 172 return; 173 } 174 list.push({ 175 pos: pos, 176 intersection: false, 177 coords: coords, 178 elementClass: Const.OBJECT_CLASS_POINT 179 }); 180 }, 181 182 /** 183 * Sort the intersection points into their path. 184 * @private 185 * @param {Array} P_crossings Array of arrays. Each array contains the intersections of the path 186 * with one segment of the other path. 187 * @return {Array} Array of intersection points ordered by first occurrence in the path. 188 */ 189 sortIntersections: function(P_crossings) { 190 var i, j, P, Q, 191 last, 192 next_node, 193 P_intersect = [], 194 P_le = P_crossings.length; 195 196 for (i = 0; i < P_le; i++) { 197 P_crossings[i].sort(function(a, b) { return (a.data.alpha > b.data.alpha) ? 1 : -1; }); 198 199 if (P_crossings[i].length > 0) { 200 // console.log("Crossings", P_crossings[i]) 201 last = P_crossings[i].length - 1; 202 P = P_crossings[i][0]; 203 204 //console.log("SORT", P.coords.usrCoords) 205 Q = P.data.path[P.pos]; 206 next_node = Q._next; // Store the next "normal" node 207 208 if (i === P_le - 1) { 209 Q._end = false; 210 } 211 212 if (P.data.alpha === 0.0 && P.data.type === 'T') { 213 // console.log("SKIP", P.coords.usrCoords, P.data.type, P.neighbour.data.type); 214 Q.intersection = true; 215 Q.data = P.data; 216 Q.neighbour = P.neighbour; 217 Q.neighbour.neighbour = Q; 218 Q.entry_exit = false; 219 P_crossings[i][0] = Q; 220 } else { 221 // Insert the first intersection point 222 P._prev = Q; 223 P._prev._next = P; 224 } 225 226 // Insert the other intersection points, but the last 227 for (j = 1; j <= last; j++) { 228 P = P_crossings[i][j]; 229 P._prev = P_crossings[i][j - 1]; 230 P._prev._next = P; 231 } 232 233 // Link last intersection point to the next node 234 P = P_crossings[i][last]; 235 P._next = next_node; 236 P._next._prev = P; 237 238 if (i === P_le - 1) { 239 P._end = true; 240 //console.log("END", P._end, P.coords.usrCoords, P._prev.coords.usrCoords, P._next.coords.usrCoords); 241 } 242 243 P_intersect = P_intersect.concat(P_crossings[i]); 244 } 245 } 246 return P_intersect; 247 }, 248 249 _inbetween: function(q, p1, p2) { 250 var alpha, 251 eps = Mat.eps * Mat.eps, 252 px = p2[1] - p1[1], 253 py = p2[2] - p1[2], 254 qx = q[1] - p1[1], 255 qy = q[2] - p1[2]; 256 257 if (px === 0 && py === 0 && qx === 0 && qy === 0) { 258 // All three points are equal 259 return true; 260 } 261 if (Math.abs(qx) < eps && Math.abs(px) < eps) { 262 alpha = qy / py; 263 } else { 264 alpha = qx / px; 265 } 266 if (Math.abs(alpha) < eps) { 267 alpha = 0.0; 268 } 269 return alpha; 270 }, 271 272 _print_array: function(arr) { 273 var i, end; 274 for (i = 0; i < arr.length; i++) { 275 //console.log(i, arr[i].coords.usrCoords, arr[i].data.type); 276 try { 277 end = ""; 278 if (arr[i]._end) { 279 end = " end"; 280 } 281 console.log(i, arr[i].coords.usrCoords, arr[i].data.type, "\t", 282 "prev", arr[i]._prev.coords.usrCoords, 283 "next", arr[i]._next.coords.usrCoords + end); 284 } catch (e) { 285 console.log(i, arr[i].coords.usrCoords); 286 } 287 } 288 }, 289 290 _print_list: function(P) { 291 var cnt = 0, alpha; 292 while (cnt < 100) { 293 if (P.data) { 294 alpha = P.data.alpha; 295 } else { 296 alpha = '-'; 297 } 298 console.log("\t", P.coords.usrCoords, "\n\t\tis:", P.intersection, "end:", P._end, 299 alpha, 300 "\n\t\t-:", P._prev.coords.usrCoords, 301 "\n\t\t+:", P._next.coords.usrCoords, 302 "\n\t\tn:", (P.intersection) ? P.neighbour.coords.usrCoords : '-' 303 ); 304 if (P._end) { 305 break; 306 } 307 P = P._next; 308 cnt++; 309 } 310 }, 311 312 _noOverlap: function(p1, p2, q1, q2) { 313 var k, 314 eps = Math.sqrt(Mat.eps), 315 minp, maxp, minq, maxq, 316 no_overlap = false; 317 318 for (k = 0; k < 3; k++) { 319 minp = Math.min(p1[k], p2[k]); 320 maxp = Math.max(p1[k], p2[k]); 321 minq = Math.min(q1[k], q2[k]); 322 maxq = Math.max(q1[k], q2[k]); 323 if (maxp < minq - eps || minp > maxq + eps) { 324 no_overlap = true; 325 break; 326 } 327 } 328 return no_overlap; 329 }, 330 331 /** 332 * Find all intersections between two paths. 333 * @private 334 * @param {Array} S Subject path 335 * @param {Array} C Clip path 336 * @param {JXG.Board} board JSXGraph board object. It is needed to convert between 337 * user coordinates and screen coordinates. 338 * @return {Array} Array containing two arrays. The first array contains the intersection vertices 339 * of the subject path and the second array contains the intersection vertices of the clip path. 340 * @see JXG.Clip#Vertex 341 */ 342 findIntersections: function(S, C, board) { 343 var res = [], 344 eps = Mat.eps, 345 i, j, 346 crds, 347 S_le = S.length, 348 C_le = C.length, 349 Si, Si1, Cj, Cj1, 350 d1, d2, 351 alpha, 352 type, 353 IS, IC, 354 S_intersect = [], 355 C_intersect = [], 356 S_crossings = [], 357 C_crossings = [], 358 hasMultCompsS = false, 359 hasMultCompsC = false, 360 DEBUG = false; 361 362 for (j = 0; j < C_le; j++) { 363 C_crossings.push([]); 364 } 365 366 // Run through the subject path. 367 for (i = 0; i < S_le; i++) { 368 S_crossings.push([]); 369 370 // Test if S[i] or its successor is a path separator. 371 // If yes, we know that the path consists of multiple components. 372 // We immediately jump to the next segment. 373 if (this._isSeparator(S[i]) || this._isSeparator(S[(i + 1) % S_le])) { 374 hasMultCompsS = true; 375 continue; 376 } 377 378 // If the path consists of multiple components then there is 379 // no path-closing segment between the last node and the first 380 // node. In this case we can leave the loop now. 381 if (hasMultCompsS && i === S_le - 1) { 382 break; 383 } 384 385 Si = S[i].coords.usrCoords; 386 Si1 = S[(i + 1) % S_le].coords.usrCoords; 387 // Run through the clip path. 388 for (j = 0; j < C_le; j++) { 389 // Test if C[j] or its successor is a path separator. 390 // If yes, we know that the path consists of multiple components. 391 // We immediately jump to the next segment. 392 if (this._isSeparator(C[j]) || this._isSeparator(C[(j + 1) % C_le])) { 393 hasMultCompsC = true; 394 continue; 395 } 396 397 // If the path consists of multiple components then there is 398 // no path-closing segment between the last node and the first 399 // node. In this case we can leave the loop now. 400 if (hasMultCompsC && j === C_le - 1) { 401 break; 402 } 403 404 // Test if bounding boxes of the two curve segments overlap 405 // If not, the expensive intersection test can be skipped. 406 Cj = C[j].coords.usrCoords; 407 Cj1 = C[(j + 1) % C_le].coords.usrCoords; 408 409 if (this._noOverlap(Si, Si1, Cj, Cj1)) { 410 continue; 411 } 412 413 // Intersection test 414 res = Geometry.meetSegmentSegment(Si, Si1, Cj, Cj1); 415 416 d1 = Geometry.distance(Si, Si1, 3); 417 d2 = Geometry.distance(Cj, Cj1, 3); 418 419 // Found an intersection point 420 if ( // "Regular" intersection 421 (res[1] * d1 > -eps && res[1] < 1 - eps / d1 && res[2] * d2 > -eps && res[2] < 1 - eps / d2) || 422 // Collinear segments 423 (res[1] === Infinity && res[2] === Infinity && Mat.norm(res[0], 3) < eps) 424 ) { 425 426 crds = new Coords(Const.COORDS_BY_USER, res[0], board); 427 type = 'X'; 428 429 // Handle degenerated cases 430 if (Math.abs(res[1]) * d1 < eps || Math.abs(res[2]) * d2 < eps) { 431 // Crossing / bouncing at vertex or 432 // end of delayed crossing / bouncing 433 type = 'T'; 434 if (Math.abs(res[1]) * d1 < eps) { 435 res[1] = 0; 436 } 437 if (Math.abs(res[2]) * d2 < eps) { 438 res[2] = 0; 439 } 440 if (res[1] === 0) { 441 crds = new Coords(Const.COORDS_BY_USER, Si, board); 442 } else { 443 crds = new Coords(Const.COORDS_BY_USER, Cj, board); 444 } 445 446 if (DEBUG) { 447 console.log("Degenerate case I", res[1], res[2], crds.usrCoords, "type", type); 448 } 449 } else if (res[1] === Infinity && 450 res[2] === Infinity && 451 Mat.norm(res[0], 3) < eps) { // console.log(C_intersect); 452 453 454 // Collinear segments 455 // Here, there might be two intersection points to be added 456 457 alpha = this._inbetween(Si, Cj, Cj1); 458 if (DEBUG) { 459 // console.log("alpha Si", alpha, Si); 460 // console.log(j, Cj) 461 // console.log((j + 1) % C_le, Cj1) 462 } 463 if (alpha >= 0 && alpha < 1) { 464 type = 'T'; 465 crds = new Coords(Const.COORDS_BY_USER, Si, board); 466 res[1] = 0; 467 res[2] = alpha; 468 IS = new this.Vertex(crds, i, res[1], S, 'S', type); 469 IC = new this.Vertex(crds, j, res[2], C, 'C', type); 470 IS.neighbour = IC; 471 IC.neighbour = IS; 472 S_crossings[i].push(IS); 473 C_crossings[j].push(IC); 474 if (DEBUG) { 475 console.log("Degenerate case II", res[1], res[2], crds.usrCoords, "type T"); 476 } 477 } 478 alpha = this._inbetween(Cj, Si, Si1); 479 if (DEBUG) { 480 // console.log("alpha Cj", alpha, Si, Geometry.distance(Si, Cj, 3)); 481 } 482 if (Geometry.distance(Si, Cj, 3) > eps && 483 alpha >= 0 && alpha < 1) { 484 485 type = 'T'; 486 crds = new Coords(Const.COORDS_BY_USER, Cj, board); 487 res[1] = alpha; 488 res[2] = 0; 489 IS = new this.Vertex(crds, i, res[1], S, 'S', type); 490 IC = new this.Vertex(crds, j, res[2], C, 'C', type); 491 IS.neighbour = IC; 492 IC.neighbour = IS; 493 S_crossings[i].push(IS); 494 C_crossings[j].push(IC); 495 if (DEBUG) { 496 console.log("Degenerate case III", res[1], res[2], crds.usrCoords, "type T"); 497 } 498 } 499 continue; 500 } 501 if (DEBUG) { 502 console.log("IS", i, j, crds.usrCoords, type); 503 } 504 505 IS = new this.Vertex(crds, i, res[1], S, 'S', type); 506 IC = new this.Vertex(crds, j, res[2], C, 'C', type); 507 IS.neighbour = IC; 508 IC.neighbour = IS; 509 510 S_crossings[i].push(IS); 511 C_crossings[j].push(IC); 512 } 513 } 514 } 515 516 // For both paths, sort their intersection points 517 S_intersect = this.sortIntersections(S_crossings); 518 519 if (DEBUG) { 520 console.log('>>>>>> Intersections '); 521 console.log("S_intersect"); 522 this._print_array(S_intersect); 523 console.log('----------'); 524 } 525 for (i = 0; i < S_intersect.length; i++) { 526 S_intersect[i].data.idx = i; 527 S_intersect[i].neighbour.data.idx = i; 528 } 529 C_intersect = this.sortIntersections(C_crossings); 530 531 if (DEBUG) { 532 console.log("C_intersect"); 533 this._print_array(C_intersect); 534 console.log('<<<<<< Phase 1 done'); 535 } 536 return [S_intersect, C_intersect]; 537 }, 538 539 /** 540 * It is testedd if the point q lies to the left or right 541 * of the poylgonal chain [p1, p2, p3]. 542 * @param {Array} q User coords array 543 * @param {Array} p1 User coords array 544 * @param {Array} p2 User coords array 545 * @param {Array} p3 User coords array 546 * @returns string 'left' or 'right' 547 * @private 548 */ 549 _getPosition: function(q, p1, p2, p3) { 550 var s1 = Geometry.det3p(q, p1, p2), 551 s2 = Geometry.det3p(q, p2, p3), 552 s3 = Geometry.det3p(p1, p2, p3); 553 554 // Left turn 555 if (s3 >= 0) { 556 if (s1 >= 0 && s2 >= 0) { 557 return 'left'; 558 } 559 return 'right'; 560 } 561 // Right turn 562 if (s1 >= 0 || s2 >= 0) { 563 return 'left'; 564 } 565 return 'right'; 566 }, 567 568 /** 569 * Determine the delayed status of degenerated intersection points. 570 * It is of the form 571 * ['on|left|right', 'on|left|right'] 572 * <p> 573 * If all four determinants are zero, we add random noise to the point. 574 * 575 * @param {JXG.Math.Clip.Vertex} P Start of path 576 * @private 577 * @see JXG.Math.Clip#markEntryExit 578 * @see JXG.Math.Clip#_handleIntersectionChains 579 */ 580 _classifyDegenerateIntersections: function(P) { 581 var Pp, Pm, Qp, Qm, Q, side, 582 cnt, tmp, det, 583 oppositeDir, 584 s1, s2, s3, s4, 585 DEBUG = false; 586 587 if (DEBUG) { 588 console.log("\n-------------- _classifyDegenerateIntersections()", (Type.exists(P.data))?P.data.pathname:' '); 589 } 590 det = Geometry.det3p; 591 cnt = 0; 592 P._tours = 0; 593 while (true) { 594 if (DEBUG) { 595 console.log("Inspect P:", P.coords.usrCoords, (P.data) ? P.data.type : " "); 596 } 597 if (P.intersection && (P.data.type === 'T')) { 598 599 // Handle the degenerate cases 600 // Decide if they are (delayed) bouncing or crossing intersections 601 Pp = P._next.coords.usrCoords; // P+ 602 Pm = P._prev.coords.usrCoords; // P- 603 604 // If the intersection point is degenerated and 605 // equal to the start and end of one component, 606 // then there will be two adjacent points with 607 // the same coordinate. 608 // In that case, we proceed to the next node. 609 if (Geometry.distance(P.coords.usrCoords, Pp, 3) < Mat.eps) { 610 Pp = P._next._next.coords.usrCoords; 611 } 612 if (Geometry.distance(P.coords.usrCoords, Pm, 3) < Mat.eps) { 613 Pm = P._prev._prev.coords.usrCoords; 614 } 615 616 Q = P.neighbour; 617 Qm = Q._prev.coords.usrCoords; // Q- 618 Qp = Q._next.coords.usrCoords; // Q+ 619 if (Geometry.distance(Q.coords.usrCoords, Qp, 3) < Mat.eps) { 620 Qp = Q._next._next.coords.usrCoords; 621 } 622 if (Geometry.distance(Q.coords.usrCoords, Qm, 3) < Mat.eps) { 623 Qm = Q._prev._prev.coords.usrCoords; 624 } 625 626 if (DEBUG) { 627 console.log("P chain:", Pm, P.coords.usrCoords, Pp); 628 console.log("Q chain:", Qm, P.neighbour.coords.usrCoords, Qp); 629 console.log("Pm", this._getPosition(Pm, Qm, Q.coords.usrCoords, Qp)); 630 console.log("Pp", this._getPosition(Pp, Qm, Q.coords.usrCoords, Qp)); 631 } 632 633 s1 = det(P.coords.usrCoords, Pm, Qm); 634 s2 = det(P.coords.usrCoords, Pp, Qp); 635 s3 = det(P.coords.usrCoords, Pm, Qp); 636 s4 = det(P.coords.usrCoords, Pp, Qm); 637 638 if (s1 === 0 && s2 === 0 && s3 === 0 && s4 === 0) { 639 P.coords.usrCoords[1] *= 1 + Math.random() * Mat.eps; 640 P.coords.usrCoords[2] *= 1 + Math.random() * Mat.eps; 641 Q.coords.usrCoords[1] = P.coords.usrCoords[1]; 642 Q.coords.usrCoords[2] = P.coords.usrCoords[2]; 643 s1 = det(P.coords.usrCoords, Pm, Qm); 644 s2 = det(P.coords.usrCoords, Pp, Qp); 645 s3 = det(P.coords.usrCoords, Pm, Qp); 646 s4 = det(P.coords.usrCoords, Pp, Qm); 647 if (DEBUG) { 648 console.log("Random shift", P.coords.usrCoords); 649 console.log(s1, s2, s3, s4, s2 === 0); 650 console.log(this._getPosition(Pm, Qm, Q.coords.usrCoords, Qp), 651 this._getPosition(Pp, Qm, Q.coords.usrCoords, Qp)); 652 } 653 } 654 oppositeDir = false; 655 if (s1 === 0) { 656 // Q-, Q=P, P- on straight line 657 if (Geometry.affineRatio(P.coords.usrCoords, Pm, Qm) < 0) { 658 oppositeDir = true; 659 } 660 } else if (s2 === 0) { 661 if (Geometry.affineRatio(P.coords.usrCoords, Pp, Qp) < 0) { 662 oppositeDir = true; 663 } 664 } else if (s3 === 0) { 665 if (Geometry.affineRatio(P.coords.usrCoords, Pm, Qp) > 0) { 666 oppositeDir = true; 667 } 668 } else if (s4 === 0) { 669 if (Geometry.affineRatio(P.coords.usrCoords, Pp, Qm) > 0) { 670 oppositeDir = true; 671 } 672 } 673 if (oppositeDir) { 674 // Swap Qm and Qp 675 // Then Qm Q Qp has the same direction as Pm P Pp 676 tmp = Qm; Qm = Qp; Qp = tmp; 677 tmp = s1; s1 = s3; s3 = tmp; 678 tmp = s2; s2 = s4; s4 = tmp; 679 } 680 681 if (DEBUG) { 682 console.log(s1, s2, s3, s4, oppositeDir); 683 } 684 685 if (!Type.exists(P.delayedStatus)) { 686 P.delayedStatus = []; 687 } 688 689 if (s1 === 0 && s2 === 0) { 690 // Line [P-,P] equals [Q-,Q] and line [P,P+] equals [Q,Q+] 691 // Interior of delayed crossing / bouncing 692 P.delayedStatus = ['on', 'on']; 693 694 } else if (s1 === 0) { 695 // P- on line [Q-,Q], P+ not on line [Q,Q+] 696 // Begin / end of delayed crossing / bouncing 697 side = this._getPosition(Pp, Qm, Q.coords.usrCoords, Qp); 698 P.delayedStatus = ['on', side]; 699 700 } else if (s2 === 0) { 701 // P+ on line [Q,Q+], P- not on line [Q-,Q] 702 // Begin / end of delayed crossing / bouncing 703 side = this._getPosition(Pm, Qm, Q.coords.usrCoords, Qp); 704 P.delayedStatus = [side, 'on']; 705 706 } else { 707 // Neither P+ on line [Q,Q+], nor P- on line [Q-,Q] 708 // No delayed crossing / bouncing 709 if (P.delayedStatus.length === 0) { 710 if (this._getPosition(Pm, Qm, Q.coords.usrCoords, Qp) !== this._getPosition(Pp, Qm, Q.coords.usrCoords, Qp)) { 711 P.data.type = 'X'; 712 } else { 713 P.data.type = 'B'; 714 } 715 } 716 } 717 718 if (DEBUG) { 719 console.log(">>>> P:", P.coords.usrCoords, "delayedStatus:", P.delayedStatus.toString(), (P.data) ? P.data.type : " ", "\n---"); 720 } 721 722 } 723 724 if (Type.exists(P._tours)) { 725 P._tours++; 726 } 727 728 if (P._tours > 3 || P._end || cnt > 1000) { 729 // Jump out if either 730 // - we reached the end 731 // - there are more than 1000 intersection points 732 // - P._tours > 3: We went already 4 times through this path. 733 if (cnt > 1000) { 734 console.log("Clipping: _classifyDegenerateIntersections exit"); 735 } 736 if (Type.exists(P._tours)) { 737 delete P._tours; 738 } 739 break; 740 } 741 if (P.intersection) { 742 cnt++; 743 } 744 P = P._next; 745 } 746 if (DEBUG) { 747 console.log("------------------------"); 748 } 749 }, 750 751 /** 752 * At this point the degenerated intersections have been classified. 753 * Now we decide if the intersection chains of the given path 754 * ultimatively cross the other path or bounce. 755 * 756 * @param {JXG.Math.Clip.Vertex} P Start of path 757 * 758 * @see JXG.Math.Clip#markEntryExit 759 * @see JXG.Math.Clip#_classifyDegenerateIntersections 760 * @private 761 */ 762 _handleIntersectionChains: function(P) { 763 var cnt = 0, 764 start_status = 'Null', 765 P_start, 766 intersection_chain = false, 767 wait_for_exit = false, 768 DEBUG = false; 769 770 if (DEBUG) { 771 console.log("\n-------------- _handleIntersectionChains()", 772 (Type.exists(P.data))?P.data.pathname:' '); 773 } 774 while (true) { 775 if (P.intersection === true) { 776 if (DEBUG) { 777 if (P.data.type === 'T') { 778 console.log("Degenerate point", P.coords.usrCoords, P.data.type, (P.data.type === 'T')?P.delayedStatus:' '); 779 } else { 780 console.log("Intersection point", P.coords.usrCoords, P.data.type); 781 } 782 } 783 if (P.data.type === 'T') { 784 if (P.delayedStatus[0] !== 'on' && P.delayedStatus[1] === 'on') { 785 // First point of intersection chain 786 intersection_chain = true; 787 P_start = P; 788 start_status = P.delayedStatus[0]; 789 790 } else if (intersection_chain && 791 P.delayedStatus[0] === 'on' && P.delayedStatus[1] === 'on') { 792 // Interior of intersection chain 793 P.data.type = 'B'; 794 if (DEBUG) { 795 console.log("Interior", P.coords.usrCoords); 796 } 797 } else if (intersection_chain && 798 P.delayedStatus[0] === 'on' && P.delayedStatus[1] !== 'on') { 799 // Last point of intersection chain 800 intersection_chain = false; 801 if (start_status === P.delayedStatus[1]) { 802 // Intersection chain is delayed bouncing 803 P_start.data.type = 'DB'; 804 P.data.type = 'DB'; 805 if (DEBUG) { 806 console.log("Chain: delayed bouncing", P_start.coords.usrCoords, '...', P.coords.usrCoords); 807 } 808 } else { 809 // Intersection chain is delayed crossing 810 P_start.data.type = 'DX'; 811 P.data.type = 'DX'; 812 if (DEBUG) { 813 console.log("Chain: delayed crossing", P_start.coords.usrCoords, '...', P.coords.usrCoords); 814 } 815 } 816 } 817 } 818 cnt++; 819 } 820 if (P._end) { 821 wait_for_exit = true; 822 } 823 if (wait_for_exit && !intersection_chain) { 824 break; 825 } 826 if (cnt > 1000) { 827 console.log("Warning: _handleIntersectionChains: intersection chain reached maximum numbers of iterations"); 828 break; 829 } 830 P = P._next; 831 } 832 }, 833 834 /** 835 * Handle the case that all vertices of one path are contained 836 * in the other path. In this case we search for a midpoint of an edge 837 * which is not contained in the other path and add it to the path. 838 * It will be used as starting point for the entry/exit algorithm. 839 * 840 * @private 841 * @param {Array} S Subject path 842 * @param {Array} C Clip path 843 * @param {JXG.board} board JSXGraph board object. It is needed to convert between 844 * user coordinates and screen coordinates. 845 */ 846 _handleFullyDegenerateCase: function(S, C, board) { 847 var P, Q, l, M, crds, q1, q2, node, 848 i, j, leP, leQ, is_on_Q, tmp, 849 is_fully_degenerated, 850 arr = [S, C]; 851 852 for (l = 0; l < 2; l++) { 853 P = arr[l]; 854 leP = P.length; 855 for (i = 0, is_fully_degenerated = true; i < leP; i++) { 856 if (!P[i].intersection) { 857 is_fully_degenerated = false; 858 break; 859 } 860 } 861 862 if (is_fully_degenerated) { 863 // All nodes of P are also on the other path. 864 Q = arr[(l + 1) % 2]; 865 leQ = Q.length; 866 867 // We search for a midpoint of one edge of P which is not the other path and 868 // we add that midpoint to P. 869 for (i = 0; i < leP; i++) { 870 q1 = P[i].coords.usrCoords; 871 q2 = P[i]._next.coords.usrCoords; 872 873 // M is the midpoint 874 M = [(q1[0] + q2[0]) * 0.5, 875 (q1[1] + q2[1]) * 0.5, 876 (q1[2] + q2[2]) * 0.5]; 877 878 // Test if M is on path Q. If this is not the case, 879 // we take M as additional point of P. 880 for (j = 0, is_on_Q = false; j < leQ; j++) { 881 if (Math.abs(Geometry.det3p(Q[j].coords.usrCoords, Q[(j + 1) % leQ].coords.usrCoords, M)) < Mat.eps) { 882 is_on_Q = true; 883 break; 884 } 885 } 886 if (!is_on_Q) { 887 // The midpoint is added to the doubly-linked list. 888 crds = new Coords(Const.COORDS_BY_USER, M, board); 889 node = { 890 pos: i, 891 intersection: false, 892 coords: crds, 893 elementClass: Const.OBJECT_CLASS_POINT 894 }; 895 896 tmp = P[i]._next; 897 P[i]._next = node; 898 node._prev = P[i]; 899 node._next = tmp; 900 tmp._prev = node; 901 902 903 if (P[i]._end) { 904 P[i]._end = false; 905 node._end = true; 906 } 907 908 break; 909 } 910 } 911 } 912 } 913 }, 914 915 _getStatus: function(P, path) { 916 var status; 917 while (P.intersection) { 918 if (P._end) { 919 break; 920 } 921 P = P._next; 922 } 923 if (Geometry.windingNumber(P.coords.usrCoords, path) === 0) { 924 // Outside 925 status = 'entry'; 926 // console.log(P.coords.usrCoords, ' is outside') 927 } else { 928 // Inside 929 status = 'exit'; 930 // console.log(P.coords.usrCoords, ' is inside') 931 } 932 933 return [P, status]; 934 }, 935 936 /** 937 * Mark the intersection vertices of path1 as entry points or as exit points 938 * in respect to path2. 939 * <p> 940 * This is the simple algorithm as in 941 * Greiner, Günther; Kai Hormann (1998). "Efficient clipping of arbitrary polygons". 942 * ACM Transactions on Graphics. 17 (2): 71–83 943 * <p> 944 * The algorithm handles also "delayed crossings" from 945 * Erich, L. Foster, and Kai Hormann, Kai, and Romeo Traaian Popa (2019), 946 * "Clipping simple polygons with degenerate intersections", Computers & Graphics:X, 2. 947 * and - as an additional improvement - 948 * handles self intersections of delayed crossings (A.W. 2021). 949 * 950 * @private 951 * @param {Array} path1 First path 952 * @param {Array} path2 Second path 953 */ 954 markEntryExit: function(path1, path2, starters) { 955 var status, P, cnt, res, 956 i, len, start, 957 chain_start = null, 958 intersection_chain = 0, 959 DEBUG = false; 960 961 len = starters.length; 962 for (i = 0; i < len; i++) { 963 start = starters[i]; 964 if (DEBUG) { 965 console.log("\n;;;;;;;;;; Labelling phase", 966 (Type.exists(path1[start].data))?path1[start].data.pathname:' ', 967 path1[start].coords.usrCoords); 968 } 969 this._classifyDegenerateIntersections(path1[start]); 970 this._handleIntersectionChains(path1[start]); 971 if (DEBUG) { 972 console.log("\n---- back to markEntryExit"); 973 } 974 975 // Decide if the first point of the component is inside or outside 976 // of the other path. 977 res = this._getStatus(path1[start], path2); 978 P = res[0]; 979 status = res[1]; 980 if (DEBUG) { 981 console.log("Start node:", P.coords.usrCoords, status); 982 } 983 984 P._starter = true; 985 986 // Greiner-Hormann entry/exit algorithm 987 // with additional handling of delayed crossing / bouncing 988 cnt = 0; 989 chain_start = null; 990 intersection_chain = 0; 991 992 while (true) { 993 if (P.intersection === true) { 994 if (P.data.type === 'X' && intersection_chain === 1) { 995 // While we are in an intersection chain, i.e. a delayed crossing, 996 // we stumble on a crossing intersection. 997 // Probably, the other path is self intersecting. 998 // We end the intersection chain here and 999 // mark this event by setting intersection_chain = 2. 1000 chain_start.entry_exit = status; 1001 if (status === 'exit') { 1002 chain_start.data.type = 'X'; 1003 } 1004 intersection_chain = 2; 1005 } 1006 1007 if (P.data.type === 'X' || P.data.type === 'DB') { 1008 P.entry_exit = status; 1009 status = (status === 'entry') ? 'exit' : 'entry'; 1010 if (DEBUG) { 1011 console.log("mark:", P.coords.usrCoords, P.data.type, P.entry_exit); 1012 } 1013 } 1014 1015 if (P.data.type === 'DX') { 1016 if (intersection_chain === 0) { 1017 // Start of intersection chain. 1018 // No active intersection chain yet, 1019 // i.e. we did not pass a the first node of a delayed crossing. 1020 chain_start = P; 1021 intersection_chain = 1; 1022 if (DEBUG) { 1023 console.log("Start intersection chain:", P.coords.usrCoords, P.data.type, status); 1024 } 1025 1026 } else if (intersection_chain === 1) { 1027 // Active intersection chain (intersection_chain===1)! 1028 // End of delayed crossing chain reached 1029 P.entry_exit = status; 1030 chain_start.entry_exit = status; 1031 if (status === 'exit') { 1032 chain_start.data.type = 'X'; 1033 } else { 1034 P.data.type = 'X'; 1035 } 1036 status = (status === 'entry') ? 'exit' : 'entry'; 1037 1038 if (DEBUG) { 1039 console.log("mark':", chain_start.coords.usrCoords, chain_start.data.type, chain_start.entry_exit); 1040 console.log("mark:", P.coords.usrCoords, P.data.type, P.entry_exit); 1041 } 1042 chain_start = null; 1043 intersection_chain = 0; 1044 1045 } else if (intersection_chain === 2) { 1046 // The delayed crossing had been interrupted by a crossing intersection. 1047 // Now we treat the end of the delayed crossing as regular crossing. 1048 P.entry_exit = status; 1049 P.data.type = 'X'; 1050 status = (status === 'entry') ? 'exit' : 'entry'; 1051 chain_start = null; 1052 intersection_chain = 0; 1053 } 1054 } 1055 } 1056 1057 P = P._next; 1058 if (Type.exists(P._starter) || cnt > 10000) { 1059 break; 1060 } 1061 1062 cnt++; 1063 } 1064 } 1065 }, 1066 1067 /** 1068 * 1069 * @private 1070 * @param {Array} P 1071 * @param {Boolean} isBackward 1072 * @returns {Boolean} True, if the node is an intersection and is of type 'X' 1073 */ 1074 _stayOnPath: function(P, status) { 1075 var stay = true; 1076 1077 if (P.intersection && P.data.type !== 'B') { 1078 stay = (status === P.entry_exit); 1079 } 1080 return stay; 1081 }, 1082 1083 /** 1084 * Add a point to the clipping path and returns if the algorithms 1085 * arrived at an intersection point which has already been visited. 1086 * In this case, true is returned. 1087 * 1088 * @param {Array} path Resulting path 1089 * @param {JXG.Math.Clip.Vertex} vertex Point to be added 1090 * @param {Boolean} DEBUG debug output to console.log 1091 * @returns {Boolean} true: point has been visited before, false otherwise 1092 * @private 1093 */ 1094 _addVertex: function(path, vertex, DEBUG) { 1095 if (!isNaN(vertex.coords.usrCoords[1]) && !isNaN(vertex.coords.usrCoords[2])) { 1096 path.push(vertex); 1097 } 1098 if (vertex.intersection && vertex.data.done) { 1099 if (DEBUG) { 1100 console.log("Add last intersection point", vertex.coords.usrCoords, 1101 "on", vertex.data.pathname, vertex.entry_exit, 1102 vertex.data.type); 1103 } 1104 return true; 1105 } 1106 if (vertex.intersection) { 1107 vertex.data.done = true; 1108 1109 if (DEBUG) { 1110 console.log("Add intersection point", vertex.coords.usrCoords, 1111 "on", vertex.data.pathname, vertex.entry_exit, 1112 vertex.data.type); 1113 } 1114 } 1115 return false; 1116 }, 1117 1118 /** 1119 * Tracing phase of the Greiner-Hormann algorithm, see 1120 * Greiner, Günther; Kai Hormann (1998). 1121 * "Efficient clipping of arbitrary polygons". ACM Transactions on Graphics. 17 (2): 71–83 1122 * 1123 * Boolean operations on polygons are distinguished: 'intersection', 'union', 'difference'. 1124 * 1125 * @private 1126 * @param {Array} S Subject path 1127 * @param {Array} S_intersect Array containing the intersection vertices of the subject path 1128 * @param {String} clip_type contains the Boolean operation: 'intersection', 'union', or 'difference' 1129 * @return {Array} Array consisting of two arrays containing the x-coordinates and the y-coordintaes of 1130 * the resulting path. 1131 */ 1132 tracing: function(S, S_intersect, clip_type) { 1133 var P, current, start, 1134 cnt = 0, 1135 status, 1136 maxCnt = 10000, 1137 S_idx = 0, 1138 path = [], 1139 done = false, 1140 DEBUG = false; 1141 1142 if (DEBUG) { 1143 console.log("\n------ Start Phase 3"); 1144 } 1145 1146 // reverse = (clip_type === 'difference' || clip_type === 'union') ? true : false; 1147 while (S_idx < S_intersect.length && cnt < maxCnt) { 1148 // Take the first intersection node of the subject path 1149 // which is not yet included as start point. 1150 current = S_intersect[S_idx]; 1151 if (current.data.done || current.data.type !== 'X' /*|| !this._isCrossing(current, reverse)*/) { 1152 S_idx++; 1153 continue; 1154 } 1155 1156 if (DEBUG) { 1157 console.log("\nStart", current.data.pathname, current.coords.usrCoords, current.data.type, current.entry_exit, S_idx); 1158 } 1159 if (path.length > 0) { // Add a new path 1160 path.push([NaN, NaN]); 1161 } 1162 1163 // Start now the tracing with that node of the subject path 1164 start = current.data.idx; 1165 P = S; 1166 1167 done = this._addVertex(path, current, DEBUG); 1168 status = current.entry_exit; 1169 do { 1170 if (done) { 1171 break; 1172 } 1173 // 1174 // Decide if we follow the current path forward or backward. 1175 // for example, in case the clipping is of type "intersection" 1176 // and the current intersection node is of type entry, we go forward. 1177 // 1178 if ((clip_type === 'intersection' && current.entry_exit === 'entry') || 1179 (clip_type === 'union' && current.entry_exit === 'exit') || 1180 (clip_type === 'difference' && (P === S) === (current.entry_exit === 'exit')) ) { 1181 1182 if (DEBUG) { 1183 console.log("Go forward on", current.data.pathname, current.entry_exit); 1184 } 1185 1186 // 1187 // Take the next nodes and add them to the path 1188 // as long as they are not intersection nodes of type 'X'. 1189 // 1190 do { 1191 current = current._next; 1192 done = this._addVertex(path, current, DEBUG); 1193 if (done) { 1194 break; 1195 } 1196 } while (this._stayOnPath(current, status)); 1197 cnt++; 1198 } else { 1199 if (DEBUG) { 1200 console.log("Go backward on", current.data.pathname); 1201 } 1202 // 1203 // Here, we go backward: 1204 // Take the previous nodes and add them to the path 1205 // as long as they are not intersection nodes of type 'X'. 1206 // 1207 do { 1208 current = current._prev; 1209 done = this._addVertex(path, current, DEBUG); 1210 if (done) { 1211 break; 1212 } 1213 } while (this._stayOnPath(current, status)); 1214 cnt++; 1215 } 1216 1217 if (done) { 1218 break; 1219 } 1220 1221 if (!current.neighbour) { 1222 console.log("Tracing: emergency break - no neighbour!!!!!!!!!!!!!!!!!", cnt); 1223 return [[0], [0]]; 1224 } 1225 // 1226 // We stopped the forward or backward loop, because we've 1227 // arrived at a crossing intersection node, i.e. we have to 1228 // switch to the other path now. 1229 if (DEBUG) { 1230 console.log("Switch from", current.coords.usrCoords, current.data.pathname, "to", 1231 current.neighbour.coords.usrCoords, "on", current.neighbour.data.pathname); 1232 } 1233 current = current.neighbour; 1234 if (current.data.done) { 1235 break; 1236 } 1237 current.data.done = true; 1238 status = current.entry_exit; 1239 1240 // if (current.data.done) { 1241 // // We arrived at an intersection node which is already 1242 // // added to the clipping path. 1243 // // We add it again to close the clipping path and jump out of the 1244 // // loop. 1245 // path.push(current); 1246 // if (DEBUG) { 1247 // console.log("Push last", current.coords.usrCoords); 1248 // } 1249 // break; 1250 // } 1251 P = current.data.path; 1252 1253 // Polygon closed: 1254 // if (DEBUG) { 1255 // console.log("End of loop:", "start=", start, "idx=", current.data.idx); 1256 // } 1257 // } while (!(current.data.pathname === 'S' && current.data.idx === start) && cnt < maxCnt); 1258 } while (current.data.idx !== start && cnt < maxCnt); 1259 1260 if (cnt >= maxCnt) { 1261 console.log("Tracing: stopping an infinite loop!", cnt); 1262 } 1263 1264 S_idx++; 1265 } 1266 return this._getCoordsArrays(path, false); 1267 }, 1268 1269 /** 1270 * Handle path clipping if one of the two paths is empty. 1271 * @private 1272 * @param {Array} S First path, array of JXG.Coords 1273 * @param {Array} C Second path, array of JXG.Coords 1274 * @param {String} clip_type Type of Boolean operation: 'intersection', 'union', 'differrence'. 1275 * @return {Boolean} true, if one of the input paths is empty, false otherwise. 1276 */ 1277 isEmptyCase: function(S, C, clip_type) { 1278 if (clip_type === 'intersection' && (S.length === 0 || C.length === 0)) { 1279 return true; 1280 } 1281 if (clip_type === 'union' && (S.length === 0 && C.length === 0)) { 1282 return true; 1283 } 1284 if (clip_type === 'difference' && S.length === 0) { 1285 return true; 1286 } 1287 1288 return false; 1289 }, 1290 1291 _getCoordsArrays: function(path, doClose) { 1292 var pathX = [], 1293 pathY = [], 1294 i, le = path.length; 1295 1296 for (i = 0; i < le; i++) { 1297 if (path[i].coords) { 1298 pathX.push(path[i].coords.usrCoords[1]); 1299 pathY.push(path[i].coords.usrCoords[2]); 1300 } else { 1301 pathX.push(path[i][0]); 1302 pathY.push(path[i][1]); 1303 } 1304 } 1305 if (doClose && le > 0) { 1306 if (path[0].coords) { 1307 pathX.push(path[0].coords.usrCoords[1]); 1308 pathY.push(path[0].coords.usrCoords[2]); 1309 } else { 1310 pathX.push(path[0][0]); 1311 pathY.push(path[0][1]); 1312 } 1313 } 1314 1315 return [pathX, pathY]; 1316 }, 1317 1318 /** 1319 * Handle cases when there are no intersection points of the two paths. This is the case if the 1320 * paths are disjoint or one is contained in the other. 1321 * @private 1322 * @param {Array} S First path, array of JXG.Coords 1323 * @param {Array} C Second path, array of JXG.Coords 1324 * @param {String} clip_type Type of Boolean operation: 'intersection', 'union', 'differrence'. 1325 * @return {Array} Array consisting of two arrays containing the x-coordinates and the y-coordinates of 1326 * the resulting path. 1327 */ 1328 handleEmptyIntersection: function(S, C, clip_type) { 1329 var P, Q, 1330 doClose = false, 1331 path = []; 1332 1333 // Handle trivial cases 1334 if (S.length === 0) { 1335 if (clip_type === 'union') { 1336 // S cup C = C 1337 path = C; 1338 } else { 1339 // S cap C = S \ C = {} 1340 path = []; 1341 } 1342 return this._getCoordsArrays(path, true); 1343 } 1344 if (C.length === 0) { 1345 if (clip_type === 'intersection') { 1346 // S cap C = {} 1347 path = []; 1348 } else { 1349 // S cup C = S \ C = S 1350 path = S; 1351 } 1352 return this._getCoordsArrays(path, true); 1353 } 1354 1355 // From now on, both paths have non-zero length. 1356 // The two paths have no crossing intersections, 1357 // but there might be bouncing intersections. 1358 1359 // First, we find -- if possible -- on each path a point which is not an intersection point. 1360 if (S.length > 0) { 1361 P = S[0]; 1362 while (P.intersection) { 1363 P = P._next; 1364 if (P._end) { 1365 break; 1366 } 1367 } 1368 } 1369 if (C.length > 0) { 1370 Q = C[0]; 1371 while (Q.intersection) { 1372 Q = Q._next; 1373 if (Q._end) { 1374 break; 1375 } 1376 } 1377 } 1378 1379 // Test if one curve is contained by the other 1380 if (Geometry.windingNumber(P.coords.usrCoords, C) === 0) { 1381 // P is outside of C: 1382 // Either S is disjoint from C or C is inside of S 1383 if (Geometry.windingNumber(Q.coords.usrCoords, S) !== 0) { 1384 // C is inside of S, i.e. C subset of S 1385 1386 if (clip_type === 'union') { 1387 path = path.concat(S); 1388 path.push(S[0]); 1389 } else if (clip_type === 'difference') { 1390 path = path.concat(S); 1391 path.push(S[0]); 1392 if (Geometry.signedPolygon(S) * Geometry.signedPolygon(C) > 0) { 1393 // Pathes have same orientation, we have to revert one. 1394 path.reverse(); 1395 } 1396 path.push([NaN, NaN]); 1397 } 1398 if (clip_type === 'difference' || clip_type === 'intersection') { 1399 path = path.concat(C); 1400 path.push(C[0]); 1401 doClose = false; 1402 } 1403 } else { // The curves are disjoint 1404 if (clip_type === 'difference') { 1405 path = path.concat(S); 1406 doClose = true; 1407 } else if (clip_type === 'union') { 1408 path = path.concat(S); 1409 path.push(S[0]); 1410 path.push([NaN, NaN]); 1411 path = path.concat(C); 1412 path.push(C[0]); 1413 } 1414 } 1415 } else { 1416 // S inside of C, i.e. S subset of C 1417 if (clip_type === 'intersection') { 1418 path = path.concat(S); 1419 doClose = true; 1420 } else if (clip_type === 'union') { 1421 path = path.concat(C); 1422 path.push(C[0]); 1423 } 1424 1425 // 'difference': path is empty 1426 } 1427 1428 return this._getCoordsArrays(path, doClose); 1429 }, 1430 1431 /** 1432 * Count intersection points of type 'X'. 1433 * @param {JXG.Mat.Clip.Vertex} intersections 1434 * @returns Number 1435 * @private 1436 */ 1437 _countCrossingIntersections: function(intersections) { 1438 var i, 1439 le = intersections.length, 1440 sum = 0; 1441 1442 for (i = 0; i < le; i++) { 1443 if (intersections[i].data.type === 'X') { 1444 sum++; 1445 } 1446 } 1447 return sum; 1448 }, 1449 1450 /** 1451 * Create path from all sorts of input elements and convert it 1452 * to a suitable input path for greinerHormann(). 1453 * 1454 * @private 1455 * @param {Object} obj Maybe curve, arc, sector, circle, polygon, array of points, array of JXG.Coords, 1456 * array of coordinate pairs. 1457 * @param {JXG.Board} board JSXGraph board object. It is needed to convert between 1458 * user coordinates and screen coordinates. 1459 * @returns {Array} Array of JXG.Coords elements containing a path. 1460 * @see JXG.Math.Clip#greinerHormann 1461 */ 1462 _getPath: function(obj, board) { 1463 var i, len, r, rad, angle, alpha, 1464 steps, 1465 S = []; 1466 1467 // Collect all points into path array S 1468 if (obj.elementClass === Const.OBJECT_CLASS_CURVE && 1469 (obj.type === Const.OBJECT_TYPE_ARC || obj.type === Const.OBJECT_TYPE_SECTOR)) { 1470 angle = Geometry.rad(obj.radiuspoint, obj.center, obj.anglepoint); 1471 steps = Math.floor(angle * 180 / Math.PI); 1472 r = obj.Radius(); 1473 rad = angle / steps; 1474 alpha = Math.atan2(obj.radiuspoint.coords.usrCoords[2] - obj.center.coords.usrCoords[2], 1475 obj.radiuspoint.coords.usrCoords[1] - obj.center.coords.usrCoords[1]); 1476 1477 if (obj.type === Const.OBJECT_TYPE_SECTOR) { 1478 this._addToList(S, obj.center.coords, 0); 1479 } 1480 for (i = 0; i <= steps; i++) { 1481 this._addToList(S, new Coords(Const.COORDS_BY_USER, [ 1482 obj.center.coords.usrCoords[0], 1483 obj.center.coords.usrCoords[1] + Math.cos(i * rad + alpha) * r, 1484 obj.center.coords.usrCoords[2] + Math.sin(i * rad + alpha) * r 1485 ], board), i + 1); 1486 } 1487 if (obj.type === Const.OBJECT_TYPE_SECTOR) { 1488 this._addToList(S, obj.center.coords, steps + 2); 1489 } 1490 1491 } else if (obj.elementClass === Const.OBJECT_CLASS_CURVE && Type.exists(obj.points)) { 1492 len = obj.numberPoints; 1493 for (i = 0; i < len; i++) { 1494 this._addToList(S, obj.points[i], i); 1495 } 1496 } else if (obj.type === Const.OBJECT_TYPE_POLYGON) { 1497 for (i = 0; i < obj.vertices.length; i++) { 1498 this._addToList(S, obj.vertices[i].coords, i); 1499 } 1500 } else if (obj.elementClass === Const.OBJECT_CLASS_CIRCLE) { 1501 steps = 359; 1502 r = obj.Radius(); 1503 rad = 2 * Math.PI / steps; 1504 for (i = 0; i <= steps; i++) { 1505 this._addToList(S, new Coords(Const.COORDS_BY_USER, [ 1506 obj.center.coords.usrCoords[0], 1507 obj.center.coords.usrCoords[1] + Math.cos(i * rad) * r, 1508 obj.center.coords.usrCoords[2] + Math.sin(i * rad) * r 1509 ], board), i); 1510 } 1511 } else if (Type.isArray(obj)) { 1512 len = obj.length; 1513 for (i = 0; i < len; i++) { 1514 if (Type.exists(obj[i].coords)) { 1515 // Point type 1516 this._addToList(S, obj[i].coords, i); 1517 } else if (Type.isArray(obj[i])) { 1518 // Coordinate pair 1519 this._addToList(S, new Coords(Const.COORDS_BY_USER, obj[i], board), i); 1520 } else if (Type.exists(obj[i].usrCoords)) { 1521 // JXG.Coordinates 1522 this._addToList(S, obj[i], i); 1523 } 1524 } 1525 } 1526 1527 return S; 1528 }, 1529 1530 /** 1531 * Determine the intersection, union or difference of two closed paths. 1532 * <p> 1533 * This is an implementation of the Greiner-Hormann algorithm, see 1534 * Günther Greiner and Kai Hormann (1998). 1535 * "Efficient clipping of arbitrary polygons". ACM Transactions on Graphics. 17 (2): 71–83. 1536 * and 1537 * Erich, L. Foster, and Kai Hormann, Kai, and Romeo Traaian Popa (2019), 1538 * "Clipping simple polygons with degenerate intersections", Computers & Graphics:X, 2. 1539 * <p> 1540 * It is assumed that the pathes are closed, whereby it does not matter if the last point indeed 1541 * equals the first point. In contrast to the original Greiner-Hormann algorithm, 1542 * this algorithm can cope with many degenerate cases. A degenerate case is a vertext of one path 1543 * which is contained in the other path. 1544 * <p> 1545 * 1546 * <p>Problematic are: 1547 * <ul> 1548 * <li>degenerate cases where one path additionally has self-intersections 1549 * <li>differences with one path having self-intersections. 1550 * </ul> 1551 * 1552 * @param {JXG.Circle|JXG.Curve|JXG.Polygon} subject First closed path, usually called 'subject'. 1553 * Maybe curve, arc, sector, circle, polygon, array of points, array of JXG.Coords, 1554 * array of coordinate pairs. 1555 * @param {JXG.Circle|JXG.Curve|JXG.Polygon} clip Second closed path, usually called 'clip'. 1556 * Maybe curve, arc, sector, circle, polygon, array of points, array of JXG.Coords, 1557 * array of coordinate pairs. 1558 * @param {String} clip_type Determines the type of boolean operation on the two paths. 1559 * Possible values are 'intersection', 'union', or 'difference'. 1560 * @param {JXG.Board} board JSXGraph board object. It is needed to convert between 1561 * user coordinates and screen coordinates. 1562 * @return {Array} Array consisting of two arrays containing the x-coordinates and the y-coordinates of 1563 * the resulting path. 1564 * 1565 * @see JXG.Math.Clip#intersection 1566 * @see JXG.Math.Clip#union 1567 * @see JXG.Math.Clip#difference 1568 * 1569 * @example 1570 * var curve1 = board.create('curve', [ 1571 * [-3, 3, 0, -3], 1572 * [3, 3, 0, 3] 1573 * ], 1574 * {strokeColor: 'black'}); 1575 * 1576 * var curve2 = board.create('curve', [ 1577 * [-4, 4, 0, -4], 1578 * [2, 2, 4, 2] 1579 * ], 1580 * {strokeColor: 'blue'}); 1581 * 1582 * var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.6}); 1583 * clip_path.updateDataArray = function() { 1584 * var a = JXG.Math.Clip.greinerHormann(curve2, curve1, 'intersection', this.board); 1585 * 1586 * this.dataX = a[0]; 1587 * this.dataY = a[1]; 1588 * }; 1589 * 1590 * board.update(); 1591 * 1592 * </pre><div id="JXG9d2a6acf-a43b-4035-8f8a-9b1bee580210" class="jxgbox" style="width: 300px; height: 300px;"></div> 1593 * <script type="text/javascript"> 1594 * (function() { 1595 * var board = JXG.JSXGraph.initBoard('JXG9d2a6acf-a43b-4035-8f8a-9b1bee580210', 1596 * {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false}); 1597 * 1598 * var curve1 = board.create('curve', [ 1599 * [-3, 3, 0, -3], 1600 * [3, 3, 0, 3] 1601 * ], 1602 * {strokeColor: 'black'}); 1603 * 1604 * var curve2 = board.create('curve', [ 1605 * [-4, 4, 0, -4], 1606 * [2, 2, 4, 2] 1607 * ], 1608 * {strokeColor: 'blue'}); 1609 * 1610 * var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.6}); 1611 * clip_path.updateDataArray = function() { 1612 * var a = JXG.Math.Clip.greinerHormann(curve2, curve1, 'intersection', this.board); 1613 * 1614 * this.dataX = a[0]; 1615 * this.dataY = a[1]; 1616 * }; 1617 * 1618 * board.update(); 1619 * 1620 * })(); 1621 * 1622 * </script><pre> 1623 * 1624 * @example 1625 * var curve1 = board.create('curve', [ 1626 * [-3, 3, 0, -3], 1627 * [3, 3, 0, 3] 1628 * ], 1629 * {strokeColor: 'black', fillColor: 'none', fillOpacity: 0.8}); 1630 * 1631 * var curve2 = board.create('polygon', [[3, 4], [-4, 0], [-4, 4]], 1632 * {strokeColor: 'blue', fillColor: 'none'}); 1633 * 1634 * var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.6}); 1635 * clip_path.updateDataArray = function() { 1636 * var a = JXG.Math.Clip.greinerHormann(curve1, curve2, 'union', this.board); 1637 * this.dataX = a[0]; 1638 * this.dataY = a[1]; 1639 * }; 1640 * 1641 * board.update(); 1642 * 1643 * </pre><div id="JXG6075c918-4d57-4b72-b600-6597a6a4f44e" class="jxgbox" style="width: 300px; height: 300px;"></div> 1644 * <script type="text/javascript"> 1645 * (function() { 1646 * var board = JXG.JSXGraph.initBoard('JXG6075c918-4d57-4b72-b600-6597a6a4f44e', 1647 * {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false}); 1648 * var curve1 = board.create('curve', [ 1649 * [-3, 3, 0, -3], 1650 * [3, 3, 0, 3] 1651 * ], 1652 * {strokeColor: 'black', fillColor: 'none', fillOpacity: 0.8}); 1653 * 1654 * var curve2 = board.create('polygon', [[3, 4], [-4, 0], [-4, 4]], 1655 * {strokeColor: 'blue', fillColor: 'none'}); 1656 * 1657 * 1658 * var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.6}); 1659 * clip_path.updateDataArray = function() { 1660 * var a = JXG.Math.Clip.greinerHormann(curve1, curve2, 'union', this.board); 1661 * this.dataX = a[0]; 1662 * this.dataY = a[1]; 1663 * }; 1664 * 1665 * board.update(); 1666 * 1667 * })(); 1668 * 1669 * </script><pre> 1670 * 1671 * @example 1672 * var curve1 = board.create('curve', [ 1673 * [-4, 4, 0, -4], 1674 * [4, 4, -2, 4] 1675 * ], 1676 * {strokeColor: 'black', fillColor: 'none', fillOpacity: 0.8}); 1677 * 1678 * var curve2 = board.create('circle', [[0, 0], [0, -2]], 1679 * {strokeColor: 'blue', strokeWidth: 1, fillColor: 'red', fixed: true, fillOpacity: 0.3, 1680 * center: {visible: true, size: 5}, point2: {size: 5}}); 1681 * 1682 * var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.6}); 1683 * clip_path.updateDataArray = function() { 1684 * var a = JXG.Math.Clip.greinerHormann(curve1, curve2, 'difference', this.board); 1685 * 1686 * this.dataX = a[0]; 1687 * this.dataY = a[1]; 1688 * }; 1689 * 1690 * board.update(); 1691 * 1692 * </pre><div id="JXG46b3316b-5ab9-4928-9473-ccb476ca4185" class="jxgbox" style="width: 300px; height: 300px;"></div> 1693 * <script type="text/javascript"> 1694 * (function() { 1695 * var board = JXG.JSXGraph.initBoard('JXG46b3316b-5ab9-4928-9473-ccb476ca4185', 1696 * {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false}); 1697 * var curve1 = board.create('curve', [ 1698 * [-4, 4, 0, -4], 1699 * [4, 4, -2, 4] 1700 * ], 1701 * {strokeColor: 'black', fillColor: 'none', fillOpacity: 0.8}); 1702 * 1703 * var curve2 = board.create('circle', [[0, 0], [0, -2]], 1704 * {strokeColor: 'blue', strokeWidth: 1, fillColor: 'red', fixed: true, fillOpacity: 0.3, 1705 * center: {visible: true, size: 5}, point2: {size: 5}}); 1706 * 1707 * 1708 * var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.6}); 1709 * clip_path.updateDataArray = function() { 1710 * var a = JXG.Math.Clip.greinerHormann(curve1, curve2, 'difference', this.board); 1711 * 1712 * this.dataX = a[0]; 1713 * this.dataY = a[1]; 1714 * }; 1715 * 1716 * board.update(); 1717 * 1718 * })(); 1719 * 1720 * </script><pre> 1721 * 1722 * @example 1723 * var clip_path = board.create('curve', [[], []], {strokeWidth: 1, fillColor: 'yellow', fillOpacity: 0.6}); 1724 * clip_path.updateDataArray = function() { 1725 * var bbox = this.board.getBoundingBox(), 1726 * canvas, triangle; 1727 * 1728 * canvas = [[bbox[0], bbox[1]], // ul 1729 * [bbox[0], bbox[3]], // ll 1730 * [bbox[2], bbox[3]], // lr 1731 * [bbox[2], bbox[1]], // ur 1732 * [bbox[0], bbox[1]]] // ul 1733 * triangle = [[-1,1], [1,1], [0,-1], [-1,1]]; 1734 * 1735 * var a = JXG.Math.Clip.greinerHormann(canvas, triangle, 'difference', this.board); 1736 * this.dataX = a[0]; 1737 * this.dataY = a[1]; 1738 * }; 1739 * 1740 * </pre><div id="JXGe94da07a-2a01-4498-ad62-f71a327f8e25" class="jxgbox" style="width: 300px; height: 300px;"></div> 1741 * <script type="text/javascript"> 1742 * (function() { 1743 * var board = JXG.JSXGraph.initBoard('JXGe94da07a-2a01-4498-ad62-f71a327f8e25', 1744 * {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false}); 1745 * var clip_path = board.create('curve', [[], []], {strokeWidth: 1, fillColor: 'yellow', fillOpacity: 0.6}); 1746 * clip_path.updateDataArray = function() { 1747 * var bbox = this.board.getBoundingBox(), 1748 * canvas, triangle; 1749 * 1750 * canvas = [[bbox[0], bbox[1]], // ul 1751 * [bbox[0], bbox[3]], // ll 1752 * [bbox[2], bbox[3]], // lr 1753 * [bbox[2], bbox[1]], // ur 1754 * [bbox[0], bbox[1]]] // ul 1755 * triangle = [[-1,1], [1,1], [0,-1], [-1,1]]; 1756 * 1757 * var a = JXG.Math.Clip.greinerHormann(canvas, triangle, 'difference', this.board); 1758 * this.dataX = a[0]; 1759 * this.dataY = a[1]; 1760 * }; 1761 * 1762 * })(); 1763 * 1764 * </script><pre> 1765 * 1766 */ 1767 greinerHormann: function(subject, clip, clip_type, board) { //}, 1768 // subject_first_point_type, clip_first_point_type) { 1769 1770 var len, S = [], 1771 C = [], 1772 S_intersect = [], 1773 // C_intersect = [], 1774 S_starters, 1775 C_starters, 1776 res = [], 1777 DEBUG = false; 1778 1779 if (DEBUG) { 1780 console.log("\n------------ GREINER-HORMANN --------------"); 1781 } 1782 // Collect all subject points into subject array S 1783 S = this._getPath(subject, board); 1784 len = S.length; 1785 if (len > 0 && Geometry.distance(S[0].coords.usrCoords, S[len - 1].coords.usrCoords, 3) < Mat.eps) { 1786 S.pop(); 1787 } 1788 1789 // Collect all points into clip array C 1790 C = this._getPath(clip, board); 1791 len = C.length; 1792 if (len > 0 && Geometry.distance(C[0].coords.usrCoords, C[len - 1].coords.usrCoords, 3) < Mat.eps * Mat.eps) { 1793 C.pop(); 1794 } 1795 1796 // Handle cases where at least one of the paths is empty 1797 if (this.isEmptyCase(S, C, clip_type)) { 1798 return [[], []]; 1799 } 1800 1801 // Add pointers for doubly linked lists 1802 S_starters = this.makeDoublyLinkedList(S); 1803 C_starters = this.makeDoublyLinkedList(C); 1804 1805 if (DEBUG) { 1806 this._print_array(S); 1807 console.log("Components:", S_starters); 1808 this._print_array(C); 1809 console.log("Components:", C_starters); 1810 } 1811 1812 res = this.findIntersections(S, C, board); 1813 S_intersect = res[0]; 1814 1815 this._handleFullyDegenerateCase(S, C, board); 1816 1817 // Phase 2: mark intersection points as entry or exit points 1818 this.markEntryExit(S, C, S_starters); 1819 1820 // if (S[0].coords.distance(Const.COORDS_BY_USER, C[0].coords) === 0) { 1821 // // Randomly disturb the first point of the second path 1822 // // if both paths start at the same point. 1823 // C[0].usrCoords[1] *= 1 + Math.random() * 0.0001 - 0.00005; 1824 // C[0].usrCoords[2] *= 1 + Math.random() * 0.0001 - 0.00005; 1825 // } 1826 this.markEntryExit(C, S, C_starters); 1827 1828 // Handle cases without intersections 1829 if (this._countCrossingIntersections(S_intersect) === 0) { 1830 return this.handleEmptyIntersection(S, C, clip_type); 1831 } 1832 1833 // Phase 3: tracing 1834 return this.tracing(S, S_intersect, clip_type); 1835 }, 1836 1837 /** 1838 * Union of two closed paths. The paths could be JSXGraph elements circle, curve, or polygon. 1839 * Computed by the Greiner-Hormann algorithm. 1840 * 1841 * @param {JXG.Circle|JXG.Curve|JXG.Polygon} subject First closed path. 1842 * @param {JXG.Circle|JXG.Curve|JXG.Polygon} clip Second closed path. 1843 * @param {JXG.Board} board JSXGraph board object. It is needed to convert between 1844 * user coordinates and screen coordinates. 1845 * @return {Array} Array consisting of two arrays containing the x-coordinates and the y-coordinates of 1846 * the resulting path. 1847 * 1848 * @see JXG.Math.Clip#greinerHormann 1849 * @see JXG.Math.Clip#intersection 1850 * @see JXG.Math.Clip#difference 1851 * 1852 * @example 1853 * var curve1 = board.create('curve', [ 1854 * [-3, 3, 0, -3], 1855 * [3, 3, 0, 3] 1856 * ], 1857 * {strokeColor: 'black'}); 1858 * 1859 * var curve2 = board.create('polygon', [[3, 4], [-4, 0], [-4, 4]], 1860 * {strokeColor: 'blue', fillColor: 'none'}); 1861 * 1862 * var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.3}); 1863 * clip_path.updateDataArray = function() { 1864 * var a = JXG.Math.Clip.union(curve1, curve2, this.board); 1865 * this.dataX = a[0]; 1866 * this.dataY = a[1]; 1867 * }; 1868 * 1869 * board.update(); 1870 * 1871 * </pre><div id="JXG7c5204aa-3824-4464-819c-80df7bf1d917" class="jxgbox" style="width: 300px; height: 300px;"></div> 1872 * <script type="text/javascript"> 1873 * (function() { 1874 * var board = JXG.JSXGraph.initBoard('JXG7c5204aa-3824-4464-819c-80df7bf1d917', 1875 * {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false}); 1876 * var curve1 = board.create('curve', [ 1877 * [-3, 3, 0, -3], 1878 * [3, 3, 0, 3] 1879 * ], 1880 * {strokeColor: 'black'}); 1881 * 1882 * var curve2 = board.create('polygon', [[3, 4], [-4, 0], [-4, 4]], 1883 * {strokeColor: 'blue', fillColor: 'none'}); 1884 * 1885 * 1886 * var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.3}); 1887 * clip_path.updateDataArray = function() { 1888 * var a = JXG.Math.Clip.union(curve1, curve2, this.board); 1889 * this.dataX = a[0]; 1890 * this.dataY = a[1]; 1891 * }; 1892 * 1893 * board.update(); 1894 * 1895 * })(); 1896 * 1897 * </script><pre> 1898 * 1899 */ 1900 union: function(path1, path2, board) { 1901 return this.greinerHormann(path1, path2, 'union', board); 1902 }, 1903 1904 /** 1905 * Intersection of two closed paths. The paths could be JSXGraph elements circle, curve, or polygon. 1906 * Computed by the Greiner-Hormann algorithm. 1907 * 1908 * @param {JXG.Circle|JXG.Curve|JXG.Polygon} subject First closed path. 1909 * @param {JXG.Circle|JXG.Curve|JXG.Polygon} clip Second closed path. 1910 * @param {JXG.Board} board JSXGraph board object. It is needed to convert between 1911 * user coordinates and screen coordinates. 1912 * @return {Array} Array consisting of two arrays containing the x-coordinates and the y-coordinates of 1913 * the resulting path. 1914 * 1915 * @see JXG.Math.Clip#greinerHormann 1916 * @see JXG.Math.Clip#union 1917 * @see JXG.Math.Clip#difference 1918 * 1919 * @example 1920 * var p = []; 1921 * p.push(board.create('point', [0, -5])); 1922 * p.push(board.create('point', [-5, 0])); 1923 * p.push(board.create('point', [-3, 3])); 1924 * 1925 * var curve1 = board.create('ellipse', p, 1926 * {strokeColor: 'black'}); 1927 * 1928 * var curve2 = board.create('curve', [function(phi){return 4 * Math.cos(2*phi); }, 1929 * [0, 0], 1930 * 0, 2 * Math.PI], 1931 * {curveType:'polar', strokeColor: 'blue', strokewidth:1}); 1932 * 1933 * var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.3}); 1934 * clip_path.updateDataArray = function() { 1935 * var a = JXG.Math.Clip.intersection(curve2, curve1, this.board); 1936 * 1937 * this.dataX = a[0]; 1938 * this.dataY = a[1]; 1939 * }; 1940 * 1941 * board.update(); 1942 * 1943 * </pre><div id="JXG7ad547eb-7b6c-4a1a-a4d4-4ed298fc7998" class="jxgbox" style="width: 300px; height: 300px;"></div> 1944 * <script type="text/javascript"> 1945 * (function() { 1946 * var board = JXG.JSXGraph.initBoard('JXG7ad547eb-7b6c-4a1a-a4d4-4ed298fc7998', 1947 * {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false}); 1948 * var p = []; 1949 * p.push(board.create('point', [0, -5])); 1950 * p.push(board.create('point', [-5, 0])); 1951 * p.push(board.create('point', [-3, 3])); 1952 * 1953 * var curve1 = board.create('ellipse', p, 1954 * {strokeColor: 'black'}); 1955 * 1956 * var curve2 = board.create('curve', [function(phi){return 4 * Math.cos(2*phi); }, 1957 * [0, 0], 1958 * 0, 2 * Math.PI], 1959 * {curveType:'polar', strokeColor: 'blue', strokewidth:1}); 1960 * 1961 * 1962 * var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.3}); 1963 * clip_path.updateDataArray = function() { 1964 * var a = JXG.Math.Clip.intersection(curve2, curve1, this.board); 1965 * 1966 * this.dataX = a[0]; 1967 * this.dataY = a[1]; 1968 * }; 1969 * 1970 * board.update(); 1971 * 1972 * })(); 1973 * 1974 * </script><pre> 1975 * 1976 * 1977 */ 1978 intersection: function(path1, path2, board) { 1979 return this.greinerHormann(path1, path2, 'intersection', board); 1980 }, 1981 1982 /** 1983 * Difference of two closed paths, i.e. path1 minus path2. 1984 * The paths could be JSXGraph elements circle, curve, or polygon. 1985 * Computed by the Greiner-Hormann algorithm. 1986 * 1987 * @param {JXG.Circle|JXG.Curve|JXG.Polygon} subject First closed path. 1988 * @param {JXG.Circle|JXG.Curve|JXG.Polygon} clip Second closed path. 1989 * @param {JXG.Board} board JSXGraph board object. It is needed to convert between 1990 * user coordinates and screen coordinates. 1991 * @return {Array} Array consisting of two arrays containing the x-coordinates and the y-coordinates of 1992 * the resulting path. 1993 * 1994 * @see JXG.Math.Clip#greinerHormann 1995 * @see JXG.Math.Clip#intersection 1996 * @see JXG.Math.Clip#union 1997 * 1998 * @example 1999 * var curve1 = board.create('polygon', [[-4, 4], [4, 4], [0, -1]], 2000 * {strokeColor: 'blue', fillColor: 'none'}); 2001 * 2002 * var curve2 = board.create('curve', [ 2003 * [-1, 1, 0, -1], 2004 * [1, 1, 3, 1] 2005 * ], 2006 * {strokeColor: 'black', fillColor: 'none', fillOpacity: 0.8}); 2007 * 2008 * var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.3}); 2009 * clip_path.updateDataArray = function() { 2010 * var a = JXG.Math.Clip.difference(curve1, curve2, this.board); 2011 * this.dataX = a[0]; 2012 * this.dataY = a[1]; 2013 * }; 2014 * 2015 * board.update(); 2016 * 2017 * </pre><div id="JXGc5ce6bb3-146c-457f-a48b-6b9081fb68a3" class="jxgbox" style="width: 300px; height: 300px;"></div> 2018 * <script type="text/javascript"> 2019 * (function() { 2020 * var board = JXG.JSXGraph.initBoard('JXGc5ce6bb3-146c-457f-a48b-6b9081fb68a3', 2021 * {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false}); 2022 * var curve1 = board.create('polygon', [[-4, 4], [4, 4], [0, -1]], 2023 * {strokeColor: 'blue', fillColor: 'none'}); 2024 * 2025 * var curve2 = board.create('curve', [ 2026 * [-1, 1, 0, -1], 2027 * [1, 1, 3, 1] 2028 * ], 2029 * {strokeColor: 'black', fillColor: 'none', fillOpacity: 0.8}); 2030 * 2031 * 2032 * var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.3}); 2033 * clip_path.updateDataArray = function() { 2034 * var a = JXG.Math.Clip.difference(curve1, curve2, this.board); 2035 * this.dataX = a[0]; 2036 * this.dataY = a[1]; 2037 * }; 2038 * 2039 * board.update(); 2040 * 2041 * })(); 2042 * 2043 * </script><pre> 2044 * 2045 */ 2046 difference: function(path1, path2, board) { 2047 return this.greinerHormann(path1, path2, 'difference', board); 2048 } 2049 }; //); 2050 2051 JXG.extend(Mat.Clip, /** @lends JXG.Math.Clip */ { 2052 }); 2053 2054 return Mat.Clip; 2055 }); 2056