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:

Optional trong Java 8
Convert XML to JSON Using Jackson
How to Manually Authenticate User with Spring Security
Using Spring ResponseEntity to Manipulate the HTTP Response
Spring Data JPA @Modifying Annotation
Spring Boot - Zuul Proxy Server and Routing
Spring Boot Actuator
Java Program to Generate All Subsets of a Given Set in the Lexico Graphic Order
Java Program to Delete a Particular Node in a Tree Without Using Recursion
Spring Security OAuth Login with WebFlux
Java Program to Test Using DFS Whether a Directed Graph is Strongly Connected or Not
Spring JDBC
Java Program to Implement ConcurrentLinkedQueue API
Supplier trong Java 8
Java Deep Learning Essentials - Yusuke Sugomori
Removing all Nulls from a List in Java
Deque và ArrayDeque trong Java
A Comparison Between Spring and Spring Boot
Java Program to Find k Numbers Closest to Median of S, Where S is a Set of n Numbers
Java Program to Implement Max Heap
Spring REST API + OAuth2 + Angular (using the Spring Security OAuth legacy stack)
A Guide to the Java ExecutorService
Java Program to Implement Vector API
Understanding Memory Leaks in Java
Java Program to Implement Traveling Salesman Problem using Nearest neighbour Algorithm
Date Time trong Java 8
Java Program to Use Boruvka’s Algorithm to Find the Minimum Spanning Tree
Form Validation with AngularJS and Spring MVC
Spring Boot - Servlet Filter
Serialization và Deserialization trong java
Java Program to Implement Multi-Threaded Version of Binary Search Tree
Java Program to Perform Partial Key Search in a K-D Tree