Calculating distance with a Java 8 Collector

Leave a comment
Dev

In a previous post I showed a way to calculate the total distance of a GPX track using Scala’s foldLeft. Continuing my current hobby of exploring the new Java 8 lambdas and streams API I thought I would see how the functional approach translated to Java.

To recap, a GPX track is just a sequence of latitude, longitude pairs. The first problem is that Java doesn’t have Scala’s handy tuples so we need a custom class to represent a point.

class Point {
    public final double lat;
    public final double lon;

    public Point(double lat, double lon) {
        this.lat = lat;
        this.lon = lon;
    }
}

My first thought was to use the reduce method on the Stream interface but given the slightly more complicated requirement to keep track of both the total distance and the previous point I ended up implementing a custom Collector. From the Javadoc a Collector is:

A mutable reduction operation that accumulates input elements into a mutable result container, optionally transforming the accumulated result into a final representation after all input elements have been processed. Reduction operations can be performed either sequentially or in parallel.

The Collector interface has three type parameters: T is the type of input elements to the reduction operation, A is the mutable accumulation type of the reduction operation and R is the result type of the reduction operation.

In our case, the input elements are Points and the result type is a Double (distance in miles). We just need a mutable accumulation type to keep track of the total distance and the last point in the track. Here it is:

class Result {
    private Point previousPoint;
    private double totalDistance = 0.0;
}

So we have an input type and an accumulation type. Now we can implement the Collector which uses the haversine formula to calculate great circle distance between each point in the track and put it all together:

package com.davidkeen.test;

import com.google.common.collect.ImmutableList;

import java.util.Collections;
import java.util.List;
import java.util.Set;
import java.util.function.BiConsumer;
import java.util.function.BinaryOperator;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.stream.Collector;

public class GpxDistanceCalculator {

    public static class Point {
        public final double lat;
        public final double lon;

        public Point(double lat, double lon) {
            this.lat = lat;
            this.lon = lon;
        }
    }

    private static class Result {
        private Point previousPoint;
        private double totalDistance = 0.0;
    }
    
    public static class GpxCollector implements Collector<Point, Result, Double> {

        public static double haversineDistance(Point pointA, Point pointB) {
            double deltaLat = Math.toRadians(pointB.lat - pointA.lat);
            double deltaLong = Math.toRadians(pointB.lon - pointA.lon);
            double a = Math.pow(Math.sin(deltaLat / 2), 2) + Math.cos(Math.toRadians(pointA.lat)) *
                    Math.cos(Math.toRadians(pointB.lat)) * Math.pow(Math.sin(deltaLong / 2), 2);
            double greatCircleDistance = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
            return 3958.761 * greatCircleDistance;
        }

        @Override
        public Supplier<Result> supplier() {
            return Result::new;
        }

        @Override
        public BiConsumer<Result, Point> accumulator() {
            return (accumulator, entry) -> {
                if (accumulator.previousPoint != null) {
                    accumulator.totalDistance += haversineDistance(accumulator.previousPoint, entry);
                }
                accumulator.previousPoint = entry;
            };
        }

        @Override
        public BinaryOperator<Result> combiner() {

            // Should not be processed in a parallel stream
            return null;
        }

        @Override
        public Function<Result, Double> finisher() {
            return accumulator -> accumulator.totalDistance;
        }

        @Override
        public Set<Characteristics> characteristics() {
            return Collections.emptySet();
        }
    }

    public static void main(String[] args) {
        List<Point> track = new ImmutableList.Builder<Point>()
                .add(new Point(51.168437004089355, -0.648922920227051))
                .add(new Point(51.16805076599121, -0.64918041229248))
                .add(new Point(51.16757869720459, -0.64995288848877))
                .build();
        double distance = track.stream().collect(new GpxCollector());
        System.out.println("Total distance: " + distance + " miles");
    }
}

So given that we need to implement a Point class and a custom Collector the end result isn’t quite as concise as Scala but it’s still a nice functional way of processing the list. Unfortunately we can’t take advantage of parallel streams as the points have to be processed in order. The more I use Java 8’s new streams and lambdas the more I like them and Collectors are a nice way of customising reduction.

 

Leave a Reply

Your email address will not be published. Required fields are marked *