Geometry Simplification

/**
 * Abstract base class for geometry simplification with memory constraints
 * @param <T> the geometry type to simplify
 */
public abstract class GeometrySimplifier<T extends Geometry> {
    
    /**
     * Maximum number of points to retain in simplified geometry
     */
    protected final int maxPoints;
    
    /**
     * Error calculator for determining point removal priority
     */
    protected final SimplificationErrorCalculator calculator;
    
    /**
     * Optional monitor for tracking simplification progress
     */
    protected final StreamingGeometrySimplifier.Monitor monitor;
    
    /**
     * Creates a geometry simplifier with specified constraints
     * @param description descriptive name for logging/monitoring
     * @param maxPoints maximum points to retain
     * @param calculator error calculator for point prioritization
     * @param monitor optional progress monitor (can be null)
     * @param innerSimplifier streaming simplifier for actual computation
     */
    protected GeometrySimplifier(
        String description,
        int maxPoints,
        SimplificationErrorCalculator calculator,
        StreamingGeometrySimplifier.Monitor monitor,
        StreamingGeometrySimplifier<T> innerSimplifier
    )
    
    /**
     * Simplifies an entire geometry in a non-streaming fashion
     * @param geometry the geometry to simplify
     * @return simplified geometry with at most maxPoints vertices
     */
    public abstract T simplify(T geometry);
    
    /**
     * Resets internal memory for reusing simplifier instance
     * Call before processing new geometry to clear previous state
     */
    public void reset();
}

/**
 * Streaming geometry simplifier that processes coordinates one at a time
 * Maintains only a fixed-size buffer of points, making it very memory efficient
 * @param <T> the geometry type to produce
 */
public class StreamingGeometrySimplifier<T extends Geometry> {
    
    /**
     * Monitor interface for tracking simplification progress
     */
    public interface Monitor {
        /**
         * Called when simplification starts
         * @param description simplification description
         * @param maxPoints maximum points allowed
         */
        void startSimplification(String description, int maxPoints);
        
        /**
         * Called when simplification completes
         * @param description simplification description  
         * @param finalPoints actual number of points in result
         */
        void endSimplification(String description, int finalPoints);
    }
    
    /**
     * Creates a streaming simplifier
     * @param maxPoints maximum points to retain
     * @param calculator error calculator for point selection
     * @param monitor optional progress monitor
     */
    public StreamingGeometrySimplifier(
        int maxPoints,
        SimplificationErrorCalculator calculator,
        Monitor monitor
    )
    
    /**
     * Adds a coordinate point to the simplification buffer
     * @param x longitude coordinate
     * @param y latitude coordinate
     * @param z altitude coordinate (can be NaN)
     */
    public void addPoint(double x, double y, double z);
    
    /**
     * Finalizes simplification and produces the simplified geometry
     * @return simplified geometry containing the most important points
     */
    public T finish();
    
    /**
     * Resets the simplifier for processing new coordinate sequence
     */
    public void reset();
}

/**
 * Interface for calculating the error introduced by removing a point
 * Uses triangle-based error calculation with three consecutive points
 */
public interface SimplificationErrorCalculator {
    
    /**
     * Represents a point with coordinates for error calculation
     */
    interface PointLike {
        /**
         * @return x coordinate (longitude)
         */
        double x();
        
        /**
         * @return y coordinate (latitude)
         */
        double y();
    }
    
    /**
     * Calculates the error introduced by removing the middle point
     * @param left the point before the candidate for removal
     * @param middle the point candidate for removal
     * @param right the point after the candidate for removal
     * @return error value (higher values indicate more important points)
     */
    double calculateError(PointLike left, PointLike middle, PointLike right);
    
    /**
     * Gets error calculator by name
     * @param calculatorName name of the calculator implementation
     * @return corresponding calculator instance
     * @throws IllegalArgumentException if calculator name is unknown
     */
    static SimplificationErrorCalculator byName(String calculatorName);
    
    // Built-in calculator implementations
    SimplificationErrorCalculator CARTESIAN_TRIANGLE_AREA = new CartesianTriangleAreaCalculator();
    SimplificationErrorCalculator TRIANGLE_AREA = new TriangleAreaCalculator();
    SimplificationErrorCalculator TRIANGLE_HEIGHT = new TriangleHeightCalculator();
    SimplificationErrorCalculator HEIGHT_AND_BACKPATH_DISTANCE = new CartesianHeightAndBackpathDistanceCalculator();
    SimplificationErrorCalculator SPHERICAL_HEIGHT_AND_BACKPATH_DISTANCE = new SphericalHeightAndBackpathDistanceCalculator();
    
    /**
     * Called when simplification ends to allow cleanup
     * @param points final point list
     */
    default void endSimplification(List<PointLike> points) {}
}

/**
 * Utility class providing fast approximations for mathematical calculations
 * Used in simplification algorithms where performance is more important than precision
 */
public class SloppyMath {
    
    /**
     * Fast approximation of distance between two points
     * @param x1 first point longitude
     * @param y1 first point latitude  
     * @param x2 second point longitude
     * @param y2 second point latitude
     * @return approximate distance
     */
    public static double distance(double x1, double y1, double x2, double y2);
    
    /**
     * Fast approximation of haversine distance for geographic coordinates
     * @param lat1 first point latitude in degrees
     * @param lon1 first point longitude in degrees
     * @param lat2 second point latitude in degrees  
     * @param lon2 second point longitude in degrees
     * @return approximate distance in meters
     */
    public static double haversinMeters(double lat1, double lon1, double lat2, double lon2);
    
    // Additional fast mathematical approximations for geometric calculations
}

/**
 * Error calculator that uses triangle area as error metric
 * Points that form larger triangles have higher error (more important)
 */
public class TriangleAreaErrorCalculator implements SimplificationErrorCalculator {
    
    @Override
    public double calculateError(List<PointLike> points, int index) {
        if (index <= 0 || index >= points.size() - 1) {
            return Double.MAX_VALUE; // Don't remove endpoints
        }
        
        PointLike prev = points.get(index - 1);
        PointLike curr = points.get(index);
        PointLike next = points.get(index + 1);
        
        // Calculate triangle area using cross product
        double area = Math.abs(
            (prev.getX() - next.getX()) * (curr.getY() - next.getY()) -
            (next.getX() - curr.getX()) * (prev.getY() - next.getY())
        ) / 2.0;
        
        return area;
    }
}

/**
 * Error calculator based on perpendicular distance to line segment
 * Points farther from the line formed by neighbors have higher error
 */
public class PerpendicularDistanceErrorCalculator implements SimplificationErrorCalculator {
    
    @Override
    public double calculateError(List<PointLike> points, int index) {
        if (index <= 0 || index >= points.size() - 1) {
            return Double.MAX_VALUE; // Don't remove endpoints
        }
        
        PointLike prev = points.get(index - 1);
        PointLike curr = points.get(index);
        PointLike next = points.get(index + 1);
        
        // Calculate perpendicular distance from curr to line prev-next
        return perpendicularDistance(
            curr.getX(), curr.getY(),
            prev.getX(), prev.getY(),
            next.getX(), next.getY()
        );
    }
    
    private double perpendicularDistance(double px, double py, 
                                       double x1, double y1, 
                                       double x2, double y2) {
        double dx = x2 - x1;
        double dy = y2 - y1;
        
        if (dx == 0 && dy == 0) {
            // Line segment is a point
            return SloppyMath.distance(px, py, x1, y1);
        }
        
        double t = ((px - x1) * dx + (py - y1) * dy) / (dx * dx + dy * dy);
        t = Math.max(0, Math.min(1, t)); // Clamp to line segment
        
        double projX = x1 + t * dx;
        double projY = y1 + t * dy;
        
        return SloppyMath.distance(px, py, projX, projY);
    }
}

/**
 * Example line simplifier implementation
 */
public class LineSimplifier extends GeometrySimplifier<Line> {
    
    public LineSimplifier(int maxPoints, SimplificationErrorCalculator calculator, Monitor monitor) {
        super("Line Simplification", maxPoints, calculator, monitor);
    }
    
    @Override
    public Line simplify(Line line) {
        if (line.isEmpty() || line.length() <= maxPoints) {
            return line; // No simplification needed
        }
        
        // Use streaming simplifier for memory efficiency
        StreamingGeometrySimplifier<Line> streaming = 
            new StreamingGeometrySimplifier<>(maxPoints, calculator, monitor);
            
        // Add all points to streaming simplifier
        for (int i = 0; i < line.length(); i++) {
            streaming.addPoint(line.getX(i), line.getY(i), line.getZ(i));
        }
        
        return streaming.finish();
    }
}

/**
 * Example polygon simplifier that handles shells and holes
 */
public class PolygonSimplifier extends GeometrySimplifier<Polygon> {
    
    public PolygonSimplifier(int maxPoints, SimplificationErrorCalculator calculator, Monitor monitor) {
        super("Polygon Simplification", maxPoints, calculator, monitor);
    }
    
    @Override
    public Polygon simplify(Polygon polygon) {
        if (polygon.isEmpty()) {
            return polygon;
        }
        
        LinearRing shell = polygon.getPolygon();
        int totalPoints = shell.length();
        
        // Count total points in all holes
        for (int i = 0; i < polygon.getNumberOfHoles(); i++) {
            totalPoints += polygon.getHole(i).length();
        }
        
        if (totalPoints <= maxPoints) {
            return polygon; // No simplification needed
        }
        
        // Allocate points proportionally
        int shellPoints = Math.max(4, (shell.length() * maxPoints) / totalPoints);
        LinearRing simplifiedShell = simplifyRing(shell, shellPoints);
        
        // Simplify holes proportionally
        List<LinearRing> simplifiedHoles = new ArrayList<>();
        int remainingPoints = maxPoints - simplifiedShell.length();
        
        for (int i = 0; i < polygon.getNumberOfHoles() && remainingPoints > 0; i++) {
            LinearRing hole = polygon.getHole(i);
            int holePoints = Math.max(4, Math.min(remainingPoints, 
                (hole.length() * maxPoints) / totalPoints));
            
            LinearRing simplifiedHole = simplifyRing(hole, holePoints);
            simplifiedHoles.add(simplifiedHole);
            remainingPoints -= simplifiedHole.length();
        }
        
        return new Polygon(simplifiedShell, simplifiedHoles);
    }
    
    private LinearRing simplifyRing(LinearRing ring, int targetPoints) {
        if (ring.length() <= targetPoints) {
            return ring;
        }
        
        // Use streaming simplifier for the ring
        StreamingGeometrySimplifier<Line> streaming = 
            new StreamingGeometrySimplifier<>(targetPoints, calculator, monitor);
            
        for (int i = 0; i < ring.length(); i++) {
            streaming.addPoint(ring.getX(i), ring.getY(i), ring.getZ(i));
        }
        
        Line simplifiedLine = streaming.finish();
        
        // Convert back to LinearRing (ensure closure)
        double[] x = simplifiedLine.getX();
        double[] y = simplifiedLine.getY();
        double[] z = simplifiedLine.getZ();
        
        // Ensure ring is closed
        if (x[0] != x[x.length - 1] || y[0] != y[y.length - 1] || 
            (z != null && z[0] != z[z.length - 1])) {
            // Add closing point
            x = Arrays.copyOf(x, x.length + 1);
            y = Arrays.copyOf(y, y.length + 1);
            x[x.length - 1] = x[0];
            y[y.length - 1] = y[0];
            
            if (z != null) {
                z = Arrays.copyOf(z, z.length + 1);
                z[z.length - 1] = z[0];
            }
        }
        
        return new LinearRing(x, y, z);
    }
}

import org.elasticsearch.geometry.*;
import org.elasticsearch.geometry.simplify.*;

// Create a complex line with many points
double[] lons = new double[1000];
double[] lats = new double[1000];
for (int i = 0; i < 1000; i++) {
    lons[i] = -74.0 + (i * 0.001); // Incremental longitude
    lats[i] = 40.7 + Math.sin(i * 0.1) * 0.01; // Wavy latitude
}
Line complexLine = new Line(lons, lats);

// Create simplifier with triangle area error calculator
SimplificationErrorCalculator calculator = new TriangleAreaErrorCalculator();
LineSimplifier simplifier = new LineSimplifier(100, calculator, null);

// Simplify the line
Line simplifiedLine = simplifier.simplify(complexLine);

System.out.println("Original points: " + complexLine.length()); // 1000
System.out.println("Simplified points: " + simplifiedLine.length()); // <= 100

// Reuse simplifier for another line
simplifier.reset();
Line anotherSimplified = simplifier.simplify(anotherComplexLine);

// Create monitoring implementation
StreamingGeometrySimplifier.Monitor monitor = new StreamingGeometrySimplifier.Monitor() {
    @Override
    public void startSimplification(String description, int maxPoints) {
        System.out.println("Starting " + description + " with max " + maxPoints + " points");
    }
    
    @Override
    public void endSimplification(String description, int finalPoints) {
        System.out.println("Completed " + description + " with " + finalPoints + " points");
    }
};

// Create complex polygon
double[] shellLons = new double[500];
double[] shellLats = new double[500];
// ... populate arrays with complex polygon boundary

LinearRing shell = new LinearRing(shellLons, shellLats);
Polygon complexPolygon = new Polygon(shell);

// Simplify with monitoring
SimplificationErrorCalculator calculator = new PerpendicularDistanceErrorCalculator();
PolygonSimplifier polygonSimplifier = new PolygonSimplifier(50, calculator, monitor);

Polygon simplified = polygonSimplifier.simplify(complexPolygon);
// Output: "Starting Polygon Simplification with max 50 points"
// Output: "Completed Polygon Simplification with 47 points"

// Direct use of streaming simplifier for coordinate streams
SimplificationErrorCalculator calculator = new TriangleAreaErrorCalculator();
StreamingGeometrySimplifier<Line> streaming = 
    new StreamingGeometrySimplifier<>(100, calculator, null);

// Process coordinates from external source (file, network, etc.)
BufferedReader coordSource = // ... coordinate source
String coordLine;
while ((coordLine = coordSource.readLine()) != null) {
    String[] parts = coordLine.split(",");
    double lon = Double.parseDouble(parts[0]);
    double lat = Double.parseDouble(parts[1]);
    
    streaming.addPoint(lon, lat, Double.NaN);
}

// Get simplified result
Line streamingResult = streaming.finish();

System.out.println("Streaming simplified to: " + streamingResult.length() + " points");

// Create custom error calculator that considers geographic distance
public class GeographicErrorCalculator implements SimplificationErrorCalculator {
    
    @Override
    public double calculateError(List<PointLike> points, int index) {
        if (index <= 0 || index >= points.size() - 1) {
            return Double.MAX_VALUE;
        }
        
        PointLike prev = points.get(index - 1);
        PointLike curr = points.get(index);
        PointLike next = points.get(index + 1);
        
        // Use haversine distance for geographic accuracy
        double distToPrev = SloppyMath.haversinMeters(
            curr.getY(), curr.getX(), prev.getY(), prev.getX());
        double distToNext = SloppyMath.haversinMeters(
            curr.getY(), curr.getX(), next.getY(), next.getX());
        double directDist = SloppyMath.haversinMeters(
            prev.getY(), prev.getX(), next.getY(), next.getX());
            
        // Error is the difference between going through curr vs. direct
        return (distToPrev + distToNext) - directDist;
    }
}

// Use custom calculator
GeographicErrorCalculator geoCalculator = new GeographicErrorCalculator();
LineSimplifier geoSimplifier = new LineSimplifier(100, geoCalculator, null);