001: /*
002: * Copyright 1998-2006 Sun Microsystems, Inc. All Rights Reserved.
003: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004: *
005: * This code is free software; you can redistribute it and/or modify it
006: * under the terms of the GNU General Public License version 2 only, as
007: * published by the Free Software Foundation. Sun designates this
008: * particular file as subject to the "Classpath" exception as provided
009: * by Sun in the LICENSE file that accompanied this code.
010: *
011: * This code is distributed in the hope that it will be useful, but WITHOUT
012: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014: * version 2 for more details (a copy is included in the LICENSE file that
015: * accompanied this code).
016: *
017: * You should have received a copy of the GNU General Public License version
018: * 2 along with this work; if not, write to the Free Software Foundation,
019: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020: *
021: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022: * CA 95054 USA or visit www.sun.com if you need additional information or
023: * have any questions.
024: */
025:
026: package sun.awt.geom;
027:
028: import java.awt.geom.Rectangle2D;
029: import java.awt.geom.PathIterator;
030: import java.awt.geom.QuadCurve2D;
031: import java.util.Vector;
032:
033: final class Order2 extends Curve {
034: private double x0;
035: private double y0;
036: private double cx0;
037: private double cy0;
038: private double x1;
039: private double y1;
040: private double xmin;
041: private double xmax;
042:
043: private double xcoeff0;
044: private double xcoeff1;
045: private double xcoeff2;
046: private double ycoeff0;
047: private double ycoeff1;
048: private double ycoeff2;
049:
050: public static void insert(Vector curves, double tmp[], double x0,
051: double y0, double cx0, double cy0, double x1, double y1,
052: int direction) {
053: int numparams = getHorizontalParams(y0, cy0, y1, tmp);
054: if (numparams == 0) {
055: // We are using addInstance here to avoid inserting horisontal
056: // segments
057: addInstance(curves, x0, y0, cx0, cy0, x1, y1, direction);
058: return;
059: }
060: // assert(numparams == 1);
061: double t = tmp[0];
062: tmp[0] = x0;
063: tmp[1] = y0;
064: tmp[2] = cx0;
065: tmp[3] = cy0;
066: tmp[4] = x1;
067: tmp[5] = y1;
068: split(tmp, 0, t);
069: int i0 = (direction == INCREASING) ? 0 : 4;
070: int i1 = 4 - i0;
071: addInstance(curves, tmp[i0], tmp[i0 + 1], tmp[i0 + 2],
072: tmp[i0 + 3], tmp[i0 + 4], tmp[i0 + 5], direction);
073: addInstance(curves, tmp[i1], tmp[i1 + 1], tmp[i1 + 2],
074: tmp[i1 + 3], tmp[i1 + 4], tmp[i1 + 5], direction);
075: }
076:
077: public static void addInstance(Vector curves, double x0, double y0,
078: double cx0, double cy0, double x1, double y1, int direction) {
079: if (y0 > y1) {
080: curves
081: .add(new Order2(x1, y1, cx0, cy0, x0, y0,
082: -direction));
083: } else if (y1 > y0) {
084: curves.add(new Order2(x0, y0, cx0, cy0, x1, y1, direction));
085: }
086: }
087:
088: /*
089: * Return the count of the number of horizontal sections of the
090: * specified quadratic Bezier curve. Put the parameters for the
091: * horizontal sections into the specified <code>ret</code> array.
092: * <p>
093: * If we examine the parametric equation in t, we have:
094: * Py(t) = C0*(1-t)^2 + 2*CP*t*(1-t) + C1*t^2
095: * = C0 - 2*C0*t + C0*t^2 + 2*CP*t - 2*CP*t^2 + C1*t^2
096: * = C0 + (2*CP - 2*C0)*t + (C0 - 2*CP + C1)*t^2
097: * Py(t) = (C0 - 2*CP + C1)*t^2 + (2*CP - 2*C0)*t + (C0)
098: * If we take the derivative, we get:
099: * Py(t) = At^2 + Bt + C
100: * dPy(t) = 2At + B = 0
101: * 2*(C0 - 2*CP + C1)t + 2*(CP - C0) = 0
102: * 2*(C0 - 2*CP + C1)t = 2*(C0 - CP)
103: * t = 2*(C0 - CP) / 2*(C0 - 2*CP + C1)
104: * t = (C0 - CP) / (C0 - CP + C1 - CP)
105: * Note that this method will return 0 if the equation is a line,
106: * which is either always horizontal or never horizontal.
107: * Completely horizontal curves need to be eliminated by other
108: * means outside of this method.
109: */
110: public static int getHorizontalParams(double c0, double cp,
111: double c1, double ret[]) {
112: if (c0 <= cp && cp <= c1) {
113: return 0;
114: }
115: c0 -= cp;
116: c1 -= cp;
117: double denom = c0 + c1;
118: // If denom == 0 then cp == (c0+c1)/2 and we have a line.
119: if (denom == 0) {
120: return 0;
121: }
122: double t = c0 / denom;
123: // No splits at t==0 and t==1
124: if (t <= 0 || t >= 1) {
125: return 0;
126: }
127: ret[0] = t;
128: return 1;
129: }
130:
131: /*
132: * Split the quadratic Bezier stored at coords[pos...pos+5] representing
133: * the paramtric range [0..1] into two subcurves representing the
134: * parametric subranges [0..t] and [t..1]. Store the results back
135: * into the array at coords[pos...pos+5] and coords[pos+4...pos+9].
136: */
137: public static void split(double coords[], int pos, double t) {
138: double x0, y0, cx, cy, x1, y1;
139: coords[pos + 8] = x1 = coords[pos + 4];
140: coords[pos + 9] = y1 = coords[pos + 5];
141: cx = coords[pos + 2];
142: cy = coords[pos + 3];
143: x1 = cx + (x1 - cx) * t;
144: y1 = cy + (y1 - cy) * t;
145: x0 = coords[pos + 0];
146: y0 = coords[pos + 1];
147: x0 = x0 + (cx - x0) * t;
148: y0 = y0 + (cy - y0) * t;
149: cx = x0 + (x1 - x0) * t;
150: cy = y0 + (y1 - y0) * t;
151: coords[pos + 2] = x0;
152: coords[pos + 3] = y0;
153: coords[pos + 4] = cx;
154: coords[pos + 5] = cy;
155: coords[pos + 6] = x1;
156: coords[pos + 7] = y1;
157: }
158:
159: public Order2(double x0, double y0, double cx0, double cy0,
160: double x1, double y1, int direction) {
161: super (direction);
162: // REMIND: Better accuracy in the root finding methods would
163: // ensure that cy0 is in range. As it stands, it is never
164: // more than "1 mantissa bit" out of range...
165: if (cy0 < y0) {
166: cy0 = y0;
167: } else if (cy0 > y1) {
168: cy0 = y1;
169: }
170: this .x0 = x0;
171: this .y0 = y0;
172: this .cx0 = cx0;
173: this .cy0 = cy0;
174: this .x1 = x1;
175: this .y1 = y1;
176: xmin = Math.min(Math.min(x0, x1), cx0);
177: xmax = Math.max(Math.max(x0, x1), cx0);
178: xcoeff0 = x0;
179: xcoeff1 = cx0 + cx0 - x0 - x0;
180: xcoeff2 = x0 - cx0 - cx0 + x1;
181: ycoeff0 = y0;
182: ycoeff1 = cy0 + cy0 - y0 - y0;
183: ycoeff2 = y0 - cy0 - cy0 + y1;
184: }
185:
186: public int getOrder() {
187: return 2;
188: }
189:
190: public double getXTop() {
191: return x0;
192: }
193:
194: public double getYTop() {
195: return y0;
196: }
197:
198: public double getXBot() {
199: return x1;
200: }
201:
202: public double getYBot() {
203: return y1;
204: }
205:
206: public double getXMin() {
207: return xmin;
208: }
209:
210: public double getXMax() {
211: return xmax;
212: }
213:
214: public double getX0() {
215: return (direction == INCREASING) ? x0 : x1;
216: }
217:
218: public double getY0() {
219: return (direction == INCREASING) ? y0 : y1;
220: }
221:
222: public double getCX0() {
223: return cx0;
224: }
225:
226: public double getCY0() {
227: return cy0;
228: }
229:
230: public double getX1() {
231: return (direction == DECREASING) ? x0 : x1;
232: }
233:
234: public double getY1() {
235: return (direction == DECREASING) ? y0 : y1;
236: }
237:
238: public double XforY(double y) {
239: if (y <= y0) {
240: return x0;
241: }
242: if (y >= y1) {
243: return x1;
244: }
245: return XforT(TforY(y));
246: }
247:
248: public double TforY(double y) {
249: if (y <= y0) {
250: return 0;
251: }
252: if (y >= y1) {
253: return 1;
254: }
255: return TforY(y, ycoeff0, ycoeff1, ycoeff2);
256: }
257:
258: public static double TforY(double y, double ycoeff0,
259: double ycoeff1, double ycoeff2) {
260: // The caller should have already eliminated y values
261: // outside of the y0 to y1 range.
262: ycoeff0 -= y;
263: if (ycoeff2 == 0.0) {
264: // The quadratic parabola has degenerated to a line.
265: // ycoeff1 should not be 0.0 since we have already eliminated
266: // totally horizontal lines, but if it is, then we will generate
267: // infinity here for the root, which will not be in the [0,1]
268: // range so we will pass to the failure code below.
269: double root = -ycoeff0 / ycoeff1;
270: if (root >= 0 && root <= 1) {
271: return root;
272: }
273: } else {
274: // From Numerical Recipes, 5.6, Quadratic and Cubic Equations
275: double d = ycoeff1 * ycoeff1 - 4.0 * ycoeff2 * ycoeff0;
276: // If d < 0.0, then there are no roots
277: if (d >= 0.0) {
278: d = Math.sqrt(d);
279: // For accuracy, calculate one root using:
280: // (-ycoeff1 +/- d) / 2ycoeff2
281: // and the other using:
282: // 2ycoeff0 / (-ycoeff1 +/- d)
283: // Choose the sign of the +/- so that ycoeff1+d
284: // gets larger in magnitude
285: if (ycoeff1 < 0.0) {
286: d = -d;
287: }
288: double q = (ycoeff1 + d) / -2.0;
289: // We already tested ycoeff2 for being 0 above
290: double root = q / ycoeff2;
291: if (root >= 0 && root <= 1) {
292: return root;
293: }
294: if (q != 0.0) {
295: root = ycoeff0 / q;
296: if (root >= 0 && root <= 1) {
297: return root;
298: }
299: }
300: }
301: }
302: /* We failed to find a root in [0,1]. What could have gone wrong?
303: * First, remember that these curves are constructed to be monotonic
304: * in Y and totally horizontal curves have already been eliminated.
305: * Now keep in mind that the Y coefficients of the polynomial form
306: * of the curve are calculated from the Y coordinates which define
307: * our curve. They should theoretically define the same curve,
308: * but they can be off by a couple of bits of precision after the
309: * math is done and so can represent a slightly modified curve.
310: * This is normally not an issue except when we have solutions near
311: * the endpoints. Since the answers we get from solving the polynomial
312: * may be off by a few bits that means that they could lie just a
313: * few bits of precision outside the [0,1] range.
314: *
315: * Another problem could be that while the parametric curve defined
316: * by the Y coordinates has a local minima or maxima at or just
317: * outside of the endpoints, the polynomial form might express
318: * that same min/max just inside of and just shy of the Y coordinate
319: * of that endpoint. In that case, if we solve for a Y coordinate
320: * at or near that endpoint, we may be solving for a Y coordinate
321: * that is below that minima or above that maxima and we would find
322: * no solutions at all.
323: *
324: * In either case, we can assume that y is so near one of the
325: * endpoints that we can just collapse it onto the nearest endpoint
326: * without losing more than a couple of bits of precision.
327: */
328: // First calculate the midpoint between y0 and y1 and choose to
329: // return either 0.0 or 1.0 depending on whether y is above
330: // or below the midpoint...
331: // Note that we subtracted y from ycoeff0 above so both y0 and y1
332: // will be "relative to y" so we are really just looking at where
333: // zero falls with respect to the "relative midpoint" here.
334: double y0 = ycoeff0;
335: double y1 = ycoeff0 + ycoeff1 + ycoeff2;
336: return (0 < (y0 + y1) / 2) ? 0.0 : 1.0;
337: }
338:
339: public double XforT(double t) {
340: return (xcoeff2 * t + xcoeff1) * t + xcoeff0;
341: }
342:
343: public double YforT(double t) {
344: return (ycoeff2 * t + ycoeff1) * t + ycoeff0;
345: }
346:
347: public double dXforT(double t, int deriv) {
348: switch (deriv) {
349: case 0:
350: return (xcoeff2 * t + xcoeff1) * t + xcoeff0;
351: case 1:
352: return 2 * xcoeff2 * t + xcoeff1;
353: case 2:
354: return 2 * xcoeff2;
355: default:
356: return 0;
357: }
358: }
359:
360: public double dYforT(double t, int deriv) {
361: switch (deriv) {
362: case 0:
363: return (ycoeff2 * t + ycoeff1) * t + ycoeff0;
364: case 1:
365: return 2 * ycoeff2 * t + ycoeff1;
366: case 2:
367: return 2 * ycoeff2;
368: default:
369: return 0;
370: }
371: }
372:
373: public double nextVertical(double t0, double t1) {
374: double t = -xcoeff1 / (2 * xcoeff2);
375: if (t > t0 && t < t1) {
376: return t;
377: }
378: return t1;
379: }
380:
381: public void enlarge(Rectangle2D r) {
382: r.add(x0, y0);
383: double t = -xcoeff1 / (2 * xcoeff2);
384: if (t > 0 && t < 1) {
385: r.add(XforT(t), YforT(t));
386: }
387: r.add(x1, y1);
388: }
389:
390: public Curve getSubCurve(double ystart, double yend, int dir) {
391: double t0, t1;
392: if (ystart <= y0) {
393: if (yend >= y1) {
394: return getWithDirection(dir);
395: }
396: t0 = 0;
397: } else {
398: t0 = TforY(ystart, ycoeff0, ycoeff1, ycoeff2);
399: }
400: if (yend >= y1) {
401: t1 = 1;
402: } else {
403: t1 = TforY(yend, ycoeff0, ycoeff1, ycoeff2);
404: }
405: double eqn[] = new double[10];
406: eqn[0] = x0;
407: eqn[1] = y0;
408: eqn[2] = cx0;
409: eqn[3] = cy0;
410: eqn[4] = x1;
411: eqn[5] = y1;
412: if (t1 < 1) {
413: split(eqn, 0, t1);
414: }
415: int i;
416: if (t0 <= 0) {
417: i = 0;
418: } else {
419: split(eqn, 0, t0 / t1);
420: i = 4;
421: }
422: return new Order2(eqn[i + 0], ystart, eqn[i + 2], eqn[i + 3],
423: eqn[i + 4], yend, dir);
424: }
425:
426: public Curve getReversedCurve() {
427: return new Order2(x0, y0, cx0, cy0, x1, y1, -direction);
428: }
429:
430: public int getSegment(double coords[]) {
431: coords[0] = cx0;
432: coords[1] = cy0;
433: if (direction == INCREASING) {
434: coords[2] = x1;
435: coords[3] = y1;
436: } else {
437: coords[2] = x0;
438: coords[3] = y0;
439: }
440: return PathIterator.SEG_QUADTO;
441: }
442:
443: public String controlPointString() {
444: return ("(" + round(cx0) + ", " + round(cy0) + "), ");
445: }
446: }
|