Tag Archives: Line Smoothing

Line smoothing in Java

4 Replies

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

Advertisement