1 package fr.orsay.lri.varna.models.geom;
4 import java.awt.geom.AffineTransform;
5 import java.awt.geom.Point2D;
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.
14 * @author Raphael Champeimont
16 public class HalfEllipse {
19 * The four points defining the curve.
27 * The number of lines approximating the curve.
35 * Get the (exact) length of the approximation curve.
37 public double getApproxCurveLength() {
44 * The n+1 points between the n lines.
46 private Point2D.Double[] points;
52 * lengths[i] is the sum of lengths of lines up to and including the
53 * line starting at point points[i].
55 private double[] lengths;
60 * The vectors along each line, with a norm of 1.
62 private Point2D.Double[] unitVectors;
67 * The standard ellipse parameterization.
68 * Argument t must be in [0,1].
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);
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).
96 public Point2D.Double[] uniformParam(double[] t) {
98 Point2D.Double[] result = new Point2D.Double[m];
100 for (int i=0; i<m; i++) {
101 while ((line<n) && (lengths[line] < t[i])) {
105 // In theory should not happen, but float computation != math.
109 throw (new IllegalArgumentException("t[" + i + "] < 0"));
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);
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.
130 public HalfEllipse(double a, double b, int n) {
135 throw (new IllegalArgumentException("n must be at least 1"));
142 * Returns that affine transform that moves the ellipse
143 * given by this class such that its 0/pi axis matches P0-P1.
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);
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);
161 lengths = new double[n];
162 unitVectors = new Point2D.Double[n];
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);
178 private double lineLength(Point2D.Double P1, Point2D.Double P2) {
179 return P2.distance(P1);
182 public double getA() {
186 public double getB() {