KickJava   Java API By Example, From Geeks To Geeks.

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


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.util.Arrays JavaDoc;
21 import java.awt.geom.Point2D JavaDoc;
22 import java.awt.geom.Rectangle2D JavaDoc;
23
24 import java.io.PrintStream JavaDoc;
25 import java.io.FileOutputStream JavaDoc;
26
27 /**
28  * An abstract class for path segments.
29  *
30  * @version $Id: AbstractSegment.java,v 1.3 2005/04/02 14:26:09 deweese Exp $
31  */
32 public abstract class AbstractSegment implements Segment {
33
34     private static final double rt3 = 1.7320508075689;
35
36     protected abstract int findRoots(double y, double [] roots);
37
38     public Segment.SplitResults split(double y) {
39         double [] roots = { 0, 0, 0 };
40         int numSol = findRoots(y, roots);
41         if (numSol == 0) return null; // No split
42
43         Arrays.sort(roots, 0, numSol);
44         double [] segs = new double[numSol+2];
45         int numSegments=0;
46         segs[numSegments++] = 0;
47         for (int i=0; i<numSol; i++) {
48             double r = roots[i];
49             if (r <= 0.0) continue;
50             if (r >= 1.0) break;
51             if (segs[numSegments-1] != r)
52                 segs[numSegments++] = r;
53         }
54         segs[numSegments++] = 1.0;
55
56         if (numSegments == 2) return null;
57         // System.err.println("Y: " + y + "#Seg: " + numSegments +
58 // " Seg: " + this);
59
60         Segment [] parts = new Segment[numSegments];
61         double pT = 0.0;
62         int pIdx = 0;
63         boolean firstAbove=false, prevAbove=false;
64         for (int i=1; i<numSegments; i++) {
65             // System.err.println("Segs: " + segs[i-1]+", "+segs[i]);
66 parts[pIdx] = getSegment(segs[i-1], segs[i]);
67             Point2D.Double JavaDoc pt = parts[pIdx].eval(0.5);
68             // System.err.println("Pt: " + pt);
69 if (pIdx == 0) {
70                 pIdx++;
71                 firstAbove = prevAbove = (pt.y < y);
72                 continue;
73             }
74             boolean above = (pt.y < y);
75             if (prevAbove == above) {
76                 // Merge segments
77 parts[pIdx-1] = getSegment(pT, segs[i]);
78             } else {
79                 pIdx++;
80                 pT=segs[i-1];
81                 prevAbove = above;
82             }
83         }
84         if (pIdx == 1) return null;
85         Segment [] below, above;
86         if (firstAbove) {
87             above = new Segment[(pIdx+1)/2];
88             below = new Segment[pIdx/2];
89         } else {
90             above = new Segment[pIdx/2];
91             below = new Segment[(pIdx+1)/2];
92         }
93         int ai=0, bi=0;
94         for (int i=0; i<pIdx; i++) {
95             if (firstAbove) above[ai++] = parts[i];
96             else below[bi++] = parts[i];
97             firstAbove = !firstAbove;
98         }
99         return new SplitResults(below, above);
100     }
101
102     public Segment splitBefore(double t) {
103         return getSegment(0.0, t);
104     }
105
106     public Segment splitAfter(double t) {
107         return getSegment(t, 1.0);
108     }
109
110     // Doubles have 48bit precision
111 static final double eps = 1/(double)(1l<<48);
112     static final double tol = 4.0*eps;
113
114     public static int solveLine(double a, double b,
115                                  double [] roots) {
116         if (a == 0) {
117             if (b != 0)
118                 // No intersection.
119 return 0;
120             // All pts intersect just return 0.
121 roots[0] = 0;
122             return 1;
123         }
124
125         roots[0] = -b/a;
126         return 1;
127     }
128
129     public static int solveQuad(double a, double b, double c,
130                                  double [] roots) {
131         // System.err.println("Quad: " + a +"t^2 + " + b +"t + " + c);
132 if (a == 0) {
133             // no square term.
134 return solveLine(b, c, roots);
135         }
136
137         double det = b*b-4*a*c;
138         // System.err.println("Det: " + det);
139
140         if (Math.abs(det) <= tol*b*b) {
141             // one real root (det doesn't contain any useful info)
142 roots[0] = -b/(2*a);
143             return 1;
144         }
145
146         if (det < 0)
147             return 0; // No real roots
148
149         // Two real roots
150 det = Math.sqrt(det);
151         double w = -(b + matchSign(det, b));
152         roots[0] = (2*c)/w;
153         roots[1] = w/(2*a);
154         return 2;
155     }
156
157     public static double matchSign(double a, double b) {
158         if (b < 0) return (a < 0)?a:-a;
159         return (a > 0)?a:-a;
160     }
161
162     public static int solveCubic(double a3, double a2,
163                                   double a1, double a0,
164                                   double [] roots) {
165
166         // System.err.println("Cubic: " + a3 + "t^3 + " +
167 // a2 +"t^2 + " +
168 // a1 +"t + " + a0);
169
170         double [] dRoots = { 0, 0};
171         int dCnt = solveQuad(3*a3, 2*a2, a1, dRoots);
172         double [] yVals = {0, 0, 0, 0};
173         double [] tVals = {0, 0, 0, 0};
174         int yCnt=0;
175         yVals[yCnt] = a0;
176         tVals[yCnt++] = 0;
177         double r;
178         switch (dCnt) {
179         case 1:
180             r = dRoots[0];
181             if ((r > 0) && (r < 1)) {
182                 yVals[yCnt] = ((a3*r+a2)*r+a1)*r+a0;
183                 tVals[yCnt++] = r;
184             }
185             break;
186         case 2:
187             if (dRoots[0] > dRoots[1]) {
188                 double t = dRoots[0];
189                 dRoots[0] = dRoots[1];
190                 dRoots[1] = t;
191             }
192             r = dRoots[0];
193             if ((r > 0) && (r < 1)) {
194                 yVals[yCnt] = ((a3*r+a2)*r+a1)*r+a0;
195                 tVals[yCnt++] = r;
196             }
197             r = dRoots[1];
198             if ((r > 0) && (r < 1)) {
199                 yVals[yCnt] = ((a3*r+a2)*r+a1)*r+a0;
200                 tVals[yCnt++] = r;
201             }
202             break;
203         default: break;
204         }
205         yVals[yCnt] = a3+a2+a1+a0;
206         tVals[yCnt++] = 1.0;
207
208         int ret=0;
209         for (int i=0; i<yCnt-1; i++) {
210             double y0 = yVals[i], t0 = tVals[i];
211             double y1 = yVals[i+1], t1 = tVals[i+1];
212             if ((y0 < 0) && (y1 < 0)) continue;
213             if ((y0 > 0) && (y1 > 0)) continue;
214
215             if (y0 > y1) { // swap so y0 < 0 and y1 > 0
216 double t;
217                 t = y0; y0=y1; y1=t;
218                 t = t0; t0=t1; t1=t;
219             }
220
221             if (-y0 < tol*y1) { roots[ret++] = t0; continue; }
222             if (y1 < -tol*y0) { roots[ret++] = t1; i++; continue; }
223
224             double epsZero = tol*(y1-y0);
225             int cnt;
226             for (cnt=0; cnt<20; cnt++) {
227                 double dt = t1-t0;
228                 double dy = y1-y0;
229                 // double t = (t0+t1)/2;
230 // double t= t0+Math.abs(y0/dy)*dt;
231 // This tends to make sure that we come up
232 // a little short each time this generaly allows
233 // you to eliminate as much of the range as possible
234 // without overshooting (in which case you may eliminate
235 // almost nothing).
236 double t= t0+(Math.abs(y0/dy)*99+.5)*dt/100;
237                 double v = ((a3*t+a2)*t+a1)*t+a0;
238                 if (Math.abs(v) < epsZero) {
239                     roots[ret++] = t; break;
240                 }
241                 if (v < 0) { t0 = t; y0=v;}
242                 else { t1 = t; y1=v;}
243             }
244             if (cnt == 20)
245                 roots[ret++] = (t0+t1)/2;
246         }
247         return ret;
248     }
249
250     /*
251     public static void check(Segment seg, float y, PrintStream ps) {
252         ps.println("<path fill=\"none\" stroke=\"black\" " +
253                    " stroke-width=\"3\" d=\"" + seg + "\"/>");
254
255         ps.println("<line x1=\"-1000\" y1=\""+y+
256                    "\" x2=\"1000\" y2=\""+y+"\" fill=\"none\" stroke=\"orange\"/>\n");
257
258         SplitResults sr = seg.split(y);
259         if (sr == null) return;
260         Segment [] above = sr.getAbove();
261         Segment [] below = sr.getBelow();
262         for (int i=0; i<above.length; i++) {
263             ps.println("<path fill=\"none\" stroke=\"blue\" " +
264                        " stroke-width=\"2.5\" " +
265                        " d=\"" + above[i] + "\"/>");
266         }
267         for (int i=0; i<below.length; i++) {
268             ps.println("<path fill=\"none\" stroke=\"red\" " +
269                        " stroke-width=\"2\" " +
270                        "d=\"" + below[i] + "\"/>");
271         }
272     }
273     public static void main(String [] args) {
274         PrintStream ps;
275         double [] roots = { 0, 0, 0 };
276         int n = solveCubic (-0.10000991821289062, 9.600013732910156,
277                             -35.70000457763672, 58.0, roots);
278         for (int i=0; i<n; i++)
279             System.err.println("Root: " + roots[i]);
280         Cubic c;
281         c = new Cubic(new Point2D.Double(153.6999969482422,5.099999904632568),
282                       new Point2D.Double(156.6999969482422,4.099999904632568),
283                       new Point2D.Double(160.39999389648438,2.3999998569488525),
284                       new Point2D.Double(164.6999969482422,0.0));
285         c.split(0);
286
287         c = new Cubic(new Point2D.Double(24.899999618530273,23.10000228881836),
288                       new Point2D.Double(41.5,8.399999618530273),
289                       new Point2D.Double(64.69999694824219,1.0),
290                       new Point2D.Double(94.5999984741211,1.0));
291         c.split(0);
292
293         try {
294             ps = new PrintStream(new FileOutputStream(args[0]));
295         } catch(java.io.IOException ioe) {
296             ioe.printStackTrace();
297             return;
298         }
299
300         ps.println("<?xml version=\"1.0\" standalone=\"no\"?>\n" +
301                    "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.0//EN\"\n" +
302                    "\"http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd\">\n" +
303                    "<svg width=\"450\" height=\"500\"\n" +
304                    " viewBox=\"-100 -100 450 500\"\n" +
305                    " xmlns=\"http://www.w3.org/2000/svg\"\n" +
306                    " xmlns:xlink=\"http://www.w3.org/1999/xlink\">");
307
308         check(new Cubic(new Point2D.Double(0, 0),
309                         new Point2D.Double(100, 100),
310                         new Point2D.Double(-50, 100),
311                         new Point2D.Double(50, 0)), 40, ps);
312
313         check(new Cubic(new Point2D.Double(100, 0),
314                         new Point2D.Double(200, 100),
315                         new Point2D.Double(50, -50),
316                         new Point2D.Double(150, 30)), 20, ps);
317
318         check(new Cubic(new Point2D.Double(200, 0),
319                         new Point2D.Double(300, 100),
320                         new Point2D.Double(150, 100),
321                         new Point2D.Double(250, 0)), 75, ps);
322
323         check(new Quadradic(new Point2D.Double(0, 100),
324                             new Point2D.Double(50,150),
325                             new Point2D.Double(10,100)), 115, ps);
326
327         check(new Linear(new Point2D.Double(100, 100),
328                          new Point2D.Double(150,150)), 115, ps);
329         ps.println("</svg>");
330     }
331     */
332 }
333
Popular Tags