001/* 002 * Copyright 1998-2006 Sun Microsystems, Inc. All Rights Reserved. 003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 004 * 005 * This code is free software; you can redistribute it and/or modify it 006 * under the terms of the GNU General Public License version 2 only, as 007 * published by the Free Software Foundation. Sun designates this 008 * particular file as subject to the "Classpath" exception as provided 009 * by Sun in the LICENSE file that accompanied this code. 010 * 011 * This code is distributed in the hope that it will be useful, but WITHOUT 012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 014 * version 2 for more details (a copy is included in the LICENSE file that 015 * accompanied this code). 016 * 017 * You should have received a copy of the GNU General Public License version 018 * 2 along with this work; if not, write to the Free Software Foundation, 019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 020 * 021 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 022 * CA 95054 USA or visit www.sun.com if you need additional information or 023 * have any questions. 024 */ 025package sec.sun.awt.geom; 026 027import armyc2.c2sd.graphics2d.*; 028 029public final class Curve { 030 031 public static final int INCREASING = 1; 032 public static final int DECREASING = -1; 033 034 //protected int direction; 035 public static void insertMove(Vector curves, double x, double y) { 036 curves.add(new Order0(x, y)); 037 } 038 039 public static void insertLine(Vector curves, 040 double x0, double y0, 041 double x1, double y1) { 042 if (y0 < y1) { 043 curves.add(new Order1(x0, y0, 044 x1, y1, 045 INCREASING)); 046 } else if (y0 > y1) { 047 curves.add(new Order1(x1, y1, 048 x0, y0, 049 DECREASING)); 050 } else { 051 // Do not add horizontal lines 052 } 053 } 054 055 public static void insertQuad(Vector curves, 056 double x0, double y0, 057 double coords[]) { 058 double y1 = coords[3]; 059 if (y0 > y1) { 060 Order2.insert(curves, coords, 061 coords[2], y1, 062 coords[0], coords[1], 063 x0, y0, 064 DECREASING); 065 066 } else if (y0 == y1 && y0 == coords[1]) { 067 // Do not add horizontal lines 068 return; 069 } else { 070 Order2.insert(curves, coords, 071 x0, y0, 072 coords[0], coords[1], 073 coords[2], y1, 074 INCREASING); 075 } 076 } 077 078 public static void insertCubic(Vector curves, 079 double x0, double y0, 080 double coords[]) { 081 double y1 = coords[5]; 082 if (y0 > y1) { 083 Order3.insert(curves, coords, 084 coords[4], y1, 085 coords[2], coords[3], 086 coords[0], coords[1], 087 x0, y0, 088 DECREASING); 089 } else if (y0 == y1 && y0 == coords[1] && y0 == coords[3]) { 090 // Do not add horizontal lines 091 return; 092 } else { 093 Order3.insert(curves, coords, 094 x0, y0, 095 coords[0], coords[1], 096 coords[2], coords[3], 097 coords[4], y1, 098 INCREASING); 099 } 100 } 101 102 /** 103 * Calculates the number of times the given path crosses the ray extending 104 * to the right from (px,py). If the point lies on a part of the path, then 105 * no crossings are counted for that intersection. +1 is added for each 106 * crossing where the Y coordinate is increasing -1 is added for each 107 * crossing where the Y coordinate is decreasing The return value is the sum 108 * of all crossings for every segment in the path. The path must start with 109 * a SEG_MOVETO, otherwise an exception is thrown. The caller must check 110 * p[xy] for NaN values. The caller may also reject infinite p[xy] values as 111 * well. 112 */ 113 public static int pointCrossingsForPath(PathIterator pi, 114 double px, double py) { 115 if (pi.isDone()) { 116 return 0; 117 } 118 double coords[] = new double[6]; 119 if (pi.currentSegment(coords) != PathIterator.SEG_MOVETO) { 120 //throw new IllegalPathStateException("missing initial moveto "+ 121 // "in path definition"); 122 return -1; 123 } 124 pi.next(); 125 double movx = coords[0]; 126 double movy = coords[1]; 127 double curx = movx; 128 double cury = movy; 129 double endx, endy; 130 int crossings = 0; 131 while (!pi.isDone()) { 132 switch (pi.currentSegment(coords)) { 133 case PathIterator.SEG_MOVETO: 134 if (cury != movy) { 135 crossings += pointCrossingsForLine(px, py, 136 curx, cury, 137 movx, movy); 138 } 139 movx = curx = coords[0]; 140 movy = cury = coords[1]; 141 break; 142 case PathIterator.SEG_LINETO: 143 endx = coords[0]; 144 endy = coords[1]; 145 crossings += pointCrossingsForLine(px, py, 146 curx, cury, 147 endx, endy); 148 curx = endx; 149 cury = endy; 150 break; 151 case PathIterator.SEG_QUADTO: 152 endx = coords[2]; 153 endy = coords[3]; 154 crossings += pointCrossingsForQuad(px, py, 155 curx, cury, 156 coords[0], coords[1], 157 endx, endy, 0); 158 curx = endx; 159 cury = endy; 160 break; 161 case PathIterator.SEG_CUBICTO: 162 endx = coords[4]; 163 endy = coords[5]; 164 crossings += pointCrossingsForCubic(px, py, 165 curx, cury, 166 coords[0], coords[1], 167 coords[2], coords[3], 168 endx, endy, 0); 169 curx = endx; 170 cury = endy; 171 break; 172 case PathIterator.SEG_CLOSE: 173 if (cury != movy) { 174 crossings += pointCrossingsForLine(px, py, 175 curx, cury, 176 movx, movy); 177 } 178 curx = movx; 179 cury = movy; 180 break; 181 } 182 pi.next(); 183 } 184 if (cury != movy) { 185 crossings += pointCrossingsForLine(px, py, 186 curx, cury, 187 movx, movy); 188 } 189 return crossings; 190 } 191 192 /** 193 * Calculates the number of times the line from (x0,y0) to (x1,y1) crosses 194 * the ray extending to the right from (px,py). If the point lies on the 195 * line, then no crossings are recorded. +1 is returned for a crossing where 196 * the Y coordinate is increasing -1 is returned for a crossing where the Y 197 * coordinate is decreasing 198 */ 199 public static int pointCrossingsForLine(double px, double py, 200 double x0, double y0, 201 double x1, double y1) { 202 if (py < y0 && py < y1) { 203 return 0; 204 } 205 if (py >= y0 && py >= y1) { 206 return 0; 207 } 208 // assert(y0 != y1); 209 if (px >= x0 && px >= x1) { 210 return 0; 211 } 212 if (px < x0 && px < x1) { 213 return (y0 < y1) ? 1 : -1; 214 } 215 double xintercept = x0 + (py - y0) * (x1 - x0) / (y1 - y0); 216 if (px >= xintercept) { 217 return 0; 218 } 219 return (y0 < y1) ? 1 : -1; 220 } 221 222 /** 223 * Calculates the number of times the quad from (x0,y0) to (x1,y1) crosses 224 * the ray extending to the right from (px,py). If the point lies on a part 225 * of the curve, then no crossings are counted for that intersection. the 226 * level parameter should be 0 at the top-level call and will count up for 227 * each recursion level to prevent infinite recursion +1 is added for each 228 * crossing where the Y coordinate is increasing -1 is added for each 229 * crossing where the Y coordinate is decreasing 230 */ 231 public static int pointCrossingsForQuad(double px, double py, 232 double x0, double y0, 233 double xc, double yc, 234 double x1, double y1, int level) { 235 if (py < y0 && py < yc && py < y1) { 236 return 0; 237 } 238 if (py >= y0 && py >= yc && py >= y1) { 239 return 0; 240 } 241 // Note y0 could equal y1... 242 if (px >= x0 && px >= xc && px >= x1) { 243 return 0; 244 } 245 if (px < x0 && px < xc && px < x1) { 246 if (py >= y0) { 247 if (py < y1) { 248 return 1; 249 } 250 } else { 251 // py < y0 252 if (py >= y1) { 253 return -1; 254 } 255 } 256 // py outside of y01 range, and/or y0==y1 257 return 0; 258 } 259 // double precision only has 52 bits of mantissa 260 if (level > 52) { 261 return pointCrossingsForLine(px, py, x0, y0, x1, y1); 262 } 263 double x0c = (x0 + xc) / 2; 264 double y0c = (y0 + yc) / 2; 265 double xc1 = (xc + x1) / 2; 266 double yc1 = (yc + y1) / 2; 267 xc = (x0c + xc1) / 2; 268 yc = (y0c + yc1) / 2; 269 if (Double.isNaN(xc) || Double.isNaN(yc)) { 270 // [xy]c are NaN if any of [xy]0c or [xy]c1 are NaN 271 // [xy]0c or [xy]c1 are NaN if any of [xy][0c1] are NaN 272 // These values are also NaN if opposing infinities are added 273 return 0; 274 } 275 return (pointCrossingsForQuad(px, py, 276 x0, y0, x0c, y0c, xc, yc, 277 level + 1) 278 + pointCrossingsForQuad(px, py, 279 xc, yc, xc1, yc1, x1, y1, 280 level + 1)); 281 } 282 283 /** 284 * Calculates the number of times the cubic from (x0,y0) to (x1,y1) crosses 285 * the ray extending to the right from (px,py). If the point lies on a part 286 * of the curve, then no crossings are counted for that intersection. the 287 * level parameter should be 0 at the top-level call and will count up for 288 * each recursion level to prevent infinite recursion +1 is added for each 289 * crossing where the Y coordinate is increasing -1 is added for each 290 * crossing where the Y coordinate is decreasing 291 */ 292 public static int pointCrossingsForCubic(double px, double py, 293 double x0, double y0, 294 double xc0, double yc0, 295 double xc1, double yc1, 296 double x1, double y1, int level) { 297 if (py < y0 && py < yc0 && py < yc1 && py < y1) { 298 return 0; 299 } 300 if (py >= y0 && py >= yc0 && py >= yc1 && py >= y1) { 301 return 0; 302 } 303 // Note y0 could equal yc0... 304 if (px >= x0 && px >= xc0 && px >= xc1 && px >= x1) { 305 return 0; 306 } 307 if (px < x0 && px < xc0 && px < xc1 && px < x1) { 308 if (py >= y0) { 309 if (py < y1) { 310 return 1; 311 } 312 } else { 313 // py < y0 314 if (py >= y1) { 315 return -1; 316 } 317 } 318 // py outside of y01 range, and/or y0==yc0 319 return 0; 320 } 321 // double precision only has 52 bits of mantissa 322 if (level > 52) { 323 return pointCrossingsForLine(px, py, x0, y0, x1, y1); 324 } 325 double xmid = (xc0 + xc1) / 2; 326 double ymid = (yc0 + yc1) / 2; 327 xc0 = (x0 + xc0) / 2; 328 yc0 = (y0 + yc0) / 2; 329 xc1 = (xc1 + x1) / 2; 330 yc1 = (yc1 + y1) / 2; 331 double xc0m = (xc0 + xmid) / 2; 332 double yc0m = (yc0 + ymid) / 2; 333 double xmc1 = (xmid + xc1) / 2; 334 double ymc1 = (ymid + yc1) / 2; 335 xmid = (xc0m + xmc1) / 2; 336 ymid = (yc0m + ymc1) / 2; 337 if (Double.isNaN(xmid) || Double.isNaN(ymid)) { 338 // [xy]mid are NaN if any of [xy]c0m or [xy]mc1 are NaN 339 // [xy]c0m or [xy]mc1 are NaN if any of [xy][c][01] are NaN 340 // These values are also NaN if opposing infinities are added 341 return 0; 342 } 343 return (pointCrossingsForCubic(px, py, 344 x0, y0, xc0, yc0, 345 xc0m, yc0m, xmid, ymid, level + 1) 346 + pointCrossingsForCubic(px, py, 347 xmid, ymid, xmc1, ymc1, 348 xc1, yc1, x1, y1, level + 1)); 349 } 350 351 /** 352 * The rectangle intersection test counts the number of times that the path 353 * crosses through the shadow that the rectangle projects to the right 354 * towards (x => +INFINITY). 355 * 356 * During processing of the path it actually counts every time the path 357 * crosses either or both of the top and bottom edges of that shadow. If the 358 * path enters from the top, the count is incremented. If it then exits back 359 * through the top, the same way it came in, the count is decremented and 360 * there is no impact on the winding count. If, instead, the path exits out 361 * the bottom, then the count is incremented again and a full pass through 362 * the shadow is indicated by the winding count having been incremented by 363 * 2. 364 * 365 * Thus, the winding count that it accumulates is actually double the real 366 * winding count. Since the path is continuous, the final answer should be a 367 * multiple of 2, otherwise there is a logic error somewhere. 368 * 369 * If the path ever has a direct hit on the rectangle, then a special value 370 * is returned. This special value terminates all ongoing accumulation on up 371 * through the call chain and ends up getting returned to the calling 372 * function which can then produce an answer directly. For intersection 373 * tests, the answer is always "true" if the path intersects the rectangle. 374 * For containment tests, the answer is always "false" if the path 375 * intersects the rectangle. Thus, no further processing is ever needed if 376 * an intersection occurs. 377 */ 378 public static final int RECT_INTERSECTS = 0x80000000; 379 380 /** 381 * Accumulate the number of times the path crosses the shadow extending to 382 * the right of the rectangle. See the comment for the RECT_INTERSECTS 383 * constant for more complete details. The return value is the sum of all 384 * crossings for both the top and bottom of the shadow for every segment in 385 * the path, or the special value RECT_INTERSECTS if the path ever enters 386 * the interior of the rectangle. The path must start with a SEG_MOVETO, 387 * otherwise an exception is thrown. The caller must check r[xy]{min,max} 388 * for NaN values. 389 */ 390 public static int rectCrossingsForPath(PathIterator pi, 391 double rxmin, double rymin, 392 double rxmax, double rymax) { 393 if (rxmax <= rxmin || rymax <= rymin) { 394 return 0; 395 } 396 if (pi.isDone()) { 397 return 0; 398 } 399 double coords[] = new double[6]; 400 if (pi.currentSegment(coords) != PathIterator.SEG_MOVETO) { 401 //throw new IllegalPathStateException("missing initial moveto "+ 402 // "in path definition"); 403 return -1; 404 } 405 pi.next(); 406 double curx, cury, movx, movy, endx, endy; 407 curx = movx = coords[0]; 408 cury = movy = coords[1]; 409 int crossings = 0; 410 while (crossings != RECT_INTERSECTS && !pi.isDone()) { 411 switch (pi.currentSegment(coords)) { 412 case PathIterator.SEG_MOVETO: 413 if (curx != movx || cury != movy) { 414 crossings = rectCrossingsForLine(crossings, 415 rxmin, rymin, 416 rxmax, rymax, 417 curx, cury, 418 movx, movy); 419 } 420 // Count should always be a multiple of 2 here. 421 // assert((crossings & 1) != 0); 422 movx = curx = coords[0]; 423 movy = cury = coords[1]; 424 break; 425 case PathIterator.SEG_LINETO: 426 endx = coords[0]; 427 endy = coords[1]; 428 crossings = rectCrossingsForLine(crossings, 429 rxmin, rymin, 430 rxmax, rymax, 431 curx, cury, 432 endx, endy); 433 curx = endx; 434 cury = endy; 435 break; 436 case PathIterator.SEG_QUADTO: 437 endx = coords[2]; 438 endy = coords[3]; 439 crossings = rectCrossingsForQuad(crossings, 440 rxmin, rymin, 441 rxmax, rymax, 442 curx, cury, 443 coords[0], coords[1], 444 endx, endy, 0); 445 curx = endx; 446 cury = endy; 447 break; 448 case PathIterator.SEG_CUBICTO: 449 endx = coords[4]; 450 endy = coords[5]; 451 crossings = rectCrossingsForCubic(crossings, 452 rxmin, rymin, 453 rxmax, rymax, 454 curx, cury, 455 coords[0], coords[1], 456 coords[2], coords[3], 457 endx, endy, 0); 458 curx = endx; 459 cury = endy; 460 break; 461 case PathIterator.SEG_CLOSE: 462 if (curx != movx || cury != movy) { 463 crossings = rectCrossingsForLine(crossings, 464 rxmin, rymin, 465 rxmax, rymax, 466 curx, cury, 467 movx, movy); 468 } 469 curx = movx; 470 cury = movy; 471 // Count should always be a multiple of 2 here. 472 // assert((crossings & 1) != 0); 473 break; 474 } 475 pi.next(); 476 } 477 if (crossings != RECT_INTERSECTS && (curx != movx || cury != movy)) { 478 crossings = rectCrossingsForLine(crossings, 479 rxmin, rymin, 480 rxmax, rymax, 481 curx, cury, 482 movx, movy); 483 } 484 // Count should always be a multiple of 2 here. 485 // assert((crossings & 1) != 0); 486 return crossings; 487 } 488 489 /** 490 * Accumulate the number of times the line crosses the shadow extending to 491 * the right of the rectangle. See the comment for the RECT_INTERSECTS 492 * constant for more complete details. 493 */ 494 public static int rectCrossingsForLine(int crossings, 495 double rxmin, double rymin, 496 double rxmax, double rymax, 497 double x0, double y0, 498 double x1, double y1) { 499 if (y0 >= rymax && y1 >= rymax) { 500 return crossings; 501 } 502 if (y0 <= rymin && y1 <= rymin) { 503 return crossings; 504 } 505 if (x0 <= rxmin && x1 <= rxmin) { 506 return crossings; 507 } 508 if (x0 >= rxmax && x1 >= rxmax) { 509 // Line is entirely to the right of the rect 510 // and the vertical ranges of the two overlap by a non-empty amount 511 // Thus, this line segment is partially in the "right-shadow" 512 // Path may have done a complete crossing 513 // Or path may have entered or exited the right-shadow 514 if (y0 < y1) { 515 // y-increasing line segment... 516 // We know that y0 < rymax and y1 > rymin 517 if (y0 <= rymin) { 518 crossings++; 519 } 520 if (y1 >= rymax) { 521 crossings++; 522 } 523 } else if (y1 < y0) { 524 // y-decreasing line segment... 525 // We know that y1 < rymax and y0 > rymin 526 if (y1 <= rymin) { 527 crossings--; 528 } 529 if (y0 >= rymax) { 530 crossings--; 531 } 532 } 533 return crossings; 534 } 535 // Remaining case: 536 // Both x and y ranges overlap by a non-empty amount 537 // First do trivial INTERSECTS rejection of the cases 538 // where one of the endpoints is inside the rectangle. 539 if ((x0 > rxmin && x0 < rxmax && y0 > rymin && y0 < rymax) 540 || (x1 > rxmin && x1 < rxmax && y1 > rymin && y1 < rymax)) { 541 return RECT_INTERSECTS; 542 } 543 // Otherwise calculate the y intercepts and see where 544 // they fall with respect to the rectangle 545 double xi0 = x0; 546 if (y0 < rymin) { 547 xi0 += ((rymin - y0) * (x1 - x0) / (y1 - y0)); 548 } else if (y0 > rymax) { 549 xi0 += ((rymax - y0) * (x1 - x0) / (y1 - y0)); 550 } 551 double xi1 = x1; 552 if (y1 < rymin) { 553 xi1 += ((rymin - y1) * (x0 - x1) / (y0 - y1)); 554 } else if (y1 > rymax) { 555 xi1 += ((rymax - y1) * (x0 - x1) / (y0 - y1)); 556 } 557 if (xi0 <= rxmin && xi1 <= rxmin) { 558 return crossings; 559 } 560 if (xi0 >= rxmax && xi1 >= rxmax) { 561 if (y0 < y1) { 562 // y-increasing line segment... 563 // We know that y0 < rymax and y1 > rymin 564 if (y0 <= rymin) { 565 crossings++; 566 } 567 if (y1 >= rymax) { 568 crossings++; 569 } 570 } else if (y1 < y0) { 571 // y-decreasing line segment... 572 // We know that y1 < rymax and y0 > rymin 573 if (y1 <= rymin) { 574 crossings--; 575 } 576 if (y0 >= rymax) { 577 crossings--; 578 } 579 } 580 return crossings; 581 } 582 return RECT_INTERSECTS; 583 } 584 585 /** 586 * Accumulate the number of times the quad crosses the shadow extending to 587 * the right of the rectangle. See the comment for the RECT_INTERSECTS 588 * constant for more complete details. 589 */ 590 public static int rectCrossingsForQuad(int crossings, 591 double rxmin, double rymin, 592 double rxmax, double rymax, 593 double x0, double y0, 594 double xc, double yc, 595 double x1, double y1, 596 int level) { 597 if (y0 >= rymax && yc >= rymax && y1 >= rymax) { 598 return crossings; 599 } 600 if (y0 <= rymin && yc <= rymin && y1 <= rymin) { 601 return crossings; 602 } 603 if (x0 <= rxmin && xc <= rxmin && x1 <= rxmin) { 604 return crossings; 605 } 606 if (x0 >= rxmax && xc >= rxmax && x1 >= rxmax) { 607 // Quad is entirely to the right of the rect 608 // and the vertical range of the 3 Y coordinates of the quad 609 // overlaps the vertical range of the rect by a non-empty amount 610 // We now judge the crossings solely based on the line segment 611 // connecting the endpoints of the quad. 612 // Note that we may have 0, 1, or 2 crossings as the control 613 // point may be causing the Y range intersection while the 614 // two endpoints are entirely above or below. 615 if (y0 < y1) { 616 // y-increasing line segment... 617 if (y0 <= rymin && y1 > rymin) { 618 crossings++; 619 } 620 if (y0 < rymax && y1 >= rymax) { 621 crossings++; 622 } 623 } else if (y1 < y0) { 624 // y-decreasing line segment... 625 if (y1 <= rymin && y0 > rymin) { 626 crossings--; 627 } 628 if (y1 < rymax && y0 >= rymax) { 629 crossings--; 630 } 631 } 632 return crossings; 633 } 634 // The intersection of ranges is more complicated 635 // First do trivial INTERSECTS rejection of the cases 636 // where one of the endpoints is inside the rectangle. 637 if ((x0 < rxmax && x0 > rxmin && y0 < rymax && y0 > rymin) 638 || (x1 < rxmax && x1 > rxmin && y1 < rymax && y1 > rymin)) { 639 return RECT_INTERSECTS; 640 } 641 // Otherwise, subdivide and look for one of the cases above. 642 // double precision only has 52 bits of mantissa 643 if (level > 52) { 644 return rectCrossingsForLine(crossings, 645 rxmin, rymin, rxmax, rymax, 646 x0, y0, x1, y1); 647 } 648 double x0c = (x0 + xc) / 2; 649 double y0c = (y0 + yc) / 2; 650 double xc1 = (xc + x1) / 2; 651 double yc1 = (yc + y1) / 2; 652 xc = (x0c + xc1) / 2; 653 yc = (y0c + yc1) / 2; 654 if (Double.isNaN(xc) || Double.isNaN(yc)) { 655 // [xy]c are NaN if any of [xy]0c or [xy]c1 are NaN 656 // [xy]0c or [xy]c1 are NaN if any of [xy][0c1] are NaN 657 // These values are also NaN if opposing infinities are added 658 return 0; 659 } 660 crossings = rectCrossingsForQuad(crossings, 661 rxmin, rymin, rxmax, rymax, 662 x0, y0, x0c, y0c, xc, yc, 663 level + 1); 664 if (crossings != RECT_INTERSECTS) { 665 crossings = rectCrossingsForQuad(crossings, 666 rxmin, rymin, rxmax, rymax, 667 xc, yc, xc1, yc1, x1, y1, 668 level + 1); 669 } 670 return crossings; 671 } 672 673 /** 674 * Accumulate the number of times the cubic crosses the shadow extending to 675 * the right of the rectangle. See the comment for the RECT_INTERSECTS 676 * constant for more complete details. 677 */ 678 public static int rectCrossingsForCubic(int crossings, 679 double rxmin, double rymin, 680 double rxmax, double rymax, 681 double x0, double y0, 682 double xc0, double yc0, 683 double xc1, double yc1, 684 double x1, double y1, 685 int level) { 686 if (y0 >= rymax && yc0 >= rymax && yc1 >= rymax && y1 >= rymax) { 687 return crossings; 688 } 689 if (y0 <= rymin && yc0 <= rymin && yc1 <= rymin && y1 <= rymin) { 690 return crossings; 691 } 692 if (x0 <= rxmin && xc0 <= rxmin && xc1 <= rxmin && x1 <= rxmin) { 693 return crossings; 694 } 695 if (x0 >= rxmax && xc0 >= rxmax && xc1 >= rxmax && x1 >= rxmax) { 696 // Cubic is entirely to the right of the rect 697 // and the vertical range of the 4 Y coordinates of the cubic 698 // overlaps the vertical range of the rect by a non-empty amount 699 // We now judge the crossings solely based on the line segment 700 // connecting the endpoints of the cubic. 701 // Note that we may have 0, 1, or 2 crossings as the control 702 // points may be causing the Y range intersection while the 703 // two endpoints are entirely above or below. 704 if (y0 < y1) { 705 // y-increasing line segment... 706 if (y0 <= rymin && y1 > rymin) { 707 crossings++; 708 } 709 if (y0 < rymax && y1 >= rymax) { 710 crossings++; 711 } 712 } else if (y1 < y0) { 713 // y-decreasing line segment... 714 if (y1 <= rymin && y0 > rymin) { 715 crossings--; 716 } 717 if (y1 < rymax && y0 >= rymax) { 718 crossings--; 719 } 720 } 721 return crossings; 722 } 723 // The intersection of ranges is more complicated 724 // First do trivial INTERSECTS rejection of the cases 725 // where one of the endpoints is inside the rectangle. 726 if ((x0 > rxmin && x0 < rxmax && y0 > rymin && y0 < rymax) 727 || (x1 > rxmin && x1 < rxmax && y1 > rymin && y1 < rymax)) { 728 return RECT_INTERSECTS; 729 } 730 // Otherwise, subdivide and look for one of the cases above. 731 // double precision only has 52 bits of mantissa 732 if (level > 52) { 733 return rectCrossingsForLine(crossings, 734 rxmin, rymin, rxmax, rymax, 735 x0, y0, x1, y1); 736 } 737 double xmid = (xc0 + xc1) / 2; 738 double ymid = (yc0 + yc1) / 2; 739 xc0 = (x0 + xc0) / 2; 740 yc0 = (y0 + yc0) / 2; 741 xc1 = (xc1 + x1) / 2; 742 yc1 = (yc1 + y1) / 2; 743 double xc0m = (xc0 + xmid) / 2; 744 double yc0m = (yc0 + ymid) / 2; 745 double xmc1 = (xmid + xc1) / 2; 746 double ymc1 = (ymid + yc1) / 2; 747 xmid = (xc0m + xmc1) / 2; 748 ymid = (yc0m + ymc1) / 2; 749 if (Double.isNaN(xmid) || Double.isNaN(ymid)) { 750 // [xy]mid are NaN if any of [xy]c0m or [xy]mc1 are NaN 751 // [xy]c0m or [xy]mc1 are NaN if any of [xy][c][01] are NaN 752 // These values are also NaN if opposing infinities are added 753 return 0; 754 } 755 crossings = rectCrossingsForCubic(crossings, 756 rxmin, rymin, rxmax, rymax, 757 x0, y0, xc0, yc0, 758 xc0m, yc0m, xmid, ymid, level + 1); 759 if (crossings != RECT_INTERSECTS) { 760 crossings = rectCrossingsForCubic(crossings, 761 rxmin, rymin, rxmax, rymax, 762 xmid, ymid, xmc1, ymc1, 763 xc1, yc1, x1, y1, level + 1); 764 } 765 return crossings; 766 } 767 768 public static double round(double v) { 769 //return Math.rint(v*10)/10; 770 return v; 771 } 772 773 public static int orderof(double x1, double x2) { 774 if (x1 < x2) { 775 return -1; 776 } 777 if (x1 > x2) { 778 return 1; 779 } 780 return 0; 781 } 782 783 public static long signeddiffbits(double y1, double y2) { 784 return (Double.doubleToLongBits(y1) - Double.doubleToLongBits(y2)); 785 } 786 787 public static long diffbits(double y1, double y2) { 788 return Math.abs(Double.doubleToLongBits(y1) 789 - Double.doubleToLongBits(y2)); 790 } 791 792 public static double prev(double v) { 793 return Double.longBitsToDouble(Double.doubleToLongBits(v) - 1); 794 } 795 796 public static double next(double v) { 797 return Double.longBitsToDouble(Double.doubleToLongBits(v) + 1); 798 } 799 800 public static final double TMIN = 1E-3; 801 802 public static boolean fairlyClose(double v1, double v2) { 803 return (Math.abs(v1 - v2) 804 < Math.max(Math.abs(v1), Math.abs(v2)) * 1E-10); 805 } 806 807 /** 808 * Solves the quadratic whose coefficients are in the <code>eqn</code> array 809 * and places the non-complex roots into the <code>res</code> array, 810 * returning the number of roots. The quadratic solved is represented by the 811 * equation: 812 * <pre> 813 * eqn = {C, B, A}; 814 * ax^2 + bx + c = 0 815 * </pre> A return value of <code>-1</code> is used to distinguish a 816 * constant equation, which might be always 0 or never 0, from an equation 817 * that has no zeroes. 818 * 819 * @param eqn the specified array of coefficients to use to solve the 820 * quadratic equation 821 * @param res the array that contains the non-complex roots resulting from 822 * the solution of the quadratic equation 823 * @return the number of roots, or <code>-1</code> if the equation is a 824 * constant. 825 * @since 1.3 826 */ 827 public static int solveQuadratic(double eqn[], double res[]) { 828 double a = eqn[2]; 829 double b = eqn[1]; 830 double c = eqn[0]; 831 int roots = 0; 832 if (a == 0.0) { 833 // The quadratic parabola has degenerated to a line. 834 if (b == 0.0) { 835 // The line has degenerated to a constant. 836 return -1; 837 } 838 res[roots++] = -c / b; 839 } else { 840 // From Numerical Recipes, 5.6, Quadratic and Cubic Equations 841 double d = b * b - 4.0 * a * c; 842 if (d < 0.0) { 843 // If d < 0.0, then there are no roots 844 return 0; 845 } 846 d = Math.sqrt(d); 847 // For accuracy, calculate one root using: 848 // (-b +/- d) / 2a 849 // and the other using: 850 // 2c / (-b +/- d) 851 // Choose the sign of the +/- so that b+d gets larger in magnitude 852 if (b < 0.0) { 853 d = -d; 854 } 855 double q = (b + d) / -2.0; 856 // We already tested a for being 0 above 857 res[roots++] = q / a; 858 if (q != 0.0) { 859 res[roots++] = c / q; 860 } 861 } 862 return roots; 863 } 864}