1 /* 2 * Copyright (c) 1998, 2018, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package sun.awt.geom; 27 28 import java.awt.geom.Rectangle2D; 29 import java.awt.geom.QuadCurve2D; 30 import java.awt.geom.CubicCurve2D; 31 import java.awt.geom.PathIterator; 32 import java.awt.geom.IllegalPathStateException; 33 import java.util.Vector; 34 35 public abstract class Curve { 36 public static final int INCREASING = 1; 37 public static final int DECREASING = -1; 38 39 protected int direction; 40 insertMove(Vector<Curve> curves, double x, double y)41 public static void insertMove(Vector<Curve> curves, double x, double y) { 42 curves.add(new Order0(x, y)); 43 } 44 insertLine(Vector<Curve> curves, double x0, double y0, double x1, double y1)45 public static void insertLine(Vector<Curve> curves, 46 double x0, double y0, 47 double x1, double y1) 48 { 49 if (y0 < y1) { 50 curves.add(new Order1(x0, y0, 51 x1, y1, 52 INCREASING)); 53 } else if (y0 > y1) { 54 curves.add(new Order1(x1, y1, 55 x0, y0, 56 DECREASING)); 57 } else { 58 // Do not add horizontal lines 59 } 60 } 61 insertQuad(Vector<Curve> curves, double x0, double y0, double[] coords)62 public static void insertQuad(Vector<Curve> curves, 63 double x0, double y0, 64 double[] coords) 65 { 66 double y1 = coords[3]; 67 if (y0 > y1) { 68 Order2.insert(curves, coords, 69 coords[2], y1, 70 coords[0], coords[1], 71 x0, y0, 72 DECREASING); 73 } else if (y0 == y1 && y0 == coords[1]) { 74 // Do not add horizontal lines 75 return; 76 } else { 77 Order2.insert(curves, coords, 78 x0, y0, 79 coords[0], coords[1], 80 coords[2], y1, 81 INCREASING); 82 } 83 } 84 insertCubic(Vector<Curve> curves, double x0, double y0, double[] coords)85 public static void insertCubic(Vector<Curve> curves, 86 double x0, double y0, 87 double[] coords) 88 { 89 double y1 = coords[5]; 90 if (y0 > y1) { 91 Order3.insert(curves, coords, 92 coords[4], y1, 93 coords[2], coords[3], 94 coords[0], coords[1], 95 x0, y0, 96 DECREASING); 97 } else if (y0 == y1 && y0 == coords[1] && y0 == coords[3]) { 98 // Do not add horizontal lines 99 return; 100 } else { 101 Order3.insert(curves, coords, 102 x0, y0, 103 coords[0], coords[1], 104 coords[2], coords[3], 105 coords[4], y1, 106 INCREASING); 107 } 108 } 109 110 /** 111 * Calculates the number of times the given path 112 * crosses the ray extending to the right from (px,py). 113 * If the point lies on a part of the path, 114 * then no crossings are counted for that intersection. 115 * +1 is added for each crossing where the Y coordinate is increasing 116 * -1 is added for each crossing where the Y coordinate is decreasing 117 * The return value is the sum of all crossings for every segment in 118 * the path. 119 * The path must start with a SEG_MOVETO, otherwise an exception is 120 * thrown. 121 * The caller must check p[xy] for NaN values. 122 * The caller may also reject infinite p[xy] values as well. 123 */ pointCrossingsForPath(PathIterator pi, double px, double py)124 public static int pointCrossingsForPath(PathIterator pi, 125 double px, double py) 126 { 127 if (pi.isDone()) { 128 return 0; 129 } 130 double[] coords = new double[6]; 131 if (pi.currentSegment(coords) != PathIterator.SEG_MOVETO) { 132 throw new IllegalPathStateException("missing initial moveto "+ 133 "in path definition"); 134 } 135 pi.next(); 136 double movx = coords[0]; 137 double movy = coords[1]; 138 double curx = movx; 139 double cury = movy; 140 double endx, endy; 141 int crossings = 0; 142 while (!pi.isDone()) { 143 switch (pi.currentSegment(coords)) { 144 case PathIterator.SEG_MOVETO: 145 if (cury != movy) { 146 crossings += pointCrossingsForLine(px, py, 147 curx, cury, 148 movx, movy); 149 } 150 movx = curx = coords[0]; 151 movy = cury = coords[1]; 152 break; 153 case PathIterator.SEG_LINETO: 154 endx = coords[0]; 155 endy = coords[1]; 156 crossings += pointCrossingsForLine(px, py, 157 curx, cury, 158 endx, endy); 159 curx = endx; 160 cury = endy; 161 break; 162 case PathIterator.SEG_QUADTO: 163 endx = coords[2]; 164 endy = coords[3]; 165 crossings += pointCrossingsForQuad(px, py, 166 curx, cury, 167 coords[0], coords[1], 168 endx, endy, 0); 169 curx = endx; 170 cury = endy; 171 break; 172 case PathIterator.SEG_CUBICTO: 173 endx = coords[4]; 174 endy = coords[5]; 175 crossings += pointCrossingsForCubic(px, py, 176 curx, cury, 177 coords[0], coords[1], 178 coords[2], coords[3], 179 endx, endy, 0); 180 curx = endx; 181 cury = endy; 182 break; 183 case PathIterator.SEG_CLOSE: 184 if (cury != movy) { 185 crossings += pointCrossingsForLine(px, py, 186 curx, cury, 187 movx, movy); 188 } 189 curx = movx; 190 cury = movy; 191 break; 192 } 193 pi.next(); 194 } 195 if (cury != movy) { 196 crossings += pointCrossingsForLine(px, py, 197 curx, cury, 198 movx, movy); 199 } 200 return crossings; 201 } 202 203 /** 204 * Calculates the number of times the line from (x0,y0) to (x1,y1) 205 * crosses the ray extending to the right from (px,py). 206 * If the point lies on the line, then no crossings are recorded. 207 * +1 is returned for a crossing where the Y coordinate is increasing 208 * -1 is returned for a crossing where the Y coordinate is decreasing 209 */ pointCrossingsForLine(double px, double py, double x0, double y0, double x1, double y1)210 public static int pointCrossingsForLine(double px, double py, 211 double x0, double y0, 212 double x1, double y1) 213 { 214 if (py < y0 && py < y1) return 0; 215 if (py >= y0 && py >= y1) return 0; 216 // assert(y0 != y1); 217 if (px >= x0 && px >= x1) return 0; 218 if (px < x0 && px < x1) return (y0 < y1) ? 1 : -1; 219 double xintercept = x0 + (py - y0) * (x1 - x0) / (y1 - y0); 220 if (px >= xintercept) return 0; 221 return (y0 < y1) ? 1 : -1; 222 } 223 224 /** 225 * Calculates the number of times the quad from (x0,y0) to (x1,y1) 226 * crosses the ray extending to the right from (px,py). 227 * If the point lies on a part of the curve, 228 * then no crossings are counted for that intersection. 229 * the level parameter should be 0 at the top-level call and will count 230 * up for each recursion level to prevent infinite recursion 231 * +1 is added for each crossing where the Y coordinate is increasing 232 * -1 is added for each crossing where the Y coordinate is decreasing 233 */ pointCrossingsForQuad(double px, double py, double x0, double y0, double xc, double yc, double x1, double y1, int level)234 public static int pointCrossingsForQuad(double px, double py, 235 double x0, double y0, 236 double xc, double yc, 237 double x1, double y1, int level) 238 { 239 if (py < y0 && py < yc && py < y1) return 0; 240 if (py >= y0 && py >= yc && py >= y1) return 0; 241 // Note y0 could equal y1... 242 if (px >= x0 && px >= xc && px >= x1) return 0; 243 if (px < x0 && px < xc && px < x1) { 244 if (py >= y0) { 245 if (py < y1) return 1; 246 } else { 247 // py < y0 248 if (py >= y1) return -1; 249 } 250 // py outside of y01 range, and/or y0==y1 251 return 0; 252 } 253 // double precision only has 52 bits of mantissa 254 if (level > 52) return pointCrossingsForLine(px, py, x0, y0, x1, y1); 255 double x0c = (x0 + xc) / 2; 256 double y0c = (y0 + yc) / 2; 257 double xc1 = (xc + x1) / 2; 258 double yc1 = (yc + y1) / 2; 259 xc = (x0c + xc1) / 2; 260 yc = (y0c + yc1) / 2; 261 if (Double.isNaN(xc) || Double.isNaN(yc)) { 262 // [xy]c are NaN if any of [xy]0c or [xy]c1 are NaN 263 // [xy]0c or [xy]c1 are NaN if any of [xy][0c1] are NaN 264 // These values are also NaN if opposing infinities are added 265 return 0; 266 } 267 return (pointCrossingsForQuad(px, py, 268 x0, y0, x0c, y0c, xc, yc, 269 level+1) + 270 pointCrossingsForQuad(px, py, 271 xc, yc, xc1, yc1, x1, y1, 272 level+1)); 273 } 274 275 /** 276 * Calculates the number of times the cubic from (x0,y0) to (x1,y1) 277 * crosses the ray extending to the right from (px,py). 278 * If the point lies on a part of the curve, 279 * then no crossings are counted for that intersection. 280 * the level parameter should be 0 at the top-level call and will count 281 * up for each recursion level to prevent infinite recursion 282 * +1 is added for each crossing where the Y coordinate is increasing 283 * -1 is added for each crossing where the Y coordinate is decreasing 284 */ pointCrossingsForCubic(double px, double py, double x0, double y0, double xc0, double yc0, double xc1, double yc1, double x1, double y1, int level)285 public static int pointCrossingsForCubic(double px, double py, 286 double x0, double y0, 287 double xc0, double yc0, 288 double xc1, double yc1, 289 double x1, double y1, int level) 290 { 291 if (py < y0 && py < yc0 && py < yc1 && py < y1) return 0; 292 if (py >= y0 && py >= yc0 && py >= yc1 && py >= y1) return 0; 293 // Note y0 could equal yc0... 294 if (px >= x0 && px >= xc0 && px >= xc1 && px >= x1) return 0; 295 if (px < x0 && px < xc0 && px < xc1 && px < x1) { 296 if (py >= y0) { 297 if (py < y1) return 1; 298 } else { 299 // py < y0 300 if (py >= y1) return -1; 301 } 302 // py outside of y01 range, and/or y0==yc0 303 return 0; 304 } 305 // double precision only has 52 bits of mantissa 306 if (level > 52) return pointCrossingsForLine(px, py, x0, y0, x1, y1); 307 double xmid = (xc0 + xc1) / 2; 308 double ymid = (yc0 + yc1) / 2; 309 xc0 = (x0 + xc0) / 2; 310 yc0 = (y0 + yc0) / 2; 311 xc1 = (xc1 + x1) / 2; 312 yc1 = (yc1 + y1) / 2; 313 double xc0m = (xc0 + xmid) / 2; 314 double yc0m = (yc0 + ymid) / 2; 315 double xmc1 = (xmid + xc1) / 2; 316 double ymc1 = (ymid + yc1) / 2; 317 xmid = (xc0m + xmc1) / 2; 318 ymid = (yc0m + ymc1) / 2; 319 if (Double.isNaN(xmid) || Double.isNaN(ymid)) { 320 // [xy]mid are NaN if any of [xy]c0m or [xy]mc1 are NaN 321 // [xy]c0m or [xy]mc1 are NaN if any of [xy][c][01] are NaN 322 // These values are also NaN if opposing infinities are added 323 return 0; 324 } 325 return (pointCrossingsForCubic(px, py, 326 x0, y0, xc0, yc0, 327 xc0m, yc0m, xmid, ymid, level+1) + 328 pointCrossingsForCubic(px, py, 329 xmid, ymid, xmc1, ymc1, 330 xc1, yc1, x1, y1, level+1)); 331 } 332 333 /** 334 * The rectangle intersection test counts the number of times 335 * that the path crosses through the shadow that the rectangle 336 * projects to the right towards (x => +INFINITY). 337 * 338 * During processing of the path it actually counts every time 339 * the path crosses either or both of the top and bottom edges 340 * of that shadow. If the path enters from the top, the count 341 * is incremented. If it then exits back through the top, the 342 * same way it came in, the count is decremented and there is 343 * no impact on the winding count. If, instead, the path exits 344 * out the bottom, then the count is incremented again and a 345 * full pass through the shadow is indicated by the winding count 346 * having been incremented by 2. 347 * 348 * Thus, the winding count that it accumulates is actually double 349 * the real winding count. Since the path is continuous, the 350 * final answer should be a multiple of 2, otherwise there is a 351 * logic error somewhere. 352 * 353 * If the path ever has a direct hit on the rectangle, then a 354 * special value is returned. This special value terminates 355 * all ongoing accumulation on up through the call chain and 356 * ends up getting returned to the calling function which can 357 * then produce an answer directly. For intersection tests, 358 * the answer is always "true" if the path intersects the 359 * rectangle. For containment tests, the answer is always 360 * "false" if the path intersects the rectangle. Thus, no 361 * further processing is ever needed if an intersection occurs. 362 */ 363 public static final int RECT_INTERSECTS = 0x80000000; 364 365 /** 366 * Accumulate the number of times the path crosses the shadow 367 * extending to the right of the rectangle. See the comment 368 * for the RECT_INTERSECTS constant for more complete details. 369 * The return value is the sum of all crossings for both the 370 * top and bottom of the shadow for every segment in the path, 371 * or the special value RECT_INTERSECTS if the path ever enters 372 * the interior of the rectangle. 373 * The path must start with a SEG_MOVETO, otherwise an exception is 374 * thrown. 375 * The caller must check r[xy]{min,max} for NaN values. 376 */ rectCrossingsForPath(PathIterator pi, double rxmin, double rymin, double rxmax, double rymax)377 public static int rectCrossingsForPath(PathIterator pi, 378 double rxmin, double rymin, 379 double rxmax, double rymax) 380 { 381 if (rxmax <= rxmin || rymax <= rymin) { 382 return 0; 383 } 384 if (pi.isDone()) { 385 return 0; 386 } 387 double[] coords = new double[6]; 388 if (pi.currentSegment(coords) != PathIterator.SEG_MOVETO) { 389 throw new IllegalPathStateException("missing initial moveto "+ 390 "in path definition"); 391 } 392 pi.next(); 393 double curx, cury, movx, movy, endx, endy; 394 curx = movx = coords[0]; 395 cury = movy = coords[1]; 396 int crossings = 0; 397 while (crossings != RECT_INTERSECTS && !pi.isDone()) { 398 switch (pi.currentSegment(coords)) { 399 case PathIterator.SEG_MOVETO: 400 if (curx != movx || cury != movy) { 401 crossings = rectCrossingsForLine(crossings, 402 rxmin, rymin, 403 rxmax, rymax, 404 curx, cury, 405 movx, movy); 406 } 407 // Count should always be a multiple of 2 here. 408 // assert((crossings & 1) != 0); 409 movx = curx = coords[0]; 410 movy = cury = coords[1]; 411 break; 412 case PathIterator.SEG_LINETO: 413 endx = coords[0]; 414 endy = coords[1]; 415 crossings = rectCrossingsForLine(crossings, 416 rxmin, rymin, 417 rxmax, rymax, 418 curx, cury, 419 endx, endy); 420 curx = endx; 421 cury = endy; 422 break; 423 case PathIterator.SEG_QUADTO: 424 endx = coords[2]; 425 endy = coords[3]; 426 crossings = rectCrossingsForQuad(crossings, 427 rxmin, rymin, 428 rxmax, rymax, 429 curx, cury, 430 coords[0], coords[1], 431 endx, endy, 0); 432 curx = endx; 433 cury = endy; 434 break; 435 case PathIterator.SEG_CUBICTO: 436 endx = coords[4]; 437 endy = coords[5]; 438 crossings = rectCrossingsForCubic(crossings, 439 rxmin, rymin, 440 rxmax, rymax, 441 curx, cury, 442 coords[0], coords[1], 443 coords[2], coords[3], 444 endx, endy, 0); 445 curx = endx; 446 cury = endy; 447 break; 448 case PathIterator.SEG_CLOSE: 449 if (curx != movx || cury != movy) { 450 crossings = rectCrossingsForLine(crossings, 451 rxmin, rymin, 452 rxmax, rymax, 453 curx, cury, 454 movx, movy); 455 } 456 curx = movx; 457 cury = movy; 458 // Count should always be a multiple of 2 here. 459 // assert((crossings & 1) != 0); 460 break; 461 } 462 pi.next(); 463 } 464 if (crossings != RECT_INTERSECTS && (curx != movx || cury != movy)) { 465 crossings = rectCrossingsForLine(crossings, 466 rxmin, rymin, 467 rxmax, rymax, 468 curx, cury, 469 movx, movy); 470 } 471 // Count should always be a multiple of 2 here. 472 // assert((crossings & 1) != 0); 473 return crossings; 474 } 475 476 /** 477 * Accumulate the number of times the line crosses the shadow 478 * extending to the right of the rectangle. See the comment 479 * for the RECT_INTERSECTS constant for more complete details. 480 */ rectCrossingsForLine(int crossings, double rxmin, double rymin, double rxmax, double rymax, double x0, double y0, double x1, double y1)481 public static int rectCrossingsForLine(int crossings, 482 double rxmin, double rymin, 483 double rxmax, double rymax, 484 double x0, double y0, 485 double x1, double y1) 486 { 487 if (y0 >= rymax && y1 >= rymax) return crossings; 488 if (y0 <= rymin && y1 <= rymin) return crossings; 489 if (x0 <= rxmin && x1 <= rxmin) return crossings; 490 if (x0 >= rxmax && x1 >= rxmax) { 491 // Line is entirely to the right of the rect 492 // and the vertical ranges of the two overlap by a non-empty amount 493 // Thus, this line segment is partially in the "right-shadow" 494 // Path may have done a complete crossing 495 // Or path may have entered or exited the right-shadow 496 if (y0 < y1) { 497 // y-increasing line segment... 498 // We know that y0 < rymax and y1 > rymin 499 if (y0 <= rymin) crossings++; 500 if (y1 >= rymax) crossings++; 501 } else if (y1 < y0) { 502 // y-decreasing line segment... 503 // We know that y1 < rymax and y0 > rymin 504 if (y1 <= rymin) crossings--; 505 if (y0 >= rymax) crossings--; 506 } 507 return crossings; 508 } 509 // Remaining case: 510 // Both x and y ranges overlap by a non-empty amount 511 // First do trivial INTERSECTS rejection of the cases 512 // where one of the endpoints is inside the rectangle. 513 if ((x0 > rxmin && x0 < rxmax && y0 > rymin && y0 < rymax) || 514 (x1 > rxmin && x1 < rxmax && y1 > rymin && y1 < rymax)) 515 { 516 return RECT_INTERSECTS; 517 } 518 // Otherwise calculate the y intercepts and see where 519 // they fall with respect to the rectangle 520 double xi0 = x0; 521 if (y0 < rymin) { 522 xi0 += ((rymin - y0) * (x1 - x0) / (y1 - y0)); 523 } else if (y0 > rymax) { 524 xi0 += ((rymax - y0) * (x1 - x0) / (y1 - y0)); 525 } 526 double xi1 = x1; 527 if (y1 < rymin) { 528 xi1 += ((rymin - y1) * (x0 - x1) / (y0 - y1)); 529 } else if (y1 > rymax) { 530 xi1 += ((rymax - y1) * (x0 - x1) / (y0 - y1)); 531 } 532 if (xi0 <= rxmin && xi1 <= rxmin) return crossings; 533 if (xi0 >= rxmax && xi1 >= rxmax) { 534 if (y0 < y1) { 535 // y-increasing line segment... 536 // We know that y0 < rymax and y1 > rymin 537 if (y0 <= rymin) crossings++; 538 if (y1 >= rymax) crossings++; 539 } else if (y1 < y0) { 540 // y-decreasing line segment... 541 // We know that y1 < rymax and y0 > rymin 542 if (y1 <= rymin) crossings--; 543 if (y0 >= rymax) crossings--; 544 } 545 return crossings; 546 } 547 return RECT_INTERSECTS; 548 } 549 550 /** 551 * Accumulate the number of times the quad crosses the shadow 552 * extending to the right of the rectangle. See the comment 553 * for the RECT_INTERSECTS constant for more complete details. 554 */ rectCrossingsForQuad(int crossings, double rxmin, double rymin, double rxmax, double rymax, double x0, double y0, double xc, double yc, double x1, double y1, int level)555 public static int rectCrossingsForQuad(int crossings, 556 double rxmin, double rymin, 557 double rxmax, double rymax, 558 double x0, double y0, 559 double xc, double yc, 560 double x1, double y1, 561 int level) 562 { 563 if (y0 >= rymax && yc >= rymax && y1 >= rymax) return crossings; 564 if (y0 <= rymin && yc <= rymin && y1 <= rymin) return crossings; 565 if (x0 <= rxmin && xc <= rxmin && x1 <= rxmin) return crossings; 566 if (x0 >= rxmax && xc >= rxmax && x1 >= rxmax) { 567 // Quad is entirely to the right of the rect 568 // and the vertical range of the 3 Y coordinates of the quad 569 // overlaps the vertical range of the rect by a non-empty amount 570 // We now judge the crossings solely based on the line segment 571 // connecting the endpoints of the quad. 572 // Note that we may have 0, 1, or 2 crossings as the control 573 // point may be causing the Y range intersection while the 574 // two endpoints are entirely above or below. 575 if (y0 < y1) { 576 // y-increasing line segment... 577 if (y0 <= rymin && y1 > rymin) crossings++; 578 if (y0 < rymax && y1 >= rymax) crossings++; 579 } else if (y1 < y0) { 580 // y-decreasing line segment... 581 if (y1 <= rymin && y0 > rymin) crossings--; 582 if (y1 < rymax && y0 >= rymax) crossings--; 583 } 584 return crossings; 585 } 586 // The intersection of ranges is more complicated 587 // First do trivial INTERSECTS rejection of the cases 588 // where one of the endpoints is inside the rectangle. 589 if ((x0 < rxmax && x0 > rxmin && y0 < rymax && y0 > rymin) || 590 (x1 < rxmax && x1 > rxmin && y1 < rymax && y1 > rymin)) 591 { 592 return RECT_INTERSECTS; 593 } 594 // Otherwise, subdivide and look for one of the cases above. 595 // double precision only has 52 bits of mantissa 596 if (level > 52) { 597 return rectCrossingsForLine(crossings, 598 rxmin, rymin, rxmax, rymax, 599 x0, y0, x1, y1); 600 } 601 double x0c = (x0 + xc) / 2; 602 double y0c = (y0 + yc) / 2; 603 double xc1 = (xc + x1) / 2; 604 double yc1 = (yc + y1) / 2; 605 xc = (x0c + xc1) / 2; 606 yc = (y0c + yc1) / 2; 607 if (Double.isNaN(xc) || Double.isNaN(yc)) { 608 // [xy]c are NaN if any of [xy]0c or [xy]c1 are NaN 609 // [xy]0c or [xy]c1 are NaN if any of [xy][0c1] are NaN 610 // These values are also NaN if opposing infinities are added 611 return 0; 612 } 613 crossings = rectCrossingsForQuad(crossings, 614 rxmin, rymin, rxmax, rymax, 615 x0, y0, x0c, y0c, xc, yc, 616 level+1); 617 if (crossings != RECT_INTERSECTS) { 618 crossings = rectCrossingsForQuad(crossings, 619 rxmin, rymin, rxmax, rymax, 620 xc, yc, xc1, yc1, x1, y1, 621 level+1); 622 } 623 return crossings; 624 } 625 626 /** 627 * Accumulate the number of times the cubic crosses the shadow 628 * extending to the right of the rectangle. See the comment 629 * for the RECT_INTERSECTS constant for more complete details. 630 */ rectCrossingsForCubic(int crossings, double rxmin, double rymin, double rxmax, double rymax, double x0, double y0, double xc0, double yc0, double xc1, double yc1, double x1, double y1, int level)631 public static int rectCrossingsForCubic(int crossings, 632 double rxmin, double rymin, 633 double rxmax, double rymax, 634 double x0, double y0, 635 double xc0, double yc0, 636 double xc1, double yc1, 637 double x1, double y1, 638 int level) 639 { 640 if (y0 >= rymax && yc0 >= rymax && yc1 >= rymax && y1 >= rymax) { 641 return crossings; 642 } 643 if (y0 <= rymin && yc0 <= rymin && yc1 <= rymin && y1 <= rymin) { 644 return crossings; 645 } 646 if (x0 <= rxmin && xc0 <= rxmin && xc1 <= rxmin && x1 <= rxmin) { 647 return crossings; 648 } 649 if (x0 >= rxmax && xc0 >= rxmax && xc1 >= rxmax && x1 >= rxmax) { 650 // Cubic is entirely to the right of the rect 651 // and the vertical range of the 4 Y coordinates of the cubic 652 // overlaps the vertical range of the rect by a non-empty amount 653 // We now judge the crossings solely based on the line segment 654 // connecting the endpoints of the cubic. 655 // Note that we may have 0, 1, or 2 crossings as the control 656 // points may be causing the Y range intersection while the 657 // two endpoints are entirely above or below. 658 if (y0 < y1) { 659 // y-increasing line segment... 660 if (y0 <= rymin && y1 > rymin) crossings++; 661 if (y0 < rymax && y1 >= rymax) crossings++; 662 } else if (y1 < y0) { 663 // y-decreasing line segment... 664 if (y1 <= rymin && y0 > rymin) crossings--; 665 if (y1 < rymax && y0 >= rymax) crossings--; 666 } 667 return crossings; 668 } 669 // The intersection of ranges is more complicated 670 // First do trivial INTERSECTS rejection of the cases 671 // where one of the endpoints is inside the rectangle. 672 if ((x0 > rxmin && x0 < rxmax && y0 > rymin && y0 < rymax) || 673 (x1 > rxmin && x1 < rxmax && y1 > rymin && y1 < rymax)) 674 { 675 return RECT_INTERSECTS; 676 } 677 // Otherwise, subdivide and look for one of the cases above. 678 // double precision only has 52 bits of mantissa 679 if (level > 52) { 680 return rectCrossingsForLine(crossings, 681 rxmin, rymin, rxmax, rymax, 682 x0, y0, x1, y1); 683 } 684 double xmid = (xc0 + xc1) / 2; 685 double ymid = (yc0 + yc1) / 2; 686 xc0 = (x0 + xc0) / 2; 687 yc0 = (y0 + yc0) / 2; 688 xc1 = (xc1 + x1) / 2; 689 yc1 = (yc1 + y1) / 2; 690 double xc0m = (xc0 + xmid) / 2; 691 double yc0m = (yc0 + ymid) / 2; 692 double xmc1 = (xmid + xc1) / 2; 693 double ymc1 = (ymid + yc1) / 2; 694 xmid = (xc0m + xmc1) / 2; 695 ymid = (yc0m + ymc1) / 2; 696 if (Double.isNaN(xmid) || Double.isNaN(ymid)) { 697 // [xy]mid are NaN if any of [xy]c0m or [xy]mc1 are NaN 698 // [xy]c0m or [xy]mc1 are NaN if any of [xy][c][01] are NaN 699 // These values are also NaN if opposing infinities are added 700 return 0; 701 } 702 crossings = rectCrossingsForCubic(crossings, 703 rxmin, rymin, rxmax, rymax, 704 x0, y0, xc0, yc0, 705 xc0m, yc0m, xmid, ymid, level+1); 706 if (crossings != RECT_INTERSECTS) { 707 crossings = rectCrossingsForCubic(crossings, 708 rxmin, rymin, rxmax, rymax, 709 xmid, ymid, xmc1, ymc1, 710 xc1, yc1, x1, y1, level+1); 711 } 712 return crossings; 713 } 714 Curve(int direction)715 public Curve(int direction) { 716 this.direction = direction; 717 } 718 getDirection()719 public final int getDirection() { 720 return direction; 721 } 722 getWithDirection(int direction)723 public final Curve getWithDirection(int direction) { 724 return (this.direction == direction ? this : getReversedCurve()); 725 } 726 round(double v)727 public static double round(double v) { 728 //return Math.rint(v*10)/10; 729 return v; 730 } 731 orderof(double x1, double x2)732 public static int orderof(double x1, double x2) { 733 if (x1 < x2) { 734 return -1; 735 } 736 if (x1 > x2) { 737 return 1; 738 } 739 return 0; 740 } 741 signeddiffbits(double y1, double y2)742 public static long signeddiffbits(double y1, double y2) { 743 return (Double.doubleToLongBits(y1) - Double.doubleToLongBits(y2)); 744 } diffbits(double y1, double y2)745 public static long diffbits(double y1, double y2) { 746 return Math.abs(Double.doubleToLongBits(y1) - 747 Double.doubleToLongBits(y2)); 748 } prev(double v)749 public static double prev(double v) { 750 return Double.longBitsToDouble(Double.doubleToLongBits(v)-1); 751 } next(double v)752 public static double next(double v) { 753 return Double.longBitsToDouble(Double.doubleToLongBits(v)+1); 754 } 755 toString()756 public String toString() { 757 return ("Curve["+ 758 getOrder()+", "+ 759 ("("+round(getX0())+", "+round(getY0())+"), ")+ 760 controlPointString()+ 761 ("("+round(getX1())+", "+round(getY1())+"), ")+ 762 (direction == INCREASING ? "D" : "U")+ 763 "]"); 764 } 765 controlPointString()766 public String controlPointString() { 767 return ""; 768 } 769 getOrder()770 public abstract int getOrder(); 771 getXTop()772 public abstract double getXTop(); getYTop()773 public abstract double getYTop(); getXBot()774 public abstract double getXBot(); getYBot()775 public abstract double getYBot(); 776 getXMin()777 public abstract double getXMin(); getXMax()778 public abstract double getXMax(); 779 getX0()780 public abstract double getX0(); getY0()781 public abstract double getY0(); getX1()782 public abstract double getX1(); getY1()783 public abstract double getY1(); 784 XforY(double y)785 public abstract double XforY(double y); TforY(double y)786 public abstract double TforY(double y); XforT(double t)787 public abstract double XforT(double t); YforT(double t)788 public abstract double YforT(double t); dXforT(double t, int deriv)789 public abstract double dXforT(double t, int deriv); dYforT(double t, int deriv)790 public abstract double dYforT(double t, int deriv); 791 nextVertical(double t0, double t1)792 public abstract double nextVertical(double t0, double t1); 793 crossingsFor(double x, double y)794 public int crossingsFor(double x, double y) { 795 if (y >= getYTop() && y < getYBot()) { 796 if (x < getXMax() && (x < getXMin() || x < XforY(y))) { 797 return 1; 798 } 799 } 800 return 0; 801 } 802 accumulateCrossings(Crossings c)803 public boolean accumulateCrossings(Crossings c) { 804 double xhi = c.getXHi(); 805 if (getXMin() >= xhi) { 806 return false; 807 } 808 double xlo = c.getXLo(); 809 double ylo = c.getYLo(); 810 double yhi = c.getYHi(); 811 double y0 = getYTop(); 812 double y1 = getYBot(); 813 double tstart, ystart, tend, yend; 814 if (y0 < ylo) { 815 if (y1 <= ylo) { 816 return false; 817 } 818 ystart = ylo; 819 tstart = TforY(ylo); 820 } else { 821 if (y0 >= yhi) { 822 return false; 823 } 824 ystart = y0; 825 tstart = 0; 826 } 827 if (y1 > yhi) { 828 yend = yhi; 829 tend = TforY(yhi); 830 } else { 831 yend = y1; 832 tend = 1; 833 } 834 boolean hitLo = false; 835 boolean hitHi = false; 836 while (true) { 837 double x = XforT(tstart); 838 if (x < xhi) { 839 if (hitHi || x > xlo) { 840 return true; 841 } 842 hitLo = true; 843 } else { 844 if (hitLo) { 845 return true; 846 } 847 hitHi = true; 848 } 849 if (tstart >= tend) { 850 break; 851 } 852 tstart = nextVertical(tstart, tend); 853 } 854 if (hitLo) { 855 c.record(ystart, yend, direction); 856 } 857 return false; 858 } 859 enlarge(Rectangle2D r)860 public abstract void enlarge(Rectangle2D r); 861 getSubCurve(double ystart, double yend)862 public Curve getSubCurve(double ystart, double yend) { 863 return getSubCurve(ystart, yend, direction); 864 } 865 getReversedCurve()866 public abstract Curve getReversedCurve(); getSubCurve(double ystart, double yend, int dir)867 public abstract Curve getSubCurve(double ystart, double yend, int dir); 868 compareTo(Curve that, double[] yrange)869 public int compareTo(Curve that, double[] yrange) { 870 /* 871 System.out.println(this+".compareTo("+that+")"); 872 System.out.println("target range = "+yrange[0]+"=>"+yrange[1]); 873 */ 874 double y0 = yrange[0]; 875 double y1 = yrange[1]; 876 y1 = Math.min(Math.min(y1, this.getYBot()), that.getYBot()); 877 if (y1 <= yrange[0]) { 878 System.err.println("this == "+this); 879 System.err.println("that == "+that); 880 System.out.println("target range = "+yrange[0]+"=>"+yrange[1]); 881 throw new InternalError("backstepping from "+yrange[0]+" to "+y1); 882 } 883 yrange[1] = y1; 884 if (this.getXMax() <= that.getXMin()) { 885 if (this.getXMin() == that.getXMax()) { 886 return 0; 887 } 888 return -1; 889 } 890 if (this.getXMin() >= that.getXMax()) { 891 return 1; 892 } 893 // Parameter s for thi(s) curve and t for tha(t) curve 894 // [st]0 = parameters for top of current section of interest 895 // [st]1 = parameters for bottom of valid range 896 // [st]h = parameters for hypothesis point 897 // [d][xy]s = valuations of thi(s) curve at sh 898 // [d][xy]t = valuations of tha(t) curve at th 899 double s0 = this.TforY(y0); 900 double ys0 = this.YforT(s0); 901 if (ys0 < y0) { 902 s0 = refineTforY(s0, ys0, y0); 903 ys0 = this.YforT(s0); 904 } 905 double s1 = this.TforY(y1); 906 if (this.YforT(s1) < y0) { 907 s1 = refineTforY(s1, this.YforT(s1), y0); 908 //System.out.println("s1 problem!"); 909 } 910 double t0 = that.TforY(y0); 911 double yt0 = that.YforT(t0); 912 if (yt0 < y0) { 913 t0 = that.refineTforY(t0, yt0, y0); 914 yt0 = that.YforT(t0); 915 } 916 double t1 = that.TforY(y1); 917 if (that.YforT(t1) < y0) { 918 t1 = that.refineTforY(t1, that.YforT(t1), y0); 919 //System.out.println("t1 problem!"); 920 } 921 double xs0 = this.XforT(s0); 922 double xt0 = that.XforT(t0); 923 double scale = Math.max(Math.abs(y0), Math.abs(y1)); 924 double ymin = Math.max(scale * 1E-14, 1E-300); 925 if (fairlyClose(xs0, xt0)) { 926 double bump = ymin; 927 double maxbump = Math.min(ymin * 1E13, (y1 - y0) * .1); 928 double y = y0 + bump; 929 while (y <= y1) { 930 if (fairlyClose(this.XforY(y), that.XforY(y))) { 931 if ((bump *= 2) > maxbump) { 932 bump = maxbump; 933 } 934 } else { 935 y -= bump; 936 while (true) { 937 bump /= 2; 938 double newy = y + bump; 939 if (newy <= y) { 940 break; 941 } 942 if (fairlyClose(this.XforY(newy), that.XforY(newy))) { 943 y = newy; 944 } 945 } 946 break; 947 } 948 y += bump; 949 } 950 if (y > y0) { 951 if (y < y1) { 952 yrange[1] = y; 953 } 954 return 0; 955 } 956 } 957 //double ymin = y1 * 1E-14; 958 if (ymin <= 0) { 959 System.out.println("ymin = "+ymin); 960 } 961 /* 962 System.out.println("s range = "+s0+" to "+s1); 963 System.out.println("t range = "+t0+" to "+t1); 964 */ 965 while (s0 < s1 && t0 < t1) { 966 double sh = this.nextVertical(s0, s1); 967 double xsh = this.XforT(sh); 968 double ysh = this.YforT(sh); 969 double th = that.nextVertical(t0, t1); 970 double xth = that.XforT(th); 971 double yth = that.YforT(th); 972 /* 973 System.out.println("sh = "+sh); 974 System.out.println("th = "+th); 975 */ 976 try { 977 if (findIntersect(that, yrange, ymin, 0, 0, 978 s0, xs0, ys0, sh, xsh, ysh, 979 t0, xt0, yt0, th, xth, yth)) { 980 break; 981 } 982 } catch (Throwable t) { 983 System.err.println("Error: "+t); 984 System.err.println("y range was "+yrange[0]+"=>"+yrange[1]); 985 System.err.println("s y range is "+ys0+"=>"+ysh); 986 System.err.println("t y range is "+yt0+"=>"+yth); 987 System.err.println("ymin is "+ymin); 988 return 0; 989 } 990 if (ysh < yth) { 991 if (ysh > yrange[0]) { 992 if (ysh < yrange[1]) { 993 yrange[1] = ysh; 994 } 995 break; 996 } 997 s0 = sh; 998 xs0 = xsh; 999 ys0 = ysh; 1000 } else { 1001 if (yth > yrange[0]) { 1002 if (yth < yrange[1]) { 1003 yrange[1] = yth; 1004 } 1005 break; 1006 } 1007 t0 = th; 1008 xt0 = xth; 1009 yt0 = yth; 1010 } 1011 } 1012 double ymid = (yrange[0] + yrange[1]) / 2; 1013 /* 1014 System.out.println("final this["+s0+", "+sh+", "+s1+"]"); 1015 System.out.println("final y["+ys0+", "+ysh+"]"); 1016 System.out.println("final that["+t0+", "+th+", "+t1+"]"); 1017 System.out.println("final y["+yt0+", "+yth+"]"); 1018 System.out.println("final order = "+orderof(this.XforY(ymid), 1019 that.XforY(ymid))); 1020 System.out.println("final range = "+yrange[0]+"=>"+yrange[1]); 1021 */ 1022 /* 1023 System.out.println("final sx = "+this.XforY(ymid)); 1024 System.out.println("final tx = "+that.XforY(ymid)); 1025 System.out.println("final order = "+orderof(this.XforY(ymid), 1026 that.XforY(ymid))); 1027 */ 1028 return orderof(this.XforY(ymid), that.XforY(ymid)); 1029 } 1030 1031 public static final double TMIN = 1E-3; 1032 findIntersect(Curve that, double[] yrange, double ymin, int slevel, int tlevel, double s0, double xs0, double ys0, double s1, double xs1, double ys1, double t0, double xt0, double yt0, double t1, double xt1, double yt1)1033 public boolean findIntersect(Curve that, double[] yrange, double ymin, 1034 int slevel, int tlevel, 1035 double s0, double xs0, double ys0, 1036 double s1, double xs1, double ys1, 1037 double t0, double xt0, double yt0, 1038 double t1, double xt1, double yt1) 1039 { 1040 /* 1041 String pad = " "; 1042 pad = pad+pad+pad+pad+pad; 1043 pad = pad+pad; 1044 System.out.println("----------------------------------------------"); 1045 System.out.println(pad.substring(0, slevel)+ys0); 1046 System.out.println(pad.substring(0, slevel)+ys1); 1047 System.out.println(pad.substring(0, slevel)+(s1-s0)); 1048 System.out.println("-------"); 1049 System.out.println(pad.substring(0, tlevel)+yt0); 1050 System.out.println(pad.substring(0, tlevel)+yt1); 1051 System.out.println(pad.substring(0, tlevel)+(t1-t0)); 1052 */ 1053 if (ys0 > yt1 || yt0 > ys1) { 1054 return false; 1055 } 1056 if (Math.min(xs0, xs1) > Math.max(xt0, xt1) || 1057 Math.max(xs0, xs1) < Math.min(xt0, xt1)) 1058 { 1059 return false; 1060 } 1061 // Bounding boxes intersect - back off the larger of 1062 // the two subcurves by half until they stop intersecting 1063 // (or until they get small enough to switch to a more 1064 // intensive algorithm). 1065 if (s1 - s0 > TMIN) { 1066 double s = (s0 + s1) / 2; 1067 double xs = this.XforT(s); 1068 double ys = this.YforT(s); 1069 if (s == s0 || s == s1) { 1070 System.out.println("s0 = "+s0); 1071 System.out.println("s1 = "+s1); 1072 throw new InternalError("no s progress!"); 1073 } 1074 if (t1 - t0 > TMIN) { 1075 double t = (t0 + t1) / 2; 1076 double xt = that.XforT(t); 1077 double yt = that.YforT(t); 1078 if (t == t0 || t == t1) { 1079 System.out.println("t0 = "+t0); 1080 System.out.println("t1 = "+t1); 1081 throw new InternalError("no t progress!"); 1082 } 1083 if (ys >= yt0 && yt >= ys0) { 1084 if (findIntersect(that, yrange, ymin, slevel+1, tlevel+1, 1085 s0, xs0, ys0, s, xs, ys, 1086 t0, xt0, yt0, t, xt, yt)) { 1087 return true; 1088 } 1089 } 1090 if (ys >= yt) { 1091 if (findIntersect(that, yrange, ymin, slevel+1, tlevel+1, 1092 s0, xs0, ys0, s, xs, ys, 1093 t, xt, yt, t1, xt1, yt1)) { 1094 return true; 1095 } 1096 } 1097 if (yt >= ys) { 1098 if (findIntersect(that, yrange, ymin, slevel+1, tlevel+1, 1099 s, xs, ys, s1, xs1, ys1, 1100 t0, xt0, yt0, t, xt, yt)) { 1101 return true; 1102 } 1103 } 1104 if (ys1 >= yt && yt1 >= ys) { 1105 if (findIntersect(that, yrange, ymin, slevel+1, tlevel+1, 1106 s, xs, ys, s1, xs1, ys1, 1107 t, xt, yt, t1, xt1, yt1)) { 1108 return true; 1109 } 1110 } 1111 } else { 1112 if (ys >= yt0) { 1113 if (findIntersect(that, yrange, ymin, slevel+1, tlevel, 1114 s0, xs0, ys0, s, xs, ys, 1115 t0, xt0, yt0, t1, xt1, yt1)) { 1116 return true; 1117 } 1118 } 1119 if (yt1 >= ys) { 1120 if (findIntersect(that, yrange, ymin, slevel+1, tlevel, 1121 s, xs, ys, s1, xs1, ys1, 1122 t0, xt0, yt0, t1, xt1, yt1)) { 1123 return true; 1124 } 1125 } 1126 } 1127 } else if (t1 - t0 > TMIN) { 1128 double t = (t0 + t1) / 2; 1129 double xt = that.XforT(t); 1130 double yt = that.YforT(t); 1131 if (t == t0 || t == t1) { 1132 System.out.println("t0 = "+t0); 1133 System.out.println("t1 = "+t1); 1134 throw new InternalError("no t progress!"); 1135 } 1136 if (yt >= ys0) { 1137 if (findIntersect(that, yrange, ymin, slevel, tlevel+1, 1138 s0, xs0, ys0, s1, xs1, ys1, 1139 t0, xt0, yt0, t, xt, yt)) { 1140 return true; 1141 } 1142 } 1143 if (ys1 >= yt) { 1144 if (findIntersect(that, yrange, ymin, slevel, tlevel+1, 1145 s0, xs0, ys0, s1, xs1, ys1, 1146 t, xt, yt, t1, xt1, yt1)) { 1147 return true; 1148 } 1149 } 1150 } else { 1151 // No more subdivisions 1152 double xlk = xs1 - xs0; 1153 double ylk = ys1 - ys0; 1154 double xnm = xt1 - xt0; 1155 double ynm = yt1 - yt0; 1156 double xmk = xt0 - xs0; 1157 double ymk = yt0 - ys0; 1158 double det = xnm * ylk - ynm * xlk; 1159 if (det != 0) { 1160 double detinv = 1 / det; 1161 double s = (xnm * ymk - ynm * xmk) * detinv; 1162 double t = (xlk * ymk - ylk * xmk) * detinv; 1163 if (s >= 0 && s <= 1 && t >= 0 && t <= 1) { 1164 s = s0 + s * (s1 - s0); 1165 t = t0 + t * (t1 - t0); 1166 if (s < 0 || s > 1 || t < 0 || t > 1) { 1167 System.out.println("Uh oh!"); 1168 } 1169 double y = (this.YforT(s) + that.YforT(t)) / 2; 1170 if (y <= yrange[1] && y > yrange[0]) { 1171 yrange[1] = y; 1172 return true; 1173 } 1174 } 1175 } 1176 //System.out.println("Testing lines!"); 1177 } 1178 return false; 1179 } 1180 refineTforY(double t0, double yt0, double y0)1181 public double refineTforY(double t0, double yt0, double y0) { 1182 double t1 = 1; 1183 while (true) { 1184 double th = (t0 + t1) / 2; 1185 if (th == t0 || th == t1) { 1186 return t1; 1187 } 1188 double y = YforT(th); 1189 if (y < y0) { 1190 t0 = th; 1191 yt0 = y; 1192 } else if (y > y0) { 1193 t1 = th; 1194 } else { 1195 return t1; 1196 } 1197 } 1198 } 1199 fairlyClose(double v1, double v2)1200 public boolean fairlyClose(double v1, double v2) { 1201 return (Math.abs(v1 - v2) < 1202 Math.max(Math.abs(v1), Math.abs(v2)) * 1E-10); 1203 } 1204 getSegment(double[] coords)1205 public abstract int getSegment(double[] coords); 1206 } 1207