Line smoothing in Java

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:
Line, pre-smoothing

And here is the line, post-smoothing:
Line, post-smoothing

Advertisements

2 thoughts on “Line smoothing in Java

  1. Hello Derek! This code is really nice, but where is the class extending JFrame (,etc.) that makes me possible to actually try your code? Thanks a lot for you answer and congratz for this really interesting blog 😉

    • Unfortunately, I think that part of the code has been lost to the sands of time. As I recall it was a pretty simple JFrame with a JPanel that I wrote a mouse listener for to keep track of the movement.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s