Shapes: An Introduction

I try to sprinkle in some fun open-source code snippets in most of my articles -- but this article is different. This article is simply an overview of the java.awt.Shape object. Several other articles build on (or assume knowledge of) what I cover here.

What is a java.awt.Shape?

When I refer to a "shape" in Java, I'm probably referring to the java.awt.Shape interface. The most interesting method in this class is getPathIterator(AffineTransform) -- the results of all the other methods can be derived from this method.

OK, so what is a java.awt.geom.PathIterator?

This is the heart of shape information in Java. This iterator is similar to the human gesture of dragging a pen from one point in space to another. A path is a series of segments, and there are 5 basic types of segments:

1. SEG_MOVETO: this is the initial position of a path. Each path must begin with this segment. If a MOVETO segment is not followed by any other segments, though: that path is considered empty. You might get a dot if you called Graphics2D.draw(shape), but you won't get anything if you call Graphics2D.fill(shape).
   
2. SEG_LINETO: this segment requires an x-coordinate and a y-coordinate. This connects a line from the last path location to the point indicated.
   
3. SEG_QUADTO: this segment requires two points: the end point and a control point (more on control points later.)
   
4. SEG_CUBICTO: this segment requires three points: two control points and an end point.
   
5. SEG_CLOSE: this is an optional segment that connects the previous segment to the SEG_MOVETO that began this shape. Even if you draw 4 sides of a square, you need to add a SEG_CLOSE for some java.awt.Strokes to correctly render the tips of all corners.

A single PathIterator can contain any number of MOVETO's. Each MOVETO is equivalent to lifting your pen off a piece of paper and repositioning it to start a new segment.

Bezier Control Points

Quadratic and cubic segments use control points. These are ingenious points that are used to tug an existing path in certain directions. There's a great wikipedia page that describes this concept in detail (with diagrams and everything). What I want to do is focus on the math. I'll break this up into the quadratic and the cubic cases:

Quadratic Parametric Equations

The javadocs are the place to start when you want to study the math here. They describe a quadratic segment as:

P(t) = B(2,0)*CP + B(2,1)*P1 + B(2,2)*P2
       0 <= t <= 1

B(n,m) = mth coefficient of nth degree Bernstein polynomial
       = C(n,m) * t^(m) * (1 - t)^(n-m)
C(n,m) = Combinations of n things, taken m at a time
       = n! / (m! * (n-m)!)

This sounds a lot more complex than it actually is if you're willing to break it down. We can get rid of C(n,m):

B(n,m) = mth coefficient of nth degree Bernstein polynomial
       = [ ( n! / (m! * (n-m)!) ) * t^(m) * (1 - t)^(n-m) ]

And then expand the first equation:

P(t) = [ ( 2! / (0! * (2-0)!) ) * t^(0) * (1 - t)^(2-0) ]* CP +
       [ ( 2! / (1! * (2-1)!) ) * t^(1) * (1 - t)^(2-1) ] * P1 +
       [ ( 2! / (2! * (2-2)!) ) * t^(2) * (1 - t)^(2-2) ] * P2

Simplify everything:

P(t) = (1 - 2*t + t^2) * CP +
       [ (2*t - 2*t^2) ] * P1 +
       [ t^(2) ] * P2

This is still not really useful to me, though. What I want is an expression in terms of t:

P(t) = (CP-2*P1+P2)*(t^2) +
       (-2*CP+2*P1)*t +
       CP

In my code this usually manifests itself something like this:

double ax = lastX-2*x1+x2;
double bx = -2*lastX+2*x1;
double cx = lastX;

Likewise you can replace "x" with "y" to get the y coefficients. From here you can treat your bezier segment as a good ole parametric equation. You can always spot-check your math (in both the quadratic and cubic case below) by checking the values at t=0 and t=1. At t=0 you get lastX -- which is the right starting point -- and at t=1 you simply add all those terms together -- and the terms cancel to x2.

I hardly ever use quadratic segments, though. If the user needs more than lines, the cubic segment gives you a lot more flexibility...

Cubic Parametric Equations

Again, we'll start by looking at the javadocs for a cubic curve:

P(t) = B(3,0)*CP + B(3,1)*P1 + B(3,2)*P2 + B(3,3)*P3
0 <= t <= 1

B(n,m) = mth coefficient of nth degree Bernstein polynomial
       = C(n,m) * t^(m) * (1 - t)^(n-m)
C(n,m) = Combinations of n things, taken m at a time
       = n! / (m! * (n-m)!)

Expand that:

P(t) = [ 3! / (0! * (3-0)!) * t^(0) * (1 - t)^(3-0) ] * CP +
       [ 3! / (1! * (3-1)!) * t^(1) * (1 - t)^(3-1) ] * P1 +
       [ 3! / (2! * (3-2)!) * t^(2) * (1 - t)^(3-2) ] * P2 +
       [ 3! / (3! * (3-3)!) * t^(3) * (1 - t)^(3-3) ] * P3 

Now simplify:

P(t) = [ (1 - t)^3 ] * CP +
       [ 3 * t^(1) * (1 - t)^2 ] * P1 +
       [ 3 * t^(2) * (1 - t)^1 ] * P2 +
       [ t^(3) ] * P3 

Expand the exponents:

P(t) = [ (1 - 3*t + 3*t^2 - t^3) ] * CP +
       [ (3*t - 6*t^2 + 3*t^3) ] * P1 +
       [ (3*t^2 - 3*t^3)^1 ] * P2 +
       [ t^(3) ] * P3 

But what we really want is the equation in terms of t:
Lastly:

P(t) = [-CP+3*P1-3*P2+P3]*(t^3) + 
       [3*CP-6*P1+3*P2]*(t^2) +
       [-3*CP+3P1]*t +
       CP

So now we have the cubic equation expressing this curve in terms of T. Here is how I'd usually integrate this into my code:

double ax = -lastX+3*x1-3*x2+x3;
double bx = 3*lastX-6*x1+3*x2;
double cx = -3*lastX+3*x1;
double dx = lastX;

... and you can likewise define ay, by, cy and dy.

This concludes the introduction; look up other articles that are prefaced with "Shape" to see possible uses for this.