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:

Lớp HashMap trong Java
Java Program to Perform the Shaker Sort
Java Program to Implement Knight’s Tour Problem
Find the Registered Spring Security Filters
Java Program to Implement LinkedBlockingQueue API
Injecting Prototype Beans into a Singleton Instance in Spring
Java – Create a File
Java Program to Check if any Graph is Possible to be Constructed for a Given Degree Sequence
Hướng dẫn sử dụng Lớp FilePermission trong java
Easy Ways to Write a Java InputStream to an OutputStream
Cơ chế Upcasting và Downcasting trong java
Returning Custom Status Codes from Spring Controllers
Toán tử trong java
Java Program to Apply DFS to Perform the Topological Sorting of a Directed Acyclic Graph
Java Program to Implement Pollard Rho Algorithm
Retrieve User Information in Spring Security
Java – Convert File to InputStream
Spring WebClient Filters
Giới thiệu Google Guice – Dependency injection (DI) framework
Java Program to Check Whether an Undirected Graph Contains a Eulerian Path
Immutable Objects in Java
Java Program to Perform Inorder Recursive Traversal of a Given Binary Tree
Java Program to Implement Vector API
Filtering and Transforming Collections in Guava
Java Program to Check if a Point d lies Inside or Outside a Circle Defined by Points a, b, c in a Pl...
Debug a JavaMail Program
Java Program to Implement Double Order Traversal of a Binary Tree
Java Program to Give an Implementation of the Traditional Chinese Postman Problem
Java Program to Perform Naive String Matching
Constructor Dependency Injection in Spring
Java Program to Implement Sieve Of Atkin
Query Entities by Dates and Times with Spring Data JPA