Java Program for Douglas-Peucker Algorithm Implementation

This is a Java Program to implement Douglas-Peucker Algorithm. The Ramer–Douglas–Peucker algorithm (RDP) is an algorithm for reducing the number of points in a curve that is approximated by a series of points. This algorithm is also known under the names Douglas–Peucker algorithm, iterative end-point fit algorithm and split-and-merge algorithm. The purpose of the algorithm is, given a curve composed of line segments, to find a similar curve with fewer points. The algorithm defines ‘dissimilar’ based on the maximum distance between the original curve and the simplified curve. The simplified curve consists of a subset of the points that defined the original curve.

Here is the source code of the Java Program for Douglas-Peucker Algorithm Implementation. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

//This is a java program to filter out points using Douglas Peucker Algorithm
import static java.lang.Math.abs;
import static java.lang.Math.pow;
import static java.lang.Math.sqrt;
 
import java.util.Random;
 
class RamerDouglasPeuckerFilter
{
 
    private double epsilon;
 
    public RamerDouglasPeuckerFilter(double epsilon)
    {
        if (epsilon <= 0)
        {
            throw new IllegalArgumentException("Epsilon nust be > 0");
        }
        this.epsilon = epsilon;
    }
 
    public double[] filter(double[] data)
    {
        return ramerDouglasPeuckerFunction(data, 0, data.length - 1);
    }
 
    public double getEpsilon()
    {
        return epsilon;
    }
 
    protected double[] ramerDouglasPeuckerFunction(double[] points,
            int startIndex, int endIndex)
    {
        double dmax = 0;
        int idx = 0;
        double a = endIndex - startIndex;
        double b = points[endIndex] - points[startIndex];
        double c = -(b * startIndex - a * points[startIndex]);
        double norm = sqrt(pow(a, 2) + pow(b, 2));
        for (int i = startIndex + 1; i < endIndex; i++)
        {
            double distance = abs(b * i - a * points[i] + c) / norm;
            if (distance > dmax)
            {
                idx = i;
                dmax = distance;
            }
        }
        if (dmax >= epsilon)
        {
            double[] recursiveResult1 = ramerDouglasPeuckerFunction(points,
                    startIndex, idx);
            double[] recursiveResult2 = ramerDouglasPeuckerFunction(points,
                    idx, endIndex);
            double[] result = new double[(recursiveResult1.length - 1)
                    + recursiveResult2.length];
            System.arraycopy(recursiveResult1, 0, result, 0,
                    recursiveResult1.length - 1);
            System.arraycopy(recursiveResult2, 0, result,
                    recursiveResult1.length - 1, recursiveResult2.length);
            return result;
        } else
        {
            return new double[] { points[startIndex], points[endIndex] };
        }
    }
 
    public void setEpsilon(double epsilon)
    {
        if (epsilon <= 0)
        {
            throw new IllegalArgumentException("Epsilon nust be > 0");
        }
        this.epsilon = epsilon;
    }
 
}
 
public class Douglas_Peucker_Algorithm
{
    public static void main(String args[])
    {
        Random random = new Random();
        double[] points = new double[20];
        double[] fpoints;
        for (int i = 0; i < points.length; i++)
            points[i] = random.nextInt(10);
        RamerDouglasPeuckerFilter rdpf = new RamerDouglasPeuckerFilter(1);
        fpoints = rdpf.filter(points);
 
        System.out.println("Orginal points");
        for (int i = 0; i < points.length; i++)
            System.out.print(points[i] + " ");
 
        System.out.println("\nFiltered points");
        for (int i = 0; i < fpoints.length; i++)
            System.out.print(fpoints[i] + " ");       
    }
}

Output:

$ javac Douglas_Peucker_Algorithm.java
$ java Douglas_Peucker_Algorithm
 
Orginal points
5.0 0.0 8.0 7.0 2.0 9.0 4.0 4.0 0.0 7.0 4.0 1.0 9.0 6.0 8.0 9.0 6.0 6.0 9.0 6.0 
Filtered points
5.0 0.0 8.0 2.0 9.0 0.0 7.0 1.0 9.0 6.0 9.0 6.0 9.0 6.0

Related posts:

Guava Collections Cookbook
Form Validation with AngularJS and Spring MVC
Java Program to Perform Deletion in a BST
Lập trình đa luồng với Callable và Future trong Java
Practical Java Examples of the Big O Notation
Derived Query Methods in Spring Data JPA Repositories
Java Program to Implement Fibonacci Heap
Java Program to Construct a Random Graph by the Method of Random Edge Selection
Java Program to implement Bit Set
Arrays.asList vs new ArrayList(Arrays.asList())
Serialization và Deserialization trong java
Simple Single Sign-On with Spring Security OAuth2
Java Program to Find k Numbers Closest to Median of S, Where S is a Set of n Numbers
An Intro to Spring Cloud Zookeeper
Rest Web service: Filter và Interceptor với Jersey 2.x (P1)
Lớp Properties trong java
Lớp LinkedHashMap trong Java
Java Program to Generate Random Numbers Using Middle Square Method
Reactive Flow with MongoDB, Kotlin, and Spring WebFlux
Java Program to Perform Naive String Matching
Sử dụng Fork/Join Framework với ForkJoinPool trong Java
Hướng dẫn Java Design Pattern – Template Method
Exploring the Spring 5 WebFlux URL Matching
Mệnh đề Switch-case trong java
Jackson – Change Name of Field
Converting Between an Array and a Set in Java
Các chương trình minh họa sử dụng Cấu trúc điều khiển trong Java
Extract network card address
Các nguyên lý thiết kế hướng đối tượng – SOLID
Case-Insensitive String Matching in Java
Java Program to implement Associate Array
Spring 5 Functional Bean Registration