Java > Open Source Codes > java > awt > geom > CubicCurve2D


1 /*
2  * @(#)CubicCurve2D.java 1.29 03/12/19
3  *
4  * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5  * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6  */
7
8 package java.awt.geom;
9
10 import java.awt.Shape ;
11 import java.awt.Rectangle ;
12 import java.util.Arrays ;
13
14 /**
15  * The <code>CubicCurve2D</code> class defines a cubic parametric curve
16  * segment in (x,&nbsp; y) coordinate space.
17  * <p>
18  * This class is only the abstract superclass for all objects which
19  * store a 2D cubic curve segment.
20  * The actual storage representation of the coordinates is left to
21  * the subclass.
22  *
23  * @version 1.29, 12/19/03
24  * @author Jim Graham
25  */
26 public abstract class CubicCurve2D implements Shape , Cloneable {
27     /**
28      * A cubic parametric curve segment specified with float coordinates.
29      */
30     public static class Float extends CubicCurve2D {
31     /**
32      * The X coordinate of the start point
33      * of the cubic curve segment.
34      */
35     public float x1;
36
37     /**
38      * The Y coordinate of the start point
39      * of the cubic curve segment.
40      */
41     public float y1;
42
43     /**
44      * The X coordinate of the first control point
45      * of the cubic curve segment.
46      */
47     public float ctrlx1;
48
49     /**
50      * The Y coordinate of the first control point
51      * of the cubic curve segment.
52      */
53     public float ctrly1;
54
55     /**
56      * The X coordinate of the second control point
57      * of the cubic curve segment.
58      */
59     public float ctrlx2;
60
61     /**
62      * The Y coordinate of the second control point
63      * of the cubic curve segment.
64      */
65     public float ctrly2;
66
67     /**
68      * The X coordinate of the end point
69      * of the cubic curve segment.
70      */
71     public float x2;
72
73     /**
74      * The Y coordinate of the end point
75      * of the cubic curve segment.
76      */
77     public float y2;
78
79     /**
80      * Constructs and initializes a CubicCurve with coordinates
81      * (0, 0, 0, 0, 0, 0).
82      */
83     public Float() {
84     }
85
86     /**
87      * Constructs and initializes a <code>CubicCurve2D</code> from
88      * the specified coordinates.
89      * @param x1,&nbsp;y1 the first specified coordinates for the start
90      * point of the resulting <code>CubicCurve2D</code>
91      * @param ctrlx1,&nbsp;ctrly1 the second specified coordinates for the
92      * first control point of the resulting
93      * <code>CubicCurve2D</code>
94      * @param ctrlx2,&nbsp;ctrly2 the third specified coordinates for the
95      * second control point of the resulting
96      * <code>CubicCurve2D</code>
97      * @param x2,&nbsp;y2 the fourth specified coordinates for the end
98      * point of the resulting <code>CubicCurve2D</code>
99      */
100     public Float(float x1, float y1,
101                    float ctrlx1, float ctrly1,
102                    float ctrlx2, float ctrly2,
103                    float x2, float y2) {
104         setCurve(x1, y1, ctrlx1, ctrly1, ctrlx2, ctrly2, x2, y2);
105     }
106
107     /**
108      * Returns the X coordinate of the start point
109      * in double precision.
110      * @return the X coordinate of the start point of the
111      * <code>CubicCurve2D</code>.
112      */
113     public double getX1() {
114         return (double) x1;
115     }
116
117     /**
118      * Returns the Y coordinate of the start point
119      * in double precision.
120      * @return the Y coordinate of the start point of the
121      * <code>CubicCurve2D</code>.
122      */
123     public double getY1() {
124         return (double) y1;
125     }
126
127     /**
128      * Returns the start point.
129      * @return a {@link Point2D} that is the start point of the
130      * <code>CubicCurve2D</code>.
131      */
132     public Point2D getP1() {
133         return new Point2D.Float (x1, y1);
134     }
135
136     /**
137      * Returns the X coordinate of the first control point
138      * in double precision.
139      * @return the X coordinate of the first control point of the
140      * <code>CubicCurve2D</code>.
141      */
142     public double getCtrlX1() {
143         return (double) ctrlx1;
144     }
145
146     /**
147      * Returns the Y coordinate of the first control point
148      * in double precision.
149      * @return the Y coordinate of the first control point of the
150      * <code>CubicCurve2D</code>.
151      */
152     public double getCtrlY1() {
153         return (double) ctrly1;
154     }
155
156     /**
157      * Returns the first control point.
158      * @return a <code>Point2D</code> that is the first control point
159      * of the <code>CubicCurve2D</code>.
160      */
161     public Point2D getCtrlP1() {
162         return new Point2D.Float (ctrlx1, ctrly1);
163     }
164
165     /**
166      * Returns the X coordinate of the second control point
167      * in double precision.
168      * @return the X coordinate of the second control point of the
169      * <code>CubicCurve2D</code>.
170      */
171     public double getCtrlX2() {
172         return (double) ctrlx2;
173     }
174
175     /**
176      * Returns the Y coordinate of the second control point
177      * in double precision.
178      * @return the Y coordinate of the second control point of the
179      * <code>CubicCurve2D</code>.
180      */
181     public double getCtrlY2() {
182         return (double) ctrly2;
183     }
184
185     /**
186      * Returns the second control point.
187      * @return a <code>Point2D</code> that is the second control point
188      * of the <code>CubicCurve2D</code>.
189      */
190     public Point2D getCtrlP2() {
191         return new Point2D.Float (ctrlx2, ctrly2);
192     }
193
194     /**
195      * Returns the X coordinate of the end point
196      * in double precision.
197      * @return the X coordinate of the end point of the
198      * <code>CubicCurve2D</code>.
199      */
200     public double getX2() {
201         return (double) x2;
202     }
203
204     /**
205      * Returns the Y coordinate of the end point
206      * in double precision.
207      * @return the Y coordinate of the end point of the
208      * <code>CubicCurve2D</code>.
209      */
210     public double getY2() {
211         return (double) y2;
212     }
213
214     /**
215      * Returns the end point.
216      * @return a <code>Point2D</code> that is the end point
217      * of the <code>CubicCurve2D</code>.
218      */
219     public Point2D getP2() {
220         return new Point2D.Float (x2, y2);
221     }
222
223     /**
224      * Sets the location of the endpoints and controlpoints
225      * of this <code>CubicCurve2D</code> to the specified double
226      * coordinates.
227      * @param x1,&nbsp;y1 the first specified coordinates used to set the start
228      * point of this <code>CubicCurve2D</code>
229      * @param ctrlx1,&nbsp;ctrly1 the second specified coordinates used to set the
230      * first control point of this <code>CubicCurve2D</code>
231      * @param ctrlx2,&nbsp;ctrly2 the third specified coordinates used to set the
232      * second control point of this <code>CubicCurve2D</code>
233      * @param x2,&nbsp;y2 the fourth specified coordinates used to set the end
234      * point of this <code>CubicCurve2D</code>
235      */
236     public void setCurve(double x1, double y1,
237                  double ctrlx1, double ctrly1,
238                  double ctrlx2, double ctrly2,
239                  double x2, double y2) {
240         this.x1 = (float) x1;
241         this.y1 = (float) y1;
242         this.ctrlx1 = (float) ctrlx1;
243         this.ctrly1 = (float) ctrly1;
244         this.ctrlx2 = (float) ctrlx2;
245         this.ctrly2 = (float) ctrly2;
246         this.x2 = (float) x2;
247         this.y2 = (float) y2;
248     }
249
250     /**
251      * Sets the location of the endpoints and controlpoints
252      * of this curve to the specified float coordinates.
253      * @param x1,&nbsp;y1 the first specified coordinates used to set the start
254      * point of this <code>CubicCurve2D</code>
255      * @param ctrlx1,&nbsp;ctrly1 the second specified coordinates used to set the
256      * first control point of this <code>CubicCurve2D</code>
257      * @param ctrlx2,&nbsp;ctrly2 the third specified coordinates used to set the
258      * second control point of this <code>CubicCurve2D</code>
259      * @param x2,&nbsp;y2 the fourth specified coordinates used to set the end
260      * point of this <code>CubicCurve2D</code>
261      */
262     public void setCurve(float x1, float y1,
263                  float ctrlx1, float ctrly1,
264                  float ctrlx2, float ctrly2,
265                  float x2, float y2) {
266         this.x1 = x1;
267         this.y1 = y1;
268         this.ctrlx1 = ctrlx1;
269         this.ctrly1 = ctrly1;
270         this.ctrlx2 = ctrlx2;
271         this.ctrly2 = ctrly2;
272         this.x2 = x2;
273         this.y2 = y2;
274     }
275
276     /**
277      * Returns the bounding box of the shape.
278      * @return a {@link Rectangle2D} that is the bounding box of the
279      * shape.
280      */
281     public Rectangle2D getBounds2D() {
282         float left = Math.min(Math.min(x1, x2),
283                     Math.min(ctrlx1, ctrlx2));
284         float top = Math.min(Math.min(y1, y2),
285                     Math.min(ctrly1, ctrly2));
286         float right = Math.max(Math.max(x1, x2),
287                     Math.max(ctrlx1, ctrlx2));
288         float bottom = Math.max(Math.max(y1, y2),
289                     Math.max(ctrly1, ctrly2));
290         return new Rectangle2D.Float (left, top,
291                      right - left, bottom - top);
292     }
293     }
294
295     /**
296      * A cubic parametric curve segment specified with double coordinates.
297      */
298     public static class Double extends CubicCurve2D {
299     /**
300      * The X coordinate of the start point
301      * of the cubic curve segment.
302      */
303     public double x1;
304
305     /**
306      * The Y coordinate of the start point
307      * of the cubic curve segment.
308      */
309     public double y1;
310
311     /**
312      * The X coordinate of the first control point
313      * of the cubic curve segment.
314      */
315     public double ctrlx1;
316
317     /**
318      * The Y coordinate of the first control point
319      * of the cubic curve segment.
320      */
321     public double ctrly1;
322
323     /**
324      * The X coordinate of the second control point
325      * of the cubic curve segment.
326      */
327     public double ctrlx2;
328
329     /**
330      * The Y coordinate of the second control point
331      * of the cubic curve segment.
332      */
333     public double ctrly2;
334
335     /**
336      * The X coordinate of the end point
337      * of the cubic curve segment.
338      */
339     public double x2;
340
341     /**
342      * The Y coordinate of the end point
343      * of the cubic curve segment.
344      */
345     public double y2;
346
347     /**
348      * Constructs and initializes a CubicCurve with coordinates
349      * (0, 0, 0, 0, 0, 0).
350      */
351     public Double() {
352     }
353
354     /**
355      * Constructs and initializes a <code>CubicCurve2D</code> from
356      * the specified coordinates.
357      * @param x1,&nbsp;y1 the first specified coordinates for the start
358      * point of the resulting <code>CubicCurve2D</code>
359      * @param ctrlx1,&nbsp;ctrly1 the second specified coordinates for the
360      * first control point of the resulting
361      * <code>CubicCurve2D</code>
362      * @param ctrlx2,&nbsp;ctrly2 the third specified coordinates for the
363      * second control point of the resulting
364      * <code>CubicCurve2D</code>
365      * @param x2,&nbsp;y2 the fourth specified coordinates for the end
366      * point of the resulting <code>CubicCurve2D</code>
367      */
368     public Double(double x1, double y1,
369               double ctrlx1, double ctrly1,
370               double ctrlx2, double ctrly2,
371               double x2, double y2) {
372         setCurve(x1, y1, ctrlx1, ctrly1, ctrlx2, ctrly2, x2, y2);
373     }
374
375     /**
376      * Returns the X coordinate of the start point
377      * in double precision.
378      * @return the X coordinate of the first control point of the
379      * <code>CubicCurve2D</code>.
380      */
381     public double getX1() {
382         return x1;
383     }
384
385     /**
386      * Returns the Y coordinate of the start point
387      * in double precision.
388      * @return the Y coordinate of the start point of the
389      * <code>CubicCurve2D</code>.
390      */
391     public double getY1() {
392         return y1;
393     }
394
395     /**
396      * Returns the start point.
397      * @return a <code>Point2D</code> that is the start point of the
398      * <code>CubicCurve2D</code>.
399      */
400     public Point2D getP1() {
401         return new Point2D.Double (x1, y1);
402     }
403
404     /**
405      * Returns the X coordinate of the first control point
406      * in double precision.
407      * @return the X coordinate of the first control point of the
408      * <code>CubicCurve2D</code>.
409      */
410     public double getCtrlX1() {
411         return ctrlx1;
412     }
413
414     /**
415      * Returns the Y coordinate of the first control point
416      * in double precision.
417      * @return the Y coordinate of the first control point of the
418      * <code>CubicCurve2D</code>.
419      */
420     public double getCtrlY1() {
421         return ctrly1;
422     }
423
424     /**
425      * Returns the first control point.
426      * @return a <code>Point2D</code> that is the first control point of the
427      * <code>CubicCurve2D</code>.
428      */
429     public Point2D getCtrlP1() {
430         return new Point2D.Double (ctrlx1, ctrly1);
431     }
432
433     /**
434      * Returns the X coordinate of the second control point
435      * in double precision.
436      * @return the X coordinate of the second control point of the
437      * <code>CubicCurve2D</code>.
438      */
439     public double getCtrlX2() {
440         return ctrlx2;
441     }
442
443     /**
444      * Returns the Y coordinate of the second control point
445      * in double precision.
446      * @return the Y coordinate of the second control point of the
447      * <code>CubicCurve2D</code>.
448      */
449     public double getCtrlY2() {
450         return ctrly2;
451     }
452
453     /**
454      * Returns the second control point.
455      * @return a <code>Point2D</code> that is the second control point of
456      * the <code>CubicCurve2D</code>.
457      */
458     public Point2D getCtrlP2() {
459         return new Point2D.Double (ctrlx2, ctrly2);
460     }
461
462     /**
463      * Returns the X coordinate of the end point
464      * in double precision.
465      * @return the X coordinate of the end point of the
466      * <code>CubicCurve2D</code>.
467      */
468     public double getX2() {
469         return x2;
470     }
471
472     /**
473      * Returns the Y coordinate of the end point
474      * in double precision.
475      * @return the Y coordinate of the end point of the
476      * <code>CubicCurve2D</code>.
477      */
478     public double getY2() {
479         return y2;
480     }
481
482     /**
483      * Returns the end point.
484      * @return a <code>Point2D</code> that is the end point of
485      * the <code>CubicCurve2D</code>.
486      */
487     public Point2D getP2() {
488         return new Point2D.Double (x2, y2);
489     }
490
491     /**
492      * Sets the location of the endpoints and controlpoints
493      * of this curve to the specified double coordinates.
494      * @param x1,&nbsp;y1 the first specified coordinates used to set the start
495      * point of this <code>CubicCurve2D</code>
496      * @param ctrlx1,&nbsp;ctrly1 the second specified coordinates used to set the
497      * first control point of this <code>CubicCurve2D</code>
498      * @param ctrlx2,&nbsp;ctrly2 the third specified coordinates used to set the
499      * second control point of this <code>CubicCurve2D</code>
500      * @param x2,&nbsp;y2 the fourth specified coordinates used to set the end
501      * point of this <code>CubicCurve2D</code>
502      */
503     public void setCurve(double x1, double y1,
504                  double ctrlx1, double ctrly1,
505                  double ctrlx2, double ctrly2,
506                  double x2, double y2) {
507         this.x1 = x1;
508         this.y1 = y1;
509         this.ctrlx1 = ctrlx1;
510         this.ctrly1 = ctrly1;
511         this.ctrlx2 = ctrlx2;
512         this.ctrly2 = ctrly2;
513         this.x2 = x2;
514         this.y2 = y2;
515     }
516
517     /**
518      * Returns the bounding box of the shape.
519      * @return a <code>Rectangle2D</code> that is the bounding box
520      * of the shape.
521      */
522     public Rectangle2D getBounds2D() {
523         double left = Math.min(Math.min(x1, x2),
524                      Math.min(ctrlx1, ctrlx2));
525         double top = Math.min(Math.min(y1, y2),
526                      Math.min(ctrly1, ctrly2));
527         double right = Math.max(Math.max(x1, x2),
528                      Math.max(ctrlx1, ctrlx2));
529         double bottom = Math.max(Math.max(y1, y2),
530                      Math.max(ctrly1, ctrly2));
531         return new Rectangle2D.Double (left, top,
532                       right - left, bottom - top);
533     }
534     }
535
536     /**
537      * This is an abstract class that cannot be instantiated directly.
538      * Type-specific implementation subclasses are available for
539      * instantiation and provide a number of formats for storing
540      * the information necessary to satisfy the various accessor
541      * methods below.
542      *
543      * @see java.awt.geom.CubicCurve2D.Float
544      * @see java.awt.geom.CubicCurve2D.Double
545      */
546     protected CubicCurve2D() {
547     }
548
549     /**
550      * Returns the X coordinate of the start point in double precision.
551      * @return the X coordinate of the start point of the
552      * <code>CubicCurve2D</code>.
553      */
554     public abstract double getX1();
555
556     /**
557      * Returns the Y coordinate of the start point in double precision.
558      * @return the Y coordinate of the start point of the
559      * <code>CubicCurve2D</code>.
560      */
561     public abstract double getY1();
562
563     /**
564      * Returns the start point.
565      * @return a <code>Point2D</code> that is the start point of
566      * the <code>CubicCurve2D</code>.
567      */
568     public abstract Point2D getP1();
569
570     /**
571      * Returns the X coordinate of the first control point in double precision.
572      * @return the X coordinate of the first control point of the
573      * <code>CubicCurve2D</code>.
574      */
575     public abstract double getCtrlX1();
576
577     /**
578      * Returns the Y coordinate of the first control point in double precision.
579      * @return the Y coordinate of the first control point of the
580      * <code>CubicCurve2D</code>.
581      */
582     public abstract double getCtrlY1();
583
584     /**
585      * Returns the first control point.
586      * @return a <code>Point2D</code> that is the first control point of
587      * the <code>CubicCurve2D</code>.
588      */
589     public abstract Point2D getCtrlP1();
590
591     /**
592      * Returns the X coordinate of the second control point
593      * in double precision.
594      * @return the X coordinate of the second control point of the
595      * <code>CubicCurve2D</code>.
596      */
597     public abstract double getCtrlX2();
598
599     /**
600      * Returns the Y coordinate of the second control point
601      * in double precision.
602      * @return the Y coordinate of the second control point of the
603      * <code>CubicCurve2D</code>.
604      */
605     public abstract double getCtrlY2();
606
607     /**
608      * Returns the second control point.
609      * @return a <code>Point2D</code> that is the second control point of
610      * the <code>CubicCurve2D</code>.
611      */
612     public abstract Point2D getCtrlP2();
613
614     /**
615      * Returns the X coordinate of the end point in double precision.
616      * @return the X coordinate of the end point of the
617      * <code>CubicCurve2D</code>.
618      */
619     public abstract double getX2();
620
621     /**
622      * Returns the Y coordinate of the end point in double precision.
623      * @return the Y coordinate of the end point of the
624      * <code>CubicCurve2D</code>.
625      */
626     public abstract double getY2();
627
628     /**
629      * Returns the end point.
630      * @return a <code>Point2D</code> that is the end point of
631      * the <code>CubicCurve2D</code>.
632      */
633     public abstract Point2D getP2();
634
635     /**
636      * Sets the location of the endpoints and controlpoints of this curve
637      * to the specified double coordinates.
638      * @param x1,&nbsp;y1 the first specified coordinates used to set the start
639      * point of this <code>CubicCurve2D</code>
640      * @param ctrlx1,&nbsp;ctrly1 the second specified coordinates used to set the
641      * first control point of this <code>CubicCurve2D</code>
642      * @param ctrlx2,&nbsp;ctrly2 the third specified coordinates used to set the
643      * second control point of this <code>CubicCurve2D</code>
644      * @param x2,&nbsp;y2 the fourth specified coordinates used to set the end
645      * point of this <code>CubicCurve2D</code>
646      */
647     public abstract void setCurve(double x1, double y1,
648                   double ctrlx1, double ctrly1,
649                   double ctrlx2, double ctrly2,
650                   double x2, double y2);
651
652     /**
653      * Sets the location of the endpoints and controlpoints of this curve
654      * to the double coordinates at the specified offset in the specified
655      * array.
656      * @param coords a double array containing coordinates
657      * @param offset the index of <code>coords</code> at which to begin
658      * setting the endpoints and controlpoints of this curve
659      * to the coordinates contained in <code>coords</code>
660      */
661     public void setCurve(double[] coords, int offset) {
662     setCurve(coords[offset + 0], coords[offset + 1],
663          coords[offset + 2], coords[offset + 3],
664          coords[offset + 4], coords[offset + 5],
665          coords[offset + 6], coords[offset + 7]);
666     }
667
668     /**
669      * Sets the location of the endpoints and controlpoints of this curve
670      * to the specified <code>Point2D</code> coordinates.
671      * @param p1 the first specified <code>Point2D</code> used to set the
672      * start point of this curve
673      * @param cp1 the second specified <code>Point2D</code> used to set the
674      * first control point of this curve
675      * @param cp2 the third specified <code>Point2D</code> used to set the
676      * second control point of this curve
677      * @param p2 the fourth specified <code>Point2D</code> used to set the
678      * end point of this curve
679      */
680     public void setCurve(Point2D p1, Point2D cp1, Point2D cp2, Point2D p2) {
681     setCurve(p1.getX(), p1.getY(), cp1.getX(), cp1.getY(),
682          cp2.getX(), cp2.getY(), p2.getX(), p2.getY());
683     }
684
685     /**
686      * Sets the location of the endpoints and controlpoints of this curve
687      * to the coordinates of the <code>Point2D</code> objects at the specified
688      * offset in the specified array.
689      * @param pts an array of <code>Point2D</code> objects
690      * @param offset the index of <code>pts</code> at which to begin setting
691      * the endpoints and controlpoints of this curve to the
692      * points contained in <code>pts</code>
693      */
694     public void setCurve(Point2D [] pts, int offset) {
695     setCurve(pts[offset + 0].getX(), pts[offset + 0].getY(),
696          pts[offset + 1].getX(), pts[offset + 1].getY(),
697          pts[offset + 2].getX(), pts[offset + 2].getY(),
698          pts[offset + 3].getX(), pts[offset + 3].getY());
699     }
700
701     /**
702      * Sets the location of the endpoints and controlpoints of this curve
703      * to the same as those in the specified <code>CubicCurve2D</code>.
704      * @param c the specified <code>CubicCurve2D</code>
705      */
706     public void setCurve(CubicCurve2D c) {
707     setCurve(c.getX1(), c.getY1(), c.getCtrlX1(), c.getCtrlY1(),
708          c.getCtrlX2(), c.getCtrlY2(), c.getX2(), c.getY2());
709     }
710
711     /**
712      * Returns the square of the flatness of the cubic curve specified
713      * by the indicated controlpoints. The flatness is the maximum distance
714      * of a controlpoint from the line connecting the endpoints.
715      * @param x1,&nbsp;y1 the first specified coordinates that specify the start
716      * point of a <code>CubicCurve2D</code>
717      * @param ctrlx1,&nbsp;ctrly1 the second specified coordinates that specify the
718      * first control point of a <code>CubicCurve2D</code>
719      * @param ctrlx2,&nbsp;ctrly2 the third specified coordinates that specify the
720      * second control point of a <code>CubicCurve2D</code>
721      * @param x2,&nbsp;y2 the fourth specified coordinates that specify the
722      * end point of a <code>CubicCurve2D</code>
723      * @return the square of the flatness of the <code>CubicCurve2D</code>
724      * represented by the specified coordinates.
725      */
726     public static double getFlatnessSq(double x1, double y1,
727                        double ctrlx1, double ctrly1,
728                        double ctrlx2, double ctrly2,
729                        double x2, double y2) {
730     return Math.max(Line2D.ptSegDistSq(x1, y1, x2, y2, ctrlx1, ctrly1),
731             Line2D.ptSegDistSq(x1, y1, x2, y2, ctrlx2, ctrly2));
732             
733     }
734
735     /**
736      * Returns the flatness of the cubic curve specified
737      * by the indicated controlpoints. The flatness is the maximum distance
738      * of a controlpoint from the line connecting the endpoints.
739      * @param x1,&nbsp;y1 the first specified coordinates that specify the start
740      * point of a <code>CubicCurve2D</code>
741      * @param ctrlx1,&nbsp;ctrly1 the second specified coordinates that specify the
742      * first control point of a <code>CubicCurve2D</code>
743      * @param ctrlx2,&nbsp;ctrly2 the third specified coordinates that specify the
744      * second control point of a <code>CubicCurve2D</code>
745      * @param x2,&nbsp;y2 the fourth specified coordinates that specify the
746      * end point of a <code>CubicCurve2D</code>
747      * @return the flatness of the <code>CubicCurve2D</code>
748      * represented by the specified coordinates.
749      */
750     public static double getFlatness(double x1, double y1,
751                      double ctrlx1, double ctrly1,
752                      double ctrlx2, double ctrly2,
753                      double x2, double y2) {
754     return Math.sqrt(getFlatnessSq(x1, y1, ctrlx1, ctrly1,
755                        ctrlx2, ctrly2, x2, y2));
756     }
757
758     /**
759      * Returns the square of the flatness of the cubic curve specified
760      * by the controlpoints stored in the indicated array at the
761      * indicated index. The flatness is the maximum distance
762      * of a controlpoint from the line connecting the endpoints.
763      * @param coords an array containing coordinates
764      * @param offset the index of <code>coords</code> at which to begin
765      * setting the endpoints and controlpoints of this curve
766      * to the coordinates contained in <code>coords</code>
767      * @return the square of the flatness of the <code>CubicCurve2D</code>
768      * specified by the coordinates in <code>coords</code> at
769      * the specified offset.
770      */
771     public static double getFlatnessSq(double coords[], int offset) {
772     return getFlatnessSq(coords[offset + 0], coords[offset + 1],
773                  coords[offset + 2], coords[offset + 3],
774                  coords[offset + 4], coords[offset + 5],
775                  coords[offset + 6], coords[offset + 7]);
776     }
777
778     /**
779      * Returns the flatness of the cubic curve specified
780      * by the controlpoints stored in the indicated array at the
781      * indicated index. The flatness is the maximum distance
782      * of a controlpoint from the line connecting the endpoints.
783      * @param coords an array containing coordinates
784      * @param offset the index of <code>coords</code> at which to begin
785      * setting the endpoints and controlpoints of this curve
786      * to the coordinates contained in <code>coords</code>
787      * @return the flatness of the <code>CubicCurve2D</code>
788      * specified by the coordinates in <code>coords</code> at
789      * the specified offset.
790      */
791     public static double getFlatness(double coords[], int offset) {
792     return getFlatness(coords[offset + 0], coords[offset + 1],
793                coords[offset + 2], coords[offset + 3],
794                coords[offset + 4], coords[offset + 5],
795                coords[offset + 6], coords[offset + 7]);
796     }
797
798     /**
799      * Returns the square of the flatness of this curve. The flatness is the
800      * maximum distance of a controlpoint from the line connecting the
801      * endpoints.
802      * @return the square of the flatness of this curve.
803      */
804     public double getFlatnessSq() {
805     return getFlatnessSq(getX1(), getY1(), getCtrlX1(), getCtrlY1(),
806                  getCtrlX2(), getCtrlY2(), getX2(), getY2());
807     }
808
809     /**
810      * Returns the flatness of this curve. The flatness is the
811      * maximum distance of a controlpoint from the line connecting the
812      * endpoints.
813      * @return the flatness of this curve.
814      */
815     public double getFlatness() {
816     return getFlatness(getX1(), getY1(), getCtrlX1(), getCtrlY1(),
817                getCtrlX2(), getCtrlY2(), getX2(), getY2());
818     }
819
820     /**
821      * Subdivides this cubic curve and stores the resulting two
822      * subdivided curves into the left and right curve parameters.
823      * Either or both of the left and right objects may be the same
824      * as this object or null.
825      * @param left the cubic curve object for storing for the left or
826      * first half of the subdivided curve
827      * @param right the cubic curve object for storing for the right or
828      * second half of the subdivided curve
829      */
830     public void subdivide(CubicCurve2D left, CubicCurve2D right) {
831     subdivide(this, left, right);
832     }
833
834     /**
835      * Subdivides the cubic curve specified by the <code>src</code> parameter
836      * and stores the resulting two subdivided curves into the
837      * <code>left</code> and <code>right</code> curve parameters.
838      * Either or both of the <code>left</code> and <code>right</code> objects
839      * may be the same as the <code>src</code> object or <code>null</code>.
840      * @param src the cubic curve to be subdivided
841      * @param left the cubic curve object for storing the left or
842      * first half of the subdivided curve
843      * @param right the cubic curve object for storing the right or
844      * second half of the subdivided curve
845      */
846     public static void subdivide(CubicCurve2D src,
847                  CubicCurve2D left,
848                  CubicCurve2D right) {
849     double x1 = src.getX1();
850     double y1 = src.getY1();
851     double ctrlx1 = src.getCtrlX1();
852     double ctrly1 = src.getCtrlY1();
853     double ctrlx2 = src.getCtrlX2();
854     double ctrly2 = src.getCtrlY2();
855     double x2 = src.getX2();
856     double y2 = src.getY2();
857     double centerx = (ctrlx1 + ctrlx2) / 2.0;
858     double centery = (ctrly1 + ctrly2) / 2.0;
859     ctrlx1 = (x1 + ctrlx1) / 2.0;
860     ctrly1 = (y1 + ctrly1) / 2.0;
861     ctrlx2 = (x2 + ctrlx2) / 2.0;
862     ctrly2 = (y2 + ctrly2) / 2.0;
863     double ctrlx12 = (ctrlx1 + centerx) / 2.0;
864     double ctrly12 = (ctrly1 + centery) / 2.0;
865     double ctrlx21 = (ctrlx2 + centerx) / 2.0;
866     double ctrly21 = (ctrly2 + centery) / 2.0;
867     centerx = (ctrlx12 + ctrlx21) / 2.0;
868     centery = (ctrly12 + ctrly21) / 2.0;
869     if (left != null) {
870         left.setCurve(x1, y1, ctrlx1, ctrly1,
871               ctrlx12, ctrly12, centerx, centery);
872     }
873     if (right != null) {
874         right.setCurve(centerx, centery, ctrlx21, ctrly21,
875                ctrlx2, ctrly2, x2, y2);
876     }
877     }
878
879     /**
880      * Subdivides the cubic curve specified by the coordinates
881      * stored in the <code>src</code> array at indices <code>srcoff</code>
882      * through (<code>srcoff</code>&nbsp;+&nbsp;7) and stores the
883      * resulting two subdivided curves into the two result arrays at the
884      * corresponding indices.
885      * Either or both of the <code>left</code> and <code>right</code>
886      * arrays may be <code>null</code> or a reference to the same array
887      * as the <code>src</code> array.
888      * Note that the last point in the first subdivided curve is the
889      * same as the first point in the second subdivided curve. Thus,
890      * it is possible to pass the same array for <code>left</code>
891      * and <code>right</code> and to use offsets, such as <code>rightoff</code>
892      * equals (<code>leftoff</code> + 6), in order
893      * to avoid allocating extra storage for this common point.
894      * @param src the array holding the coordinates for the source curve
895      * @param srcoff the offset into the array of the beginning of the
896      * the 6 source coordinates
897      * @param left the array for storing the coordinates for the first
898      * half of the subdivided curve
899      * @param leftoff the offset into the array of the beginning of the
900      * the 6 left coordinates
901      * @param right the array for storing the coordinates for the second
902      * half of the subdivided curve
903      * @param rightoff the offset into the array of the beginning of the
904      * the 6 right coordinates
905      */
906     public static void subdivide(double src[], int srcoff,
907                  double left[], int leftoff,
908                  double right[], int rightoff) {
909     double x1 = src[srcoff + 0];
910     double y1 = src[srcoff + 1];
911     double ctrlx1 = src[srcoff + 2];
912     double ctrly1 = src[srcoff + 3];
913     double ctrlx2 = src[srcoff + 4];
914     double ctrly2 = src[srcoff + 5];
915     double x2 = src[srcoff + 6];
916     double y2 = src[srcoff + 7];
917     if (left != null) {
918         left[leftoff + 0] = x1;
919         left[leftoff + 1] = y1;
920     }
921     if (right != null) {
922         right[rightoff + 6] = x2;
923         right[rightoff + 7] = y2;
924     }
925     x1 = (x1 + ctrlx1) / 2.0;
926     y1 = (y1 + ctrly1) / 2.0;
927     x2 = (x2 + ctrlx2) / 2.0;
928     y2 = (y2 + ctrly2) / 2.0;
929     double centerx = (ctrlx1 + ctrlx2) / 2.0;
930     double centery = (ctrly1 + ctrly2) / 2.0;
931     ctrlx1 = (x1 + centerx) / 2.0;
932     ctrly1 = (y1 + centery) / 2.0;
933     ctrlx2 = (x2 + centerx) / 2.0;
934     ctrly2 = (y2 + centery) / 2.0;
935     centerx = (ctrlx1 + ctrlx2) / 2.0;
936     centery = (ctrly1 + ctrly2) / 2.0;
937     if (left != null) {
938         left[leftoff + 2] = x1;
939         left[leftoff + 3] = y1;
940         left[leftoff + 4] = ctrlx1;
941         left[leftoff + 5] = ctrly1;
942         left[leftoff + 6] = centerx;
943         left[leftoff + 7] = centery;
944     }
945     if (right != null) {
946         right[rightoff + 0] = centerx;
947         right[rightoff + 1] = centery;
948         right[rightoff + 2] = ctrlx2;
949         right[rightoff + 3] = ctrly2;
950         right[rightoff + 4] = x2;
951         right[rightoff + 5] = y2;
952     }
953     }
954
955     /**
956      * Solves the cubic whose coefficients are in the <code>eqn</code>
957      * array and places the non-complex roots back into the same array,
958      * returning the number of roots. The solved cubic is represented
959      * by the equation:
960      * <pre>
961      * eqn = {c, b, a, d}
962      * dx^3 + ax^2 + bx + c = 0
963      * </pre>
964      * A return value of -1 is used to distinguish a constant equation
965      * that might be always 0 or never 0 from an equation that has no
966      * zeroes.
967      * @param eqn an array containing coefficients for a cubic
968      * @return the number of roots, or -1 if the equation is a constant.
969      */
970     public static int solveCubic(double eqn[]) {
971     return solveCubic(eqn, eqn);
972     }
973
974     /**
975      * Solve the cubic whose coefficients are in the <code>eqn</code>
976      * array and place the non-complex roots into the <code>res</code>
977      * array, returning the number of roots.
978      * The cubic solved is represented by the equation:
979      * eqn = {c, b, a, d}
980      * dx^3 + ax^2 + bx + c = 0
981      * A return value of -1 is used to distinguish a constant equation,
982      * which may be always 0 or never 0, from an equation which has no
983      * zeroes.
984      * @param eqn the specified array of coefficients to use to solve
985      * the cubic equation
986      * @param res the array that contains the non-complex roots
987      * resulting from the solution of the cubic equation
988      * @return the number of roots, or -1 if the equation is a constant
989      */
990     public static int solveCubic(double eqn[], double res[]) {
991     // From Numerical Recipes, 5.6, Quadratic and Cubic Equations
992 double d = eqn[3];
993     if (d == 0.0) {
994         // The cubic has degenerated to quadratic (or line or ...).
995 return QuadCurve2D.solveQuadratic(eqn, res);
996     }
997     double a = eqn[2] / d;
998     double b = eqn[1] / d;
999     double c = eqn[0] / d;
1000    int roots = 0;
1001    double Q = (a * a - 3.0 * b) / 9.0;
1002    double R = (2.0 * a * a * a - 9.0 * a * b + 27.0 * c) / 54.0;
1003    double R2 = R * R;
1004    double Q3 = Q * Q * Q;
1005    a = a / 3.0;
1006    if (R2 < Q3) {
1007        double theta = Math.acos(R / Math.sqrt(Q3));
1008        Q = -2.0 * Math.sqrt(Q);
1009        if (res == eqn) {
1010        // Copy the eqn so that we don't clobber it with the
1011 // roots. This is needed so that fixRoots can do its
1012 // work with the original equation.
1013 eqn = new double[4];
1014        System.arraycopy(res, 0, eqn, 0, 4);
1015        }
1016        res[roots++] = Q * Math.cos(theta / 3.0) - a;
1017        res[roots++] = Q * Math.cos((theta + Math.PI * 2.0)/ 3.0) - a;
1018        res[roots++] = Q * Math.cos((theta - Math.PI * 2.0)/ 3.0) - a;
1019        fixRoots(res, eqn);
1020    } else {
1021        boolean neg = (R < 0.0);
1022        double S = Math.sqrt(R2 - Q3);
1023        if (neg) {
1024        R = -R;
1025        }
1026        double A = Math.pow(R + S, 1.0 / 3.0);
1027        if (!neg) {
1028        A = -A;
1029        }
1030        double B = (A == 0.0) ? 0.0 : (Q / A);
1031        res[roots++] = (A + B) - a;
1032    }
1033    return roots;
1034    }
1035
1036    /*
1037     * This pruning step is necessary since solveCubic uses the
1038     * cosine function to calculate the roots when there are 3
1039     * of them. Since the cosine method can have an error of
1040     * +/- 1E-14 we need to make sure that we don't make any
1041     * bad decisions due to an error.
1042     *
1043     * If the root is not near one of the endpoints, then we will
1044     * only have a slight inaccuracy in calculating the x intercept
1045     * which will only cause a slightly wrong answer for some
1046     * points very close to the curve. While the results in that
1047     * case are not as accurate as they could be, they are not
1048     * disastrously inaccurate either.
1049     *
1050     * On the other hand, if the error happens near one end of
1051     * the curve, then our processing to reject values outside
1052     * of the t=[0,1] range will fail and the results of that
1053     * failure will be disastrous since for an entire horizontal
1054     * range of test points, we will either overcount or undercount
1055     * the crossings and get a wrong answer for all of them, even
1056     * when they are clearly and obviously inside or outside the
1057     * curve.
1058     *
1059     * To work around this problem, we try a couple of Newton-Raphson
1060     * iterations to see if the true root is closer to the endpoint
1061     * or further away. If it is further away, then we can stop
1062     * since we know we are on the right side of the endpoint. If
1063     * we change direction, then either we are now being dragged away
1064     * from the endpoint in which case the first condition will cause
1065     * us to stop, or we have passed the endpoint and are headed back.
1066     * In the second case, we simply evaluate the slope at the
1067     * endpoint itself and place ourselves on the appropriate side
1068     * of it or on it depending on that result.
1069     */
1070    private static void fixRoots(double res[], double eqn[]) {
1071    final double EPSILON = 1E-5;
1072    for (int i = 0; i < 3; i++) {
1073        double t = res[i];
1074        if (Math.abs(t) < EPSILON) {
1075        res[i] = findZero(t, 0, eqn);
1076        } else if (Math.abs(t - 1) < EPSILON) {
1077        res[i] = findZero(t, 1, eqn);
1078        }
1079    }
1080    }
1081
1082    private static double solveEqn(double eqn[], int order, double t) {
1083    double v = eqn[order];
1084    while (--order >= 0) {
1085        v = v * t + eqn[order];
1086    }
1087    return v;
1088    }
1089
1090    private static double findZero(double t, double target, double eqn[]) {
1091    double slopeqn[] = {eqn[1], 2*eqn[2], 3*eqn[3]};
1092    double slope;
1093    double origdelta = 0;
1094    double origt = t;
1095    while (true) {
1096        slope = solveEqn(slopeqn, 2, t);
1097        if (slope == 0) {
1098        // At a local minima - must return
1099 return t;
1100        }
1101        double y = solveEqn(eqn, 3, t);
1102        if (y == 0) {
1103        // Found it! - return it
1104 return t;
1105        }
1106        // assert(slope != 0 && y != 0);
1107 double delta = - (y / slope);
1108        // assert(delta != 0);
1109 if (origdelta == 0) {
1110        origdelta = delta;
1111        }
1112        if (t < target) {
1113        if (delta < 0) return t;
1114        } else if (t > target) {
1115        if (delta > 0) return t;
1116        } else { /* t == target */
1117        return (delta > 0
1118            ? (target + java.lang.Double.MIN_VALUE)
1119            : (target - java.lang.Double.MIN_VALUE));
1120        }
1121        double newt = t + delta;
1122        if (t == newt) {
1123        // The deltas are so small that we aren't moving...
1124 return t;
1125        }
1126        if (delta * origdelta < 0) {
1127        // We have reversed our path.
1128 int tag = (origt < t
1129               ? getTag(target, origt, t)
1130               : getTag(target, t, origt));
1131        if (tag != INSIDE) {
1132            // Local minima found away from target - return the middle
1133 return (origt + t) / 2;
1134        }
1135        // Local minima somewhere near target - move to target
1136 // and let the slope determine the resulting t.
1137 t = target;
1138        } else {
1139        t = newt;
1140        }
1141    }
1142    }
1143
1144    /**
1145     * Tests if a specified coordinate is inside the boundary of the shape.
1146     * @param x,&nbsp;y the specified coordinate to be tested
1147     * @return <code>true</code> if the coordinate is inside the boundary of
1148     * the shape; <code>false</code> otherwise.
1149     */
1150    public boolean contains(double x, double y) {
1151    // We count the "Y" crossings to determine if the point is
1152 // inside the curve bounded by its closing line.
1153 int crossings = 0;
1154    double x1 = getX1();
1155    double y1 = getY1();
1156    double x2 = getX2();
1157    double y2 = getY2();
1158    // First check for a crossing of the line connecting the endpoints
1159 double dy = y2 - y1;
1160    if ((dy > 0.0 && y >= y1 && y <= y2) ||
1161        (dy < 0.0 && y <= y1 && y >= y2))
1162    {
1163        if (x < x1 + (y - y1) * (x2 - x1) / dy) {
1164        crossings++;
1165        }
1166    }
1167    // Solve the Y parametric equation for intersections with y
1168 double ctrlx1 = getCtrlX1();
1169    double ctrly1 = getCtrlY1();
1170    double ctrlx2 = getCtrlX2();
1171    double ctrly2 = getCtrlY2();
1172    boolean include0 = ((y2 - y1) * (ctrly1 - y1) >= 0);
1173    boolean include1 = ((y1 - y2) * (ctrly2 - y2) >= 0);
1174    double eqn[] = new double[4];
1175    double res[] = new double[4];
1176    fillEqn(eqn, y, y1, ctrly1, ctrly2, y2);
1177    int roots = solveCubic(eqn, res);
1178    roots = evalCubic(res, roots,
1179              include0, include1, eqn,
1180              x1, ctrlx1, ctrlx2, x2);
1181    while (--roots >= 0) {
1182        if (x < res[roots]) {
1183        crossings++;
1184        }
1185    }
1186    return ((crossings & 1) == 1);
1187    }
1188
1189    /**
1190     * Tests if a specified <code>Point2D</code> is inside the boundary of
1191     * the shape.
1192     * @param p the specified <code>Point2D</code> to be tested
1193     * @return <code>true</code> if the <code>p</code> is inside the boundary
1194     * of the shape; <code>false</code> otherwise.
1195     */
1196    public boolean contains(Point2D p) {
1197    return contains(p.getX(), p.getY());
1198    }
1199
1200    /*
1201     * Fill an array with the coefficients of the parametric equation
1202     * in t, ready for solving against val with solveCubic.
1203     * We currently have:
1204     * val = P(t) = C1(1-t)^3 + 3CP1 t(1-t)^2 + 3CP2 t^2(1-t) + C2 t^3
1205     * = C1 - 3C1t + 3C1t^2 - C1t^3 +
1206     * 3CP1t - 6CP1t^2 + 3CP1t^3 +
1207     * 3CP2t^2 - 3CP2t^3 +
1208     * C2t^3
1209     * 0 = (C1 - val) +
1210     * (3CP1 - 3C1) t +
1211     * (3C1 - 6CP1 + 3CP2) t^2 +
1212     * (C2 - 3CP2 + 3CP1 - C1) t^3
1213     * 0 = C + Bt + At^2 + Dt^3
1214     * C = C1 - val
1215     * B = 3*CP1 - 3*C1
1216     * A = 3*CP2 - 6*CP1 + 3*C1
1217     * D = C2 - 3*CP2 + 3*CP1 - C1
1218     * @param x,&nbsp;y the coordinates of the upper left corner of the specified
1219     * rectangular shape
1220     * @param w the width of the specified rectangular shape
1221     * @param h the height of the specified rectangular shape
1222     * @return <code>true</code> if the shape intersects the interior of the
1223     * the specified set of rectangular coordinates;
1224     * <code>false</code> otherwise.
1225     */
1226    private static void fillEqn(double eqn[], double val,
1227                double c1, double cp1, double cp2, double c2) {
1228    eqn[0] = c1 - val;
1229    eqn[1] = (cp1 - c1) * 3.0;
1230    eqn[2] = (cp2 - cp1 - cp1 + c1) * 3.0;
1231    eqn[3] = c2 + (cp1 - cp2) * 3.0 - c1;
1232    return;
1233    }
1234
1235    /*
1236     * Evaluate the t values in the first num slots of the vals[] array
1237     * and place the evaluated values back into the same array. Only
1238     * evaluate t values that are within the range <0, 1>, including
1239     * the 0 and 1 ends of the range iff the include0 or include1
1240     * booleans are true. If an "inflection" equation is handed in,
1241     * then any points which represent a point of inflection for that
1242     * cubic equation are also ignored.
1243     */
1244    private static int evalCubic(double vals[], int num,
1245                 boolean include0,
1246                 boolean include1,
1247                 double inflect[],
1248                 double c1, double cp1,
1249                 double cp2, double c2) {
1250    int j = 0;
1251    for (int i = 0; i < num; i++) {
1252        double t = vals[i];
1253        if ((include0 ? t >= 0 : t > 0) &&
1254        (include1 ? t <= 1 : t < 1) &&
1255        (inflect == null ||
1256         inflect[1] + (2*inflect[2] + 3*inflect[3]*t)*t != 0))
1257        {
1258        double u = 1 - t;
1259        vals[j++] = c1*u*u*u + 3*cp1*t*u*u + 3*cp2*t*t*u + c2*t*t*t;
1260        }
1261    }
1262    return j;
1263    }
1264
1265    private static final int BELOW = -2;
1266    private static final int LOWEDGE = -1;
1267    private static final int INSIDE = 0;
1268    private static final int HIGHEDGE = 1;
1269    private static final int ABOVE = 2;
1270
1271    /*
1272     * Determine where coord lies with respect to the range from
1273     * low to high. It is assumed that low <= high. The return
1274     * value is one of the 5 values BELOW, LOWEDGE, INSIDE, HIGHEDGE,
1275     * or ABOVE.
1276     */
1277    private static int getTag(double coord, double low, double high) {
1278    if (coord <= low) {
1279        return (coord < low ? BELOW : LOWEDGE);
1280    }
1281    if (coord >= high) {
1282        return (coord > high ? ABOVE : HIGHEDGE);
1283    }
1284    return INSIDE;
1285    }
1286
1287    /*
1288     * Determine if the pttag represents a coordinate that is already
1289     * in its test range, or is on the border with either of the two
1290     * opttags representing another coordinate that is "towards the
1291     * inside" of that test range. In other words, are either of the
1292     * two "opt" points "drawing the pt inward"?
1293     */
1294    private static boolean inwards(int pttag, int opt1tag, int opt2tag) {
1295    switch (pttag) {
1296    case BELOW:
1297    case ABOVE:
1298    default:
1299        return false;
1300    case LOWEDGE:
1301        return (opt1tag >= INSIDE || opt2tag >= INSIDE);
1302    case INSIDE:
1303        return true;
1304    case HIGHEDGE:
1305        return (opt1tag <= INSIDE || opt2tag <= INSIDE);
1306    }
1307    }
1308
1309    /**
1310     * Tests if the shape intersects the interior of a specified
1311     * set of rectangular coordinates.
1312     * @param x,&nbsp;y the coordinates of the upper left corner
1313     * of the specified rectangular area
1314     * @param w the width of the specified rectangular area
1315     * @param h the height of the specified rectangular area
1316     * @return <code>true</code> if the shape intersects the
1317     * interior of the specified rectangular area;
1318     * <code>false</code> otherwise.
1319     */
1320    public boolean intersects(double x, double y, double w, double h) {
1321    // Trivially reject non-existant rectangles
1322 if (w < 0 || h < 0) {
1323        return false;
1324    }
1325
1326    // Trivially accept if either endpoint is inside the rectangle
1327 // (not on its border since it may end there and not go inside)
1328 // Record where they lie with respect to the rectangle.
1329 // -1 => left, 0 => inside, 1 => right
1330 double x1 = getX1();
1331    double y1 = getY1();
1332    int x1tag = getTag(x1, x, x+w);
1333    int y1tag = getTag(y1, y, y+h);
1334    if (x1tag == INSIDE && y1tag == INSIDE) {
1335        return true;
1336    }
1337    double x2 = getX2();
1338    double y2 = getY2();
1339    int x2tag = getTag(x2, x, x+w);
1340    int y2tag = getTag(y2, y, y+h);
1341    if (x2tag == INSIDE && y2tag == INSIDE) {
1342        return true;
1343    }
1344
1345    double ctrlx1 = getCtrlX1();
1346    double ctrly1 = getCtrlY1();
1347    double ctrlx2 = getCtrlX2();
1348    double ctrly2 = getCtrlY2();
1349    int ctrlx1tag = getTag(ctrlx1, x, x+w);
1350    int ctrly1tag = getTag(ctrly1, y, y+h);
1351    int ctrlx2tag = getTag(ctrlx2, x, x+w);
1352    int ctrly2tag = getTag(ctrly2, y, y+h);
1353
1354    // Trivially reject if all points are entirely to one side of
1355 // the rectangle.
1356 if (x1tag < INSIDE && x2tag < INSIDE &&
1357        ctrlx1tag < INSIDE && ctrlx2tag < INSIDE)
1358    {
1359        return false; // All points left
1360 }
1361    if (y1tag < INSIDE && y2tag < INSIDE &&
1362        ctrly1tag < INSIDE && ctrly2tag < INSIDE)
1363    {
1364        return false; // All points above
1365 }
1366    if (x1tag > INSIDE && x2tag > INSIDE &&
1367        ctrlx1tag > INSIDE && ctrlx2tag > INSIDE)
1368    {
1369        return false; // All points right
1370 }
1371    if (y1tag > INSIDE && y2tag > INSIDE &&
1372        ctrly1tag > INSIDE && ctrly2tag > INSIDE)
1373    {
1374        return false; // All points below
1375 }
1376
1377    // Test for endpoints on the edge where either the segment
1378 // or the curve is headed "inwards" from them
1379 // Note: These tests are a superset of the fast endpoint tests
1380 // above and thus repeat those tests, but take more time
1381 // and cover more cases
1382 if (inwards(x1tag, x2tag, ctrlx1tag) &&
1383        inwards(y1tag, y2tag, ctrly1tag))
1384    {
1385        // First endpoint on border with either edge moving inside
1386 return true;
1387    }
1388    if (inwards(x2tag, x1tag, ctrlx2tag) &&
1389        inwards(y2tag, y1tag, ctrly2tag))
1390    {
1391        // Second endpoint on border with either edge moving inside
1392 return true;
1393    }
1394
1395    // Trivially accept if endpoints span directly across the rectangle
1396 boolean xoverlap = (x1tag * x2tag <= 0);
1397    boolean yoverlap = (y1tag * y2tag <= 0);
1398    if (x1tag == INSIDE && x2tag == INSIDE && yoverlap) {
1399        return true;
1400    }
1401    if (y1tag == INSIDE && y2tag == INSIDE && xoverlap) {
1402        return true;
1403    }
1404
1405    // We now know that both endpoints are outside the rectangle
1406 // but the 4 points are not all on one side of the rectangle.
1407 // Therefore the curve cannot be contained inside the rectangle,
1408 // but the rectangle might be contained inside the curve, or
1409 // the curve might intersect the boundary of the rectangle.
1410
1411    double[] eqn = new double[4];
1412    double[] res = new double[4];
1413    if (!yoverlap) {
1414        // Both y coordinates for the closing segment are above or
1415 // below the rectangle which means that we can only intersect
1416 // if the curve crosses the top (or bottom) of the rectangle
1417 // in more than one place and if those crossing locations
1418 // span the horizontal range of the rectangle.
1419 fillEqn(eqn, (y1tag < INSIDE ? y : y+h), y1, ctrly1, ctrly2, y2);
1420        int num = solveCubic(eqn, res);
1421        num = evalCubic(res, num, true, true, null,
1422                x1, ctrlx1, ctrlx2, x2);
1423        // odd counts imply the crossing was out of [0,1] bounds
1424 // otherwise there is no way for that part of the curve to
1425 // "return" to meet its endpoint
1426 return (num == 2 &&
1427            getTag(res[0], x, x+w) * getTag(res[1], x, x+w) <= 0);
1428    }
1429
1430    // Y ranges overlap. Now we examine the X ranges
1431 if (!xoverlap) {
1432        // Both x coordinates for the closing segment are left of
1433 // or right of the rectangle which means that we can only
1434 // intersect if the curve crosses the left (or right) edge
1435 // of the rectangle in more than one place and if those
1436 // crossing locations span the vertical range of the rectangle.
1437 fillEqn(eqn, (x1tag < INSIDE ? x : x+w), x1, ctrlx1, ctrlx2, x2);
1438        int num = solveCubic(eqn, res);
1439        num = evalCubic(res, num, true, true, null,
1440                y1, ctrly1, ctrly2, y2);
1441        // odd counts imply the crossing was out of [0,1] bounds
1442 // otherwise there is no way for that part of the curve to
1443 // "return" to meet its endpoint
1444 return (num == 2 &&
1445            getTag(res[0], y, y+h) * getTag(res[1], y, y+h) <= 0);
1446    }
1447
1448    // The X and Y ranges of the endpoints overlap the X and Y
1449 // ranges of the rectangle, now find out how the endpoint
1450 // line segment intersects the Y range of the rectangle
1451 double dx = x2 - x1;
1452    double dy = y2 - y1;
1453    double k = y2 * x1 - x2 * y1;
1454    int c1tag, c2tag;
1455    if (y1tag == INSIDE) {
1456        c1tag = x1tag;
1457    } else {
1458        c1tag = getTag((k + dx * (y1tag < INSIDE ? y : y+h)) / dy, x, x+w);
1459    }
1460    if (y2tag == INSIDE) {
1461        c2tag = x2tag;
1462    } else {
1463        c2tag = getTag((k + dx * (y2tag < INSIDE ? y : y+h)) / dy, x, x+w);
1464    }
1465    // If the part of the line segment that intersects the Y range
1466 // of the rectangle crosses it horizontally - trivially accept
1467 if (c1tag * c2tag <= 0) {
1468        return true;
1469    }
1470
1471    // Now we know that both the X and Y ranges intersect and that
1472 // the endpoint line segment does not directly cross the rectangle.
1473 //
1474 // We can almost treat this case like one of the cases above
1475 // where both endpoints are to one side, except that we may
1476 // get one or three intersections of the curve with the vertical
1477 // side of the rectangle. This is because the endpoint segment
1478 // accounts for the other intersection in an even pairing. Thus,
1479 // with the endpoint crossing we end up with 2 or 4 total crossings.
1480 //
1481 // (Remember there is overlap in both the X and Y ranges which
1482 // means that the segment itself must cross at least one vertical
1483 // edge of the rectangle - in particular, the "near vertical side"
1484 // - leaving an odd number of intersections for the curve.)
1485 //
1486 // Now we calculate the y tags of all the intersections on the
1487 // "near vertical side" of the rectangle. We will have one with
1488 // the endpoint segment, and one or three with the curve. If
1489 // any pair of those vertical intersections overlap the Y range
1490 // of the rectangle, we have an intersection. Otherwise, we don't.
1491
1492    // c1tag = vertical intersection class of the endpoint segment
1493 //
1494 // Choose the y tag of the endpoint that was not on the same
1495 // side of the rectangle as the subsegment calculated above.
1496 // Note that we can "steal" the existing Y tag of that endpoint
1497 // since it will be provably the same as the vertical intersection.
1498 c1tag = ((c1tag * x1tag <= 0) ? y1tag : y2tag);
1499
1500    // Now we have to calculate an array of solutions of the curve
1501 // with the "near vertical side" of the rectangle. Then we
1502 // need to sort the tags and do a pairwise range test to see
1503 // if either of the pairs of crossings spans the Y range of
1504 // the rectangle.
1505 //
1506 // Note that the c2tag can still tell us which vertical edge
1507 // to test against.
1508 fillEqn(eqn, (c2tag < INSIDE ? x : x+w), x1, ctrlx1, ctrlx2, x2);
1509    int num = solveCubic(eqn, res);
1510    num = evalCubic(res, num, true, true, null, y1, ctrly1, ctrly2, y2);
1511
1512    // Now put all of the tags into a bucket and sort them. There
1513 // is an intersection iff one of the pairs of tags "spans" the
1514 // Y range of the rectangle.
1515 int tags[] = new int[num+1];
1516    for (int i = 0; i < num; i++) {
1517        tags[i] = getTag(res[i], y, y+h);
1518    }
1519    tags[num] = c1tag;
1520    Arrays.sort(tags);
1521    return ((num >= 1 && tags[0] * tags[1] <= 0) ||
1522        (num >= 3 && tags[2] * tags[3] <= 0));
1523    }
1524
1525    /**
1526     * Tests if the shape intersects the interior of a specified
1527     * <code>Rectangle2D</code>.
1528     * @param r the specified <code>Rectangle2D</code> to be tested
1529     * @return <code>true</code> if the shape intersects the interior of
1530     * the specified <code>Rectangle2D</code>;
1531     * <code>false</code> otherwise.
1532     */
1533    public boolean intersects(Rectangle2D r) {
1534    return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight());
1535    }
1536
1537    /**
1538     * Tests if the interior of the shape entirely contains the specified
1539     * set of rectangular coordinates.
1540     * @param x,&nbsp;y the coordinates of the upper left corner of the specified
1541     * rectangular shape
1542     * @param w the width of the specified rectangular shape
1543     * @param h the height of the specified rectangular shape
1544     * @return <code>true</code> if the shape entirely contains
1545     * the specified set of rectangular coordinates;
1546     * <code>false</code> otherwise.
1547     */
1548    public boolean contains(double x, double y, double w, double h) {
1549    // Assertion: Cubic curves closed by connecting their
1550 // endpoints form either one or two convex halves with
1551 // the closing line segment as an edge of both sides.
1552 if (!(contains(x, y) &&
1553          contains(x + w, y) &&
1554          contains(x + w, y + h) &&
1555          contains(x, y + h))) {
1556        return false;
1557    }
1558    // Either the rectangle is entirely inside one of the convex
1559 // halves or it crosses from one to the other, in which case
1560 // it must intersect the closing line segment.
1561 Rectangle2D rect = new Rectangle2D.Double (x, y, w, h);
1562    return !rect.intersectsLine(getX1(), getY1(), getX2(), getY2());
1563    }
1564
1565    /**
1566     * Tests if the interior of the shape entirely contains the specified
1567     * <code>Rectangle2D</code>.
1568     * @param r the specified <code>Rectangle2D</code> to be tested
1569     * @return <code>true</code> if the shape entirely contains
1570     * the specified <code>Rectangle2D</code>;
1571     * <code>false</code> otherwise.
1572     */
1573    public boolean contains(Rectangle2D r) {
1574    return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight());
1575    }
1576
1577    /**
1578     * Returns the bounding box of the shape.
1579     * @return a {@link Rectangle} that is the bounding box of the shape.
1580     */
1581    public Rectangle getBounds() {
1582    return getBounds2D().getBounds();
1583    }
1584
1585    /**
1586     * Returns an iteration object that defines the boundary of the
1587     * shape.
1588     * The iterator for this class is not multi-threaded safe,
1589     * which means that this <code>CubicCurve2D</code> class does not
1590     * guarantee that modifications to the geometry of this
1591     * <code>CubicCurve2D</code> object do not affect any iterations of
1592     * that geometry that are already in process.
1593     * @param at an optional <code>AffineTransform</code> to be applied to the
1594     * coordinates as they are returned in the iteration, or <code>null</code>
1595     * if untransformed coordinates are desired
1596     * @return the <code>PathIterator</code> object that returns the
1597     * geometry of the outline of this <code>CubicCurve2D</code>, one
1598     * segment at a time.
1599     */
1600    public PathIterator getPathIterator(AffineTransform at) {
1601    return new CubicIterator (this, at);
1602    }
1603
1604    /**
1605     * Return an iteration object that defines the boundary of the
1606     * flattened shape.
1607     * The iterator for this class is not multi-threaded safe,
1608     * which means that this <code>CubicCurve2D</code> class does not
1609     * guarantee that modifications to the geometry of this
1610     * <code>CubicCurve2D</code> object do not affect any iterations of
1611     * that geometry that are already in process.
1612     * @param at an optional <code>AffineTransform</code> to be applied to the
1613     * coordinates as they are returned in the iteration, or <code>null</code>
1614     * if untransformed coordinates are desired
1615     * @param flatness the maximum amount that the control points
1616     * for a given curve can vary from colinear before a subdivided
1617     * curve is replaced by a straight line connecting the endpoints
1618     * @return the <code>PathIterator</code> object that returns the
1619     * geometry of the outline of this <code>CubicCurve2D</code>, one segment at a time.
1620     */
1621    public PathIterator getPathIterator(AffineTransform at, double flatness) {
1622    return new FlatteningPathIterator (getPathIterator(at), flatness);
1623    }
1624
1625    /**
1626     * Creates a new object of the same class as this object.
1627     *
1628     * @return a clone of this instance.
1629     * @exception OutOfMemoryError if there is not enough memory.
1630     * @see java.lang.Cloneable
1631     * @since 1.2
1632     */
1633    public Object clone() {
1634    try {
1635        return super.clone();
1636    } catch (CloneNotSupportedException e) {
1637        // this shouldn't happen, since we are Cloneable
1638 throw new InternalError ();
1639    }
1640    }
1641}
1642

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags