A friend of mine recently asked me to help him with a Java GUI to demonstrate the finer points of his PhD thesis. Part of this GUI included a canvas wherein the user would “hand draw” a line, which his algorithm would use as input (which I stored as a List of line segments). Long story short, this line needed to be smoothed out to remove the inaccuracies created from its hand-drawedness.

Now, there are a number of algorithms (e.g. Bézier Curves, Spline Interpolation), but I wanted something simple enough that the user could just hand-draw the line and hit a button that said “smooth.” After a bit of searching I settled on McMaster’s Slide Averaging Algorithm, which I have implemented below:

import java.awt.Point; import java.util.ArrayList; import java.util.List; /** * A method to smooth a hand-drawn line based on the McMaster * line smoothing algorithm * * @author Derek Springer */ public class LineSmoother { /** * @param lineSegments A list of line segments representing a line * @return A list line segments representing the smoothed line */ public static List<Line> smoothLine(List<Line> lineSegments) { if(lineSegments.size() < 4) return lineSegments; List<Line> smoothedLine = new ArrayList<Line>(); List<Point> points = getPoints(lineSegments); smoothedLine.add(lineSegments.get(0)); Point newPoint = points.get(1); for(int i = 2; i < points.size()-2; i++) { Point lastPoint = newPoint; newPoint = smoothPoint(points.subList(i-2, i+3)); smoothedLine.add(new Line(lastPoint, newPoint)); } Line lastSegment = lineSegments.get(lineSegments.size()-1); smoothedLine.add(new Line( newPoint, new Point(lastSegment.x1, lastSegment.y1))); smoothedLine.add(lastSegment); return smoothedLine; } /** * @param lineSegments A list of line segments representing a line * @return A list of Points representing the points in a series of * line segments */ public static List<Point> getPoints(List<Line> lineSegments) { List<Point> points = new ArrayList<Point>(); for(Line segment : lineSegments) { points.add(new Point(segment.x1, segment.y1)); } points.add(new Point( lineSegments.get(lineSegments.size()-1).x2, lineSegments.get(lineSegments.size()-1).y2)); return points; } /** * Find the new point for a smoothed line segment * @param points The five points needed * @return The new point for the smoothed line segment */ public static Point smoothPoint(List<Point> points) { int avgX = 0; int avgY = 0; for(Point point : points) { avgX += point.x; avgY += point.y; } avgX = avgX/points.size(); avgY = avgY/points.size(); Point newPoint = new Point(avgX, avgY); Point oldPoint = points.get(points.size()/2); int newX = (newPoint.x + oldPoint.x)/2; int newY = (newPoint.y + oldPoint.y)/2; return new Point(newX, newY); } }

Also, here is the Line class I reference above:

import java.awt.Point; /** * A class to represent a line created from two points * @author Derek Springer */ public class Line { public int x1; public int y1; public int x2; public int y2; public Line(int x1, int y1, int x2, int y2) { this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2; } public Line(Point point1, Point point2) { this.x1 = point1.x; this.y1 = point1.y; this.x2 = point2.x; this.y2 = point2.y; } public double slope() { if(x2-x1 == 0) return Double.NaN; return (double)(y2-y1)/(double)(x2-x1); } public double intercept() { return y1 - slope() * x1; } public static double slope(double x1, double y1, double x2, double y2) { return (y2-y1)/(x2-x1); } public static double slope(Point point1, Point point2) { return slope(point1.getX(), point1.getY(), point2.getX(), point2.getY()); } public static double intercept(double x1, double y1, double x2, double y2) { return y1 - slope(x1, y1, x2, y2) * x1; } public static double intercept(Point point1, Point point2) { return intercept(point1.getX(), point1.getY(), point2.getX(), point2.getY()); } @Override public String toString() { return "[(" + x1 + ", " + x2 + "), (" + y1 + ", " + y2 + ")] " + "m=" + slope() + ", b=" + intercept(); } }

Here is the original, unsmooth line:

And here is the line, post-smoothing: