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.io.Serializable;
31 import sun.awt.geom.Curve;
32
33 /**
34 * The <code>QuadCurve2D</code> class defines a quadratic parametric curve
35 * segment in {@code (x,y)} coordinate space.
36 * <p>
37 * This class is only the abstract superclass for all objects that
38 * store a 2D quadratic curve segment.
39 * The actual storage representation of the coordinates is left to
40 * the subclass.
41 *
42 * @author Jim Graham
43 * @since 1.2
44 */
45 public abstract class QuadCurve2D implements Shape, Cloneable {
46
47 /**
48 * A quadratic parametric curve segment specified with
49 * {@code float} coordinates.
50 *
51 * @since 1.2
52 */
53 public static class Float extends QuadCurve2D implements Serializable {
54 /**
55 * The X coordinate of the start point of the quadratic curve
56 * segment.
57 * @since 1.2
58 * @serial
59 */
60 public float x1;
61
62 /**
63 * The Y coordinate of the start point of the quadratic curve
64 * segment.
65 * @since 1.2
66 * @serial
67 */
68 public float y1;
69
70 /**
71 * The X coordinate of the control point of the quadratic curve
72 * segment.
73 * @since 1.2
74 * @serial
75 */
76 public float ctrlx;
77
78 /**
79 * The Y coordinate of the control point of the quadratic curve
80 * segment.
81 * @since 1.2
82 * @serial
83 */
84 public float ctrly;
85
86 /**
87 * The X coordinate of the end point of the quadratic curve
88 * segment.
89 * @since 1.2
90 * @serial
91 */
92 public float x2;
93
94 /**
95 * The Y coordinate of the end point of the quadratic curve
96 * segment.
97 * @since 1.2
98 * @serial
99 */
100 public float y2;
101
102 /**
103 * Constructs and initializes a <code>QuadCurve2D</code> with
104 * coordinates (0, 0, 0, 0, 0, 0).
105 * @since 1.2
106 */
107 public Float() {
108 }
109
110 /**
111 * Constructs and initializes a <code>QuadCurve2D</code> from the
112 * specified {@code float} coordinates.
113 *
114 * @param x1 the X coordinate of the start point
115 * @param y1 the Y coordinate of the start point
116 * @param ctrlx the X coordinate of the control point
117 * @param ctrly the Y coordinate of the control point
118 * @param x2 the X coordinate of the end point
119 * @param y2 the Y coordinate of the end point
120 * @since 1.2
121 */
122 public Float(float x1, float y1,
123 float ctrlx, float ctrly,
124 float x2, float y2)
125 {
126 setCurve(x1, y1, ctrlx, ctrly, x2, y2);
127 }
128
129 /**
130 * {@inheritDoc}
131 * @since 1.2
132 */
133 public double getX1() {
134 return (double) x1;
135 }
136
137 /**
138 * {@inheritDoc}
139 * @since 1.2
140 */
141 public double getY1() {
142 return (double) y1;
143 }
144
145 /**
146 * {@inheritDoc}
147 * @since 1.2
148 */
149 public Point2D getP1() {
150 return new Point2D.Float(x1, y1);
151 }
152
153 /**
154 * {@inheritDoc}
155 * @since 1.2
156 */
157 public double getCtrlX() {
158 return (double) ctrlx;
159 }
160
161 /**
162 * {@inheritDoc}
163 * @since 1.2
164 */
165 public double getCtrlY() {
166 return (double) ctrly;
167 }
168
169 /**
170 * {@inheritDoc}
171 * @since 1.2
172 */
173 public Point2D getCtrlPt() {
174 return new Point2D.Float(ctrlx, ctrly);
175 }
176
177 /**
178 * {@inheritDoc}
179 * @since 1.2
180 */
181 public double getX2() {
182 return (double) x2;
183 }
184
185 /**
186 * {@inheritDoc}
187 * @since 1.2
188 */
189 public double getY2() {
190 return (double) y2;
191 }
192
193 /**
194 * {@inheritDoc}
195 * @since 1.2
196 */
197 public Point2D getP2() {
198 return new Point2D.Float(x2, y2);
199 }
200
201 /**
202 * {@inheritDoc}
203 * @since 1.2
204 */
205 public void setCurve(double x1, double y1,
206 double ctrlx, double ctrly,
207 double x2, double y2)
208 {
209 this.x1 = (float) x1;
210 this.y1 = (float) y1;
211 this.ctrlx = (float) ctrlx;
212 this.ctrly = (float) ctrly;
213 this.x2 = (float) x2;
214 this.y2 = (float) y2;
215 }
216
217 /**
218 * Sets the location of the end points and control point of this curve
219 * to the specified {@code float} coordinates.
220 *
221 * @param x1 the X coordinate of the start point
222 * @param y1 the Y coordinate of the start point
223 * @param ctrlx the X coordinate of the control point
224 * @param ctrly the Y coordinate of the control point
225 * @param x2 the X coordinate of the end point
226 * @param y2 the Y coordinate of the end point
227 * @since 1.2
228 */
229 public void setCurve(float x1, float y1,
230 float ctrlx, float ctrly,
231 float x2, float y2)
232 {
233 this.x1 = x1;
234 this.y1 = y1;
235 this.ctrlx = ctrlx;
236 this.ctrly = ctrly;
237 this.x2 = x2;
238 this.y2 = y2;
239 }
240
241 /**
242 * {@inheritDoc}
243 * @since 1.2
244 */
245 public Rectangle2D getBounds2D() {
246 float left = Math.min(Math.min(x1, x2), ctrlx);
247 float top = Math.min(Math.min(y1, y2), ctrly);
248 float right = Math.max(Math.max(x1, x2), ctrlx);
249 float bottom = Math.max(Math.max(y1, y2), ctrly);
250 return new Rectangle2D.Float(left, top,
251 right - left, bottom - top);
252 }
253
254 /*
255 * JDK 1.6 serialVersionUID
256 */
257 private static final long serialVersionUID = -8511188402130719609L;
258 }
259
260 /**
261 * A quadratic parametric curve segment specified with
262 * {@code double} coordinates.
263 *
264 * @since 1.2
265 */
266 public static class Double extends QuadCurve2D implements Serializable {
267 /**
268 * The X coordinate of the start point of the quadratic curve
269 * segment.
270 * @since 1.2
271 * @serial
272 */
273 public double x1;
274
275 /**
276 * The Y coordinate of the start point of the quadratic curve
277 * segment.
278 * @since 1.2
279 * @serial
280 */
281 public double y1;
282
283 /**
284 * The X coordinate of the control point of the quadratic curve
285 * segment.
286 * @since 1.2
287 * @serial
288 */
289 public double ctrlx;
290
291 /**
292 * The Y coordinate of the control point of the quadratic curve
293 * segment.
294 * @since 1.2
295 * @serial
296 */
297 public double ctrly;
298
299 /**
300 * The X coordinate of the end point of the quadratic curve
301 * segment.
302 * @since 1.2
303 * @serial
304 */
305 public double x2;
306
307 /**
308 * The Y coordinate of the end point of the quadratic curve
309 * segment.
310 * @since 1.2
311 * @serial
312 */
313 public double y2;
314
315 /**
316 * Constructs and initializes a <code>QuadCurve2D</code> with
317 * coordinates (0, 0, 0, 0, 0, 0).
318 * @since 1.2
319 */
320 public Double() {
321 }
322
323 /**
324 * Constructs and initializes a <code>QuadCurve2D</code> from the
325 * specified {@code double} coordinates.
326 *
327 * @param x1 the X coordinate of the start point
328 * @param y1 the Y coordinate of the start point
329 * @param ctrlx the X coordinate of the control point
330 * @param ctrly the Y coordinate of the control point
331 * @param x2 the X coordinate of the end point
332 * @param y2 the Y coordinate of the end point
333 * @since 1.2
334 */
335 public Double(double x1, double y1,
336 double ctrlx, double ctrly,
337 double x2, double y2)
338 {
339 setCurve(x1, y1, ctrlx, ctrly, x2, y2);
340 }
341
342 /**
343 * {@inheritDoc}
344 * @since 1.2
345 */
346 public double getX1() {
347 return x1;
348 }
349
350 /**
351 * {@inheritDoc}
352 * @since 1.2
353 */
354 public double getY1() {
355 return y1;
356 }
357
358 /**
359 * {@inheritDoc}
360 * @since 1.2
361 */
362 public Point2D getP1() {
363 return new Point2D.Double(x1, y1);
364 }
365
366 /**
367 * {@inheritDoc}
368 * @since 1.2
369 */
370 public double getCtrlX() {
371 return ctrlx;
372 }
373
374 /**
375 * {@inheritDoc}
376 * @since 1.2
377 */
378 public double getCtrlY() {
379 return ctrly;
380 }
381
382 /**
383 * {@inheritDoc}
384 * @since 1.2
385 */
386 public Point2D getCtrlPt() {
387 return new Point2D.Double(ctrlx, ctrly);
388 }
389
390 /**
391 * {@inheritDoc}
392 * @since 1.2
393 */
394 public double getX2() {
395 return x2;
396 }
397
398 /**
399 * {@inheritDoc}
400 * @since 1.2
401 */
402 public double getY2() {
403 return y2;
404 }
405
406 /**
407 * {@inheritDoc}
408 * @since 1.2
409 */
410 public Point2D getP2() {
411 return new Point2D.Double(x2, y2);
412 }
413
414 /**
415 * {@inheritDoc}
416 * @since 1.2
417 */
418 public void setCurve(double x1, double y1,
419 double ctrlx, double ctrly,
420 double x2, double y2)
421 {
422 this.x1 = x1;
423 this.y1 = y1;
424 this.ctrlx = ctrlx;
425 this.ctrly = ctrly;
426 this.x2 = x2;
427 this.y2 = y2;
428 }
429
430 /**
431 * {@inheritDoc}
432 * @since 1.2
433 */
434 public Rectangle2D getBounds2D() {
435 double left = Math.min(Math.min(x1, x2), ctrlx);
436 double top = Math.min(Math.min(y1, y2), ctrly);
437 double right = Math.max(Math.max(x1, x2), ctrlx);
438 double bottom = Math.max(Math.max(y1, y2), ctrly);
439 return new Rectangle2D.Double(left, top,
440 right - left, bottom - top);
441 }
442
443 /*
444 * JDK 1.6 serialVersionUID
445 */
446 private static final long serialVersionUID = 4217149928428559721L;
447 }
448
449 /**
450 * This is an abstract class that cannot be instantiated directly.
451 * Type-specific implementation subclasses are available for
452 * instantiation and provide a number of formats for storing
453 * the information necessary to satisfy the various accessor
454 * methods below.
455 *
456 * @see java.awt.geom.QuadCurve2D.Float
457 * @see java.awt.geom.QuadCurve2D.Double
458 * @since 1.2
459 */
460 protected QuadCurve2D() {
461 }
462
463 /**
464 * Returns the X coordinate of the start point in
465 * <code>double</code> in precision.
466 * @return the X coordinate of the start point.
467 * @since 1.2
468 */
469 public abstract double getX1();
470
471 /**
472 * Returns the Y coordinate of the start point in
473 * <code>double</code> precision.
474 * @return the Y coordinate of the start point.
475 * @since 1.2
476 */
477 public abstract double getY1();
478
479 /**
480 * Returns the start point.
481 * @return a <code>Point2D</code> that is the start point of this
482 * <code>QuadCurve2D</code>.
483 * @since 1.2
484 */
485 public abstract Point2D getP1();
486
487 /**
488 * Returns the X coordinate of the control point in
489 * <code>double</code> precision.
490 * @return X coordinate the control point
491 * @since 1.2
492 */
493 public abstract double getCtrlX();
494
495 /**
496 * Returns the Y coordinate of the control point in
497 * <code>double</code> precision.
498 * @return the Y coordinate of the control point.
499 * @since 1.2
500 */
501 public abstract double getCtrlY();
502
503 /**
504 * Returns the control point.
505 * @return a <code>Point2D</code> that is the control point of this
506 * <code>Point2D</code>.
507 * @since 1.2
508 */
509 public abstract Point2D getCtrlPt();
510
511 /**
512 * Returns the X coordinate of the end point in
513 * <code>double</code> precision.
514 * @return the x coordiante of the end point.
515 * @since 1.2
516 */
517 public abstract double getX2();
518
519 /**
520 * Returns the Y coordinate of the end point in
521 * <code>double</code> precision.
522 * @return the Y coordinate of the end point.
523 * @since 1.2
524 */
525 public abstract double getY2();
526
527 /**
528 * Returns the end point.
529 * @return a <code>Point</code> object that is the end point
530 * of this <code>Point2D</code>.
531 * @since 1.2
532 */
533 public abstract Point2D getP2();
534
535 /**
536 * Sets the location of the end points and control point of this curve
537 * to the specified <code>double</code> coordinates.
538 *
539 * @param x1 the X coordinate of the start point
540 * @param y1 the Y coordinate of the start point
541 * @param ctrlx the X coordinate of the control point
542 * @param ctrly the Y coordinate of the control point
543 * @param x2 the X coordinate of the end point
544 * @param y2 the Y coordinate of the end point
545 * @since 1.2
546 */
547 public abstract void setCurve(double x1, double y1,
548 double ctrlx, double ctrly,
549 double x2, double y2);
550
551 /**
552 * Sets the location of the end points and control points of this
553 * <code>QuadCurve2D</code> to the <code>double</code> coordinates at
554 * the specified offset in the specified array.
555 * @param coords the array containing coordinate values
556 * @param offset the index into the array from which to start
557 * getting the coordinate values and assigning them to this
558 * <code>QuadCurve2D</code>
559 * @since 1.2
560 */
561 public void setCurve(double[] coords, int offset) {
562 setCurve(coords[offset + 0], coords[offset + 1],
563 coords[offset + 2], coords[offset + 3],
564 coords[offset + 4], coords[offset + 5]);
565 }
566
567 /**
568 * Sets the location of the end points and control point of this
569 * <code>QuadCurve2D</code> to the specified <code>Point2D</code>
570 * coordinates.
571 * @param p1 the start point
572 * @param cp the control point
573 * @param p2 the end point
574 * @since 1.2
575 */
576 public void setCurve(Point2D p1, Point2D cp, Point2D p2) {
577 setCurve(p1.getX(), p1.getY(),
578 cp.getX(), cp.getY(),
579 p2.getX(), p2.getY());
580 }
581
582 /**
583 * Sets the location of the end points and control points of this
584 * <code>QuadCurve2D</code> to the coordinates of the
585 * <code>Point2D</code> objects at the specified offset in
586 * the specified array.
587 * @param pts an array containing <code>Point2D</code> that define
588 * coordinate values
589 * @param offset the index into <code>pts</code> from which to start
590 * getting the coordinate values and assigning them to this
591 * <code>QuadCurve2D</code>
592 * @since 1.2
593 */
594 public void setCurve(Point2D[] pts, int offset) {
595 setCurve(pts[offset + 0].getX(), pts[offset + 0].getY(),
596 pts[offset + 1].getX(), pts[offset + 1].getY(),
597 pts[offset + 2].getX(), pts[offset + 2].getY());
598 }
599
600 /**
601 * Sets the location of the end points and control point of this
602 * <code>QuadCurve2D</code> to the same as those in the specified
603 * <code>QuadCurve2D</code>.
604 * @param c the specified <code>QuadCurve2D</code>
605 * @since 1.2
606 */
607 public void setCurve(QuadCurve2D c) {
608 setCurve(c.getX1(), c.getY1(),
609 c.getCtrlX(), c.getCtrlY(),
610 c.getX2(), c.getY2());
611 }
612
613 /**
614 * Returns the square of the flatness, or maximum distance of a
615 * control point from the line connecting the end points, of the
616 * quadratic curve specified by the indicated control points.
617 *
618 * @param x1 the X coordinate of the start point
619 * @param y1 the Y coordinate of the start point
620 * @param ctrlx the X coordinate of the control point
621 * @param ctrly the Y coordinate of the control point
622 * @param x2 the X coordinate of the end point
623 * @param y2 the Y coordinate of the end point
624 * @return the square of the flatness of the quadratic curve
625 * defined by the specified coordinates.
626 * @since 1.2
627 */
628 public static double getFlatnessSq(double x1, double y1,
629 double ctrlx, double ctrly,
630 double x2, double y2) {
631 return Line2D.ptSegDistSq(x1, y1, x2, y2, ctrlx, ctrly);
632 }
633
634 /**
635 * Returns the flatness, or maximum distance of a
636 * control point from the line connecting the end points, of the
637 * quadratic curve specified by the indicated control points.
638 *
639 * @param x1 the X coordinate of the start point
640 * @param y1 the Y coordinate of the start point
641 * @param ctrlx the X coordinate of the control point
642 * @param ctrly the Y coordinate of the control point
643 * @param x2 the X coordinate of the end point
644 * @param y2 the Y coordinate of the end point
645 * @return the flatness of the quadratic curve defined by the
646 * specified coordinates.
647 * @since 1.2
648 */
649 public static double getFlatness(double x1, double y1,
650 double ctrlx, double ctrly,
651 double x2, double y2) {
652 return Line2D.ptSegDist(x1, y1, x2, y2, ctrlx, ctrly);
653 }
654
655 /**
656 * Returns the square of the flatness, or maximum distance of a
657 * control point from the line connecting the end points, of the
658 * quadratic curve specified by the control points stored in the
659 * indicated array at the indicated index.
660 * @param coords an array containing coordinate values
661 * @param offset the index into <code>coords</code> from which to
662 * to start getting the values from the array
663 * @return the flatness of the quadratic curve that is defined by the
664 * values in the specified array at the specified index.
665 * @since 1.2
666 */
667 public static double getFlatnessSq(double coords[], int offset) {
668 return Line2D.ptSegDistSq(coords[offset + 0], coords[offset + 1],
669 coords[offset + 4], coords[offset + 5],
670 coords[offset + 2], coords[offset + 3]);
671 }
672
673 /**
674 * Returns the flatness, or maximum distance of a
675 * control point from the line connecting the end points, of the
676 * quadratic curve specified by the control points stored in the
677 * indicated array at the indicated index.
678 * @param coords an array containing coordinate values
679 * @param offset the index into <code>coords</code> from which to
680 * start getting the coordinate values
681 * @return the flatness of a quadratic curve defined by the
682 * specified array at the specified offset.
683 * @since 1.2
684 */
685 public static double getFlatness(double coords[], int offset) {
686 return Line2D.ptSegDist(coords[offset + 0], coords[offset + 1],
687 coords[offset + 4], coords[offset + 5],
688 coords[offset + 2], coords[offset + 3]);
689 }
690
691 /**
692 * Returns the square of the flatness, or maximum distance of a
693 * control point from the line connecting the end points, of this
694 * <code>QuadCurve2D</code>.
695 * @return the square of the flatness of this
696 * <code>QuadCurve2D</code>.
697 * @since 1.2
698 */
699 public double getFlatnessSq() {
700 return Line2D.ptSegDistSq(getX1(), getY1(),
701 getX2(), getY2(),
702 getCtrlX(), getCtrlY());
703 }
704
705 /**
706 * Returns the flatness, or maximum distance of a
707 * control point from the line connecting the end points, of this
708 * <code>QuadCurve2D</code>.
709 * @return the flatness of this <code>QuadCurve2D</code>.
710 * @since 1.2
711 */
712 public double getFlatness() {
713 return Line2D.ptSegDist(getX1(), getY1(),
714 getX2(), getY2(),
715 getCtrlX(), getCtrlY());
716 }
717
718 /**
719 * Subdivides this <code>QuadCurve2D</code> and stores the resulting
720 * two subdivided curves into the <code>left</code> and
721 * <code>right</code> curve parameters.
722 * Either or both of the <code>left</code> and <code>right</code>
723 * objects can be the same as this <code>QuadCurve2D</code> or
724 * <code>null</code>.
725 * @param left the <code>QuadCurve2D</code> object for storing the
726 * left or first half of the subdivided curve
727 * @param right the <code>QuadCurve2D</code> object for storing the
728 * right or second half of the subdivided curve
729 * @since 1.2
730 */
731 public void subdivide(QuadCurve2D left, QuadCurve2D right) {
732 subdivide(this, left, right);
733 }
734
735 /**
736 * Subdivides the quadratic curve specified by the <code>src</code>
737 * parameter and stores the resulting two subdivided curves into the
738 * <code>left</code> and <code>right</code> curve parameters.
739 * Either or both of the <code>left</code> and <code>right</code>
740 * objects can be the same as the <code>src</code> object or
741 * <code>null</code>.
742 * @param src the quadratic curve to be subdivided
743 * @param left the <code>QuadCurve2D</code> object for storing the
744 * left or first half of the subdivided curve
745 * @param right the <code>QuadCurve2D</code> object for storing the
746 * right or second half of the subdivided curve
747 * @since 1.2
748 */
749 public static void subdivide(QuadCurve2D src,
750 QuadCurve2D left,
751 QuadCurve2D right) {
752 double x1 = src.getX1();
753 double y1 = src.getY1();
754 double ctrlx = src.getCtrlX();
755 double ctrly = src.getCtrlY();
756 double x2 = src.getX2();
757 double y2 = src.getY2();
758 double ctrlx1 = (x1 + ctrlx) / 2.0;
759 double ctrly1 = (y1 + ctrly) / 2.0;
760 double ctrlx2 = (x2 + ctrlx) / 2.0;
761 double ctrly2 = (y2 + ctrly) / 2.0;
762 ctrlx = (ctrlx1 + ctrlx2) / 2.0;
763 ctrly = (ctrly1 + ctrly2) / 2.0;
764 if (left != null) {
765 left.setCurve(x1, y1, ctrlx1, ctrly1, ctrlx, ctrly);
766 }
767 if (right != null) {
768 right.setCurve(ctrlx, ctrly, ctrlx2, ctrly2, x2, y2);
769 }
770 }
771
772 /**
773 * Subdivides the quadratic curve specified by the coordinates
774 * stored in the <code>src</code> array at indices
775 * <code>srcoff</code> through <code>srcoff</code> + 5
776 * and stores the resulting two subdivided curves into the two
777 * result arrays at the corresponding indices.
778 * Either or both of the <code>left</code> and <code>right</code>
779 * arrays can be <code>null</code> or a reference to the same array
780 * and offset as the <code>src</code> array.
781 * Note that the last point in the first subdivided curve is the
782 * same as the first point in the second subdivided curve. Thus,
783 * it is possible to pass the same array for <code>left</code> and
784 * <code>right</code> and to use offsets such that
785 * <code>rightoff</code> equals <code>leftoff</code> + 4 in order
786 * to avoid allocating extra storage for this common point.
787 * @param src the array holding the coordinates for the source curve
788 * @param srcoff the offset into the array of the beginning of the
789 * the 6 source coordinates
790 * @param left the array for storing the coordinates for the first
791 * half of the subdivided curve
792 * @param leftoff the offset into the array of the beginning of the
793 * the 6 left coordinates
794 * @param right the array for storing the coordinates for the second
795 * half of the subdivided curve
796 * @param rightoff the offset into the array of the beginning of the
797 * the 6 right coordinates
798 * @since 1.2
799 */
800 public static void subdivide(double src[], int srcoff,
801 double left[], int leftoff,
802 double right[], int rightoff) {
803 double x1 = src[srcoff + 0];
804 double y1 = src[srcoff + 1];
805 double ctrlx = src[srcoff + 2];
806 double ctrly = src[srcoff + 3];
807 double x2 = src[srcoff + 4];
808 double y2 = src[srcoff + 5];
809 if (left != null) {
810 left[leftoff + 0] = x1;
811 left[leftoff + 1] = y1;
812 }
813 if (right != null) {
814 right[rightoff + 4] = x2;
815 right[rightoff + 5] = y2;
816 }
817 x1 = (x1 + ctrlx) / 2.0;
818 y1 = (y1 + ctrly) / 2.0;
819 x2 = (x2 + ctrlx) / 2.0;
820 y2 = (y2 + ctrly) / 2.0;
821 ctrlx = (x1 + x2) / 2.0;
822 ctrly = (y1 + y2) / 2.0;
823 if (left != null) {
824 left[leftoff + 2] = x1;
825 left[leftoff + 3] = y1;
826 left[leftoff + 4] = ctrlx;
827 left[leftoff + 5] = ctrly;
828 }
829 if (right != null) {
830 right[rightoff + 0] = ctrlx;
831 right[rightoff + 1] = ctrly;
832 right[rightoff + 2] = x2;
833 right[rightoff + 3] = y2;
834 }
835 }
836
837 /**
838 * Solves the quadratic whose coefficients are in the <code>eqn</code>
839 * array and places the non-complex roots back into the same array,
840 * returning the number of roots. The quadratic solved is represented
841 * by the equation:
842 * <pre>
843 * eqn = {C, B, A};
844 * ax^2 + bx + c = 0
845 * </pre>
846 * A return value of <code>-1</code> is used to distinguish a constant
847 * equation, which might be always 0 or never 0, from an equation that
848 * has no zeroes.
849 * @param eqn the array that contains the quadratic coefficients
850 * @return the number of roots, or <code>-1</code> if the equation is
851 * a constant
852 * @since 1.2
853 */
854 public static int solveQuadratic(double eqn[]) {
855 return solveQuadratic(eqn, eqn);
856 }
857
858 /**
859 * Solves the quadratic whose coefficients are in the <code>eqn</code>
860 * array and places the non-complex roots into the <code>res</code>
861 * array, returning the number of roots.
862 * The quadratic solved is represented by the equation:
863 * <pre>
864 * eqn = {C, B, A};
865 * ax^2 + bx + c = 0
866 * </pre>
867 * A return value of <code>-1</code> is used to distinguish a constant
868 * equation, which might be always 0 or never 0, from an equation that
869 * has no zeroes.
870 * @param eqn the specified array of coefficients to use to solve
871 * the quadratic equation
872 * @param res the array that contains the non-complex roots
873 * resulting from the solution of the quadratic equation
874 * @return the number of roots, or <code>-1</code> if the equation is
875 * a constant.
876 * @since 1.3
877 */
878 public static int solveQuadratic(double eqn[], double res[]) {
879 double a = eqn[2];
880 double b = eqn[1];
881 double c = eqn[0];
882 int roots = 0;
883 if (a == 0.0) {
884 // The quadratic parabola has degenerated to a line.
885 if (b == 0.0) {
886 // The line has degenerated to a constant.
887 return -1;
888 }
889 res[roots++] = -c / b;
890 } else {
891 // From Numerical Recipes, 5.6, Quadratic and Cubic Equations
892 double d = b * b - 4.0 * a * c;
893 if (d < 0.0) {
894 // If d < 0.0, then there are no roots
895 return 0;
896 }
897 d = Math.sqrt(d);
898 // For accuracy, calculate one root using:
899 // (-b +/- d) / 2a
900 // and the other using:
901 // 2c / (-b +/- d)
902 // Choose the sign of the +/- so that b+d gets larger in magnitude
903 if (b < 0.0) {
904 d = -d;
905 }
906 double q = (b + d) / -2.0;
907 // We already tested a for being 0 above
908 res[roots++] = q / a;
909 if (q != 0.0) {
910 res[roots++] = c / q;
911 }
912 }
913 return roots;
914 }
915
916 /**
917 * {@inheritDoc}
918 * @since 1.2
919 */
920 public boolean contains(double x, double y) {
921
922 double x1 = getX1();
923 double y1 = getY1();
924 double xc = getCtrlX();
925 double yc = getCtrlY();
926 double x2 = getX2();
927 double y2 = getY2();
928
929 /*
930 * We have a convex shape bounded by quad curve Pc(t)
931 * and ine Pl(t).
932 *
933 * P1 = (x1, y1) - start point of curve
934 * P2 = (x2, y2) - end point of curve
935 * Pc = (xc, yc) - control point
936 *
937 * Pq(t) = P1*(1 - t)^2 + 2*Pc*t*(1 - t) + P2*t^2 =
938 * = (P1 - 2*Pc + P2)*t^2 + 2*(Pc - P1)*t + P1
939 * Pl(t) = P1*(1 - t) + P2*t
940 * t = [0:1]
941 *
942 * P = (x, y) - point of interest
943 *
944 * Let's look at second derivative of quad curve equation:
945 *
946 * Pq''(t) = 2 * (P1 - 2 * Pc + P2) = Pq''
947 * It's constant vector.
948 *
949 * Let's draw a line through P to be parallel to this
950 * vector and find the intersection of the quad curve
951 * and the line.
952 *
953 * Pq(t) is point of intersection if system of equations
954 * below has the solution.
955 *
956 * L(s) = P + Pq''*s == Pq(t)
957 * Pq''*s + (P - Pq(t)) == 0
958 *
959 * | xq''*s + (x - xq(t)) == 0
960 * | yq''*s + (y - yq(t)) == 0
961 *
962 * This system has the solution if rank of its matrix equals to 1.
963 * That is, determinant of the matrix should be zero.
964 *
965 * (y - yq(t))*xq'' == (x - xq(t))*yq''
966 *
967 * Let's solve this equation with 't' variable.
968 * Also let kx = x1 - 2*xc + x2
969 * ky = y1 - 2*yc + y2
970 *
971 * t0q = (1/2)*((x - x1)*ky - (y - y1)*kx) /
972 * ((xc - x1)*ky - (yc - y1)*kx)
973 *
974 * Let's do the same for our line Pl(t):
975 *
976 * t0l = ((x - x1)*ky - (y - y1)*kx) /
977 * ((x2 - x1)*ky - (y2 - y1)*kx)
978 *
979 * It's easy to check that t0q == t0l. This fact means
980 * we can compute t0 only one time.
981 *
982 * In case t0 < 0 or t0 > 1, we have an intersections outside
983 * of shape bounds. So, P is definitely out of shape.
984 *
985 * In case t0 is inside [0:1], we should calculate Pq(t0)
986 * and Pl(t0). We have three points for now, and all of them
987 * lie on one line. So, we just need to detect, is our point
988 * of interest between points of intersections or not.
989 *
990 * If the denominator in the t0q and t0l equations is
991 * zero, then the points must be collinear and so the
992 * curve is degenerate and encloses no area. Thus the
993 * result is false.
994 */
995 double kx = x1 - 2 * xc + x2;
996 double ky = y1 - 2 * yc + y2;
997 double dx = x - x1;
998 double dy = y - y1;
999 double dxl = x2 - x1;
1000 double dyl = y2 - y1;
1001
1002 double t0 = (dx * ky - dy * kx) / (dxl * ky - dyl * kx);
1003 if (t0 < 0 || t0 > 1 || t0 != t0) {
1004 return false;
1005 }
1006
1007 double xb = kx * t0 * t0 + 2 * (xc - x1) * t0 + x1;
1008 double yb = ky * t0 * t0 + 2 * (yc - y1) * t0 + y1;
1009 double xl = dxl * t0 + x1;
1010 double yl = dyl * t0 + y1;
1011
1012 return (x >= xb && x < xl) ||
1013 (x >= xl && x < xb) ||
1014 (y >= yb && y < yl) ||
1015 (y >= yl && y < yb);
1016 }
1017
1018 /**
1019 * {@inheritDoc}
1020 * @since 1.2
1021 */
1022 public boolean contains(Point2D p) {
1023 return contains(p.getX(), p.getY());
1024 }
1025
1026 /**
1027 * Fill an array with the coefficients of the parametric equation
1028 * in t, ready for solving against val with solveQuadratic.
1029 * We currently have:
1030 * val = Py(t) = C1*(1-t)^2 + 2*CP*t*(1-t) + C2*t^2
1031 * = C1 - 2*C1*t + C1*t^2 + 2*CP*t - 2*CP*t^2 + C2*t^2
1032 * = C1 + (2*CP - 2*C1)*t + (C1 - 2*CP + C2)*t^2
1033 * 0 = (C1 - val) + (2*CP - 2*C1)*t + (C1 - 2*CP + C2)*t^2
1034 * 0 = C + Bt + At^2
1035 * C = C1 - val
1036 * B = 2*CP - 2*C1
1037 * A = C1 - 2*CP + C2
1038 */
1039 private static void fillEqn(double eqn[], double val,
1040 double c1, double cp, double c2) {
1041 eqn[0] = c1 - val;
1042 eqn[1] = cp + cp - c1 - c1;
1043 eqn[2] = c1 - cp - cp + c2;
1044 return;
1045 }
1046
1047 /**
1048 * Evaluate the t values in the first num slots of the vals[] array
1049 * and place the evaluated values back into the same array. Only
1050 * evaluate t values that are within the range <0, 1>, including
1051 * the 0 and 1 ends of the range iff the include0 or include1
1052 * booleans are true. If an "inflection" equation is handed in,
1053 * then any points which represent a point of inflection for that
1054 * quadratic equation are also ignored.
1055 */
1056 private static int evalQuadratic(double vals[], int num,
1057 boolean include0,
1058 boolean include1,
1059 double inflect[],
1060 double c1, double ctrl, double c2) {
1061 int j = 0;
1062 for (int i = 0; i < num; i++) {
1063 double t = vals[i];
1064 if ((include0 ? t >= 0 : t > 0) &&
1065 (include1 ? t <= 1 : t < 1) &&
1066 (inflect == null ||
1067 inflect[1] + 2*inflect[2]*t != 0))
1068 {
1069 double u = 1 - t;
1070 vals[j++] = c1*u*u + 2*ctrl*t*u + c2*t*t;
1071 }
1072 }
1073 return j;
1074 }
1075
1076 private static final int BELOW = -2;
1077 private static final int LOWEDGE = -1;
1078 private static final int INSIDE = 0;
1079 private static final int HIGHEDGE = 1;
1080 private static final int ABOVE = 2;
1081
1082 /**
1083 * Determine where coord lies with respect to the range from
1084 * low to high. It is assumed that low <= high. The return
1085 * value is one of the 5 values BELOW, LOWEDGE, INSIDE, HIGHEDGE,
1086 * or ABOVE.
1087 */
1088 private static int getTag(double coord, double low, double high) {
1089 if (coord <= low) {
1090 return (coord < low ? BELOW : LOWEDGE);
1091 }
1092 if (coord >= high) {
1093 return (coord > high ? ABOVE : HIGHEDGE);
1094 }
1095 return INSIDE;
1096 }
1097
1098 /**
1099 * Determine if the pttag represents a coordinate that is already
1100 * in its test range, or is on the border with either of the two
1101 * opttags representing another coordinate that is "towards the
1102 * inside" of that test range. In other words, are either of the
1103 * two "opt" points "drawing the pt inward"?
1104 */
1105 private static boolean inwards(int pttag, int opt1tag, int opt2tag) {
1106 switch (pttag) {
1107 case BELOW:
1108 case ABOVE:
1109 default:
1110 return false;
1111 case LOWEDGE:
1112 return (opt1tag >= INSIDE || opt2tag >= INSIDE);
1113 case INSIDE:
1114 return true;
1115 case HIGHEDGE:
1116 return (opt1tag <= INSIDE || opt2tag <= INSIDE);
1117 }
1118 }
1119
1120 /**
1121 * {@inheritDoc}
1122 * @since 1.2
1123 */
1124 public boolean intersects(double x, double y, double w, double h) {
1125 // Trivially reject non-existant rectangles
1126 if (w <= 0 || h <= 0) {
1127 return false;
1128 }
1129
1130 // Trivially accept if either endpoint is inside the rectangle
1131 // (not on its border since it may end there and not go inside)
1132 // Record where they lie with respect to the rectangle.
1133 // -1 => left, 0 => inside, 1 => right
1134 double x1 = getX1();
1135 double y1 = getY1();
1136 int x1tag = getTag(x1, x, x+w);
1137 int y1tag = getTag(y1, y, y+h);
1138 if (x1tag == INSIDE && y1tag == INSIDE) {
1139 return true;
1140 }
1141 double x2 = getX2();
1142 double y2 = getY2();
1143 int x2tag = getTag(x2, x, x+w);
1144 int y2tag = getTag(y2, y, y+h);
1145 if (x2tag == INSIDE && y2tag == INSIDE) {
1146 return true;
1147 }
1148 double ctrlx = getCtrlX();
1149 double ctrly = getCtrlY();
1150 int ctrlxtag = getTag(ctrlx, x, x+w);
1151 int ctrlytag = getTag(ctrly, y, y+h);
1152
1153 // Trivially reject if all points are entirely to one side of
1154 // the rectangle.
1155 if (x1tag < INSIDE && x2tag < INSIDE && ctrlxtag < INSIDE) {
1156 return false; // All points left
1157 }
1158 if (y1tag < INSIDE && y2tag < INSIDE && ctrlytag < INSIDE) {
1159 return false; // All points above
1160 }
1161 if (x1tag > INSIDE && x2tag > INSIDE && ctrlxtag > INSIDE) {
1162 return false; // All points right
1163 }
1164 if (y1tag > INSIDE && y2tag > INSIDE && ctrlytag > INSIDE) {
1165 return false; // All points below
1166 }
1167
1168 // Test for endpoints on the edge where either the segment
1169 // or the curve is headed "inwards" from them
1170 // Note: These tests are a superset of the fast endpoint tests
1171 // above and thus repeat those tests, but take more time
1172 // and cover more cases
1173 if (inwards(x1tag, x2tag, ctrlxtag) &&
1174 inwards(y1tag, y2tag, ctrlytag))
1175 {
1176 // First endpoint on border with either edge moving inside
1177 return true;
1178 }
1179 if (inwards(x2tag, x1tag, ctrlxtag) &&
1180 inwards(y2tag, y1tag, ctrlytag))
1181 {
1182 // Second endpoint on border with either edge moving inside
1183 return true;
1184 }
1185
1186 // Trivially accept if endpoints span directly across the rectangle
1187 boolean xoverlap = (x1tag * x2tag <= 0);
1188 boolean yoverlap = (y1tag * y2tag <= 0);
1189 if (x1tag == INSIDE && x2tag == INSIDE && yoverlap) {
1190 return true;
1191 }
1192 if (y1tag == INSIDE && y2tag == INSIDE && xoverlap) {
1193 return true;
1194 }
1195
1196 // We now know that both endpoints are outside the rectangle
1197 // but the 3 points are not all on one side of the rectangle.
1198 // Therefore the curve cannot be contained inside the rectangle,
1199 // but the rectangle might be contained inside the curve, or
1200 // the curve might intersect the boundary of the rectangle.
1201
1202 double[] eqn = new double[3];
1203 double[] res = new double[3];
1204 if (!yoverlap) {
1205 // Both Y coordinates for the closing segment are above or
1206 // below the rectangle which means that we can only intersect
1207 // if the curve crosses the top (or bottom) of the rectangle
1208 // in more than one place and if those crossing locations
1209 // span the horizontal range of the rectangle.
1210 fillEqn(eqn, (y1tag < INSIDE ? y : y+h), y1, ctrly, y2);
1211 return (solveQuadratic(eqn, res) == 2 &&
1212 evalQuadratic(res, 2, true, true, null,
1213 x1, ctrlx, x2) == 2 &&
1214 getTag(res[0], x, x+w) * getTag(res[1], x, x+w) <= 0);
1215 }
1216
1217 // Y ranges overlap. Now we examine the X ranges
1218 if (!xoverlap) {
1219 // Both X coordinates for the closing segment are left of
1220 // or right of the rectangle which means that we can only
1221 // intersect if the curve crosses the left (or right) edge
1222 // of the rectangle in more than one place and if those
1223 // crossing locations span the vertical range of the rectangle.
1224 fillEqn(eqn, (x1tag < INSIDE ? x : x+w), x1, ctrlx, x2);
1225 return (solveQuadratic(eqn, res) == 2 &&
1226 evalQuadratic(res, 2, true, true, null,
1227 y1, ctrly, y2) == 2 &&
1228 getTag(res[0], y, y+h) * getTag(res[1], y, y+h) <= 0);
1229 }
1230
1231 // The X and Y ranges of the endpoints overlap the X and Y
1232 // ranges of the rectangle, now find out how the endpoint
1233 // line segment intersects the Y range of the rectangle
1234 double dx = x2 - x1;
1235 double dy = y2 - y1;
1236 double k = y2 * x1 - x2 * y1;
1237 int c1tag, c2tag;
1238 if (y1tag == INSIDE) {
1239 c1tag = x1tag;
1240 } else {
1241 c1tag = getTag((k + dx * (y1tag < INSIDE ? y : y+h)) / dy, x, x+w);
1242 }
1243 if (y2tag == INSIDE) {
1244 c2tag = x2tag;
1245 } else {
1246 c2tag = getTag((k + dx * (y2tag < INSIDE ? y : y+h)) / dy, x, x+w);
1247 }
1248 // If the part of the line segment that intersects the Y range
1249 // of the rectangle crosses it horizontally - trivially accept
1250 if (c1tag * c2tag <= 0) {
1251 return true;
1252 }
1253
1254 // Now we know that both the X and Y ranges intersect and that
1255 // the endpoint line segment does not directly cross the rectangle.
1256 //
1257 // We can almost treat this case like one of the cases above
1258 // where both endpoints are to one side, except that we will
1259 // only get one intersection of the curve with the vertical
1260 // side of the rectangle. This is because the endpoint segment
1261 // accounts for the other intersection.
1262 //
1263 // (Remember there is overlap in both the X and Y ranges which
1264 // means that the segment must cross at least one vertical edge
1265 // of the rectangle - in particular, the "near vertical side" -
1266 // leaving only one intersection for the curve.)
1267 //
1268 // Now we calculate the y tags of the two intersections on the
1269 // "near vertical side" of the rectangle. We will have one with
1270 // the endpoint segment, and one with the curve. If those two
1271 // vertical intersections overlap the Y range of the rectangle,
1272 // we have an intersection. Otherwise, we don't.
1273
1274 // c1tag = vertical intersection class of the endpoint segment
1275 //
1276 // Choose the y tag of the endpoint that was not on the same
1277 // side of the rectangle as the subsegment calculated above.
1278 // Note that we can "steal" the existing Y tag of that endpoint
1279 // since it will be provably the same as the vertical intersection.
1280 c1tag = ((c1tag * x1tag <= 0) ? y1tag : y2tag);
1281
1282 // c2tag = vertical intersection class of the curve
1283 //
1284 // We have to calculate this one the straightforward way.
1285 // Note that the c2tag can still tell us which vertical edge
1286 // to test against.
1287 fillEqn(eqn, (c2tag < INSIDE ? x : x+w), x1, ctrlx, x2);
1288 int num = solveQuadratic(eqn, res);
1289
1290 // Note: We should be able to assert(num == 2); since the
1291 // X range "crosses" (not touches) the vertical boundary,
1292 // but we pass num to evalQuadratic for completeness.
1293 evalQuadratic(res, num, true, true, null, y1, ctrly, y2);
1294
1295 // Note: We can assert(num evals == 1); since one of the
1296 // 2 crossings will be out of the [0,1] range.
1297 c2tag = getTag(res[0], y, y+h);
1298
1299 // Finally, we have an intersection if the two crossings
1300 // overlap the Y range of the rectangle.
1301 return (c1tag * c2tag <= 0);
1302 }
1303
1304 /**
1305 * {@inheritDoc}
1306 * @since 1.2
1307 */
1308 public boolean intersects(Rectangle2D r) {
1309 return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight());
1310 }
1311
1312 /**
1313 * {@inheritDoc}
1314 * @since 1.2
1315 */
1316 public boolean contains(double x, double y, double w, double h) {
1317 if (w <= 0 || h <= 0) {
1318 return false;
1319 }
1320 // Assertion: Quadratic curves closed by connecting their
1321 // endpoints are always convex.
1322 return (contains(x, y) &&
1323 contains(x + w, y) &&
1324 contains(x + w, y + h) &&
1325 contains(x, y + h));
1326 }
1327
1328 /**
1329 * {@inheritDoc}
1330 * @since 1.2
1331 */
1332 public boolean contains(Rectangle2D r) {
1333 return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight());
1334 }
1335
1336 /**
1337 * {@inheritDoc}
1338 * @since 1.2
1339 */
1340 public Rectangle getBounds() {
1341 return getBounds2D().getBounds();
1342 }
1343
1344 /**
1345 * Returns an iteration object that defines the boundary of the
1346 * shape of this <code>QuadCurve2D</code>.
1347 * The iterator for this class is not multi-threaded safe,
1348 * which means that this <code>QuadCurve2D</code> class does not
1349 * guarantee that modifications to the geometry of this
1350 * <code>QuadCurve2D</code> object do not affect any iterations of
1351 * that geometry that are already in process.
1352 * @param at an optional {@link AffineTransform} to apply to the
1353 * shape boundary
1354 * @return a {@link PathIterator} object that defines the boundary
1355 * of the shape.
1356 * @since 1.2
1357 */
1358 public PathIterator getPathIterator(AffineTransform at) {
1359 return new QuadIterator(this, at);
1360 }
1361
1362 /**
1363 * Returns an iteration object that defines the boundary of the
1364 * flattened shape of this <code>QuadCurve2D</code>.
1365 * The iterator for this class is not multi-threaded safe,
1366 * which means that this <code>QuadCurve2D</code> class does not
1367 * guarantee that modifications to the geometry of this
1368 * <code>QuadCurve2D</code> object do not affect any iterations of
1369 * that geometry that are already in process.
1370 * @param at an optional <code>AffineTransform</code> to apply
1371 * to the boundary of the shape
1372 * @param flatness the maximum distance that the control points for a
1373 * subdivided curve can be with respect to a line connecting
1374 * the end points of this curve before this curve is
1375 * replaced by a straight line connecting the end points.
1376 * @return a <code>PathIterator</code> object that defines the
1377 * flattened boundary of the shape.
1378 * @since 1.2
1379 */
1380 public PathIterator getPathIterator(AffineTransform at, double flatness) {
1381 return new FlatteningPathIterator(getPathIterator(at), flatness);
1382 }
1383
1384 /**
1385 * Creates a new object of the same class and with the same contents
1386 * as this object.
1387 *
1388 * @return a clone of this instance.
1389 * @exception OutOfMemoryError if there is not enough memory.
1390 * @see java.lang.Cloneable
1391 * @since 1.2
1392 */
1393 public Object clone() {
1394 try {
1395 return super.clone();
1396 } catch (CloneNotSupportedException e) {
1397 // this shouldn't happen, since we are Cloneable
1398 throw new InternalError();
1399 }
1400 }
1401 }
Save This Page