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