org.jhotdraw.geom
Class Bezier

java.lang.Object
  extended by org.jhotdraw.geom.Bezier

public class Bezier
extends java.lang.Object

Provides algorithms for fitting Bezier curves to a set of digitized points.

Source:
Phoenix: An Interactive Curve Design System Based on the Automatic Fitting of Hand-Sketched Curves.
© Copyright by Philip J. Schneider 1988.
A thesis submitted in partial fulfillment of the requirements for the degree of Master of Science, University of Washington.

http://autotrace.sourceforge.net/Interactive_Curve_Design.ps.gz

Version:
$Id: Bezier.java 717 2010-11-21 12:30:57Z rawcoder $
Author:
Werner Randelshofer

Constructor Summary
private Bezier()
          Prevent instance creation.
 
Method Summary
private static void addCurveTo(java.awt.geom.Point2D.Double[] bezCurve, BezierPath bezierPath, double errorSquared, boolean connectsCorners)
          Adds the curve to the bezier path.
private static double b0(double u)
          B0, B1, B2, B3 : Bezier multipliers
private static double b1(double u)
           
private static double b2(double u)
           
private static double b3(double u)
           
private static java.awt.geom.Point2D.Double bezierII(int degree, java.awt.geom.Point2D.Double[] V, double t)
          Evaluate a Bezier curve at a particular parameter value.
private static double[] chordLengthParameterize(java.util.ArrayList<java.awt.geom.Point2D.Double> d, int first, int last)
          Assign parameter values to digitized points using relative distances between points.
private static java.awt.geom.Point2D.Double computeCenterTangent(java.util.ArrayList<java.awt.geom.Point2D.Double> d, int center)
          Approximate unit tangents at "center" of digitized curve.
private static java.awt.geom.Point2D.Double computeLeftTangent(java.util.ArrayList<java.awt.geom.Point2D.Double> d, int end)
          Approximate unit tangents at "left" endpoint of digitized curve.
private static double computeMaxError(java.util.ArrayList<java.awt.geom.Point2D.Double> d, int first, int last, java.awt.geom.Point2D.Double[] bezCurve, double[] u, int[] splitPoint)
          Find the maximum squared distance of digitized points to fitted curve.
private static java.awt.geom.Point2D.Double computeRightTangent(java.util.ArrayList<java.awt.geom.Point2D.Double> d, int end)
          Approximate unit tangents at "right" endpoint of digitized curve.
static java.util.ArrayList<java.lang.Integer> findCorners(java.util.List<java.awt.geom.Point2D.Double> digitizedPoints, double minAngle, double minDistance)
          Finds corners in the provided point list, and returns their indices.
static BezierPath fitBezierPath(BezierPath digitizedPoints, double error)
          Fits a bezier path to the specified list of digitized points.
static BezierPath fitBezierPath(java.util.List<java.awt.geom.Point2D.Double> digitizedPoints, double error)
          Fits a bezier path to the specified list of digitized points.
static BezierPath fitBezierPath(java.awt.geom.Point2D.Double[] digitizedPoints, double error)
          Fits a bezier path to the specified list of digitized points.
private static void fitCubic(java.util.ArrayList<java.awt.geom.Point2D.Double> d, int first, int last, java.awt.geom.Point2D.Double tHat1, java.awt.geom.Point2D.Double tHat2, double errorSquared, BezierPath bezierPath)
          Fit one or multiple subsequent cubic bezier curves to a (sub)set of digitized points.
private static java.awt.geom.Point2D.Double[] generateBezier(java.util.ArrayList<java.awt.geom.Point2D.Double> d, int first, int last, double[] uPrime, java.awt.geom.Point2D.Double tHat1, java.awt.geom.Point2D.Double tHat2)
          Use least-squares method to find Bezier control points for region.
static void main(java.lang.String[] args)
           
private static double newtonRaphsonRootFind(java.awt.geom.Point2D.Double[] Q, java.awt.geom.Point2D.Double P, double u)
          Use Newton-Raphson iteration to find better root.
static java.util.ArrayList<java.awt.geom.Point2D.Double> reduceNoise(java.util.List<java.awt.geom.Point2D.Double> digitizedPoints, double weight)
          Reduces noise from the digitized points, by applying an approximation of a gaussian filter to the data.
static java.util.ArrayList<java.awt.geom.Point2D.Double> removeClosePoints(java.util.List<java.awt.geom.Point2D.Double> digitizedPoints, double minDistance)
          Removes points which are closer together than the specified minimal distance.
private static java.util.ArrayList<java.awt.geom.Point2D.Double> removeCoincidentPoints(java.util.List<java.awt.geom.Point2D.Double> digitizedPoints)
          Removes sequences of coincident points.
private static double[] reparameterize(java.util.ArrayList<java.awt.geom.Point2D.Double> d, int first, int last, double[] u, java.awt.geom.Point2D.Double[] bezCurve)
          Given set of points and their parameterization, try to find a better parameterization.
static java.util.ArrayList<java.util.ArrayList<java.awt.geom.Point2D.Double>> splitAtCorners(java.util.List<java.awt.geom.Point2D.Double> digitizedPoints, double maxAngle, double minDistance)
          Splits the digitized points into multiple segments at each corner point.
private static java.awt.geom.Point2D.Double v2Add(java.awt.geom.Point2D.Double a, java.awt.geom.Point2D.Double b, java.awt.geom.Point2D.Double c)
          Return vector sum c = a+b.
private static java.awt.geom.Point2D.Double v2AddII(java.awt.geom.Point2D.Double a, java.awt.geom.Point2D.Double b)
          Return vector sum = a+b.
private static double v2DistanceBetween2Points(java.awt.geom.Point2D.Double a, java.awt.geom.Point2D.Double b)
          Return the distance between two points
private static double v2Dot(java.awt.geom.Point2D.Double a, java.awt.geom.Point2D.Double b)
          Return the dot product of vectors a and b.
private static double v2Length(java.awt.geom.Point2D.Double a)
          Returns length of input vector.
private static java.awt.geom.Point2D.Double v2Negate(java.awt.geom.Point2D.Double v)
          Negates the input vector and returns it.
private static java.awt.geom.Point2D.Double v2Normalize(java.awt.geom.Point2D.Double v)
          Normalizes the input vector and returns it.
private static java.awt.geom.Point2D.Double v2Scale(java.awt.geom.Point2D.Double v, double newlen)
          Scales the input vector to the new length and returns it.
private static java.awt.geom.Point2D.Double v2ScaleIII(java.awt.geom.Point2D.Double v, double s)
          Scales the input vector by the specified factor and returns it.
private static double v2SquaredDistanceBetween2Points(java.awt.geom.Point2D.Double a, java.awt.geom.Point2D.Double b)
          Return the distance between two points
private static double v2SquaredLength(java.awt.geom.Point2D.Double a)
          Returns squared length of input vector.
private static java.awt.geom.Point2D.Double v2SubII(java.awt.geom.Point2D.Double a, java.awt.geom.Point2D.Double b)
          Subtract Vector a from Vector b.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

Bezier

private Bezier()
Prevent instance creation.

Method Detail

main

public static void main(java.lang.String[] args)

fitBezierPath

public static BezierPath fitBezierPath(java.awt.geom.Point2D.Double[] digitizedPoints,
                                       double error)
Fits a bezier path to the specified list of digitized points.

This is a convenience method for calling fitCubicSegments(List, double);

Parameters:
digitizedPoints - digited points.
error - the maximal allowed error between the bezier path and the digitized points.

fitBezierPath

public static BezierPath fitBezierPath(java.util.List<java.awt.geom.Point2D.Double> digitizedPoints,
                                       double error)
Fits a bezier path to the specified list of digitized points.

Parameters:
digitizedPoints - digited points.
error - the maximal allowed error between the bezier path and the digitized points.

fitBezierPath

public static BezierPath fitBezierPath(BezierPath digitizedPoints,
                                       double error)
Fits a bezier path to the specified list of digitized points.

This is a convenience method for calling fitCubicSegments(List, double);

Parameters:
digitizedPoints - digited points.
error - the maximal allowed error between the bezier path and the digitized points.

removeClosePoints

public static java.util.ArrayList<java.awt.geom.Point2D.Double> removeClosePoints(java.util.List<java.awt.geom.Point2D.Double> digitizedPoints,
                                                                                  double minDistance)
Removes points which are closer together than the specified minimal distance.

The minimal distance should be chosen dependent on the size and resolution of the display device, and on the sampling rate. A good value for mouse input on a display with 100% Zoom factor is 2.

The purpose of this method, is to remove points, which add no additional information about the shape of the curve from the list of digitized points.

The cleaned up set of digitized points gives better results, when used as input for method splitAtCorners(java.util.List, double, double).

Parameters:
digitizedPoints - Digitized points
minDistance - minimal distance between two points. If minDistance is 0, this method only removes sequences of coincident points.
Returns:
Digitized points with a minimal distance.

removeCoincidentPoints

private static java.util.ArrayList<java.awt.geom.Point2D.Double> removeCoincidentPoints(java.util.List<java.awt.geom.Point2D.Double> digitizedPoints)
Removes sequences of coincident points.

The purpose of this method, is to clean up a list of digitized points for later processing using method splitAtCorners(java.util.List, double, double).

Use this method only, if you know that the digitized points contain no quantization errors - which is never the case, unless you want to debug the curve fitting algorithm of this class.

Parameters:
digitizedPoints - Digitized points
Returns:
Digitized points without subsequent duplicates.

splitAtCorners

public static java.util.ArrayList<java.util.ArrayList<java.awt.geom.Point2D.Double>> splitAtCorners(java.util.List<java.awt.geom.Point2D.Double> digitizedPoints,
                                                                                                    double maxAngle,
                                                                                                    double minDistance)
Splits the digitized points into multiple segments at each corner point.

Corner points are both contained as the last point of a segment and the first point of a subsequent segment.

Parameters:
digitizedPoints - Digitized points
maxAngle - maximal angle in radians between the current point and its predecessor and successor up to which the point does not break the digitized list into segments. Recommended value 44° = 44 * 180d / Math.PI
Returns:
Segments of digitized points, each segment having less than maximal angle between points.

findCorners

public static java.util.ArrayList<java.lang.Integer> findCorners(java.util.List<java.awt.geom.Point2D.Double> digitizedPoints,
                                                                 double minAngle,
                                                                 double minDistance)
Finds corners in the provided point list, and returns their indices.

Parameters:
digitizedPoints - List of digitized points.
minAngle - Minimal angle for corner points
minDistance - Minimal distance between a point and adjacent points for corner detection
Returns:
list of corner indices.

reduceNoise

public static java.util.ArrayList<java.awt.geom.Point2D.Double> reduceNoise(java.util.List<java.awt.geom.Point2D.Double> digitizedPoints,
                                                                            double weight)
Reduces noise from the digitized points, by applying an approximation of a gaussian filter to the data.

The filter does the following for each point P, with weight 0.5:

x[i] = 0.5*x[i] + 0.25*x[i-1] + 0.25*x[i+1]; y[i] = 0.5*y[i] + 0.25*y[i-1] + 0.25*y[i+1];

Parameters:
digitizedPoints - Digitized points
weight - Weight of the current point
Returns:
Digitized points with reduced noise.

fitCubic

private static void fitCubic(java.util.ArrayList<java.awt.geom.Point2D.Double> d,
                             int first,
                             int last,
                             java.awt.geom.Point2D.Double tHat1,
                             java.awt.geom.Point2D.Double tHat2,
                             double errorSquared,
                             BezierPath bezierPath)
Fit one or multiple subsequent cubic bezier curves to a (sub)set of digitized points. The digitized points represent a smooth curve without corners.

Parameters:
d - Array of digitized points. Must not contain subsequent coincident points.
first - Indice of first point in d.
last - Indice of last point in d.
tHat1 - Unit tangent vectors at start point.
tHat2 - Unit tanget vector at end point.
errorSquared - User-defined errorSquared squared.
bezierPath - Path to which the bezier curve segments are added.

addCurveTo

private static void addCurveTo(java.awt.geom.Point2D.Double[] bezCurve,
                               BezierPath bezierPath,
                               double errorSquared,
                               boolean connectsCorners)
Adds the curve to the bezier path.

Parameters:
bezCurve -
bezierPath -

computeLeftTangent

private static java.awt.geom.Point2D.Double computeLeftTangent(java.util.ArrayList<java.awt.geom.Point2D.Double> d,
                                                               int end)
Approximate unit tangents at "left" endpoint of digitized curve.

Parameters:
d - Digitized points.
end - Index to "left" end of region.

computeRightTangent

private static java.awt.geom.Point2D.Double computeRightTangent(java.util.ArrayList<java.awt.geom.Point2D.Double> d,
                                                                int end)
Approximate unit tangents at "right" endpoint of digitized curve.

Parameters:
d - Digitized points.
end - Index to "right" end of region.

computeCenterTangent

private static java.awt.geom.Point2D.Double computeCenterTangent(java.util.ArrayList<java.awt.geom.Point2D.Double> d,
                                                                 int center)
Approximate unit tangents at "center" of digitized curve.

Parameters:
d - Digitized points.
center - Index to "center" end of region.

chordLengthParameterize

private static double[] chordLengthParameterize(java.util.ArrayList<java.awt.geom.Point2D.Double> d,
                                                int first,
                                                int last)
Assign parameter values to digitized points using relative distances between points.

Parameters:
d - Digitized points.
first - Indice of first point of region in d.
last - Indice of last point of region in d.

reparameterize

private static double[] reparameterize(java.util.ArrayList<java.awt.geom.Point2D.Double> d,
                                       int first,
                                       int last,
                                       double[] u,
                                       java.awt.geom.Point2D.Double[] bezCurve)
Given set of points and their parameterization, try to find a better parameterization.

Parameters:
d - Array of digitized points.
first - Indice of first point of region in d.
last - Indice of last point of region in d.
u - Current parameter values.
bezCurve - Current fitted curve.

newtonRaphsonRootFind

private static double newtonRaphsonRootFind(java.awt.geom.Point2D.Double[] Q,
                                            java.awt.geom.Point2D.Double P,
                                            double u)
Use Newton-Raphson iteration to find better root.

Parameters:
Q - Current fitted bezier curve.
P - Digitized point.
u - Parameter value vor P.

computeMaxError

private static double computeMaxError(java.util.ArrayList<java.awt.geom.Point2D.Double> d,
                                      int first,
                                      int last,
                                      java.awt.geom.Point2D.Double[] bezCurve,
                                      double[] u,
                                      int[] splitPoint)
Find the maximum squared distance of digitized points to fitted curve.

Parameters:
d - Digitized points.
first - Indice of first point of region in d.
last - Indice of last point of region in d.
bezCurve - Fitted Bezier curve
u - Parameterization of points*
splitPoint - Point of maximum error (input/output parameter, must be an array of 1)

generateBezier

private static java.awt.geom.Point2D.Double[] generateBezier(java.util.ArrayList<java.awt.geom.Point2D.Double> d,
                                                             int first,
                                                             int last,
                                                             double[] uPrime,
                                                             java.awt.geom.Point2D.Double tHat1,
                                                             java.awt.geom.Point2D.Double tHat2)
Use least-squares method to find Bezier control points for region.

Parameters:
d - Array of digitized points.
first - Indice of first point in d.
last - Indice of last point in d.
uPrime - Parameter values for region .
tHat1 - Unit tangent vectors at start point.
tHat2 - Unit tanget vector at end point.
Returns:
A cubic bezier curve consisting of 4 control points.

bezierII

private static java.awt.geom.Point2D.Double bezierII(int degree,
                                                     java.awt.geom.Point2D.Double[] V,
                                                     double t)
Evaluate a Bezier curve at a particular parameter value.

Parameters:
degree - The degree of the bezier curve.
V - Array of control points.
t - Parametric value to find point for.

v2DistanceBetween2Points

private static double v2DistanceBetween2Points(java.awt.geom.Point2D.Double a,
                                               java.awt.geom.Point2D.Double b)
Return the distance between two points


v2SquaredDistanceBetween2Points

private static double v2SquaredDistanceBetween2Points(java.awt.geom.Point2D.Double a,
                                                      java.awt.geom.Point2D.Double b)
Return the distance between two points


v2Scale

private static java.awt.geom.Point2D.Double v2Scale(java.awt.geom.Point2D.Double v,
                                                    double newlen)
Scales the input vector to the new length and returns it.

This method alters the value of the input point!


v2ScaleIII

private static java.awt.geom.Point2D.Double v2ScaleIII(java.awt.geom.Point2D.Double v,
                                                       double s)
Scales the input vector by the specified factor and returns it.

This method alters the value of the input point!


v2Length

private static double v2Length(java.awt.geom.Point2D.Double a)
Returns length of input vector.


v2SquaredLength

private static double v2SquaredLength(java.awt.geom.Point2D.Double a)
Returns squared length of input vector.


v2Add

private static java.awt.geom.Point2D.Double v2Add(java.awt.geom.Point2D.Double a,
                                                  java.awt.geom.Point2D.Double b,
                                                  java.awt.geom.Point2D.Double c)
Return vector sum c = a+b.

This method alters the value of c.


v2AddII

private static java.awt.geom.Point2D.Double v2AddII(java.awt.geom.Point2D.Double a,
                                                    java.awt.geom.Point2D.Double b)
Return vector sum = a+b.


v2Negate

private static java.awt.geom.Point2D.Double v2Negate(java.awt.geom.Point2D.Double v)
Negates the input vector and returns it.


v2Dot

private static double v2Dot(java.awt.geom.Point2D.Double a,
                            java.awt.geom.Point2D.Double b)
Return the dot product of vectors a and b.


v2Normalize

private static java.awt.geom.Point2D.Double v2Normalize(java.awt.geom.Point2D.Double v)
Normalizes the input vector and returns it.


v2SubII

private static java.awt.geom.Point2D.Double v2SubII(java.awt.geom.Point2D.Double a,
                                                    java.awt.geom.Point2D.Double b)
Subtract Vector a from Vector b.

Parameters:
a - Vector a - the value is not changed by this method
b - Vector b - the value is not changed by this method
Returns:
Vector a subtracted by Vector v.

b0

private static double b0(double u)
B0, B1, B2, B3 : Bezier multipliers


b1

private static double b1(double u)

b2

private static double b2(double u)

b3

private static double b3(double u)