com.tensegrity.graphics
Class UtilitiesLine

java.lang.Object
  com.tensegrity.graphics.UtilitiesLine

public class UtilitiesLine

extends java.lang.Object

The UtilitiesLine class provides the basic functionalities needed to work on lines.

The parametric representation of a line in 2D space looks like follows:
x=x(t)
y=y(t)

In most cases cubic polynomials are used, because lower-degree polynomials give too little flexibility in controlling the shape of a line, and higher- degree polynomials can introduce unwanted difficulties and require more computation time.

The cubic polynomials that define in 2D space a line segment
Q(t)=[x(t) y(t)]
are of the form
x(t)=axt^3 + bxt^2 + cxt + dx
y(t)=ayt^3 + byt^2 + cyt + dy
Where t is restricted to the interval [0, 1].

Defining a row vector
T=[t^3 t^2 t 1]
and a coefficient matrix

C=	[ax ay bx by cx cy dx dy]

The polynomials can be rewritten as
Q(t)=[x(t) y(t)]=T*C

The coefficient matrix C can be rewritten as
C=M*G
where M is a 4x4 matrix and G is a four element column vector of geometric constraints, called the geometry vector.
For the different types of cubic lines(hermite, bezier, catmull rom, b spline, ...) M and/or G may differ.

Now the polynomials can be rewritten as
Q(t)=[x(t) y(t)]=T*M*G
expanding this gives

Q(t)=[x(t) y(t)]=

[t^3 t^2 t 1]

[m11 m12 m13 m14 m21 m22 m23 m24 m31 m32 m33 m34 m41 m42 m43 m44]

[G1 G2 G3 G4]

To see now that the coefficients of the cubic polynomial can depend on four constraints, this definition is multiplied out just for
x(t)=T*M*Gx
Where Gx refers to the column vector of just the x components of the geometry vector.
x(t)=
(t^3*m11 + t^2*m21 + t*m31 + m41)g1x +
(t^3*m12 + t^2*m22 + t*m32 + m42)g2x +
(t^3*m13 + t^2*m23 + t*m33 + m43)g3x +
(t^3*m14 + t^2*m24 + t*m34 + m44)g4x

The Hermite form of the cubic polynomial line segment is determined by the endpoints P1 and P4 and tangent vectors at the endpoints R1 and R4.
The geometry vector is
Gh=
[P1
P4
R1
R2]
and the basis matrix is
Mh=
[ 2 -2 1 1
-3 3 -2 -1
0 0 1 0
1 0 0 0]

The B�zier form of the cubic polynomial line segment indirectly specifies the endpoint tangent vectors by specifing two intermediate points that are not on the line. The starting and ending tangent vectors are determined by the vectors P1 P2 and P3 P4 and are related to R1 and R4 of the Hermite form. The geometry vector is
Gb=
[P1
P2
P3
P4]
and the basis matrix is
Mh=
[-1 3 -3 1
3 -6 3 0
-3 3 0 0
1 0 0 0]

Because the Hermite form of the cubic polynomial line segments can always be represented by the B�zier form of the cubic polynomial line segments and have no benefit against the B�zier form they are not supported by this library.

For a further discussion on parametric cubic lines see the book 'Computer Graphics:Principles and Practice' from our library!

Version:

$Id: UtilitiesLine.java,v 1.22 2005/11/17 09:51:21 MichaelKegel Exp $

Author:

MichaelKegel

Field Summary

static int	BEZIER_GEOMETRY_VECTOR_P1 enumeration that tells about the indices in the bezier geometry vector
static int	BEZIER_GEOMETRY_VECTOR_P2 enumeration that tells about the indices in the bezier geometry vector
static int	BEZIER_GEOMETRY_VECTOR_P3 enumeration that tells about the indices in the bezier geometry vector
static int	BEZIER_GEOMETRY_VECTOR_P4 enumeration that tells about the indices in the bezier geometry vector
static Matrix44D	BEZIER_TRANSFORM the transformation matrix needed to calculate the bezier line path
static Matrix44D	BEZIER_TRANSFORM_INVERSE the inverse transformation matrix to the bezier transformation matrix
static int	CATMULL_ROM_GEOMETRY_VECTOR_P1 enumeration that tells about the indices in the catmull rom geometry vector
static int	CATMULL_ROM_GEOMETRY_VECTOR_P2 enumeration that tells about the indices in the catmull rom geometry vector
static int	CATMULL_ROM_GEOMETRY_VECTOR_P3 enumeration that tells about the indices in the catmull rom geometry vector
static int	CATMULL_ROM_GEOMETRY_VECTOR_P4 enumeration that tells about the indices in the catmull rom geometry vector
static Matrix44D	CATMULL_ROM_TRANSFORM the transformation matrix needed to calculate the catmull rom line path
static Matrix44D	CATMULL_ROM_TRANSFORM_INVERSE the inverse transformation matrix to the catmull rom transformation matrix
static int	CUBIC_BEZIER enumeration that tells about the different types of the cubic polynomial line segments
static int	CUBIC_BEZIER_SEGMENT enumeration that tells about the different styles a line segment can have
static int	CUBIC_CATMULL_ROM enumeration that tells about the different types of the cubic polynomial line segments
static int	CUBIC_CATMULL_ROM_SEGMENT enumeration that tells about the different styles a line segment can have
static int	LINEAR_SEGMENT enumeration that tells about the different styles a line segment can have
static int	UNDEFINED constant for any undefined state

Method Summary

static Boundary	computeBoundingBox(int[] coordsX, int[] coordsY, int[] coordsXRef, int[] coordsYRef, int[] segmentTypes) Computes the bounding box of a closed (polygon) or open (polyline) primitive.
static Coordinate	computeCoordinateOfSegment(double[] segment, double t)
static void	computeCoordinateOfSegment(double[] segment, double t, int[] result)
static int	createCubicSegments(double[] coordsX, double[] coordsY, ArrayListInt ptXSegments, ArrayListInt ptYSegments, int transformation, double weight) creates linear segments of the cubic line that is given by the coordsX and coordsY.
static double	getLineDirection(int x1, int y1, int x2, int y2) Calculates the counter clockwise angle between the line given by x1, y1, x2 and y2 and the x axis.
static boolean	hits(double x1, double y1, double x2, double y2, int x, int y, int weight) returns a flag that indicates whether the coordinate given by the components x and y hits the linear line segment between the two given line points by with the coordinates x1 and y1 and x2 and y2 or not.
static boolean	isLinearSegment(double[] geometryX, double[] geometryY, double epsilon) This method checks weather the amplitude of a bezier line segment is less than the given epsilon or not.
static void	subdivideBezier(ArrayListInt linePtX, ArrayListInt linePtY, double[] geometryX, double[] geometryY, double segmentStart, double segmentEnd, double weight, int index) This method devides a bezier line segment into a set of line segments, such that every generated segment is approximately a straight line.
static void	subdivideBezier(double[] geometryX, double[] geometryY, double[] geometryXFirst, double[] geometryYFirst, double[] geometryXSecond, double[] geometryYSecond) This method devides a bezier line segment at position t=0.5 into two parts.
static void	transformGeometryVector(double[] geometryXconverted, double[] geometryYconverted, int[] geometryX, int[] geometryY, int type, int typeConvertTo) This method converts the geometry vectors of one cubic line segment type, given by geometryX and geometryY, into the geometry vector of antoher type.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

UNDEFINED

public static final int UNDEFINED

constant for any undefined state

See Also:

Constant Field Values

LINEAR_SEGMENT

public static final int LINEAR_SEGMENT

enumeration that tells about the different styles a line segment can have

See Also:

Constant Field Values

CUBIC_BEZIER_SEGMENT

public static final int CUBIC_BEZIER_SEGMENT

enumeration that tells about the different styles a line segment can have

See Also:

Constant Field Values

CUBIC_CATMULL_ROM_SEGMENT

public static final int CUBIC_CATMULL_ROM_SEGMENT

enumeration that tells about the different styles a line segment can have

See Also:

Constant Field Values

CUBIC_BEZIER

public static final int CUBIC_BEZIER

enumeration that tells about the different types of the cubic polynomial line segments

See Also:

Constant Field Values

CUBIC_CATMULL_ROM

public static final int CUBIC_CATMULL_ROM

enumeration that tells about the different types of the cubic polynomial line segments

See Also:

Constant Field Values

BEZIER_GEOMETRY_VECTOR_P1

public static final int BEZIER_GEOMETRY_VECTOR_P1

enumeration that tells about the indices in the bezier geometry vector

See Also:

Constant Field Values

BEZIER_GEOMETRY_VECTOR_P2

public static final int BEZIER_GEOMETRY_VECTOR_P2

enumeration that tells about the indices in the bezier geometry vector

See Also:

Constant Field Values

BEZIER_GEOMETRY_VECTOR_P3

public static final int BEZIER_GEOMETRY_VECTOR_P3

enumeration that tells about the indices in the bezier geometry vector

See Also:

Constant Field Values

BEZIER_GEOMETRY_VECTOR_P4

public static final int BEZIER_GEOMETRY_VECTOR_P4

enumeration that tells about the indices in the bezier geometry vector

See Also:

Constant Field Values

CATMULL_ROM_GEOMETRY_VECTOR_P1

public static final int CATMULL_ROM_GEOMETRY_VECTOR_P1

enumeration that tells about the indices in the catmull rom geometry vector

See Also:

Constant Field Values

CATMULL_ROM_GEOMETRY_VECTOR_P2

public static final int CATMULL_ROM_GEOMETRY_VECTOR_P2

enumeration that tells about the indices in the catmull rom geometry vector

See Also:

Constant Field Values

CATMULL_ROM_GEOMETRY_VECTOR_P3

public static final int CATMULL_ROM_GEOMETRY_VECTOR_P3

enumeration that tells about the indices in the catmull rom geometry vector

See Also:

Constant Field Values

CATMULL_ROM_GEOMETRY_VECTOR_P4

public static final int CATMULL_ROM_GEOMETRY_VECTOR_P4

enumeration that tells about the indices in the catmull rom geometry vector

See Also:

Constant Field Values

BEZIER_TRANSFORM

public static final Matrix44D BEZIER_TRANSFORM

the transformation matrix needed to calculate the bezier line path

BEZIER_TRANSFORM_INVERSE

public static final Matrix44D BEZIER_TRANSFORM_INVERSE

the inverse transformation matrix to the bezier transformation matrix

CATMULL_ROM_TRANSFORM

public static final Matrix44D CATMULL_ROM_TRANSFORM

the transformation matrix needed to calculate the catmull rom line path

CATMULL_ROM_TRANSFORM_INVERSE

public static final Matrix44D CATMULL_ROM_TRANSFORM_INVERSE

the inverse transformation matrix to the catmull rom transformation matrix

Method Detail

getLineDirection

public static final double getLineDirection(int x1,
                                            int y1,
                                            int x2,
                                            int y2)

Calculates the counter clockwise angle between the line given by x1, y1, x2 and y2 and the x axis. The returned angle is given in degree. The starting point of the line must not lie at the origin.

Parameters:

x1 - the x component of the lines starting point

y1 - the y component of the lines starting point

x2 - the x component of the lines ending point

y2 - the y component of the lines ending point

Returns:

double the counter clockwise angle between the given line and the x axis.

hits

public static final boolean hits(double x1,
                                 double y1,
                                 double x2,
                                 double y2,
                                 int x,
                                 int y,
                                 int weight)

returns a flag that indicates whether the coordinate given by the components x and y hits the linear line segment between the two given line points by with the coordinates x1 and y1 and x2 and y2 or not.

Parameters:

x1 - the x coordinate of the first line point

y1 - the y coordinate of the first line point

x2 - the x coordinate of the second line point

y2 - the y coordinate of the second line point

x - the x coordinate of the point to check for

y - the y coordinate of the point to check for

weight - the weight of the line

Returns:

boolean flag that indicates whether the segment is hit or not

transformGeometryVector

public static void transformGeometryVector(double[] geometryXconverted,
                                           double[] geometryYconverted,
                                           int[] geometryX,
                                           int[] geometryY,
                                           int type,
                                           int typeConvertTo)

This method converts the geometry vectors of one cubic line segment type, given by geometryX and geometryY, into the geometry vector of antoher type. The converted geometry vectors are returned through geometryXconverted and geometryYconverted.

Parameters:

geometryXconverted - x components of the converted geometry vector

geometryYconverted - y components of the converted geometry vector

geometryX - x components of the geometry vector to convert

geometryY - y components of the geometry vector to convert

type - of the geometry vectors to convert

typeConvertTo - the type of geometry vectors to convert to

subdivideBezier

public static final void subdivideBezier(ArrayListInt linePtX,
                                         ArrayListInt linePtY,
                                         double[] geometryX,
                                         double[] geometryY,
                                         double segmentStart,
                                         double segmentEnd,
                                         double weight,
                                         int index)

This method devides a bezier line segment into a set of line segments, such that every generated segment is approximately a straight line.
The given vectors geometryX and geometryY are the geometry vector for a bezier line segment.
The resulting line segments are returned through the given lists linePtX and linePtY.

Parameters:

linePtX - the x components of the generated segments

linePtY - the y components of the generated segments

geometryX - the x components of the line to devide

geometryY - the y components of the line to devide

segmentStart - the starting delta of the given line segment

segmentEnd - the ending delta of the given line segment

subdivideBezier

public static final void subdivideBezier(double[] geometryX,
                                         double[] geometryY,
                                         double[] geometryXFirst,
                                         double[] geometryYFirst,
                                         double[] geometryXSecond,
                                         double[] geometryYSecond)

This method devides a bezier line segment at position t=0.5 into two parts.
The given vectors geometryX and geometryY are the geometry vector for a bezier line segment. The resulting bezier line segments are returned through the given vectors geometryXFirst and geometryYFirst for the left segment and geometryXSecond and geometryYSecond for the right segment. They are also geometry vectors.

Parameters:

geometryX - x components of the bezier geometry vector

geometryY - y components of the bezier geometry vector

geometryXFirst - x components of the first bezier geometry vector

geometryYFirst - y components of the first bezier geometry vector

geometryXSecond - x components of the second bezier geometry vector

geometryYSecond - y components of the second bezier geometry vector

isLinearSegment

public static final boolean isLinearSegment(double[] geometryX,
                                            double[] geometryY,
                                            double epsilon)

This method checks weather the amplitude of a bezier line segment is less than the given epsilon or not. The given vectors geometryX and geometryY are the geometry vector for a bezier line segment.

Parameters:

geometryX - x components of the bezier geometry vector

geometryY - y components of the bezier geometry vector

Returns:

boolean a flag indicating that the amplitude of the given line segment is lass than the given epsilon range

createCubicSegments

public static final int createCubicSegments(double[] coordsX,
                                            double[] coordsY,
                                            ArrayListInt ptXSegments,
                                            ArrayListInt ptYSegments,
                                            int transformation,
                                            double weight)

creates linear segments of the cubic line that is given by the coordsX and coordsY. The x components of the linear segment coordinates are stored in ptXSegment and the y components are stored in ptYSegment. The transformation type of the cubic line is given by transformation.

Parameters:

coordsX - the x components of the line coordinates

coordsY - the y components of the line coordinates

ptXSegments - the calculated x components of the linear segments

ptYSegments - the calculated y components of the linear segments

transformation - the transformation type of the cubic line

weight - the weight of the cubic line

Returns:

int the amount of linear line segments that has been calculated

See Also:

CUBIC_BEZIER, CUBIC_CATMULL_ROM

computeCoordinateOfSegment

public static final Coordinate computeCoordinateOfSegment(double[] segment,
                                                          double t)

computeCoordinateOfSegment

public static final void computeCoordinateOfSegment(double[] segment,
                                                    double t,
                                                    int[] result)

computeBoundingBox

public static Boundary computeBoundingBox(int[] coordsX,
                                          int[] coordsY,
                                          int[] coordsXRef,
                                          int[] coordsYRef,
                                          int[] segmentTypes)

Computes the bounding box of a closed (polygon) or open (polyline) primitive.

Parameters:

coordsX - The x coordinates of the shape

coordsY - The y coordinates of the shape

coordsXRef - The reference x coordinates of the shape

coordsYRef - The reference y coordinates of the shape

segmentTypes - The segment types of the shape

Returns:

The bounding box of the shape