# 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);

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));
}

Line lastSegment = lineSegments.get(lineSegments.size()-1);
newPoint,
new Point(lastSegment.x1, lastSegment.y1)));

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) {
}
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:

# Perl tip – Reading a file into a string

I recently needed to check to see if a file had a particular tag in it before continuing, but I didn’t want to have to read it line by line to find out.

To my astonishment, there is no simple way to read a whole file into a string in Perl. The simple solution would be to use File::Slurp, but since the script will be running in a closed system I could only use default libraries. Also, because it’s Perl, I wanted to do it in a single line to maintain maximum incomprehensibility.

After a bit of tooling around I came up with this:

#!/usr/bin/perl -w

use strict;
use warnings;

# Check the file to ensure it contains the tag before continuing
my \$FILE = \$ARGV[0] or die \$!;
die "File is missing required TIMESTAMP tag.n" unless do { local \$/; local @ARGV = \$FILE; <> } =~ /TIMESTAMP/;
...

More simply, here is the code to just stick the file contents in a variable:

my \$contents = do { local \$/; local @ARGV = \$FILE; <> };

Essentially, what’s going on here is that I’m unsetting ‘\$/’, the Input Record Separator, to make <> give the whole file at once.

Props to Stack Overflow for pointing me in the right direction.

# Syntax highlighting comes to Posterous

## Here is some Python code!

# sample Python code snippet
# bonus points if you know what this is
from __future__ import generators

def firstn(g, n):
for i in range(n):
yield g.next()

def intsfrom(i):
while 1:
yield i
i = i + 1

def exclude_multiples(n, ints):
for i in ints:
if (i % n): yield i

def sieve(ints):
while 1:
prime = ints.next()
yield prime
ints = exclude_multiples(prime, ints)

if __name__ == '__main__':
for i in firstn(sieve(intsfrom(2)), 400):
print i

# Crab People…

Q: Who is the best wife? A: J.J. is the best wife.

# Next in the series of adorable animals from my nightmares

As a bonus, keep on the lookout for a secret goatse around ~1:35.

It features my cousin Miles decorating Easter Eggs–OH BOY!

# Bobby Lots Steps Down

I always remember him being a pretty cool dude. I wonder who the new prez will be?

———- Forwarded message ———-
From: Office of the LMU President
Date: Mon, Mar 1, 2010 at 5:04 PM
Subject: Message From the LMU President

 March 1, 2010