1 package fr.orsay.lri.varna.models.geom;
4 import java.awt.geom.Point2D;
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
17 * @author Raphael Champeimont
19 public class CubicBezierCurve {
22 * The four points defining the curve.
24 private Point2D.Double P0, P1, P2, P3;
30 * The number of lines approximating the Bezier curve.
38 * Get the (exact) length of the approximation curve.
40 public double getApproxCurveLength() {
47 * The n+1 points between the n lines.
49 private Point2D.Double[] points;
55 * lengths[i] is the sum of lengths of lines up to and including the
56 * line starting at point points[i].
58 private double[] lengths;
63 * The vectors along each line, with a norm of 1.
65 private Point2D.Double[] unitVectors;
70 * The standard exact cubic Bezier curve parametrization.
71 * Argument t must be in [0,1].
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
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
82 return new Point2D.Double(x, y);
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).
105 public Point2D.Double[] uniformParam(double[] t) {
107 Point2D.Double[] result = new Point2D.Double[m];
109 for (int i=0; i<m; i++) {
110 while ((line<n) && (lengths[line] < t[i])) {
114 // In theory should not happen, but float computation != math.
118 throw (new IllegalArgumentException("t[" + i + "] < 0"));
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);
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.
139 public CubicBezierCurve(
151 throw (new IllegalArgumentException("n must be at least 1"));
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);
163 lengths = new double[n];
164 unitVectors = new Point2D.Double[n];
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);
180 private double lineLength(Point2D.Double P1, Point2D.Double P2) {
181 return P2.distance(P1);
185 public Point2D.Double getP0() {
189 public Point2D.Double getP1() {
193 public Point2D.Double getP2() {
197 public Point2D.Double getP3() {