Cubic Bezier Curves in JTS

As the title of this blog indicates, I'm a fan of linearity.  But sometimes a little non-linearity makes things more interesting.  A convenient way to generate non-linear curved lines is to use Bezier Curves.  Bezier Curves are curves defined by polynomials.  Bezier curves can be defined for polynomials of any degree, but a popular choice is to use cubic Bezier curves defined by polynomials of degree 3.  These are relatively easy to implement, visually pleasing, and versatile since they can model ogee or sigmoid ("S"-shaped) curves.

A single cubic Bezier curve is specified by four points: two endpoints forming the baseline, and two control points.  The curve shape lies within the quadrilateral convex hull of these points.

Note: the images in this post are created using the JTS TestBuilder.

Cubic Bezier Curves, showing endpoints and control points

A sequence of Bezier curves can be chained together to form a curved path of any required shape. There are several ways to join composite Bezier curves.  The simplest join constraint is C0-continuity: the curves touch at endpoints, but the join may be a sharp angle.  C1-continuity (differentiable) makes the join smooth. This requires the control vectors at a join point to be collinear and opposite.  If the control vectors are of different lengths there will be a different radius of curvature on either side.  The most visually appealing join is provided by C2-continuity (twice-differentiable), where the curvature is identical on both sides of the join.  To provide this the control vectors at a vertex must be collinear, opposite and have the same length.

Bezier Curve with C2-continuity

A recent addition to the JTS Topology Suite is the CubicBezierCurve class, which supports constructing Bezier Curves from LineStrings and Polygons.  JTS only supports representing linear geometries, so curves must be approximated by sequences of line segments. (The buffer algorithm uses this technique to approximate the circular arcs required by round joins.)   

Bezier Curve approximated by line segments

Bezier curves can be generated on both lines and polygons (including holes):

Bezier Curve on a polygon

There are two ways of specifying the control points needed to define the curve:  

Alpha (Curvedness) Parameter

The easiest way to define the shape of a curve is via the parameter alpha, which indicates the "curvedness".  This value is used to automatically generate the control points at each vertex of the baseline.  A value of 1 creates a roughly circular curve at right angles.  Higher values of alpha make the result more curved; lower values (down to 0) make the curve flatter.

Alpha is used to determine the length of the control vectors at each vertex.  The control vectors on either side of the vertex are collinear and of equal length, which provides C2-continuity.  The angle of the control vectors is perpendicular to the bisector of the vertex angle, to make the curve symmetrical.  

Bezier Curve for alpha = 1

Bezier Curve for alpha = 1.3

Bezier Curve for alpha = 0.3

Explicit Control Points

Alternatively, the Bezier curve control points can be provided explicitly.  This gives complete control over the shape of the generated curve.  Two control points are required for each line segment of the baseline geometry, in the same order.  A convenient way to provide these is as a LineString (or MultiLineString for composite geometries) containing the required number of vertices.

Bezier Curve defined by control points, with C2 continuity

When using this approach only C0-continuity is provided automatically.  The caller must enforce C1 or C2-continuity via suitable positioning of the control points.

Bezier Curve defined by control points showing C0 and C1 continuity

Further Ideas

• Allow specifying the number of vertices used to approximate each curve
• Add a function to return the constructed control vectors (e.g. for display and analysis purposes)
• Make specifying explicit control points easier by generating C2-continuous control vectors from a single control point at each vertex

Christmas Wrapping

 Every so often I produce an image in the JTS TestBuilder which strikes me as worthy of capture.  Here's one that seems pretty seasonal:

It is generated like this:

1. Produce two sets of 1000 random points roughly aligned with a grid
2. Compute their fully-eroded Convex Hulls
3. Compute the intersection of the two hulls
4. Theme the intersection with random fill

Even-distribution Random Point and Polygons in JTS

Recently I fixed the JTS KD-Tree implementation so that it works as advertised with a distance tolerance to provide point snapping.  This gives a fast way to produce random point fields with even distribution (i.e. no points too close together).

First, generate a batch of random points using RandomPointsBuilder.  As is well known, this produces a very "lumpy" distribution of points:

Then, put them in a KD-Tree using a snapping distance tolerance.  Querying all points in the final tree produces a nice even distribution of points:

Using the Concave Hull algorithm available here with the same distance tolerance produces a random polygon with a very pleasing appearance:

I suspect that these kinds of polygons might be useful for generating stress tests for geometric algorithms.

UPDATE: Adding a bit of Bezier Smoothing produces an even cooler-looking polygon:

Halton sequences, at last

A while ago I posted on generating random point sets, and Sean Gillies suggested Halton sequences as a way of generating nice-looking point distributions.  I finally got around to looking into this idea. Indeed he was correct - Halton sequences provide a very pleasing appearance for point distributions (much better than purely random distributions).

The above shows the first 1000 elements of the Halton sequence with bases (2,3).  Larger bases exhibit progressively more coherence, which may or may not be desirable depending on application. Here's H(7,9):

 The code to generate Halton sequences is pretty trivial - see the Wikipedia article for some pseudo-code.  (Although I have to say that the explanation of their derivation is pretty poor.  I've seen this sad trend on some other Wikipedia mathematical articles as well - in particular the one for Barnes surface interpolation.  I suppose the rejoinder would be to get in there and improve it!)

Keying off something else that Sean showed on his blog, I also played around with using Halton sequences to generate quasi-random sets of polygons.  Here's one example, using a slightly different approach to Sean's:

And the same for H(5,7), which looks slightly nicer I think:

Might come in handy someday for generating test data, or possibly as a visual texture.

Visualizations of Sorting Algorithms in your browser

Here's a nifty web page which shows a way of visualizing the operation of various common sorting algorithms.

Sample output for Heapsort:



The coolest thing about this of course is the ability to dynamically generate rich graphics in the browser. All hail the HTML5 <canvas> element!

Wordlicious

After seeing this post on Wordle, I had to try it....


and there's no stopping at just one...

Complex Functions as Algorithmic Art

Hans Lundmark has an interesting page on visualizing complex functions. The idea is to map functions from f : C → C using position, hue, and saturation. The domain values of the function provide the (x, y) position. The function output value provides the hue and saturation; the hue is determined by the complex argument (angle), and the saturation is determined by the absolute value.

The output struck me as a nice example of algorithmic art. I whipped up my own version in Java to experiment, and to be able to produce high-resolution images for printing. Here's a couple of my images:

An example function from the paper ( f ( z ) = ( z − 2 )² ( z + 1 − 2i ) ( z + 2 + 2i ) / z³ )



^{"Wild Walrus"}