java.lang.Object
org.apache.sis.internal.referencing.j2d.Bezier
Direct Known Subclasses:
GeodeticCalculator.PathBuilder

public abstract class Bezier extends Object
Helper class for appending Bézier curves to a path. This class computes cubic Bézier from 3 points and two slopes. The three points are the start point (t=0), middle point (t=½) and end point (t=1). The slopes are at start point and end point. The Bézier curve will obey exactly to those conditions (up to rounding errors).

After creating each Bézier curve, this class performs a quality control using 2 additional points located at one quarter (t≈¼) and three quarters (t≈¾) of the curve. If the distance between given points and a close point on the curve is greater than εx and εy thresholds, then the curve is divided in two smaller curves and the process is repeated until curves meet the quality controls.

If a quadratic curve degenerates to a cubic curve or a straight line, ignoring errors up to εx and εy, then CubicCurve2D are replaced by QuadCurve2D or Line2D.

Since:
1.0
Version:
1.0
See Also:
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected int
    The number of times a curve has been divided in smaller curves.
    private static final int
    Limit the maximal depth for avoiding shapes of unreasonable size.
    protected double
    Components of α=(∂y/∂x) derivative at the point evaluated by evaluateAt(double).
    private double
    Components of α=(∂y/∂x) derivative at starting point t=0.
    protected double
    Components of α=(∂y/∂x) derivative at the point evaluated by evaluateAt(double).
    private double
    Components of α=(∂y/∂x) derivative at starting point t=0.
    protected boolean
    Whether to force the creation of QuadCurve2D.
    private static final int
    Maximum number of iterations for iterative computations.
    private final Path2D
    The path where to append Bézier curves.
    protected final double[]
    A buffer used by subclasses for storing results of evaluateAt(double).
    private double
    (x and y) coordinates at starting point t=0.
    private double
    (x and y) coordinates at starting point t=0.
    protected double
    Maximal distance (approximate) on x and y axis between Bézier curves and desired curve.
    protected double
    Maximal distance (approximate) on x and y axis between Bézier curves and desired curve.
  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    Bezier(int dimension)
    Creates a new builder.
  • Method Summary

    Modifier and Type
    Method
    Description
    final Path2D
    Creates a sequence of Bézier curves from the position given by evaluateAt(0) to the position given by evaluateAt(1).
    private boolean
    curve(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4, double dx4, double dy4)
    Computes a Bézier curve passing by the given points and with the given derivatives at end points.
    protected abstract void
    evaluateAt(double t)
    Invoked for computing a new point on the Bézier curve.
    private boolean
    isNear(double x, double y, double t, double ax, double ay, double am, double bx, double by, double bm, double x4, double y4, double cm, double xp, double yp)
    Returns true if the point specified by the (xp, yp) coordinates is close to the Bézier curve specified by the given control points.
    private void
    sequence(double tmin, double tmax, double x2, double y2, double dx2, double dy2, double x4, double y4, double dx4, double dy4)
    Creates a sequence of Bézier curves from the position given by evaluateAt(tmin) to the position given by evaluateAt(tmax).

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • DEPTH_LIMIT

      private static final int DEPTH_LIMIT
      Limit the maximal depth for avoiding shapes of unreasonable size.
      See Also:
    • MAXIMUM_ITERATIONS

      private static final int MAXIMUM_ITERATIONS
      Maximum number of iterations for iterative computations. We use a small value because failure to provide an answer with a small number of iterations probably means that the curve needs to be separated again in two smaller curves.
      See Also:
    • path

      private final Path2D path
      The path where to append Bézier curves.
    • εx

      protected double εx
      Maximal distance (approximate) on x and y axis between Bézier curves and desired curve. Also used for deciding if a cubic Bézier curve can be simplified to quadratic curve or straight line. Initial value is zero. Subclasses should set the values either in their constructor or at evaluateAt(double) method call. Can be set to infinity or NaN for disabling the quality checks, or to negative value for forcing unconditional divisions of Bézier curves in two sub-curves.
    • εy

      protected double εy
      Maximal distance (approximate) on x and y axis between Bézier curves and desired curve. Also used for deciding if a cubic Bézier curve can be simplified to quadratic curve or straight line. Initial value is zero. Subclasses should set the values either in their constructor or at evaluateAt(double) method call. Can be set to infinity or NaN for disabling the quality checks, or to negative value for forcing unconditional divisions of Bézier curves in two sub-curves.
    • x0

      private double x0
      (x and y) coordinates at starting point t=0. This is initialized by build() and updated by sequence(double, double, double, double, double, double, double, double, double, double) when moving along the path.
    • y0

      private double y0
      (x and y) coordinates at starting point t=0. This is initialized by build() and updated by sequence(double, double, double, double, double, double, double, double, double, double) when moving along the path.
    • dx0

      private double dx0
      Components of α=(∂y/∂x) derivative at starting point t=0. Initialized and updated at the same time than x0 and y0.
    • dy0

      private double dy0
      Components of α=(∂y/∂x) derivative at starting point t=0. Initialized and updated at the same time than x0 and y0.
    • dx

      protected double dx
      Components of α=(∂y/∂x) derivative at the point evaluated by evaluateAt(double).
    • dy

      protected double dy
      Components of α=(∂y/∂x) derivative at the point evaluated by evaluateAt(double).
    • point

      protected final double[] point
      A buffer used by subclasses for storing results of evaluateAt(double). The two first elements are x and y coordinates respectively. Other elements (if any) are ignored.
    • depth

      protected int depth
      The number of times a curve has been divided in smaller curves.
      See Also:
    • forceCubic

      protected boolean forceCubic
      Whether to force the creation of QuadCurve2D. The default value is false, which allows simplification to CubicCurve2D or Line2D. This flag can be set to true when building circular shapes, in which case simplifications to CubicCurve2D produce bad results.
  • Constructor Details

    • Bezier

      protected Bezier(int dimension)
      Creates a new builder.
      Parameters:
      dimension - length of the point array. Must be at least 2.
  • Method Details

    • evaluateAt

      protected abstract void evaluateAt(double t) throws org.opengis.referencing.operation.TransformException
      Invoked for computing a new point on the Bézier curve. This method is invoked with a t value varying from 0 to 1 inclusive. Value 0 is for the starting point and value 1 is for the ending point. Other values are for points interpolated between the start and end points. In particular value ½ is for the point in the middle of the curve. This method will also be invoked at least for values ¼ and ¾, and potentially for other values too.

      This method shall store the point coordinates in the point array with x coordinate in the first element and y coordinate in the second element. This method shall also store derivative (∂y/∂x) at that location in the dx and dy fields. If this method cannot compute a coordinate, it can store Double.NaN values except for t=0, ½ and 1 where finite coordinates are mandatory.

      Subclasses can optionally update the εx and εy values if the tolerance thresholds change as a result of this method call, for example because we come closer to a pole. The tolerance values used for each Bézier curve are the ones computed at t=¼ and t=¾ of that curve.

      Parameters:
      t - desired point on the curve, from 0 (start point) to 1 (end point) inclusive.
      Throws:
      org.opengis.referencing.operation.TransformException - if the point coordinates cannot be computed.
    • build

      public final Path2D build() throws org.opengis.referencing.operation.TransformException
      Creates a sequence of Bézier curves from the position given by evaluateAt(0) to the position given by evaluateAt(1). This method determines the number of intermediate points required for achieving the precision requested by the εx and εy parameters given at construction time.
      Returns:
      the sequence of Bézier curves.
      Throws:
      org.opengis.referencing.operation.TransformException - if the coordinates of a point cannot be computed.
    • sequence

      private void sequence(double tmin, double tmax, double x2, double y2, double dx2, double dy2, double x4, double y4, double dx4, double dy4) throws org.opengis.referencing.operation.TransformException
      Creates a sequence of Bézier curves from the position given by evaluateAt(tmin) to the position given by evaluateAt(tmax). This method invokes itself recursively as long as more points are needed for achieving the precision requested by the εx and εy parameters given at construction time.

      The x0, y0, dx0 and dy0 fields must be set to the start point before this method is invoked. On method completion those fields will be updated to the coordinates and derivative of end point, thus enabling chaining with the next sequence(…) call.

      Parameters:
      tmin - t value of the start point (initially 0).
      tmax - t value of the end point (initially 1).
      x2 - x coordinate at t=½ (mid-point).
      y2 - y coordinate at t=½ (mid-point).
      dx2 - x component of the the derivative (∂y/∂x) at mid-point.
      dy2 - y component of the the derivative (∂y/∂x) at mid-point.
      x4 - x coordinate at t=1 (end point).
      y4 - y coordinate at t=1 (end point).
      dx4 - x component of the derivative (∂y/∂x) at end point.
      dy4 - y component of the derivative (∂y/∂x) at end point.
      Throws:
      org.opengis.referencing.operation.TransformException - if the coordinates of a point cannot be computed.
    • curve

      private boolean curve(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4, double dx4, double dy4)
      Computes a Bézier curve passing by the given points and with the given derivatives at end points. The cubic curve equation is:
      B(t) = (1−t)³⋅P₀ + 3(1−t)²t⋅A + 3(1−t)t²⋅B + t³⋅P₄
      where t ∈ [0…1], P₀ and P₄ are start and end points of the curve and A and B are control points generally not on the curve. For any point Pi, the index i gives the value of the parameter t where the point is located with t = i/4, and coordinates (x, y) follow the same indices. The (x₀,y₀) fields give the coordinates of point P₀ at t=0 (0/4). The (x₂,y₂) arguments give the coordinates of the point at t=½ (2/4). The (x₄,y₄) arguments give the coordinates of point P₄ at t=1 (4/4).

      The P₁ and P₃ points are for quality control. They should be points at t≈¼ t≈¾ respectively. Those points are not used for computing the curve, but are used for checking if the curve is an accurate approximation. If the curve is not accurate enough, then this method does nothing and return false. In that case, the caller should split the curve in two smaller parts and invoke this method again.

      If the full equation is required for representing the curve, then this method appends a CubicCurve2D. If the same curve can be represented by a quadratic curve, then this method appends a QuadCurve2D. If the curve is actually a straight line, then this method appends a Line2D.

      Parameters:
      x1 - x coordinate at t≈¼ (quality control, may be NaN).
      y1 - y coordinate at t≈¼ (quality control, may be NaN).
      x2 - x coordinate at t=½ (mid-point).
      y2 - y coordinate at t=½ (mid-point).
      x3 - x coordinate at t≈¾ (quality control, may be NaN).
      y3 - y coordinate at t≈¾ (quality control, may be NaN).
      x4 - x coordinate at t=1 (end point).
      y4 - y coordinate at t=1 (end point).
      dx4 - x component of the derivative α₄=∂y/∂x at ending point.
      dy4 - y component of the derivative α₄=∂y/∂x at ending point.
      Returns:
      true if the curve has been added to the path, or false if the approximation is not sufficient.
    • isNear

      private boolean isNear(double x, double y, double t, double ax, double ay, double am, double bx, double by, double bm, double x4, double y4, double cm, double xp, double yp)
      Returns true if the point specified by the (xp, yp) coordinates is close to the Bézier curve specified by the given control points. All given control points shall be shifted as if (x₀,y₀) coordinates are (0,0). If this method cannot determine for sure that the given point is close, it conservatively returns false. This is okay since failure to determine whether the point is close may mean that the curvature is strong, in which case we should probably split the curves in two smaller curves again.
      Parameters:
      ax - the x coordinate of first control point.
      ay - the y coordinate of first control point.
      bx - the x coordinate of mid-point.
      by - the y coordinate of mid-point.
      x4 - the x coordinate of last control point.
      y4 - the y coordinate of last control point.
      xp - the x coordinate of the point to test for proximity.
      yp - the y coordinate of the point to test for proximity.
      x - the x coordinate of a close point on the curve.
      y - the y coordinate of a close point on the curve.
      t - the t parameter of Bézier curve where (x,y), and m are evaluated.
      am - the 3(1−t)² multiplication factor of ax and ay coordinates for given t value.
      bm - the 6t(1−t) multiplication factor of bx and by coordinates for given t value.
      cm - the 3t² multiplication factor of x4 and y4 coordinates for given t value.
      Returns:
      true if the given point is close to the Bézier curve, or false otherwise or in case of doubt.
      See Also: