// Catalano Math Library
// The Catalano Framework
//
// Copyright © Diego Catalano, 2012-2018
// diego.catalano at live.com
//
// Copyright © Pier Lorenzo Paracchini, 2007-2008
// https://pparacch.github.io/
//
//    This library is free software; you can redistribute it and/or
//    modify it under the terms of the GNU Lesser General Public
//    License as published by the Free Software Foundation; either
//    version 2.1 of the License, or (at your option) any later version.
//
//    This library is distributed in the hope that it will be useful,
//    but WITHOUT ANY WARRANTY; without even the implied warranty of
//    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
//    Lesser General Public License for more details.
//
//    You should have received a copy of the GNU Lesser General Public
//    License along with this library; if not, write to the Free Software
//    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
//

package Catalano.Math.Geometry;

import Catalano.Core.IntPoint;
import Catalano.Math.Distances.Distance;
import java.util.ArrayList;
import java.util.List;

/**
 * Ramer-Douglas-Peucker.
 * 
 * Douglas–Peucker algorithm and iterative end-point fit algorithm, is an algorithm
 * that decimates a curve composed of line segments to a similar curve with fewer points.
 * 
 * @author Diego Catalano
 */
public class RamerDouglasPeucker implements IShapeOptimizer {
    
    private double distanceThreshold;

    /**
     * Get distance threshold.
     * @return Distance threshold.
     */
    public double getDistanceThreshold() {
        return distanceThreshold;
    }

    /**
     * Distance threshold.
     * @param distanceThreshold Distance threshold.
     */
    public void setDistanceThreshold(double distanceThreshold) {
        this.distanceThreshold = distanceThreshold;
    }

    /**
     * Initializes a new instance of the RamerDouglasPeucker class.
     */
    public RamerDouglasPeucker() {
        this(0.5);
    }

    /**
     * Initializes a new instance of the RamerDouglasPeucker class.
     * @param distanceThreshold Distance threshold.
     */
    public RamerDouglasPeucker(double distanceThreshold) {
        this.distanceThreshold = distanceThreshold;
    }

    @Override
    public List OptimizeShape(List shape) {
        List simplifiedVertices = new ArrayList();

        Double maxDistance = null;
        int maxDistancePointIdx = 0;

        int lastPointIdx = shape.size()-1;

        int currentIdx = 0;
        for (IntPoint aVertex : shape) {

            if (currentIdx != 0 && currentIdx != lastPointIdx) {

                Double distance = shortestDistanceToSegment(aVertex, shape.get(0), shape.get(lastPointIdx));

                if (maxDistance == null || distance > maxDistance) {
                    maxDistancePointIdx = currentIdx;
                    maxDistance = distance;
                }

            }
            currentIdx++;
        }

        if (maxDistance != null) {
            if (maxDistance > distanceThreshold) {
                List sub = OptimizeShape(shape.subList(0, maxDistancePointIdx+1));
                List sup = OptimizeShape(shape.subList(maxDistancePointIdx, lastPointIdx+1));

                simplifiedVertices.addAll(sub);
                simplifiedVertices.addAll(sup);

            } else {
                simplifiedVertices.add(shape.get(0));
                simplifiedVertices.add(shape.get(lastPointIdx));
            }
        }
        return simplifiedVertices;
    }
    
    private double shortestDistanceToSegment(IntPoint thePoint, IntPoint segmentPoint_A, IntPoint segmentPoint_B) {
        double area = calculateTriangleAreaGivenVertices(thePoint, segmentPoint_A, segmentPoint_B);
        double lengthSegment = Distance.Euclidean(segmentPoint_A, segmentPoint_B);
        return (2 * area) / lengthSegment;
    }

    private double calculateTriangleAreaGivenVertices(IntPoint a, IntPoint b, IntPoint c) {
        // http://www.mathopenref.com/coordtrianglearea.html
        double area = Math.abs(((a.x * (b.y - c.y)) + (b.x * (c.y - a.y)) + (c.x * (a.y - b.y))) / 2);
        return area;
    }
}
 

Ads help maintain this website.