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

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