1 /*
2 * Copyright (c) 1998, 2014, 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
41 public static void insertMove(Vector<Curve> curves, double x, double y) {
42 curves.add(new Order0(x, y));
43 }
44
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
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
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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
715 public Curve(int direction) {
716 this.direction = direction;
717 }
718
719 public final int getDirection() {
720 return direction;
721 }
722
723 public final Curve getWithDirection(int direction) {
724 return (this.direction == direction ? this : getReversedCurve());
725 }
726
727 public static double round(double v) {
728 //return Math.rint(v*10)/10;
729 return v;
730 }
731
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
742 public static long signeddiffbits(double y1, double y2) {
743 return (Double.doubleToLongBits(y1) - Double.doubleToLongBits(y2));
744 }
745 public static long diffbits(double y1, double y2) {
746 return Math.abs(Double.doubleToLongBits(y1) -
747 Double.doubleToLongBits(y2));
748 }
749 public static double prev(double v) {
750 return Double.longBitsToDouble(Double.doubleToLongBits(v)-1);
751 }
752 public static double next(double v) {
753 return Double.longBitsToDouble(Double.doubleToLongBits(v)+1);
754 }
755
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
766 public String controlPointString() {
767 return "";
768 }
769
770 public abstract int getOrder();
771
772 public abstract double getXTop();
773 public abstract double getYTop();
774 public abstract double getXBot();
775 public abstract double getYBot();
776
777 public abstract double getXMin();
778 public abstract double getXMax();
779
780 public abstract double getX0();
781 public abstract double getY0();
782 public abstract double getX1();
783 public abstract double getY1();
784
785 public abstract double XforY(double y);
786 public abstract double TforY(double y);
787 public abstract double XforT(double t);
788 public abstract double YforT(double t);
789 public abstract double dXforT(double t, int deriv);
790 public abstract double dYforT(double t, int deriv);
791
792 public abstract double nextVertical(double t0, double t1);
793
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
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
860 public abstract void enlarge(Rectangle2D r);
861
862 public Curve getSubCurve(double ystart, double yend) {
863 return getSubCurve(ystart, yend, direction);
864 }
865
866 public abstract Curve getReversedCurve();
867 public abstract Curve getSubCurve(double ystart, double yend, int dir);
868
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
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
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
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
1205 public abstract int getSegment(double coords[]);
1206 }