1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 /** 18 * @author Denis M. Kishenko 19 * @version $Revision$ 20 */ 21 package org.apache.harmony.awt.gl; 22 23 import java.awt.Shape; 24 import java.awt.geom.PathIterator; 25 26 public class Crossing { 27 28 /** 29 * Allowable tolerance for bounds comparison 30 */ 31 static final double DELTA = 1E-5; 32 33 /** 34 * If roots have distance less then <code>ROOT_DELTA</code> they are double 35 */ 36 static final double ROOT_DELTA = 1E-10; 37 38 /** 39 * Rectangle cross segment 40 */ 41 public static final int CROSSING = 255; 42 43 /** 44 * Unknown crossing result 45 */ 46 static final int UNKNOWN = 254; 47 48 /** 49 * Solves quadratic equation 50 * @param eqn - the coefficients of the equation 51 * @param res - the roots of the equation 52 * @return a number of roots 53 */ 54 public static int solveQuad(double eqn[], double res[]) { 55 double a = eqn[2]; 56 double b = eqn[1]; 57 double c = eqn[0]; 58 int rc = 0; 59 if (a == 0.0) { 60 if (b == 0.0) { 61 return -1; 62 } 63 res[rc++] = -c / b; 64 } else { 65 double d = b * b - 4.0 * a * c; 66 // d < 0.0 67 if (d < 0.0) { 68 return 0; 69 } 70 d = Math.sqrt(d); 71 res[rc++] = (- b + d) / (a * 2.0); 72 // d != 0.0 73 if (d != 0.0) { 74 res[rc++] = (- b - d) / (a * 2.0); 75 } 76 } 77 return fixRoots(res, rc); 78 } 79 80 /** 81 * Solves cubic equation 82 * @param eqn - the coefficients of the equation 83 * @param res - the roots of the equation 84 * @return a number of roots 85 */ 86 public static int solveCubic(double eqn[], double res[]) { 87 double d = eqn[3]; 88 if (d == 0) { 89 return solveQuad(eqn, res); 90 } 91 double a = eqn[2] / d; 92 double b = eqn[1] / d; 93 double c = eqn[0] / d; 94 int rc = 0; 95 96 double Q = (a * a - 3.0 * b) / 9.0; 97 double R = (2.0 * a * a * a - 9.0 * a * b + 27.0 * c) / 54.0; 98 double Q3 = Q * Q * Q; 99 double R2 = R * R; 100 double n = - a / 3.0; 101 102 if (R2 < Q3) { 103 double t = Math.acos(R / Math.sqrt(Q3)) / 3.0; 104 double p = 2.0 * Math.PI / 3.0; 105 double m = -2.0 * Math.sqrt(Q); 106 res[rc++] = m * Math.cos(t) + n; 107 res[rc++] = m * Math.cos(t + p) + n; 108 res[rc++] = m * Math.cos(t - p) + n; 109 } else { 110 // Debug.println("R2 >= Q3 (" + R2 + "/" + Q3 + ")"); 111 double A = Math.pow(Math.abs(R) + Math.sqrt(R2 - Q3), 1.0 / 3.0); 112 if (R > 0.0) { 113 A = -A; 114 } 115 // if (A == 0.0) { 116 if (-ROOT_DELTA < A && A < ROOT_DELTA) { 117 res[rc++] = n; 118 } else { 119 double B = Q / A; 120 res[rc++] = A + B + n; 121 // if (R2 == Q3) { 122 double delta = R2 - Q3; 123 if (-ROOT_DELTA < delta && delta < ROOT_DELTA) { 124 res[rc++] = - (A + B) / 2.0 + n; 125 } 126 } 127 128 } 129 return fixRoots(res, rc); 130 } 131 132 /** 133 * Excludes double roots. Roots are double if they lies enough close with each other. 134 * @param res - the roots 135 * @param rc - the roots count 136 * @return new roots count 137 */ 138 static int fixRoots(double res[], int rc) { 139 int tc = 0; 140 for(int i = 0; i < rc; i++) { 141 out: { 142 for(int j = i + 1; j < rc; j++) { 143 if (isZero(res[i] - res[j])) { 144 break out; 145 } 146 } 147 res[tc++] = res[i]; 148 } 149 } 150 return tc; 151 } 152 153 /** 154 * QuadCurve class provides basic functionality to find curve crossing and calculating bounds 155 */ 156 public static class QuadCurve { 157 158 double ax, ay, bx, by; 159 double Ax, Ay, Bx, By; 160 161 public QuadCurve(double x1, double y1, double cx, double cy, double x2, double y2) { 162 ax = x2 - x1; 163 ay = y2 - y1; 164 bx = cx - x1; 165 by = cy - y1; 166 167 Bx = bx + bx; // Bx = 2.0 * bx 168 Ax = ax - Bx; // Ax = ax - 2.0 * bx 169 170 By = by + by; // By = 2.0 * by 171 Ay = ay - By; // Ay = ay - 2.0 * by 172 } 173 174 int cross(double res[], int rc, double py1, double py2) { 175 int cross = 0; 176 177 for (int i = 0; i < rc; i++) { 178 double t = res[i]; 179 180 // CURVE-OUTSIDE 181 if (t < -DELTA || t > 1 + DELTA) { 182 continue; 183 } 184 // CURVE-START 185 if (t < DELTA) { 186 if (py1 < 0.0 && (bx != 0.0 ? bx : ax - bx) < 0.0) { 187 cross--; 188 } 189 continue; 190 } 191 // CURVE-END 192 if (t > 1 - DELTA) { 193 if (py1 < ay && (ax != bx ? ax - bx : bx) > 0.0) { 194 cross++; 195 } 196 continue; 197 } 198 // CURVE-INSIDE 199 double ry = t * (t * Ay + By); 200 // ry = t * t * Ay + t * By 201 if (ry > py2) { 202 double rxt = t * Ax + bx; 203 // rxt = 2.0 * t * Ax + Bx = 2.0 * t * Ax + 2.0 * bx 204 if (rxt > -DELTA && rxt < DELTA) { 205 continue; 206 } 207 cross += rxt > 0.0 ? 1 : -1; 208 } 209 } // for 210 211 return cross; 212 } 213 214 int solvePoint(double res[], double px) { 215 double eqn[] = {-px, Bx, Ax}; 216 return solveQuad(eqn, res); 217 } 218 219 int solveExtrem(double res[]) { 220 int rc = 0; 221 if (Ax != 0.0) { 222 res[rc++] = - Bx / (Ax + Ax); 223 } 224 if (Ay != 0.0) { 225 res[rc++] = - By / (Ay + Ay); 226 } 227 return rc; 228 } 229 230 int addBound(double bound[], int bc, double res[], int rc, double minX, double maxX, boolean changeId, int id) { 231 for(int i = 0; i < rc; i++) { 232 double t = res[i]; 233 if (t > -DELTA && t < 1 + DELTA) { 234 double rx = t * (t * Ax + Bx); 235 if (minX <= rx && rx <= maxX) { 236 bound[bc++] = t; 237 bound[bc++] = rx; 238 bound[bc++] = t * (t * Ay + By); 239 bound[bc++] = id; 240 if (changeId) { 241 id++; 242 } 243 } 244 } 245 } 246 return bc; 247 } 248 249 } 250 251 /** 252 * CubicCurve class provides basic functionality to find curve crossing and calculating bounds 253 */ 254 public static class CubicCurve { 255 256 double ax, ay, bx, by, cx, cy; 257 double Ax, Ay, Bx, By, Cx, Cy; 258 double Ax3, Bx2; 259 260 public CubicCurve(double x1, double y1, double cx1, double cy1, double cx2, double cy2, double x2, double y2) { 261 ax = x2 - x1; 262 ay = y2 - y1; 263 bx = cx1 - x1; 264 by = cy1 - y1; 265 cx = cx2 - x1; 266 cy = cy2 - y1; 267 268 Cx = bx + bx + bx; // Cx = 3.0 * bx 269 Bx = cx + cx + cx - Cx - Cx; // Bx = 3.0 * cx - 6.0 * bx 270 Ax = ax - Bx - Cx; // Ax = ax - 3.0 * cx + 3.0 * bx 271 272 Cy = by + by + by; // Cy = 3.0 * by 273 By = cy + cy + cy - Cy - Cy; // By = 3.0 * cy - 6.0 * by 274 Ay = ay - By - Cy; // Ay = ay - 3.0 * cy + 3.0 * by 275 276 Ax3 = Ax + Ax + Ax; 277 Bx2 = Bx + Bx; 278 } 279 280 int cross(double res[], int rc, double py1, double py2) { 281 int cross = 0; 282 for (int i = 0; i < rc; i++) { 283 double t = res[i]; 284 285 // CURVE-OUTSIDE 286 if (t < -DELTA || t > 1 + DELTA) { 287 continue; 288 } 289 // CURVE-START 290 if (t < DELTA) { 291 if (py1 < 0.0 && (bx != 0.0 ? bx : (cx != bx ? cx - bx : ax - cx)) < 0.0) { 292 cross--; 293 } 294 continue; 295 } 296 // CURVE-END 297 if (t > 1 - DELTA) { 298 if (py1 < ay && (ax != cx ? ax - cx : (cx != bx ? cx - bx : bx)) > 0.0) { 299 cross++; 300 } 301 continue; 302 } 303 // CURVE-INSIDE 304 double ry = t * (t * (t * Ay + By) + Cy); 305 // ry = t * t * t * Ay + t * t * By + t * Cy 306 if (ry > py2) { 307 double rxt = t * (t * Ax3 + Bx2) + Cx; 308 // rxt = 3.0 * t * t * Ax + 2.0 * t * Bx + Cx 309 if (rxt > -DELTA && rxt < DELTA) { 310 rxt = t * (Ax3 + Ax3) + Bx2; 311 // rxt = 6.0 * t * Ax + 2.0 * Bx 312 if (rxt < -DELTA || rxt > DELTA) { 313 // Inflection point 314 continue; 315 } 316 rxt = ax; 317 } 318 cross += rxt > 0.0 ? 1 : -1; 319 } 320 } //for 321 322 return cross; 323 } 324 325 int solvePoint(double res[], double px) { 326 double eqn[] = {-px, Cx, Bx, Ax}; 327 return solveCubic(eqn, res); 328 } 329 330 int solveExtremX(double res[]) { 331 double eqn[] = {Cx, Bx2, Ax3}; 332 return solveQuad(eqn, res); 333 } 334 335 int solveExtremY(double res[]) { 336 double eqn[] = {Cy, By + By, Ay + Ay + Ay}; 337 return solveQuad(eqn, res); 338 } 339 340 int addBound(double bound[], int bc, double res[], int rc, double minX, double maxX, boolean changeId, int id) { 341 for(int i = 0; i < rc; i++) { 342 double t = res[i]; 343 if (t > -DELTA && t < 1 + DELTA) { 344 double rx = t * (t * (t * Ax + Bx) + Cx); 345 if (minX <= rx && rx <= maxX) { 346 bound[bc++] = t; 347 bound[bc++] = rx; 348 bound[bc++] = t * (t * (t * Ay + By) + Cy); 349 bound[bc++] = id; 350 if (changeId) { 351 id++; 352 } 353 } 354 } 355 } 356 return bc; 357 } 358 359 } 360 361 /** 362 * Returns how many times ray from point (x,y) cross line. 363 */ 364 public static int crossLine(double x1, double y1, double x2, double y2, double x, double y) { 365 366 // LEFT/RIGHT/UP/EMPTY 367 if ((x < x1 && x < x2) || 368 (x > x1 && x > x2) || 369 (y > y1 && y > y2) || 370 (x1 == x2)) 371 { 372 return 0; 373 } 374 375 // DOWN 376 if (y < y1 && y < y2) { 377 } else { 378 // INSIDE 379 if ((y2 - y1) * (x - x1) / (x2 - x1) <= y - y1) { 380 // INSIDE-UP 381 return 0; 382 } 383 } 384 385 // START 386 if (x == x1) { 387 return x1 < x2 ? 0 : -1; 388 } 389 390 // END 391 if (x == x2) { 392 return x1 < x2 ? 1 : 0; 393 } 394 395 // INSIDE-DOWN 396 return x1 < x2 ? 1 : -1; 397 } 398 399 /** 400 * Returns how many times ray from point (x,y) cross quard curve 401 */ 402 public static int crossQuad(double x1, double y1, double cx, double cy, double x2, double y2, double x, double y) { 403 404 // LEFT/RIGHT/UP/EMPTY 405 if ((x < x1 && x < cx && x < x2) || 406 (x > x1 && x > cx && x > x2) || 407 (y > y1 && y > cy && y > y2) || 408 (x1 == cx && cx == x2)) 409 { 410 return 0; 411 } 412 413 // DOWN 414 if (y < y1 && y < cy && y < y2 && x != x1 && x != x2) { 415 if (x1 < x2) { 416 return x1 < x && x < x2 ? 1 : 0; 417 } 418 return x2 < x && x < x1 ? -1 : 0; 419 } 420 421 // INSIDE 422 QuadCurve c = new QuadCurve(x1, y1, cx, cy, x2, y2); 423 double px = x - x1; 424 double py = y - y1; 425 double res[] = new double[3]; 426 int rc = c.solvePoint(res, px); 427 428 return c.cross(res, rc, py, py); 429 } 430 431 /** 432 * Returns how many times ray from point (x,y) cross cubic curve 433 */ 434 public static int crossCubic(double x1, double y1, double cx1, double cy1, double cx2, double cy2, double x2, double y2, double x, double y) { 435 436 // LEFT/RIGHT/UP/EMPTY 437 if ((x < x1 && x < cx1 && x < cx2 && x < x2) || 438 (x > x1 && x > cx1 && x > cx2 && x > x2) || 439 (y > y1 && y > cy1 && y > cy2 && y > y2) || 440 (x1 == cx1 && cx1 == cx2 && cx2 == x2)) 441 { 442 return 0; 443 } 444 445 // DOWN 446 if (y < y1 && y < cy1 && y < cy2 && y < y2 && x != x1 && x != x2) { 447 if (x1 < x2) { 448 return x1 < x && x < x2 ? 1 : 0; 449 } 450 return x2 < x && x < x1 ? -1 : 0; 451 } 452 453 // INSIDE 454 CubicCurve c = new CubicCurve(x1, y1, cx1, cy1, cx2, cy2, x2, y2); 455 double px = x - x1; 456 double py = y - y1; 457 double res[] = new double[3]; 458 int rc = c.solvePoint(res, px); 459 return c.cross(res, rc, py, py); 460 } 461 462 /** 463 * Returns how many times ray from point (x,y) cross path 464 */ 465 public static int crossPath(PathIterator p, double x, double y) { 466 int cross = 0; 467 double mx, my, cx, cy; 468 mx = my = cx = cy = 0.0; 469 double coords[] = new double[6]; 470 471 while (!p.isDone()) { 472 switch (p.currentSegment(coords)) { 473 case PathIterator.SEG_MOVETO: 474 if (cx != mx || cy != my) { 475 cross += crossLine(cx, cy, mx, my, x, y); 476 } 477 mx = cx = coords[0]; 478 my = cy = coords[1]; 479 break; 480 case PathIterator.SEG_LINETO: 481 cross += crossLine(cx, cy, cx = coords[0], cy = coords[1], x, y); 482 break; 483 case PathIterator.SEG_QUADTO: 484 cross += crossQuad(cx, cy, coords[0], coords[1], cx = coords[2], cy = coords[3], x, y); 485 break; 486 case PathIterator.SEG_CUBICTO: 487 cross += crossCubic(cx, cy, coords[0], coords[1], coords[2], coords[3], cx = coords[4], cy = coords[5], x, y); 488 break; 489 case PathIterator.SEG_CLOSE: 490 if (cy != my || cx != mx) { 491 cross += crossLine(cx, cy, cx = mx, cy = my, x, y); 492 } 493 break; 494 } 495 p.next(); 496 } 497 if (cy != my) { 498 cross += crossLine(cx, cy, mx, my, x, y); 499 } 500 return cross; 501 } 502 503 /** 504 * Returns how many times ray from point (x,y) cross shape 505 */ 506 public static int crossShape(Shape s, double x, double y) { 507 if (!s.getBounds2D().contains(x, y)) { 508 return 0; 509 } 510 return crossPath(s.getPathIterator(null), x, y); 511 } 512 513 /** 514 * Returns true if value enough small 515 */ 516 public static boolean isZero(double val) { 517 return -DELTA < val && val < DELTA; 518 } 519 520 /** 521 * Sort bound array 522 */ 523 static void sortBound(double bound[], int bc) { 524 for(int i = 0; i < bc - 4; i += 4) { 525 int k = i; 526 for(int j = i + 4; j < bc; j += 4) { 527 if (bound[k] > bound[j]) { 528 k = j; 529 } 530 } 531 if (k != i) { 532 double tmp = bound[i]; 533 bound[i] = bound[k]; 534 bound[k] = tmp; 535 tmp = bound[i + 1]; 536 bound[i + 1] = bound[k + 1]; 537 bound[k + 1] = tmp; 538 tmp = bound[i + 2]; 539 bound[i + 2] = bound[k + 2]; 540 bound[k + 2] = tmp; 541 tmp = bound[i + 3]; 542 bound[i + 3] = bound[k + 3]; 543 bound[k + 3] = tmp; 544 } 545 } 546 } 547 548 /** 549 * Returns are bounds intersect or not intersect rectangle 550 */ 551 static int crossBound(double bound[], int bc, double py1, double py2) { 552 553 // LEFT/RIGHT 554 if (bc == 0) { 555 return 0; 556 } 557 558 // Check Y coordinate 559 int up = 0; 560 int down = 0; 561 for(int i = 2; i < bc; i += 4) { 562 if (bound[i] < py1) { 563 up++; 564 continue; 565 } 566 if (bound[i] > py2) { 567 down++; 568 continue; 569 } 570 return CROSSING; 571 } 572 573 // UP 574 if (down == 0) { 575 return 0; 576 } 577 578 if (up != 0) { 579 // bc >= 2 580 sortBound(bound, bc); 581 boolean sign = bound[2] > py2; 582 for(int i = 6; i < bc; i += 4) { 583 boolean sign2 = bound[i] > py2; 584 if (sign != sign2 && bound[i + 1] != bound[i - 3]) { 585 return CROSSING; 586 } 587 sign = sign2; 588 } 589 } 590 return UNKNOWN; 591 } 592 593 /** 594 * Returns how many times rectangle stripe cross line or the are intersect 595 */ 596 public static int intersectLine(double x1, double y1, double x2, double y2, double rx1, double ry1, double rx2, double ry2) { 597 598 // LEFT/RIGHT/UP 599 if ((rx2 < x1 && rx2 < x2) || 600 (rx1 > x1 && rx1 > x2) || 601 (ry1 > y1 && ry1 > y2)) 602 { 603 return 0; 604 } 605 606 // DOWN 607 if (ry2 < y1 && ry2 < y2) { 608 } else { 609 610 // INSIDE 611 if (x1 == x2) { 612 return CROSSING; 613 } 614 615 // Build bound 616 double bx1, bx2; 617 if (x1 < x2) { 618 bx1 = x1 < rx1 ? rx1 : x1; 619 bx2 = x2 < rx2 ? x2 : rx2; 620 } else { 621 bx1 = x2 < rx1 ? rx1 : x2; 622 bx2 = x1 < rx2 ? x1 : rx2; 623 } 624 double k = (y2 - y1) / (x2 - x1); 625 double by1 = k * (bx1 - x1) + y1; 626 double by2 = k * (bx2 - x1) + y1; 627 628 // BOUND-UP 629 if (by1 < ry1 && by2 < ry1) { 630 return 0; 631 } 632 633 // BOUND-DOWN 634 if (by1 > ry2 && by2 > ry2) { 635 } else { 636 return CROSSING; 637 } 638 } 639 640 // EMPTY 641 if (x1 == x2) { 642 return 0; 643 } 644 645 // CURVE-START 646 if (rx1 == x1) { 647 return x1 < x2 ? 0 : -1; 648 } 649 650 // CURVE-END 651 if (rx1 == x2) { 652 return x1 < x2 ? 1 : 0; 653 } 654 655 if (x1 < x2) { 656 return x1 < rx1 && rx1 < x2 ? 1 : 0; 657 } 658 return x2 < rx1 && rx1 < x1 ? -1 : 0; 659 660 } 661 662 /** 663 * Returns how many times rectangle stripe cross quad curve or the are intersect 664 */ 665 public static int intersectQuad(double x1, double y1, double cx, double cy, double x2, double y2, double rx1, double ry1, double rx2, double ry2) { 666 667 // LEFT/RIGHT/UP ------------------------------------------------------ 668 if ((rx2 < x1 && rx2 < cx && rx2 < x2) || 669 (rx1 > x1 && rx1 > cx && rx1 > x2) || 670 (ry1 > y1 && ry1 > cy && ry1 > y2)) 671 { 672 return 0; 673 } 674 675 // DOWN --------------------------------------------------------------- 676 if (ry2 < y1 && ry2 < cy && ry2 < y2 && rx1 != x1 && rx1 != x2) { 677 if (x1 < x2) { 678 return x1 < rx1 && rx1 < x2 ? 1 : 0; 679 } 680 return x2 < rx1 && rx1 < x1 ? -1 : 0; 681 } 682 683 // INSIDE ------------------------------------------------------------- 684 QuadCurve c = new QuadCurve(x1, y1, cx, cy, x2, y2); 685 double px1 = rx1 - x1; 686 double py1 = ry1 - y1; 687 double px2 = rx2 - x1; 688 double py2 = ry2 - y1; 689 690 double res1[] = new double[3]; 691 double res2[] = new double[3]; 692 int rc1 = c.solvePoint(res1, px1); 693 int rc2 = c.solvePoint(res2, px2); 694 695 // INSIDE-LEFT/RIGHT 696 if (rc1 == 0 && rc2 == 0) { 697 return 0; 698 } 699 700 // Build bound -------------------------------------------------------- 701 double minX = px1 - DELTA; 702 double maxX = px2 + DELTA; 703 double bound[] = new double[28]; 704 int bc = 0; 705 // Add roots 706 bc = c.addBound(bound, bc, res1, rc1, minX, maxX, false, 0); 707 bc = c.addBound(bound, bc, res2, rc2, minX, maxX, false, 1); 708 // Add extremal points` 709 rc2 = c.solveExtrem(res2); 710 bc = c.addBound(bound, bc, res2, rc2, minX, maxX, true, 2); 711 // Add start and end 712 if (rx1 < x1 && x1 < rx2) { 713 bound[bc++] = 0.0; 714 bound[bc++] = 0.0; 715 bound[bc++] = 0.0; 716 bound[bc++] = 4; 717 } 718 if (rx1 < x2 && x2 < rx2) { 719 bound[bc++] = 1.0; 720 bound[bc++] = c.ax; 721 bound[bc++] = c.ay; 722 bound[bc++] = 5; 723 } 724 // End build bound ---------------------------------------------------- 725 726 int cross = crossBound(bound, bc, py1, py2); 727 if (cross != UNKNOWN) { 728 return cross; 729 } 730 return c.cross(res1, rc1, py1, py2); 731 } 732 733 /** 734 * Returns how many times rectangle stripe cross cubic curve or the are intersect 735 */ 736 public static int intersectCubic(double x1, double y1, double cx1, double cy1, double cx2, double cy2, double x2, double y2, double rx1, double ry1, double rx2, double ry2) { 737 738 // LEFT/RIGHT/UP 739 if ((rx2 < x1 && rx2 < cx1 && rx2 < cx2 && rx2 < x2) || 740 (rx1 > x1 && rx1 > cx1 && rx1 > cx2 && rx1 > x2) || 741 (ry1 > y1 && ry1 > cy1 && ry1 > cy2 && ry1 > y2)) 742 { 743 return 0; 744 } 745 746 // DOWN 747 if (ry2 < y1 && ry2 < cy1 && ry2 < cy2 && ry2 < y2 && rx1 != x1 && rx1 != x2) { 748 if (x1 < x2) { 749 return x1 < rx1 && rx1 < x2 ? 1 : 0; 750 } 751 return x2 < rx1 && rx1 < x1 ? -1 : 0; 752 } 753 754 // INSIDE 755 CubicCurve c = new CubicCurve(x1, y1, cx1, cy1, cx2, cy2, x2, y2); 756 double px1 = rx1 - x1; 757 double py1 = ry1 - y1; 758 double px2 = rx2 - x1; 759 double py2 = ry2 - y1; 760 761 double res1[] = new double[3]; 762 double res2[] = new double[3]; 763 int rc1 = c.solvePoint(res1, px1); 764 int rc2 = c.solvePoint(res2, px2); 765 766 // LEFT/RIGHT 767 if (rc1 == 0 && rc2 == 0) { 768 return 0; 769 } 770 771 double minX = px1 - DELTA; 772 double maxX = px2 + DELTA; 773 774 // Build bound -------------------------------------------------------- 775 double bound[] = new double[40]; 776 int bc = 0; 777 // Add roots 778 bc = c.addBound(bound, bc, res1, rc1, minX, maxX, false, 0); 779 bc = c.addBound(bound, bc, res2, rc2, minX, maxX, false, 1); 780 // Add extrimal points 781 rc2 = c.solveExtremX(res2); 782 bc = c.addBound(bound, bc, res2, rc2, minX, maxX, true, 2); 783 rc2 = c.solveExtremY(res2); 784 bc = c.addBound(bound, bc, res2, rc2, minX, maxX, true, 4); 785 // Add start and end 786 if (rx1 < x1 && x1 < rx2) { 787 bound[bc++] = 0.0; 788 bound[bc++] = 0.0; 789 bound[bc++] = 0.0; 790 bound[bc++] = 6; 791 } 792 if (rx1 < x2 && x2 < rx2) { 793 bound[bc++] = 1.0; 794 bound[bc++] = c.ax; 795 bound[bc++] = c.ay; 796 bound[bc++] = 7; 797 } 798 // End build bound ---------------------------------------------------- 799 800 int cross = crossBound(bound, bc, py1, py2); 801 if (cross != UNKNOWN) { 802 return cross; 803 } 804 return c.cross(res1, rc1, py1, py2); 805 } 806 807 /** 808 * Returns how many times rectangle stripe cross path or the are intersect 809 */ 810 public static int intersectPath(PathIterator p, double x, double y, double w, double h) { 811 812 int cross = 0; 813 int count; 814 double mx, my, cx, cy; 815 mx = my = cx = cy = 0.0; 816 double coords[] = new double[6]; 817 818 double rx1 = x; 819 double ry1 = y; 820 double rx2 = x + w; 821 double ry2 = y + h; 822 823 while (!p.isDone()) { 824 count = 0; 825 switch (p.currentSegment(coords)) { 826 case PathIterator.SEG_MOVETO: 827 if (cx != mx || cy != my) { 828 count = intersectLine(cx, cy, mx, my, rx1, ry1, rx2, ry2); 829 } 830 mx = cx = coords[0]; 831 my = cy = coords[1]; 832 break; 833 case PathIterator.SEG_LINETO: 834 count = intersectLine(cx, cy, cx = coords[0], cy = coords[1], rx1, ry1, rx2, ry2); 835 break; 836 case PathIterator.SEG_QUADTO: 837 count = intersectQuad(cx, cy, coords[0], coords[1], cx = coords[2], cy = coords[3], rx1, ry1, rx2, ry2); 838 break; 839 case PathIterator.SEG_CUBICTO: 840 count = intersectCubic(cx, cy, coords[0], coords[1], coords[2], coords[3], cx = coords[4], cy = coords[5], rx1, ry1, rx2, ry2); 841 break; 842 case PathIterator.SEG_CLOSE: 843 if (cy != my || cx != mx) { 844 count = intersectLine(cx, cy, mx, my, rx1, ry1, rx2, ry2); 845 } 846 cx = mx; 847 cy = my; 848 break; 849 } 850 if (count == CROSSING) { 851 return CROSSING; 852 } 853 cross += count; 854 p.next(); 855 } 856 if (cy != my) { 857 count = intersectLine(cx, cy, mx, my, rx1, ry1, rx2, ry2); 858 if (count == CROSSING) { 859 return CROSSING; 860 } 861 cross += count; 862 } 863 return cross; 864 } 865 866 /** 867 * Returns how many times rectangle stripe cross shape or the are intersect 868 */ 869 public static int intersectShape(Shape s, double x, double y, double w, double h) { 870 if (!s.getBounds2D().intersects(x, y, w, h)) { 871 return 0; 872 } 873 return intersectPath(s.getPathIterator(null), x, y, w, h); 874 } 875 876 /** 877 * Returns true if cross count correspond inside location for non zero path rule 878 */ 879 public static boolean isInsideNonZero(int cross) { 880 return cross != 0; 881 } 882 883 /** 884 * Returns true if cross count correspond inside location for even-odd path rule 885 */ 886 public static boolean isInsideEvenOdd(int cross) { 887 return (cross & 1) != 0; 888 } 889 }
