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