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