Category Archives: Uncategorized

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

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

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 <thepresident@lmu.edu>
Date: Mon, Mar 1, 2010 at 5:04 PM
Subject: Message From the LMU President

March 1, 2010

Message From the President
March 1, 2010

Dear LMU Community,

At today’s quarterly meeting of the Board of Trustees, I submitted my resignation as LMU’s 14th president, effective at the end of this academic year.  Our board has accepted my resignation, and a search will begin soon for my successor.  Executive Vice President and Provost David W. Burcham will become interim president and will serve during the search for a new president.  Dave has a long and distinguished history with LMU, first as a student, having received his J.D. from Loyola Law School, as a faculty member when he returned in 1991 and as an administrator when he was appointed the 15th dean of the law school in 2000.  He took on the role of provost in 2008.  Dave is well-prepared to lead LMU until a new president is selected.

Two (not three!) considerations have motivated my decision.  One is my health.  The recovery from my back operation has been slow and has affected my ability, because of my schedule, to do the physical activity and exercise advised and, more importantly, to do my job to the fullest.  I plan to take a sabbatical and that should allow me time to do what is required to return to full health, or at least to as much health as my age allows!

The other consideration is deeper.  It is what I might call “the rule of ten.”  Ten years in these kinds of jobs is usually enough and after that both the institution and the person benefit from change.  At least that is true of me.  I served as Dean of Georgetown College for ten years and had originally intended to serve in this job for ten as well.  I am now in my eleventh.  I subsequently thought that it made sense, given the extension of the campaign until October, 2011 and the centennial celebration in 2012, to continue until then.  But our fundraising professionals are superb, and both Dave and, I am sure, my successor will be more than able to work with them to meet our ambitious goal of $380 million.

Moreover, the dedication of the William H. Hannon Library affected me deeply.  John Ruskin “proposed that we seek two things of our buildings.  We want them to shelter us, and we want them to speak to us.”  The library said powerfully to me that my work at LMU was basically complete, that I had accomplished what I came here to do.

 Now, finally, we get to what I most want to say (I guess I do have three points after all)!  As Sebastian says to Antonio in “Twelfth Night,” “I can no other answer make, but, thanks, and thanks, and ever thanks.”  Thank you all, faculty, staff, students and alumni, so much for making my LMU years so wonderful and fulfilling.  To have worked and played with you in caring for this great university and the larger worlds it serves has been a grace indeed.  My feelings these days are best expressed by Saint Exupéry:

Old friends cannot be created out of hand. Nothing can match the treasure of common memories, of trials endured together, of quarrels and reconciliations and generous emotions.

May God bless LMU now and for centuries to come.

Sincerely,
 
Robert B. Lawton, S.J.

1 LMU Drive, Los Angeles, CA 90045-2659 Phone: 310.338.3065 | http://alumni.lmu.edu

Loyola Marymount University
1 LMU Drive
Los Angeles CA 90045
www.lmu.edu