Java: Bresenham's algorithm

README.md

Java implementation of Bresenham's algorithm.

http://stackoverflow.com/questions/6339328/iterate-through-each-point-on-a-line-path-in-java

CollectionUtils.java

package com.stackoverflow.utils;

import java.util.List;

import com.google.common.base.Function;
import com.google.common.base.Joiner;
import com.google.common.collect.Collections2;

public class CollectionUtils {
	public static <T> String mapJoin(List<T> list) {
		return mapJoin(list, new Function<T, String>() {
			public String apply(T item) {
				return item.toString();
			}
		}, ", ");
	}

	public static <T> String mapJoin(List<T> list,
			Function<T, String> mapper, String delimiter) {
		return Joiner.on(delimiter).join(Collections2.transform(list, mapper));
	}
}

LineIterator.java

package com.stackoverflow.iterator;

import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.util.Iterator;

/**
 * Implementation of Bresenham's algorithm to find all pixels on a Line2D.
 * 
 * @see https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
 */
public class LineIterator implements Iterator<Point2D> {
	final static double DEFAULT_PRECISION = 1.0;
	final Line2D line;
	final double precision;

	final double sx, sy;
	final double dx, dy;

	private double x, y, error;

	public LineIterator(Line2D line, double precision) {
		this.line = line;
		this.precision = precision;

		sx = line.getX1() < line.getX2() ? precision : -1 * precision;
		sy = line.getY1() < line.getY2() ? precision : -1 * precision;

		dx = Math.abs(line.getX2() - line.getX1());
		dy = Math.abs(line.getY2() - line.getY1());

		error = dx - dy;

		y = line.getY1();
		x = line.getX1();
	}

	public LineIterator(Line2D line) {
		this(line, DEFAULT_PRECISION);
	}

	public boolean hasNext() {
		return Math.abs(x - line.getX2()) > 0.9 || (Math.abs(y - line.getY2()) > 0.9);
	}

	public Point2D next() {
		Point2D ret = new Point2D.Double(x, y);

		double e2 = 2 * error;
		if (e2 > -dy) {
			error -= dy;
			x += sx;
		}
		if (e2 < dx) {
			error += dx;
			y += sy;
		}

		return ret;
	}

	public void remove() {
		throw new AssertionError();
	}
}

LineIteratorTest.java

package com.stackoverflow.iterator;

import static org.junit.Assert.assertEquals;

import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.util.List;

import org.junit.Test;

import com.stackoverflow.utils.PointUtils;

public class LineIteratorTest {
	@Test
	public void testIterator() {
		Line2D line = new Line2D.Double(0, 0, 8, 4);
		List<Point2D> points = PointUtils.lineToPoints(line);
		String expected = "(0.0, 0.0), (1.0, 0.0), (2.0, 1.0), (3.0, 1.0), "
				+ "(4.0, 2.0), (5.0, 2.0), (6.0, 3.0), (7.0, 3.0)";

		assertEquals(expected, PointUtils.pointsToString(points));
	}

	@Test
	public void testIterator2() {
		Point2D startPoint = new Point2D.Double(4, 4);
		Point2D endPoint = new Point2D.Double(10, 0);
		Line2D line = new Line2D.Double(startPoint, endPoint);
		List<Point2D> points = PointUtils.lineToPoints(line);
		String expected = "(4.0, 4.0), (5.0, 3.0), (6.0, 3.0), "
				+ "(7.0, 2.0), (8.0, 1.0), (9.0, 1.0)";

		assertEquals(expected, PointUtils.pointsToString(points));
	}

	@Test
	public void testIterator3() {
		Point2D startPoint = new Point2D.Double(0, 0);
		Point2D endPoint = new Point2D.Double(100, 0);
		Line2D line = new Line2D.Double(startPoint, endPoint);
		List<Point2D> points = PointUtils.lineToPoints(line);

		assertEquals(points.size(), 100);
	}
}

PointUtils.java

package com.stackoverflow.utils;

import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

import com.google.common.base.Function;
import com.stackoverflow.iterator.LineIterator;

public class PointUtils {
	public static String pointsToString(List<Point2D> points) {
		return CollectionUtils.mapJoin(points, new Function<Point2D, String>() {
			public String apply(Point2D point) {
				return String.format("(%.1f, %.1f)", point.getX(), point.getY());
			}
		}, ", ");
	}

	public static List<Point2D> lineToPoints(Line2D line) {
		List<Point2D> points = new ArrayList<Point2D>();
		Point2D current;

		for (Iterator<Point2D> iter = new LineIterator(line); iter.hasNext();) {
			current = iter.next();
			points.add(current);
		}

		return points;
	}

	public static void main(String[] args) {
		List<Point2D> points = new ArrayList<Point2D>(Arrays.asList(
				new Point2D.Double(0, 0), new Point2D.Double(1, 2),
				new Point2D.Double(2, 4), new Point2D.Double(3, 6),
				new Point2D.Double(4, 8), new Point2D.Double(5, 10)));
		
		System.out.println(pointsToString(points));
	}
}

pom.xml

<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
	xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
	<modelVersion>4.0.0</modelVersion>

	<groupId>line-iterator</groupId>
	<artifactId>com.stackoverflow</artifactId>
	<version>0.0.1-SNAPSHOT</version>
	<packaging>jar</packaging>

	<name>com.stackoverflow</name>
	<url>http://maven.apache.org</url>

	<properties>
		<!-- Configuration -->

		<java.compiler.version>1.6</java.compiler.version>
		<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
		<!-- Versions -->
		<junit.version>4.12</junit.version>
		
		<guava-collections.version>r03</guava-collections.version>
	</properties>

	<dependencies>
		<dependency>
			<groupId>junit</groupId>
			<artifactId>junit</artifactId>
			<version>${junit.version}</version>
			<scope>test</scope>
		</dependency>

		<dependency>
			<groupId>com.google.guava</groupId>
			<artifactId>guava-collections</artifactId>
			<version>${guava-collections.version}</version>
		</dependency>
	</dependencies>

	<build>
		<plugins>
			<plugin>
				<artifactId>maven-compiler-plugin</artifactId>
				<configuration>
					<source>${java.compiler.version}</source>
					<target>${java.compiler.version}</target>
				</configuration>
			</plugin>
		</plugins>
	</build>
</project>