| GNU Classpath (0.95) | |
| Frames | No Frames |
1: /* CubicCurve2D.java -- represents a parameterized cubic curve in 2-D space 2: Copyright (C) 2002, 2003, 2004 Free Software Foundation 3: 4: This file is part of GNU Classpath. 5: 6: GNU Classpath is free software; you can redistribute it and/or modify 7: it under the terms of the GNU General Public License as published by 8: the Free Software Foundation; either version 2, or (at your option) 9: any later version. 10: 11: GNU Classpath is distributed in the hope that it will be useful, but 12: WITHOUT ANY WARRANTY; without even the implied warranty of 13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14: General Public License for more details. 15: 16: You should have received a copy of the GNU General Public License 17: along with GNU Classpath; see the file COPYING. If not, write to the 18: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 19: 02110-1301 USA. 20: 21: Linking this library statically or dynamically with other modules is 22: making a combined work based on this library. Thus, the terms and 23: conditions of the GNU General Public License cover the whole 24: combination. 25: 26: As a special exception, the copyright holders of this library give you 27: permission to link this library with independent modules to produce an 28: executable, regardless of the license terms of these independent 29: modules, and to copy and distribute the resulting executable under 30: terms of your choice, provided that you also meet, for each linked 31: independent module, the terms and conditions of the license of that 32: module. An independent module is a module which is not derived from 33: or based on this library. If you modify this library, you may extend 34: this exception to your version of the library, but you are not 35: obligated to do so. If you do not wish to do so, delete this 36: exception statement from your version. */ 37: 38: package java.awt.geom; 39: 40: import java.awt.Rectangle; 41: import java.awt.Shape; 42: import java.util.NoSuchElementException; 43: 44: 45: /** 46: * A two-dimensional curve that is parameterized with a cubic 47: * function. 48: * 49: * <p><img src="doc-files/CubicCurve2D-1.png" width="350" height="180" 50: * alt="A drawing of a CubicCurve2D" /> 51: * 52: * @author Eric Blake (ebb9@email.byu.edu) 53: * @author Graydon Hoare (graydon@redhat.com) 54: * @author Sascha Brawer (brawer@dandelis.ch) 55: * @author Sven de Marothy (sven@physto.se) 56: * 57: * @since 1.2 58: */ 59: public abstract class CubicCurve2D implements Shape, Cloneable 60: { 61: private static final double BIG_VALUE = java.lang.Double.MAX_VALUE / 10.0; 62: private static final double EPSILON = 1E-10; 63: 64: /** 65: * Constructs a new CubicCurve2D. Typical users will want to 66: * construct instances of a subclass, such as {@link 67: * CubicCurve2D.Float} or {@link CubicCurve2D.Double}. 68: */ 69: protected CubicCurve2D() 70: { 71: } 72: 73: /** 74: * Returns the <i>x</i> coordinate of the curve’s start 75: * point. 76: */ 77: public abstract double getX1(); 78: 79: /** 80: * Returns the <i>y</i> coordinate of the curve’s start 81: * point. 82: */ 83: public abstract double getY1(); 84: 85: /** 86: * Returns the curve’s start point. 87: */ 88: public abstract Point2D getP1(); 89: 90: /** 91: * Returns the <i>x</i> coordinate of the curve’s first 92: * control point. 93: */ 94: public abstract double getCtrlX1(); 95: 96: /** 97: * Returns the <i>y</i> coordinate of the curve’s first 98: * control point. 99: */ 100: public abstract double getCtrlY1(); 101: 102: /** 103: * Returns the curve’s first control point. 104: */ 105: public abstract Point2D getCtrlP1(); 106: 107: /** 108: * Returns the <i>x</i> coordinate of the curve’s second 109: * control point. 110: */ 111: public abstract double getCtrlX2(); 112: 113: /** 114: * Returns the <i>y</i> coordinate of the curve’s second 115: * control point. 116: */ 117: public abstract double getCtrlY2(); 118: 119: /** 120: * Returns the curve’s second control point. 121: */ 122: public abstract Point2D getCtrlP2(); 123: 124: /** 125: * Returns the <i>x</i> coordinate of the curve’s end 126: * point. 127: */ 128: public abstract double getX2(); 129: 130: /** 131: * Returns the <i>y</i> coordinate of the curve’s end 132: * point. 133: */ 134: public abstract double getY2(); 135: 136: /** 137: * Returns the curve’s end point. 138: */ 139: public abstract Point2D getP2(); 140: 141: /** 142: * Changes the curve geometry, separately specifying each coordinate 143: * value. 144: * 145: * <p><img src="doc-files/CubicCurve2D-1.png" width="350" height="180" 146: * alt="A drawing of a CubicCurve2D" /> 147: * 148: * @param x1 the <i>x</i> coordinate of the curve’s new start 149: * point. 150: * 151: * @param y1 the <i>y</i> coordinate of the curve’s new start 152: * point. 153: * 154: * @param cx1 the <i>x</i> coordinate of the curve’s new 155: * first control point. 156: * 157: * @param cy1 the <i>y</i> coordinate of the curve’s new 158: * first control point. 159: * 160: * @param cx2 the <i>x</i> coordinate of the curve’s new 161: * second control point. 162: * 163: * @param cy2 the <i>y</i> coordinate of the curve’s new 164: * second control point. 165: * 166: * @param x2 the <i>x</i> coordinate of the curve’s new end 167: * point. 168: * 169: * @param y2 the <i>y</i> coordinate of the curve’s new end 170: * point. 171: */ 172: public abstract void setCurve(double x1, double y1, double cx1, double cy1, 173: double cx2, double cy2, double x2, double y2); 174: 175: /** 176: * Changes the curve geometry, specifying coordinate values in an 177: * array. 178: * 179: * @param coords an array containing the new coordinate values. The 180: * <i>x</i> coordinate of the new start point is located at 181: * <code>coords[offset]</code>, its <i>y</i> coordinate at 182: * <code>coords[offset + 1]</code>. The <i>x</i> coordinate of the 183: * new first control point is located at <code>coords[offset + 184: * 2]</code>, its <i>y</i> coordinate at <code>coords[offset + 185: * 3]</code>. The <i>x</i> coordinate of the new second control 186: * point is located at <code>coords[offset + 4]</code>, its <i>y</i> 187: * coordinate at <code>coords[offset + 5]</code>. The <i>x</i> 188: * coordinate of the new end point is located at <code>coords[offset 189: * + 6]</code>, its <i>y</i> coordinate at <code>coords[offset + 190: * 7]</code>. 191: * 192: * @param offset the offset of the first coordinate value in 193: * <code>coords</code>. 194: */ 195: public void setCurve(double[] coords, int offset) 196: { 197: setCurve(coords[offset++], coords[offset++], coords[offset++], 198: coords[offset++], coords[offset++], coords[offset++], 199: coords[offset++], coords[offset++]); 200: } 201: 202: /** 203: * Changes the curve geometry, specifying coordinate values in 204: * separate Point objects. 205: * 206: * <p><img src="doc-files/CubicCurve2D-1.png" width="350" height="180" 207: * alt="A drawing of a CubicCurve2D" /> 208: * 209: * <p>The curve does not keep any reference to the passed point 210: * objects. Therefore, a later change to <code>p1</code>, 211: * <code>c1</code>, <code>c2</code> or <code>p2</code> will not 212: * affect the curve geometry. 213: * 214: * @param p1 the new start point. 215: * @param c1 the new first control point. 216: * @param c2 the new second control point. 217: * @param p2 the new end point. 218: */ 219: public void setCurve(Point2D p1, Point2D c1, Point2D c2, Point2D p2) 220: { 221: setCurve(p1.getX(), p1.getY(), c1.getX(), c1.getY(), c2.getX(), c2.getY(), 222: p2.getX(), p2.getY()); 223: } 224: 225: /** 226: * Changes the curve geometry, specifying coordinate values in an 227: * array of Point objects. 228: * 229: * <p><img src="doc-files/CubicCurve2D-1.png" width="350" height="180" 230: * alt="A drawing of a CubicCurve2D" /> 231: * 232: * <p>The curve does not keep references to the passed point 233: * objects. Therefore, a later change to the <code>pts</code> array 234: * or any of its elements will not affect the curve geometry. 235: * 236: * @param pts an array containing the points. The new start point 237: * is located at <code>pts[offset]</code>, the new first control 238: * point at <code>pts[offset + 1]</code>, the new second control 239: * point at <code>pts[offset + 2]</code>, and the new end point 240: * at <code>pts[offset + 3]</code>. 241: * 242: * @param offset the offset of the start point in <code>pts</code>. 243: */ 244: public void setCurve(Point2D[] pts, int offset) 245: { 246: setCurve(pts[offset].getX(), pts[offset++].getY(), pts[offset].getX(), 247: pts[offset++].getY(), pts[offset].getX(), pts[offset++].getY(), 248: pts[offset].getX(), pts[offset++].getY()); 249: } 250: 251: /** 252: * Changes the curve geometry to that of another curve. 253: * 254: * @param c the curve whose coordinates will be copied. 255: */ 256: public void setCurve(CubicCurve2D c) 257: { 258: setCurve(c.getX1(), c.getY1(), c.getCtrlX1(), c.getCtrlY1(), 259: c.getCtrlX2(), c.getCtrlY2(), c.getX2(), c.getY2()); 260: } 261: 262: /** 263: * Calculates the squared flatness of a cubic curve, directly 264: * specifying each coordinate value. The flatness is the maximal 265: * distance of a control point to the line between start and end 266: * point. 267: * 268: * <p><img src="doc-files/CubicCurve2D-4.png" width="350" height="180" 269: * alt="A drawing that illustrates the flatness" /> 270: * 271: * <p>In the above drawing, the straight line connecting start point 272: * P1 and end point P2 is depicted in gray. In comparison to C1, 273: * control point C2 is father away from the gray line. Therefore, 274: * the result will be the square of the distance between C2 and the 275: * gray line, i.e. the squared length of the red line. 276: * 277: * @param x1 the <i>x</i> coordinate of the start point P1. 278: * @param y1 the <i>y</i> coordinate of the start point P1. 279: * @param cx1 the <i>x</i> coordinate of the first control point C1. 280: * @param cy1 the <i>y</i> coordinate of the first control point C1. 281: * @param cx2 the <i>x</i> coordinate of the second control point C2. 282: * @param cy2 the <i>y</i> coordinate of the second control point C2. 283: * @param x2 the <i>x</i> coordinate of the end point P2. 284: * @param y2 the <i>y</i> coordinate of the end point P2. 285: */ 286: public static double getFlatnessSq(double x1, double y1, double cx1, 287: double cy1, double cx2, double cy2, 288: double x2, double y2) 289: { 290: return Math.max(Line2D.ptSegDistSq(x1, y1, x2, y2, cx1, cy1), 291: Line2D.ptSegDistSq(x1, y1, x2, y2, cx2, cy2)); 292: } 293: 294: /** 295: * Calculates the flatness of a cubic curve, directly specifying 296: * each coordinate value. The flatness is the maximal distance of a 297: * control point to the line between start and end point. 298: * 299: * <p><img src="doc-files/CubicCurve2D-4.png" width="350" height="180" 300: * alt="A drawing that illustrates the flatness" /> 301: * 302: * <p>In the above drawing, the straight line connecting start point 303: * P1 and end point P2 is depicted in gray. In comparison to C1, 304: * control point C2 is father away from the gray line. Therefore, 305: * the result will be the distance between C2 and the gray line, 306: * i.e. the length of the red line. 307: * 308: * @param x1 the <i>x</i> coordinate of the start point P1. 309: * @param y1 the <i>y</i> coordinate of the start point P1. 310: * @param cx1 the <i>x</i> coordinate of the first control point C1. 311: * @param cy1 the <i>y</i> coordinate of the first control point C1. 312: * @param cx2 the <i>x</i> coordinate of the second control point C2. 313: * @param cy2 the <i>y</i> coordinate of the second control point C2. 314: * @param x2 the <i>x</i> coordinate of the end point P2. 315: * @param y2 the <i>y</i> coordinate of the end point P2. 316: */ 317: public static double getFlatness(double x1, double y1, double cx1, 318: double cy1, double cx2, double cy2, 319: double x2, double y2) 320: { 321: return Math.sqrt(getFlatnessSq(x1, y1, cx1, cy1, cx2, cy2, x2, y2)); 322: } 323: 324: /** 325: * Calculates the squared flatness of a cubic curve, specifying the 326: * coordinate values in an array. The flatness is the maximal 327: * distance of a control point to the line between start and end 328: * point. 329: * 330: * <p><img src="doc-files/CubicCurve2D-4.png" width="350" height="180" 331: * alt="A drawing that illustrates the flatness" /> 332: * 333: * <p>In the above drawing, the straight line connecting start point 334: * P1 and end point P2 is depicted in gray. In comparison to C1, 335: * control point C2 is father away from the gray line. Therefore, 336: * the result will be the square of the distance between C2 and the 337: * gray line, i.e. the squared length of the red line. 338: * 339: * @param coords an array containing the coordinate values. The 340: * <i>x</i> coordinate of the start point P1 is located at 341: * <code>coords[offset]</code>, its <i>y</i> coordinate at 342: * <code>coords[offset + 1]</code>. The <i>x</i> coordinate of the 343: * first control point C1 is located at <code>coords[offset + 344: * 2]</code>, its <i>y</i> coordinate at <code>coords[offset + 345: * 3]</code>. The <i>x</i> coordinate of the second control point C2 346: * is located at <code>coords[offset + 4]</code>, its <i>y</i> 347: * coordinate at <code>coords[offset + 5]</code>. The <i>x</i> 348: * coordinate of the end point P2 is located at <code>coords[offset 349: * + 6]</code>, its <i>y</i> coordinate at <code>coords[offset + 350: * 7]</code>. 351: * 352: * @param offset the offset of the first coordinate value in 353: * <code>coords</code>. 354: */ 355: public static double getFlatnessSq(double[] coords, int offset) 356: { 357: return getFlatnessSq(coords[offset++], coords[offset++], coords[offset++], 358: coords[offset++], coords[offset++], coords[offset++], 359: coords[offset++], coords[offset++]); 360: } 361: 362: /** 363: * Calculates the flatness of a cubic curve, specifying the 364: * coordinate values in an array. The flatness is the maximal 365: * distance of a control point to the line between start and end 366: * point. 367: * 368: * <p><img src="doc-files/CubicCurve2D-4.png" width="350" height="180" 369: * alt="A drawing that illustrates the flatness" /> 370: * 371: * <p>In the above drawing, the straight line connecting start point 372: * P1 and end point P2 is depicted in gray. In comparison to C1, 373: * control point C2 is father away from the gray line. Therefore, 374: * the result will be the distance between C2 and the gray line, 375: * i.e. the length of the red line. 376: * 377: * @param coords an array containing the coordinate values. The 378: * <i>x</i> coordinate of the start point P1 is located at 379: * <code>coords[offset]</code>, its <i>y</i> coordinate at 380: * <code>coords[offset + 1]</code>. The <i>x</i> coordinate of the 381: * first control point C1 is located at <code>coords[offset + 382: * 2]</code>, its <i>y</i> coordinate at <code>coords[offset + 383: * 3]</code>. The <i>x</i> coordinate of the second control point C2 384: * is located at <code>coords[offset + 4]</code>, its <i>y</i> 385: * coordinate at <code>coords[offset + 5]</code>. The <i>x</i> 386: * coordinate of the end point P2 is located at <code>coords[offset 387: * + 6]</code>, its <i>y</i> coordinate at <code>coords[offset + 388: * 7]</code>. 389: * 390: * @param offset the offset of the first coordinate value in 391: * <code>coords</code>. 392: */ 393: public static double getFlatness(double[] coords, int offset) 394: { 395: return Math.sqrt(getFlatnessSq(coords[offset++], coords[offset++], 396: coords[offset++], coords[offset++], 397: coords[offset++], coords[offset++], 398: coords[offset++], coords[offset++])); 399: } 400: 401: /** 402: * Calculates the squared flatness of this curve. The flatness is 403: * the maximal distance of a control point to the line between start 404: * and end point. 405: * 406: * <p><img src="doc-files/CubicCurve2D-4.png" width="350" height="180" 407: * alt="A drawing that illustrates the flatness" /> 408: * 409: * <p>In the above drawing, the straight line connecting start point 410: * P1 and end point P2 is depicted in gray. In comparison to C1, 411: * control point C2 is father away from the gray line. Therefore, 412: * the result will be the square of the distance between C2 and the 413: * gray line, i.e. the squared length of the red line. 414: */ 415: public double getFlatnessSq() 416: { 417: return getFlatnessSq(getX1(), getY1(), getCtrlX1(), getCtrlY1(), 418: getCtrlX2(), getCtrlY2(), getX2(), getY2()); 419: } 420: 421: /** 422: * Calculates the flatness of this curve. The flatness is the 423: * maximal distance of a control point to the line between start and 424: * end point. 425: * 426: * <p><img src="doc-files/CubicCurve2D-4.png" width="350" height="180" 427: * alt="A drawing that illustrates the flatness" /> 428: * 429: * <p>In the above drawing, the straight line connecting start point 430: * P1 and end point P2 is depicted in gray. In comparison to C1, 431: * control point C2 is father away from the gray line. Therefore, 432: * the result will be the distance between C2 and the gray line, 433: * i.e. the length of the red line. 434: */ 435: public double getFlatness() 436: { 437: return Math.sqrt(getFlatnessSq(getX1(), getY1(), getCtrlX1(), getCtrlY1(), 438: getCtrlX2(), getCtrlY2(), getX2(), getY2())); 439: } 440: 441: /** 442: * Subdivides this curve into two halves. 443: * 444: * <p><img src="doc-files/CubicCurve2D-3.png" width="700" 445: * height="180" alt="A drawing that illustrates the effects of 446: * subdividing a CubicCurve2D" /> 447: * 448: * @param left a curve whose geometry will be set to the left half 449: * of this curve, or <code>null</code> if the caller is not 450: * interested in the left half. 451: * 452: * @param right a curve whose geometry will be set to the right half 453: * of this curve, or <code>null</code> if the caller is not 454: * interested in the right half. 455: */ 456: public void subdivide(CubicCurve2D left, CubicCurve2D right) 457: { 458: // Use empty slots at end to share single array. 459: double[] d = new double[] 460: { 461: getX1(), getY1(), getCtrlX1(), getCtrlY1(), getCtrlX2(), 462: getCtrlY2(), getX2(), getY2(), 0, 0, 0, 0, 0, 0 463: }; 464: subdivide(d, 0, d, 0, d, 6); 465: if (left != null) 466: left.setCurve(d, 0); 467: if (right != null) 468: right.setCurve(d, 6); 469: } 470: 471: /** 472: * Subdivides a cubic curve into two halves. 473: * 474: * <p><img src="doc-files/CubicCurve2D-3.png" width="700" 475: * height="180" alt="A drawing that illustrates the effects of 476: * subdividing a CubicCurve2D" /> 477: * 478: * @param src the curve to be subdivided. 479: * 480: * @param left a curve whose geometry will be set to the left half 481: * of <code>src</code>, or <code>null</code> if the caller is not 482: * interested in the left half. 483: * 484: * @param right a curve whose geometry will be set to the right half 485: * of <code>src</code>, or <code>null</code> if the caller is not 486: * interested in the right half. 487: */ 488: public static void subdivide(CubicCurve2D src, CubicCurve2D left, 489: CubicCurve2D right) 490: { 491: src.subdivide(left, right); 492: } 493: 494: /** 495: * Subdivides a cubic curve into two halves, passing all coordinates 496: * in an array. 497: * 498: * <p><img src="doc-files/CubicCurve2D-3.png" width="700" 499: * height="180" alt="A drawing that illustrates the effects of 500: * subdividing a CubicCurve2D" /> 501: * 502: * <p>The left end point and the right start point will always be 503: * identical. Memory-concious programmers thus may want to pass the 504: * same array for both <code>left</code> and <code>right</code>, and 505: * set <code>rightOff</code> to <code>leftOff + 6</code>. 506: * 507: * @param src an array containing the coordinates of the curve to be 508: * subdivided. The <i>x</i> coordinate of the start point P1 is 509: * located at <code>src[srcOff]</code>, its <i>y</i> at 510: * <code>src[srcOff + 1]</code>. The <i>x</i> coordinate of the 511: * first control point C1 is located at <code>src[srcOff + 512: * 2]</code>, its <i>y</i> at <code>src[srcOff + 3]</code>. The 513: * <i>x</i> coordinate of the second control point C2 is located at 514: * <code>src[srcOff + 4]</code>, its <i>y</i> at <code>src[srcOff + 515: * 5]</code>. The <i>x</i> coordinate of the end point is located at 516: * <code>src[srcOff + 6]</code>, its <i>y</i> at <code>src[srcOff + 517: * 7]</code>. 518: * 519: * @param srcOff an offset into <code>src</code>, specifying 520: * the index of the start point’s <i>x</i> coordinate. 521: * 522: * @param left an array that will receive the coordinates of the 523: * left half of <code>src</code>. It is acceptable to pass 524: * <code>src</code>. A caller who is not interested in the left half 525: * can pass <code>null</code>. 526: * 527: * @param leftOff an offset into <code>left</code>, specifying the 528: * index where the start point’s <i>x</i> coordinate will be 529: * stored. 530: * 531: * @param right an array that will receive the coordinates of the 532: * right half of <code>src</code>. It is acceptable to pass 533: * <code>src</code> or <code>left</code>. A caller who is not 534: * interested in the right half can pass <code>null</code>. 535: * 536: * @param rightOff an offset into <code>right</code>, specifying the 537: * index where the start point’s <i>x</i> coordinate will be 538: * stored. 539: */ 540: public static void subdivide(double[] src, int srcOff, double[] left, 541: int leftOff, double[] right, int rightOff) 542: { 543: // To understand this code, please have a look at the image 544: // "CubicCurve2D-3.png" in the sub-directory "doc-files". 545: double src_C1_x; 546: double src_C1_y; 547: double src_C2_x; 548: double src_C2_y; 549: double left_P1_x; 550: double left_P1_y; 551: double left_C1_x; 552: double left_C1_y; 553: double left_C2_x; 554: double left_C2_y; 555: double right_C1_x; 556: double right_C1_y; 557: double right_C2_x; 558: double right_C2_y; 559: double right_P2_x; 560: double right_P2_y; 561: double Mid_x; // Mid = left.P2 = right.P1 562: double Mid_y; // Mid = left.P2 = right.P1 563: 564: left_P1_x = src[srcOff]; 565: left_P1_y = src[srcOff + 1]; 566: src_C1_x = src[srcOff + 2]; 567: src_C1_y = src[srcOff + 3]; 568: src_C2_x = src[srcOff + 4]; 569: src_C2_y = src[srcOff + 5]; 570: right_P2_x = src[srcOff + 6]; 571: right_P2_y = src[srcOff + 7]; 572: 573: left_C1_x = (left_P1_x + src_C1_x) / 2; 574: left_C1_y = (left_P1_y + src_C1_y) / 2; 575: right_C2_x = (right_P2_x + src_C2_x) / 2; 576: right_C2_y = (right_P2_y + src_C2_y) / 2; 577: Mid_x = (src_C1_x + src_C2_x) / 2; 578: Mid_y = (src_C1_y + src_C2_y) / 2; 579: left_C2_x = (left_C1_x + Mid_x) / 2; 580: left_C2_y = (left_C1_y + Mid_y) / 2; 581: right_C1_x = (Mid_x + right_C2_x) / 2; 582: right_C1_y = (Mid_y + right_C2_y) / 2; 583: Mid_x = (left_C2_x + right_C1_x) / 2; 584: Mid_y = (left_C2_y + right_C1_y) / 2; 585: 586: if (left != null) 587: { 588: left[leftOff] = left_P1_x; 589: left[leftOff + 1] = left_P1_y; 590: left[leftOff + 2] = left_C1_x; 591: left[leftOff + 3] = left_C1_y; 592: left[leftOff + 4] = left_C2_x; 593: left[leftOff + 5] = left_C2_y; 594: left[leftOff + 6] = Mid_x; 595: left[leftOff + 7] = Mid_y; 596: } 597: 598: if (right != null) 599: { 600: right[rightOff] = Mid_x; 601: right[rightOff + 1] = Mid_y; 602: right[rightOff + 2] = right_C1_x; 603: right[rightOff + 3] = right_C1_y; 604: right[rightOff + 4] = right_C2_x; 605: right[rightOff + 5] = right_C2_y; 606: right[rightOff + 6] = right_P2_x; 607: right[rightOff + 7] = right_P2_y; 608: } 609: } 610: 611: /** 612: * Finds the non-complex roots of a cubic equation, placing the 613: * results into the same array as the equation coefficients. The 614: * following equation is being solved: 615: * 616: * <blockquote><code>eqn[3]</code> · <i>x</i><sup>3</sup> 617: * + <code>eqn[2]</code> · <i>x</i><sup>2</sup> 618: * + <code>eqn[1]</code> · <i>x</i> 619: * + <code>eqn[0]</code> 620: * = 0 621: * </blockquote> 622: * 623: * <p>For some background about solving cubic equations, see the 624: * article <a 625: * href="http://planetmath.org/encyclopedia/CubicFormula.html" 626: * >“Cubic Formula”</a> in <a 627: * href="http://planetmath.org/" >PlanetMath</a>. For an extensive 628: * library of numerical algorithms written in the C programming 629: * language, see the <a href= "http://www.gnu.org/software/gsl/">GNU 630: * Scientific Library</a>, from which this implementation was 631: * adapted. 632: * 633: * @param eqn an array with the coefficients of the equation. When 634: * this procedure has returned, <code>eqn</code> will contain the 635: * non-complex solutions of the equation, in no particular order. 636: * 637: * @return the number of non-complex solutions. A result of 0 638: * indicates that the equation has no non-complex solutions. A 639: * result of -1 indicates that the equation is constant (i.e., 640: * always or never zero). 641: * 642: * @see #solveCubic(double[], double[]) 643: * @see QuadCurve2D#solveQuadratic(double[],double[]) 644: * 645: * @author Brian Gough (bjg@network-theory.com) 646: * (original C implementation in the <a href= 647: * "http://www.gnu.org/software/gsl/">GNU Scientific Library</a>) 648: * 649: * @author Sascha Brawer (brawer@dandelis.ch) 650: * (adaptation to Java) 651: */ 652: public static int solveCubic(double[] eqn) 653: { 654: return solveCubic(eqn, eqn); 655: } 656: 657: /** 658: * Finds the non-complex roots of a cubic equation. The following 659: * equation is being solved: 660: * 661: * <blockquote><code>eqn[3]</code> · <i>x</i><sup>3</sup> 662: * + <code>eqn[2]</code> · <i>x</i><sup>2</sup> 663: * + <code>eqn[1]</code> · <i>x</i> 664: * + <code>eqn[0]</code> 665: * = 0 666: * </blockquote> 667: * 668: * <p>For some background about solving cubic equations, see the 669: * article <a 670: * href="http://planetmath.org/encyclopedia/CubicFormula.html" 671: * >“Cubic Formula”</a> in <a 672: * href="http://planetmath.org/" >PlanetMath</a>. For an extensive 673: * library of numerical algorithms written in the C programming 674: * language, see the <a href= "http://www.gnu.org/software/gsl/">GNU 675: * Scientific Library</a>, from which this implementation was 676: * adapted. 677: * 678: * @see QuadCurve2D#solveQuadratic(double[],double[]) 679: * 680: * @param eqn an array with the coefficients of the equation. 681: * 682: * @param res an array into which the non-complex roots will be 683: * stored. The results may be in an arbitrary order. It is safe to 684: * pass the same array object reference for both <code>eqn</code> 685: * and <code>res</code>. 686: * 687: * @return the number of non-complex solutions. A result of 0 688: * indicates that the equation has no non-complex solutions. A 689: * result of -1 indicates that the equation is constant (i.e., 690: * always or never zero). 691: * 692: * @author Brian Gough (bjg@network-theory.com) 693: * (original C implementation in the <a href= 694: * "http://www.gnu.org/software/gsl/">GNU Scientific Library</a>) 695: * 696: * @author Sascha Brawer (brawer@dandelis.ch) 697: * (adaptation to Java) 698: */ 699: public static int solveCubic(double[] eqn, double[] res) 700: { 701: // Adapted from poly/solve_cubic.c in the GNU Scientific Library 702: // (GSL), revision 1.7 of 2003-07-26. For the original source, see 703: // http://www.gnu.org/software/gsl/ 704: // 705: // Brian Gough, the author of that code, has granted the 706: // permission to use it in GNU Classpath under the GNU Classpath 707: // license, and has assigned the copyright to the Free Software 708: // Foundation. 709: // 710: // The Java implementation is very similar to the GSL code, but 711: // not a strict one-to-one copy. For example, GSL would sort the 712: // result. 713: 714: double a; 715: double b; 716: double c; 717: double q; 718: double r; 719: double Q; 720: double R; 721: double c3; 722: double Q3; 723: double R2; 724: double CR2; 725: double CQ3; 726: 727: // If the cubic coefficient is zero, we have a quadratic equation. 728: c3 = eqn[3]; 729: if (c3 == 0) 730: return QuadCurve2D.solveQuadratic(eqn, res); 731: 732: // Divide the equation by the cubic coefficient. 733: c = eqn[0] / c3; 734: b = eqn[1] / c3; 735: a = eqn[2] / c3; 736: 737: // We now need to solve x^3 + ax^2 + bx + c = 0. 738: q = a * a - 3 * b; 739: r = 2 * a * a * a - 9 * a * b + 27 * c; 740: 741: Q = q / 9; 742: R = r / 54; 743: 744: Q3 = Q * Q * Q; 745: R2 = R * R; 746: 747: CR2 = 729 * r * r; 748: CQ3 = 2916 * q * q * q; 749: 750: if (R == 0 && Q == 0) 751: { 752: // The GNU Scientific Library would return three identical 753: // solutions in this case. 754: res[0] = -a / 3; 755: return 1; 756: } 757: 758: if (CR2 == CQ3) 759: { 760: /* this test is actually R2 == Q3, written in a form suitable 761: for exact computation with integers */ 762: /* Due to finite precision some double roots may be missed, and 763: considered to be a pair of complex roots z = x +/- epsilon i 764: close to the real axis. */ 765: double sqrtQ = Math.sqrt(Q); 766: 767: if (R > 0) 768: { 769: res[0] = -2 * sqrtQ - a / 3; 770: res[1] = sqrtQ - a / 3; 771: } 772: else 773: { 774: res[0] = -sqrtQ - a / 3; 775: res[1] = 2 * sqrtQ - a / 3; 776: } 777: return 2; 778: } 779: 780: if (CR2 < CQ3) /* equivalent to R2 < Q3 */ 781: { 782: double sqrtQ = Math.sqrt(Q); 783: double sqrtQ3 = sqrtQ * sqrtQ * sqrtQ; 784: double theta = Math.acos(R / sqrtQ3); 785: double norm = -2 * sqrtQ; 786: res[0] = norm * Math.cos(theta / 3) - a / 3; 787: res[1] = norm * Math.cos((theta + 2.0 * Math.PI) / 3) - a / 3; 788: res[2] = norm * Math.cos((theta - 2.0 * Math.PI) / 3) - a / 3; 789: 790: // The GNU Scientific Library sorts the results. We don't. 791: return 3; 792: } 793: 794: double sgnR = (R >= 0 ? 1 : -1); 795: double A = -sgnR * Math.pow(Math.abs(R) + Math.sqrt(R2 - Q3), 1.0 / 3.0); 796: double B = Q / A; 797: res[0] = A + B - a / 3; 798: return 1; 799: } 800: 801: /** 802: * Determines whether a position lies inside the area bounded 803: * by the curve and the straight line connecting its end points. 804: * 805: * <p><img src="doc-files/CubicCurve2D-5.png" width="350" height="180" 806: * alt="A drawing of the area spanned by the curve" /> 807: * 808: * <p>The above drawing illustrates in which area points are 809: * considered “inside” a CubicCurve2D. 810: */ 811: public boolean contains(double x, double y) 812: { 813: if (! getBounds2D().contains(x, y)) 814: return false; 815: 816: return ((getAxisIntersections(x, y, true, BIG_VALUE) & 1) != 0); 817: } 818: 819: /** 820: * Determines whether a point lies inside the area bounded 821: * by the curve and the straight line connecting its end points. 822: * 823: * <p><img src="doc-files/CubicCurve2D-5.png" width="350" height="180" 824: * alt="A drawing of the area spanned by the curve" /> 825: * 826: * <p>The above drawing illustrates in which area points are 827: * considered “inside” a CubicCurve2D. 828: */ 829: public boolean contains(Point2D p) 830: { 831: return contains(p.getX(), p.getY()); 832: } 833: 834: /** 835: * Determines whether any part of a rectangle is inside the area bounded 836: * by the curve and the straight line connecting its end points. 837: * 838: * <p><img src="doc-files/CubicCurve2D-5.png" width="350" height="180" 839: * alt="A drawing of the area spanned by the curve" /> 840: * 841: * <p>The above drawing illustrates in which area points are 842: * considered “inside” in a CubicCurve2D. 843: * @see #contains(double, double) 844: */ 845: public boolean intersects(double x, double y, double w, double h) 846: { 847: if (!