edu.neu.ccs.gui
Class AlgebraicArea

java.lang.Object
  edu.neu.ccs.gui.AlgebraicArea

public class AlgebraicArea

extends Object

Class AlgebraicArea provides static methods to compute the signed area of a Java Shape and of a JPT PathList object.

The area computation is based on calculus. Since any Shape or PathList is built by a combination of 5 commands (move, line, quad, cubic, and close), the calculus may be done in advance and the area reduced to algebraic formulas in the x,y coordinates of the path data. The resulting formulas for lines, quads, and cubics are instantiated in static helper methods.

Limitations of computing signed area via calculus.

If a path is a simple path (one segment) and has no self intersections, then the area will be numerically valid.

If the path has multiple segments or self intersections, then portions of the area may be added in multiple times or may cancel out if the orientations of different portions of the path are opposite. For example, a perfectly symmetrical figure-8 will have zero area. A path that goes over the same geometric point sequence multiple times will add up the area multiple times. Therefore, the tools in this class must be used with care.

The Sign of the Area

The interpretation of the sign of the area depends on the point of view adopted.

Mathematics View: In mathematics, the x-axis increases to the right, the y-axis increases upwards, and the origin is usually in the lower left. In this view, a simple path has positive area if it is oriented clockwise and negative area if it is oriented counter-clockwise.

Computer Graphics View: In computer graphics, the origin is always at the upper left of the entity in question (screen or window), the x-axis increases to the right, and the y-axis increases downwards. In effect, this is a mirror reflection of the Mathematics View, with the mirror being a horizontal axis. The effect of mirror reflection is to interchange clockwise and counter-clockwise. Thus, in the computer graphics view, a simple path has positive area if it is oriented counter-clockwise and negative area if it is oriented clockwise.

Classic Java shapes such as rectangles and ellipses are created as shapes in a clockwise fashion relative to the computer graphics view. Thus, the area functions in this class will return a negative signed area for the classic shapes.

To sidestep the issue of sign, we provide the absolute area functions absArea which return the absolute value of the signed area.

Notes on Numerical Accuracy

Java stores path data in the GeneralPath class in float format. This is an unfortunate artifact of the time period when Java was designed. To obtain the path data for an arbitrary Shape, one must go through the GeneralPath class, and hence the precision of the data is inherently float.

The JPT class PathList provides an accessible data structure for a path as a list of PathNode objects plus a winding rule. To allow one to go back and forth between a Shape and a PathList without changes of precision, we made the decision in JPT to store data in a PathNode object in float format. This was a reluctant decision.

In any case, the available path data for area computation is in float format so no greater precision is possible. Nevertheless, to reduce round-off error, the internal calculations of area are done in double precision. That is why the helper methods return type double.

Notes on Circles and Ellipses

Circles and ellipses are approximated in Java by 4 cubic Bezier segments. This approximation does NOT preserve area. Hence, if the area of a circle of radius 1 is computed by the methods of this class, the result will be close to but not equal to the correct value, pi. Therefore, if you require a more accurate area for circles and ellipses, use the traditional mathematical formulas.

The advantage of the tools in this class is that they give accurate signed area to floating point precision based on the actual path representation of a shape as lines, quads, and cubics.

Since:

2.6.0

Version:

2.6.0a

Constructor Summary

private

AlgebraicArea() Prevent instantiation.

Method Summary

static float	absArea(PathList path) Returns the absolute value of area(path).
static float	absArea(Shape shape) Returns the absolute value of area(shape).
static float	area(PathList path) Returns the signed area enclosed by the given path following calculus conventions for its computation.
static float	area(Shape shape) Returns the signed area enclosed by the given shape following calculus conventions for its computation.
static double	area1(double x0, double y0, double x1, double y1) Returns the signed area of the trapezoid bounded by the line from (x0,y0) to (x1,y1), the x-axis, and vertical lines dropped from the endpoints of the line to the x-axis.
static double	area2(double x0, double y0, double x1, double y1, double x2, double y2) Returns the signed area of the generalized trapezoid bounded by the quadratic Bezier curve with control points (x0,y0), (x1,y1), (x2,y2), the x-axis, and vertical lines dropped from the endpoints of the curve to the x-axis.
static double	area3(double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3) Returns the signed area of the generalized trapezoid bounded by the cubic Bezier curve with control points (x0,y0), (x1,y1), (x2,y2), (x3,y3), the x-axis, and vertical lines dropped from the endpoints of the curve to the x-axis.

Methods inherited from class java.lang.Object

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

Constructor Detail

AlgebraicArea

private AlgebraicArea()

Prevent instantiation.

Method Detail

area1

public static double area1(double x0,
                           double y0,
                           double x1,
                           double y1)

Returns the signed area of the trapezoid bounded by the line from (x0,y0) to (x1,y1), the x-axis, and vertical lines dropped from the endpoints of the line to the x-axis.

The formula computed is:

    (x1 - x0) * (y0 + y1) / 2

area2

public static double area2(double x0,
                           double y0,
                           double x1,
                           double y1,
                           double x2,
                           double y2)

Returns the signed area of the generalized trapezoid bounded by the quadratic Bezier curve with control points (x0,y0), (x1,y1), (x2,y2), the x-axis, and vertical lines dropped from the endpoints of the curve to the x-axis.

The formula computed is:

    ((x1 - x0) * (3 * y0 + 2 * y1 + y2) +
     (x2 - x1) * (y0 + 2 * y1 + 3 * y2)) / 6

area3

public static double area3(double x0,
                           double y0,
                           double x1,
                           double y1,
                           double x2,
                           double y2,
                           double x3,
                           double y3)

Returns the signed area of the generalized trapezoid bounded by the cubic Bezier curve with control points (x0,y0), (x1,y1), (x2,y2), (x3,y3), the x-axis, and vertical lines dropped from the endpoints of the curve to the x-axis.

The formula computed is:

    ((x1 - x0) * (10 * y0 + 6 * y1 + 3 * y2 + y3) +
     (x2 - x1) * (4 * y0 + 6 * y1 + 6 * y2 + 4 * y3) +
     (x3 - x2) * (y0 + 3 * y1 + 6 * y2 + 10 * y3)) / 20

area

public static float area(PathList path)

Returns the signed area enclosed by the given path following calculus conventions for its computation.

Returns zero if the given path is null or empty.

As of 2.6.0a, parallels the changes to the class PathList to attempt the area computation even if the path list does not start with a move. Skips all initial nodes that are close nodes. Then uses the endpoint of the first non-close node to seed the initial position for the area computation. After that, the computation proceeds using the path data as it would if the path list were valid.

Parameters:

path - the path whose area is to be computed

area

public static float area(Shape shape)

Returns the signed area enclosed by the given shape following calculus conventions for its computation.

Returns zero if the given shape is null.

Parameters:

shape - the shape whose area is to be computed

absArea

public static float absArea(PathList path)

Returns the absolute value of area(path).

Parameters:

path - the path whose area is to be computed

absArea

public static float absArea(Shape shape)

Returns the absolute value of area(shape).

Parameters:

shape - the shape whose area is to be computed