Skip to main content

Posts

Showing posts from December, 2010

Smooth as...

For a current project I needed a polygon smoothing algorithm in Java that:
generated a curve passing through all polygon vertices
had some way of controlling tightness of fit to the polygon
fell within the domain of my very limited mathematical grasp
Luckily for me, Maxim Shemanarev had not only worked out a Bezier curve algorithm that satisfied all of the above, but he also published a beautifully clear explanation of how it worksnote 1. Maxim also provided some illustrative C code, but my Java implementation below is an independent effort (ie. all mistakes are my fault). It uses geometry objects from the JTS library.

Below is an example of the algorithm in action. The original polygon is in black. The smoothed polygon composed of fitted cubic Bezier segments is in blue. The red points and lines indicate positions of the Bezier control points calculated with Maxim's algorithm. There are a pair of control points for each vertex of the input polygon.

The tightness of fit of the smooth…