/*
 *  Copyright 2012 Peter Karich info@jetsli.de
 * 
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 * 
 *       http://www.apache.org/licenses/LICENSE-2.0
 * 
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */
package com.graphhopper.util;

import com.graphhopper.storage.Graph;
import gnu.trove.list.array.TIntArrayList;

/**
 * Simplyfies a list of points which are not too far away.
 *
 * @author Peter Karich
 */
public class DouglasPeucker {

    public static final int EMPTY = -1;
    private double normedMaxDist;
    private Graph g;
    private DistanceCalc calc;

    public DouglasPeucker(Graph g) {
        this.g = g;
        calc = new DistanceCalc();
        // 1m
        setMaxDist(1);
    }

    /**
     * distance in meter
     */
    public DouglasPeucker setMaxDist(double dist) {
        this.normedMaxDist = calc.normalizeDist(dist);
        return this;
    }

    /**
     * Points which should be removed will get the EMPTY value
     *
     * @return deleted nodes
     */
    public int simplify(TIntArrayList points) {
        return simplify(points, 0, points.size() - 1);
    }

    public int simplify(TIntArrayList points, int fromIndex, int toIndex) {
        if (toIndex - fromIndex < 2)
            return 0;
        int indexWithMaxDist = -1;
        double maxDist = -1;
        int lastIndex = toIndex;
        double firstLat = g.getLatitude(points.get(fromIndex));
        double firstLon = g.getLongitude(points.get(fromIndex));
        double lastLat = g.getLatitude(points.get(lastIndex));
        double lastLon = g.getLongitude(points.get(lastIndex));
        for (int i = fromIndex + 1; i < lastIndex; i++) {
            int tmpIndex = points.get(i);
            if (tmpIndex == EMPTY)
                continue;
            double lat = g.getLatitude(i);
            double lon = g.getLongitude(i);
            double dist = calc.calcNormalizedEdgeDistance(lat, lon, firstLat, firstLon, lastLat, lastLon);
            if (maxDist < dist) {
                indexWithMaxDist = i;
                maxDist = dist;
            }
        }

        if (indexWithMaxDist < 0)
            throw new IllegalStateException("maximum not found in [" + fromIndex + "," + toIndex + "]");

        int counter = 0;
        if (maxDist < normedMaxDist) {
            for (int i = fromIndex + 1; i < toIndex; i++) {
                points.set(i, EMPTY);
                counter++;
            }
        } else {
            counter = simplify(points, fromIndex, indexWithMaxDist);
            counter += simplify(points, indexWithMaxDist, toIndex);
        }
        return counter;
    }
}

@@ -1585,18 +1585,20 @@
 ex, int 
+las
 t
-o
 Index) %7B
@@ -1610,18 +1610,20 @@
     if (
+las
 t
-o
 Index - 
@@ -1727,41 +1727,8 @@
 -1;%0A
-        int lastIndex = toIndex;%0A
     
@@ -2586,18 +2586,20 @@
 + %22,%22 + 
+las
 t
-o
 Index + 
@@ -2713,18 +2713,20 @@
  1; i %3C 
+las
 t
-o
 Index; i
@@ -2954,18 +2954,20 @@
 axDist, 
+las
 t
-o
 Index);%0A

mini rename to peucker