srcjar/fr/orsay/lri/varna/models/geom/CubicBezierCurve.java

   1 package fr.orsay.lri.varna.models.geom;
   2
   3
   4 import java.awt.geom.Point2D;
   5
   6 /**
   7  * This class implements a cubic Bezier curve
   8  * with a constant speed parametrization.
   9  * The Bezier curve is approximated by a sequence of n straight lines,
  10  * where the n+1 points between the lines are
  11  * { B(k/n), k=0,1,...,n } where B is the standard
  12  * parametrization given here:
  13  * http://en.wikipedia.org/wiki/Bezier_curve#Cubic_B.C3.A9zier_curves
  14  * You can then use the constant speed parametrization over this sequence
  15  * of straight lines.
  16  *
  17  * @author Raphael Champeimont
  18  */
  19 public class CubicBezierCurve {
  20
  21         /**
  22          * The four points defining the curve.
  23          */
  24         private Point2D.Double P0, P1, P2, P3;
  25
  26
  27
  28         private int n;
  29         /**
  30          * The number of lines approximating the Bezier curve.
  31          */
  32         public int getN() {
  33                 return n;
  34         }
  35
  36
  37         /**
  38          * Get the (exact) length of the approximation curve.
  39          */
  40         public double getApproxCurveLength() {
  41                 return lengths[n-1];
  42         }
  43
  44
  45
  46         /**
  47          * The n+1 points between the n lines.
  48          */
  49         private Point2D.Double[] points;
  50
  51
  52
  53         /**
  54          * Array of length n.
  55          * lengths[i] is the sum of lengths of lines up to and including the
  56          * line starting at point points[i].
  57          */
  58         private double[] lengths;
  59
  60
  61         /**
  62          * Array of length n.
  63          * The vectors along each line, with a norm of 1.
  64          */
  65         private Point2D.Double[] unitVectors;
  66
  67
  68
  69         /**
  70          * The standard exact cubic Bezier curve parametrization.
  71          * Argument t must be in [0,1].
  72          */
  73         public Point2D.Double standardParam(double t) {
  74                 double x = Math.pow(1-t,3) * P0.x
  75                  + 3 * Math.pow(1-t,2) * t * P1.x
  76                  + 3 * (1-t) * t * t * P2.x
  77                  + t * t * t * P3.x;
  78                 double y = Math.pow(1-t,3) * P0.y
  79                  + 3 * Math.pow(1-t,2) * t * P1.y
  80                  + 3 * (1-t) * t * t * P2.y
  81                  + t * t * t * P3.y;
  82                 return new Point2D.Double(x, y);
  83         }
  84
  85
  86
  87
  88
  89         /**
  90          * Uniform approximated parameterization.
  91          * A value in t must be in [0, getApproxCurveLength()].
  92          * We have built a function f such that f(t) is the position of
  93          * the point on the approximation curve (n straight lines).
  94          * The interesting property is that the length of the curve
  95          * { f(t), t in [0,l] } is exactly l.
  96          * The java function is simply the application of f over each element
  97          * of a sorted array, ie. uniformParam(t)[k] = f(t[k]).
  98          * Computation time is O(n+m) where n is the number of lines in which
  99          * the curve is divided and m is the length of the array given as an
 100          * argument. The use of a sorted array instead of m calls to the
 101          * function enables us to have a complexity of O(n+m) instead of O(n*m)
 102          * because we don't need to search in all the n possible lines for
 103          * each value in t (as we know their are in increasing order).
 104          */
 105         public Point2D.Double[] uniformParam(double[] t) {
 106                 int m = t.length;
 107                 Point2D.Double[] result = new Point2D.Double[m];
 108                 int line = 0;
 109                 for (int i=0; i<m; i++) {
 110                         while ((line<n) && (lengths[line] < t[i])) {
 111                                 line++;
 112                         }
 113                         if (line >= n) {
 114                                 // In theory should not happen, but float computation != math.
 115                                 line = n-1;
 116                         }
 117                         if (t[i] < 0) {
 118                                 throw (new IllegalArgumentException("t[" + i + "] < 0"));
 119                         }
 120                         // So now we know on which line we are
 121                         double lengthOnLine = t[i] - (line != 0 ? lengths[line-1] : 0);
 122                         double x = points[line].x + unitVectors[line].x * lengthOnLine;
 123                         double y = points[line].y + unitVectors[line].y * lengthOnLine;
 124                         result[i] = new Point2D.Double(x, y);
 125                 }
 126                 return result;
 127         }
 128
 129
 130
 131         /**
 132          * A Bezier curve can be defined by four points,
 133          * see http://en.wikipedia.org/wiki/Bezier_curve#Cubic_B.C3.A9zier_curves
 134          * Here we give this four points and a integer to say in how many
 135          * line segments we want to cut the Bezier curve (if n is bigger
 136          * the computation takes longer but the precision is better).
 137          * The number of lines must be at least 1.
 138          */
 139         public CubicBezierCurve(
 140                         Point2D.Double P0,
 141                         Point2D.Double P1,
 142                         Point2D.Double P2,
 143                         Point2D.Double P3,
 144                         int n) {
 145                 this.P0 = P0;
 146                 this.P1 = P1;
 147                 this.P2 = P2;
 148                 this.P3 = P3;
 149                 this.n = n;
 150                 if (n < 1) {
 151                         throw (new IllegalArgumentException("n must be at least 1"));
 152                 }
 153                 computeData();
 154         }
 155
 156
 157         private void computeData() {
 158                 points = new Point2D.Double[n+1];
 159                 for (int k=0; k<=n; k++) {
 160                         points[k] = standardParam(((double) k) / n);
 161                 }
 162
 163                 lengths = new double[n];
 164                 unitVectors = new Point2D.Double[n];
 165                 double sum = 0;
 166                 for (int i=0; i<n; i++) {
 167                         double l = lineLength(points[i], points[i+1]);
 168                         double dx = (points[i+1].x - points[i].x) / l;
 169                         double dy = (points[i+1].y - points[i].y) / l;
 170                         unitVectors[i] = new Point2D.Double(dx, dy);
 171                         sum += l;
 172                         lengths[i] = sum;
 173                 }
 174
 175
 176
 177         }
 178
 179
 180         private double lineLength(Point2D.Double P1, Point2D.Double P2) {
 181                 return P2.distance(P1);
 182         }
 183
 184
 185         public Point2D.Double getP0() {
 186                 return P0;
 187         }
 188
 189         public Point2D.Double getP1() {
 190                 return P1;
 191         }
 192
 193         public Point2D.Double getP2() {
 194                 return P2;
 195         }
 196
 197         public Point2D.Double getP3() {
 198                 return P3;
 199         }
 200
 201
 202
 203
 204
 205 }