View Javadoc
1   /*
2    * Copyright (c) 1998, 2006, 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 curves, double x, double y) {
42          curves.add(new Order0(x, y));
43      }
44  
45      public static void insertLine(Vector 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 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 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 }