package CH.ifa.draw.figures;

import java.awt.Point;
import java.util.Vector;

/**
 * Helper class to simplify given list of points using Ramer-Douglas-Peucker algorithm
 * <br><br>
* The Ramer-Douglas-Peucker algorithm is a powerful line simplification technique designed to reduce the number of points in a polyline while preserving its overall shape. It achieves this by recursively eliminating points that do not significantly deviate from the line formed by the start and end points of the polyline.
 * @deprecated This class is not to be used externally and will later be hidden.
 */
@Deprecated(since = "5.0", forRemoval = true)
class RamerDouglasPeucker {

    /**
     * private constructor that prevents the creation of instances of the RamerDouglasPeucker class.
     * Since all methods in this class are accessed statically, instantiation is not allowed.
     */
    private RamerDouglasPeucker() {}

    /**
     * The maximum tolerance for simplification at the maximum smoothness.
     * <br><br>
     * This constant represents the maximum tolerance value used in the simplification process when the smoothness is set to its maximum value
     * The tolerance determines the degree of simplification, with a larger value resulting in more significant point reduction and fewer points being returned.
     */
    public final static double MAX_TOLERANCE = 3;

    /**
     * The size of the tail window used to split a list of points into two parts: head and tail. In case it's only needed to simplify the tail part to improve performance and reduce complexity.
     */
    private final static int TAIL_WINDOW_SIZE = 50;


    /**
     * Simplify points with given smoothness
     * @param points The original points represented as a list.
     * @param smoothness The desired smoothness level for the simplification process. The smoothness value should be normalized and within the range of 0 to 1. A smoothness value of 0 indicates no smoothing, while a value of 1 represents maximum smoothing.
     * @return The list of simplified points, including the first and last original points.
     */
    public static Vector<Point> simplifyBySmoothness(Vector<Point> points, double smoothness) {
        smoothness = getValidSmoothness(smoothness);
        double tolerance = convertingSmoothnessToTolerance(smoothness);
        return simplifyByTolerance(points, tolerance);
    }

    /**
     * Simplifies the tail part of points with given smoothness.
     * <br><br>
     * Simplification is performed exclusively on the tail part to enhance performance and minimize complexity.
     * <br>
     * If the number of points is less than or equal to the tail window size, it simplifies the entire vector of points.
     * @param points     The vector of points to be simplified.
     * @param smoothness The smoothness factor used for simplification.
     * @return A new vector of points with the tail part simplified based on the given smoothness.
     */
    public static Vector<Point> simplifyTailBySmoothness(Vector<Point> points, double smoothness) {
        if (points.size() <= TAIL_WINDOW_SIZE) {
            return simplifyBySmoothness(points, smoothness);
        } else {
            // Split list of points into 2 part: head and tail
            int startIndex = points.size() - TAIL_WINDOW_SIZE;
            Vector<Point> headPoints = new Vector<>(points.subList(0, startIndex));
            Vector<Point> tailPoints = new Vector<>(points.subList(startIndex, points.size()));
            // Only simplify tail for better performance
            double tolerance = convertingSmoothnessToTolerance(smoothness);
            Vector<Point> simplifiedTail = simplifyBySmoothness(tailPoints, tolerance);
            // Join head and simplified tail
            Vector<Point> simplifiedPoints = new Vector<>();
            simplifiedPoints.addAll(headPoints);
            simplifiedPoints.addAll(simplifiedTail);
            return simplifiedPoints;
        }
    }

    /**
     * Simplifies a given set of points with given tolerance value
     * @param points List of original points
     * @param tolerance Threshold used to determine the maximum distance between a point on the original polyline and the simplified line formed by the start and end points of the polyline, A smaller epsilon value results in a more accurate simplified line but with more points, while a larger epsilon value results in a less accurate line with fewer points.
     * @return List of simplified points including the first and last original points
     */
    public static Vector<Point> simplifyByTolerance(Vector<Point> points, double tolerance) {
        // Only simplify if there are more than 2 points
        if (points.size() < 2) {
            return points;
        }

        Vector<Point> simplifiedPoints = new Vector<>();

        // Find the point that has the maximum distance from the start and end points
        double maxDistance = 0.0;
        int index = 0;
        int end = points.size() - 1;
        for (int i = 1; i < end; ++i) {
            double perpendicularDistance = perpendicularDistance(
                points.elementAt(i), points.elementAt(0), points.elementAt(end));
            if (perpendicularDistance > maxDistance) {
                index = i;
                maxDistance = perpendicularDistance;
            }
        }

        // If max distance is bigger than epsilon, simplify recursively
        if (maxDistance > tolerance) {
            Vector<Point> recResults1;
            Vector<Point> recResults2;
            Vector<Point> firstLine = new Vector<>(points.subList(0, index + 1));
            Vector<Point> lastLine = new Vector<>(points.subList(index, points.size()));
            recResults1 = simplifyByTolerance(firstLine, tolerance);
            recResults2 = simplifyByTolerance(lastLine, tolerance);

            // Create a list of points from the results of recursive method calls
            simplifiedPoints.addAll(recResults1.subList(0, recResults1.size() - 1));
            simplifiedPoints.addAll(recResults2);
            if (simplifiedPoints.size() < 2) {
                return points;
            }
        } else { // Keep only the start and end points
            simplifiedPoints.add(points.elementAt(0));
            simplifiedPoints.add(points.elementAt(points.size() - 1));
        }

        return simplifiedPoints;
    }

    /**
     * Helper function for Douglas Peucker algorithm to calculate perpendicular distance from a point to given line
     * <br><br>
     * Math explanation: <a href="https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line">Wikipedia: Distance from a point to a line</a>
     * @param currentPoint The point to find the distance of it to given line
     * @param startPoint   The point at the start of the line
     * @param endPoint     The point at the end of the line
     * @return The perpendicular distance from the point to given line
     */
    private static double perpendicularDistance(
        Point currentPoint, Point startPoint, Point endPoint)
    {
        double x = currentPoint.getX();
        double y = currentPoint.getY();
        double x1 = startPoint.getX();
        double y1 = startPoint.getY();
        double x2 = endPoint.getX();
        double y2 = endPoint.getY();
        double numerator = Math.abs((y2 - y1) * x - (x2 - x1) * y + x2 * y1 - y2 * x1);
        double denominator = Math.sqrt(Math.pow(y2 - y1, 2) + Math.pow(x2 - x1, 2));
        return numerator / denominator;
    }

    /**
     * Converts the smoothness value to a tolerance value for simplifying points with the Ramer-Douglas-Peucker algorithm.
     * <br>
     This method takes a normalized smoothness value in the range of 0 to 1 and converts it to a corresponding tolerance value in the range of 0 to MAX_TOLERANCE.
     * <br>
     * Normalized smoothness is a useful parameter for adjusting the smoothness through an API, but it cannot be directly used as the simplification tolerance. If the distance between points is larger than 1, the Ramer-Douglas-Peucker algorithm cannot effectively simplify the points.
     * <br>
     * Example: If the smoothness is 1 and the maximum tolerance is 3, the returned tolerance value will be 3. This means that at maximum smoothness (1), the tolerance for simplification will be 3 pixels.
     * @param smoothness The normalized smoothness value in the range of 0 to 1.
     * @return The tolerance value for the Ramer-Douglas-Peucker algorithm.
     */
    private static double convertingSmoothnessToTolerance(double smoothness) {
        smoothness = getValidSmoothness(smoothness);
        double inputStart = 0;
        double inputEnd = 1;
        double outputStart = 0;
        double x = (MAX_TOLERANCE - outputStart) * (smoothness - inputStart);
        double y = (inputEnd - inputStart);
        return x / y + outputStart;
    }

    /**
     Ensures that the smoothness value is within the valid range of 0 to 1.
     If the smoothness is less than 0, the returned valid smoothness is 0.
     If the smoothness is greater than 1, the returned valid smoothness is 1.
     @param smoothness The input smoothness value to be validated.
     @return The smoothness value within the range of 0 to 1.
     **/
    private static double getValidSmoothness(double smoothness) {
        return Math.max(0, Math.min(1, smoothness));
    }
}
