Java > Open Source Codes > org > apache > batik > ext > awt > geom > Cubic


1 /*
2
3    Copyright 2003 The Apache Software Foundation
4
5    Licensed under the Apache License, Version 2.0 (the "License");
6    you may not use this file except in compliance with the License.
7    You may obtain a copy of the License at
8
9        http://www.apache.org/licenses/LICENSE-2.0
10
11    Unless required by applicable law or agreed to in writing, software
12    distributed under the License is distributed on an "AS IS" BASIS,
13    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14    See the License for the specific language governing permissions and
15    limitations under the License.
16
17  */
18 package org.apache.batik.ext.awt.geom;
19
20 import java.awt.geom.CubicCurve2D ;
21 import java.awt.geom.Point2D ;
22 import java.awt.geom.QuadCurve2D ;
23 import java.awt.geom.Rectangle2D ;
24
25 /**
26  * A class representing a cubic path segment.
27  *
28  * @version $Id: Cubic.java,v 1.3 2005/03/27 08:58:32 cam Exp $
29  */
30 public class Cubic extends AbstractSegment {
31
32     public Point2D.Double p1, p2, p3, p4;
33     public Cubic() {
34         p1 = new Point2D.Double ();
35         p2 = new Point2D.Double ();
36         p3 = new Point2D.Double ();
37         p4 = new Point2D.Double ();
38     }
39     public Cubic(double x1, double y1, double x2, double y2,
40                  double x3, double y3, double x4, double y4) {
41         p1 = new Point2D.Double (x1, y1);
42         p2 = new Point2D.Double (x2, y2);
43         p3 = new Point2D.Double (x3, y3);
44         p4 = new Point2D.Double (x4, y4);
45     }
46
47     public Cubic(Point2D.Double p1, Point2D.Double p2,
48                  Point2D.Double p3, Point2D.Double p4) {
49         this.p1 = p1;
50         this.p2 = p2;
51         this.p3 = p3;
52         this.p4 = p4;
53     }
54
55     public Object clone() {
56         return new Cubic(new Point2D.Double (p1.x, p1.y),
57                          new Point2D.Double (p2.x, p2.y),
58                          new Point2D.Double (p3.x, p3.y),
59                          new Point2D.Double (p4.x, p4.y));
60     }
61
62     public Segment reverse() {
63         return new Cubic(new Point2D.Double (p4.x, p4.y),
64                          new Point2D.Double (p3.x, p3.y),
65                          new Point2D.Double (p2.x, p2.y),
66                          new Point2D.Double (p1.x, p1.y));
67     }
68
69     private void getMinMax(double p1, double p2,
70                            double p3, double p4,
71                            double [] minMax) {
72         double min, max;
73         if (p4 > p1){
74             minMax[0] = p1; minMax[1] = p4;
75         } else {
76             minMax[0] = p4; minMax[1] = p1;
77         }
78
79         double c0 = 3*(p2-p1);
80         double c1 = 6*(p3-p2);
81         double c2 = 3*(p4-p3);
82         double [] eqn = { c0, c1-2*c0, c2-c1+c0 };
83         int roots = QuadCurve2D.solveQuadratic(eqn);
84         for (int r=0; r<roots; r++) {
85             double tv = eqn[r];
86             if ((tv <= 0) || (tv >= 1)) continue;
87             tv = ((1-tv)*(1-tv)*(1-tv)*p1 +
88                     3*tv*(1-tv)*(1-tv)*p2 +
89                     3*tv*tv*(1-tv)*p3 +
90                     tv*tv*tv*p4);
91             if (tv < minMax[0]) minMax[0] = tv;
92             else if (tv > minMax[1]) minMax[1] = tv;
93         }
94     }
95     public double minX() {
96         double [] minMax = {0, 0};
97         getMinMax(p1.x, p2.x, p3.x, p4.x, minMax);
98         return minMax[0];
99     }
100     public double maxX() {
101         double [] minMax = {0, 0};
102         getMinMax(p1.x, p2.x, p3.x, p4.x, minMax);
103         return minMax[1];
104     }
105     public double minY() {
106         double [] minMax = {0, 0};
107         getMinMax(p1.y, p2.y, p3.y, p4.y, minMax);
108         return minMax[0];
109     }
110     public double maxY() {
111         double [] minMax = {0, 0};
112         getMinMax(p1.y, p2.y, p3.y, p4.y, minMax);
113         return minMax[1];
114     }
115
116     public Rectangle2D getBounds2D() {
117         double [] minMaxX = {0, 0};
118         getMinMax(p1.x, p2.x, p3.x, p4.x, minMaxX);
119         double [] minMaxY = {0, 0};
120         getMinMax(p1.y, p2.y, p3.y, p4.y, minMaxY);
121
122         return new Rectangle2D.Double
123             (minMaxX[0], minMaxY[0],
124              minMaxX[1]-minMaxX[0], minMaxY[1]-minMaxY[0]);
125     }
126
127     protected int findRoots(double y, double [] roots) {
128         double [] eqn = { p1.y-y, 3*(p2.y-p1.y), 3*(p1.y-2*p2.y+p3.y),
129                           3*p2.y-p1.y+p4.y-3*p3.y };
130         return CubicCurve2D.solveCubic(eqn, roots);
131         // return solveCubic(eqn[3], eqn[2], eqn[1], eqn[0], roots);
132 }
133
134     public Point2D.Double evalDt(double t) {
135         double x = 3*( (p2.x-p1.x)*(1-t)*(1-t) +
136                       2*(p3.x-p2.x)*(1-t)*t +
137                         (p4.x-p3.x)*t*t);
138         double y = 3*( (p2.y-p1.y)*(1-t)*(1-t) +
139                       2*(p3.y-p2.y)*(1-t)*t +
140                         (p4.y-p3.y)*t*t);
141         return new Point2D.Double (x, y);
142     }
143
144
145     public Point2D.Double eval(double t) {
146         double x = ((1-t)*(1-t)*(1-t)*p1.x +
147                     3*(t* (1-t)*(1-t)*p2.x +
148                        t* t* (1-t)*p3.x) +
149                     t*t*t *p4.x);
150         double y = ((1-t)*(1-t)*(1-t)*p1.y +
151                     3*(t* (1-t)*(1-t)*p2.y +
152                        t* t* (1-t)*p3.y) +
153                     t*t*t *p4.y);
154         return new Point2D.Double (x, y);
155     }
156
157     /**
158      * Subdivides this Cubic curve into two curves at t = 0.5.
159      * can be done with getSegment but this is more efficent.
160      * @param s0 if non-null contains portion of curve from 0->.5
161      * @param s1 if non-null contains portion of curve from .5->1
162      */
163     public void subdivide(Segment s0, Segment s1) {
164         Cubic c0=null, c1=null;
165         if (s0 instanceof Cubic) c0 = (Cubic)s0;
166         if (s1 instanceof Cubic) c1 = (Cubic)s1;
167         subdivide(c0, c1);
168     }
169
170     /**
171      * Subdivides this Cubic curve into two curves at given t.
172      * @param s0 if non-null contains portion of curve from 0->t.
173      * @param s1 if non-null contains portion of curve from t->1.
174      */
175     public void subdivide(double t, Segment s0, Segment s1) {
176         Cubic c0=null, c1=null;
177         if (s0 instanceof Cubic) c0 = (Cubic)s0;
178         if (s1 instanceof Cubic) c1 = (Cubic)s1;
179         subdivide(t, c0, c1);
180     }
181
182     /**
183      * Subdivides this Cubic curve into two curves at t = 0.5.
184      * can be done with getSegment but this is more efficent.
185      * @param c0 if non-null contains portion of curve from 0->.5
186      * @param c1 if non-null contains portion of curve from .5->1
187      */
188     public void subdivide(Cubic c0, Cubic c1) {
189         if ((c0 == null) && (c1 == null)) return;
190
191         double npX = (p1.x+3*(p2.x+p3.x)+p4.x)*0.125;
192         double npY = (p1.y+3*(p2.y+p3.y)+p4.y)*0.125;
193
194         double npdx = ((p2.x-p1.x)+2*(p3.x-p2.x)+(p4.x-p3.x))*.125;
195         double npdy = ((p2.y-p1.y)+2*(p3.y-p2.y)+(p4.y-p3.y))*.125;
196
197         if (c0 != null) {
198             c0.p1.x = p1.x;
199             c0.p1.y = p1.y;
200             c0.p2.x = (p2.x+p1.x)*.5;
201             c0.p2.y = (p2.y+p1.y)*.5;
202             
203             c0.p3.x = npX-npdx;
204             c0.p3.y = npY-npdy;
205             c0.p4.x = npX;
206             c0.p4.y = npY;
207         }
208
209         if (c1 != null) {
210             c1.p1.x = npX;
211             c1.p1.y = npY;
212             c1.p2.x = npX+npdx;
213             c1.p2.y = npY+npdy;
214             
215             c1.p3.x = (p4.x+p3.x)*.5;
216             c1.p3.y = (p4.y+p3.y)*.5;
217             c1.p4.x = p4.x;
218             c1.p4.y = p4.y;
219         }
220     }
221
222     /**
223      * Subdivides this Cubic curve into two curves at given t.
224      * @param c0 if non-null contains portion of curve from 0->t.
225      * @param c1 if non-null contains portion of curve from t->1.
226      */
227     public void subdivide(double t, Cubic c0, Cubic c1) {
228         if ((c0 == null) && (c1 == null)) return;
229
230         Point2D.Double np = eval(t);
231         Point2D.Double npd = evalDt(t);
232
233         if (c0 != null) {
234             c0.p1.x = p1.x;
235             c0.p1.y = p1.y;
236             c0.p2.x = (p2.x+p1.x)*t;
237             c0.p2.y = (p2.y+p1.y)*t;
238             
239             c0.p3.x = np.x-(npd.x*t/3);
240             c0.p3.y = np.y-(npd.y*t/3);
241             c0.p4.x = np.x;
242             c0.p4.y = np.y;
243         }
244
245         if (c1 != null) {
246             c1.p1.x = np.x;
247             c1.p1.y = np.y;
248             c1.p2.x = np.x+(npd.x*(1-t)/3);
249             c1.p2.y = np.y+(npd.y*(1-t)/3);
250             
251             c1.p3.x = (p4.x+p3.x)*(1-t);
252             c1.p3.y = (p4.y+p3.y)*(1-t);
253             c1.p4.x = p4.x;
254             c1.p4.y = p4.y;
255         }
256     }
257
258     public Segment getSegment(double t0, double t1) {
259         double dt = t1-t0;
260         Point2D.Double np1 = eval(t0);
261         Point2D.Double dp1 = evalDt(t0);
262         Point2D.Double np2 = new Point2D.Double (np1.x+dt*dp1.x/3,
263                                                 np1.y+dt*dp1.y/3);
264         
265         Point2D.Double np4 = eval(t1);
266         Point2D.Double dp4 = evalDt(t1);
267
268         Point2D.Double np3 = new Point2D.Double (np4.x-dt*dp4.x/3,
269                                                 np4.y-dt*dp4.y/3);
270         return new Cubic(np1, np2, np3, np4);
271     }
272
273     private static int count = 0;
274     private static int countExp = 0;
275
276     protected double subLength(double leftLegLen, double rightLegLen,
277                                double maxErr) {
278         count++;
279         double cldx, cldy, cdx, cdy;
280         cldx = p3.x-p2.x;
281         cldy = p3.y-p2.y;
282         double crossLegLen = Math.sqrt(cldx*cldx+cldy*cldy);
283
284         cdx = p4.x-p1.x;
285         cdy = p4.y-p1.y;
286         double cordLen = Math.sqrt(cdx*cdx+cdy*cdy);
287
288         double hullLen = leftLegLen+rightLegLen+crossLegLen;
289         if (hullLen < maxErr) return (hullLen+cordLen)/2;
290
291         double err = (hullLen-cordLen);
292         if (err < maxErr)
293             return (hullLen+cordLen)/2;
294
295         Cubic c = new Cubic();
296         double npX = (p1.x+3*(p2.x+p3.x)+p4.x)*0.125;
297         double npY = (p1.y+3*(p2.y+p3.y)+p4.y)*0.125;
298
299         double npdx = (cldx + cdx)*.125;
300         double npdy = (cldy + cdy)*.125;
301         
302         c.p1.x = p1.x;
303         c.p1.y = p1.y;
304         c.p2.x = (p2.x+p1.x)*.5;
305         c.p2.y = (p2.y+p1.y)*.5;
306         
307         c.p3.x = npX-npdx;
308         c.p3.y = npY-npdy;
309         c.p4.x = npX;
310         c.p4.y = npY;
311         
312         double midLen = Math.sqrt(npdx*npdx+npdy*npdy);
313         double len = c.subLength(leftLegLen/2, midLen, maxErr/2);
314
315         c.p1.x = npX;
316         c.p1.y = npY;
317         c.p2.x = npX+npdx;
318         c.p2.y = npY+npdy;
319             
320         c.p3.x = (p4.x+p3.x)*.5;
321         c.p3.y = (p4.y+p3.y)*.5;
322         c.p4.x = p4.x;
323         c.p4.y = p4.y;
324
325         len += c.subLength(midLen, rightLegLen/2, maxErr/2);
326         return len;
327     }
328
329     public double getLength() {
330         return getLength(0.000001);
331     }
332
333     public double getLength(double maxErr) {
334         double dx, dy;
335         dx = p2.x-p1.x;
336         dy = p2.y-p1.y;
337         double leftLegLen = Math.sqrt(dx*dx+dy*dy);
338         dx = p4.x-p3.x;
339         dy = p4.y-p3.y;
340         double rightLegLen = Math.sqrt(dx*dx+dy*dy);
341         dx = p3.x-p2.x;
342         dy = p3.y-p2.y;
343         double crossLegLen = Math.sqrt(dx*dx+dy*dy);
344         
345         double eps = maxErr*(leftLegLen+rightLegLen+crossLegLen);
346
347         return subLength(leftLegLen, rightLegLen, eps);
348     }
349
350     public String toString() {
351         return ("M" + p1.x + "," + p1.y +
352                 "C" + p2.x + "," + p2.y + " " +
353                 p3.x + "," + p3.y + " " +
354                 p4.x + "," + p4.y);
355     }
356     /*
357     public static boolean epsEq(double a, double b) {
358         final double eps = 0.000001;
359         return (((a + eps) > b) && ((a-eps) < b));
360     }
361
362     public static void sub(Cubic orig, Cubic curr,
363                            double t, double inc, int lev) {
364         Cubic left=new Cubic();
365         Cubic right=new Cubic();
366         curr.subdivide(left, right);
367         Point2D.Double ptl = left.eval(.5);
368         Point2D.Double ptr = right.eval(.5);
369         Point2D.Double pt1 = orig.eval(t-inc);
370         Point2D.Double pt2 = orig.eval(t+inc);
371         int steps = 100;
372         Point2D.Double l, r, o;
373         for (int i=0; i<=steps; i++) {
374             l = left.eval(i/(double)steps);
375             o = orig.eval(t-(2*inc)*(1-i/(double)steps));
376             if (!epsEq(l.x, o.x) || !epsEq(l.y, o.y))
377                 System.err.println("Lf Pt: [" + l.x + "," + l.y +
378                                    "] Orig: [" + o.x + "," + o.y +"]");
379             r = right.eval(i/(double)steps);
380             o = orig.eval(t+(2*inc*i/(double)steps));
381             if (!epsEq(r.x, o.x) || !epsEq(r.y, o.y))
382                 System.err.println("Rt Pt: [" + r.x + "," + r.y +
383                                    "] Orig: [" + o.x + "," + o.y +"]");
384         }
385         if (lev != 0) {
386             sub(orig, left, t-inc, inc/2, lev-1);
387             sub(orig, right, t+inc, inc/2, lev-1);
388         }
389     }
390
391     public static void evalCubic(Cubic c) {
392
393         int steps = 1000000;
394         Point2D.Double oldP = c.eval(0);
395         Point2D.Double newP;
396         double len = 0;
397         for (int i=1; i<=steps; i++) {
398             newP = c.eval(i/(double)steps);
399             double dx = newP.x-oldP.x;
400             double dy = newP.y-oldP.y;
401             len += Math.sqrt(dx*dx + dy*dy);
402             oldP = newP;
403         }
404         System.err.println("Length(.1): " + c.getLength(.001) +
405                            " x " + count); count = 0;
406         System.err.println("Length : " + c.getLength() +
407                            " x " + count); count = 0;
408         System.err.println("D Len : " + len);
409     }
410
411     public static void main(String args[]) {
412         Cubic c;
413
414         c = new Cubic(0,0, 10,10, 20,-10, 30,0);
415         sub(c, c, .5, .25, 3);
416         evalCubic(c);
417
418         c = new Cubic(0,0, 1,0, 2,-1, 3,0);
419         sub(c, c, .5, .25, 3);
420         evalCubic(c);
421     }
422     */
423 }
424

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags