package gecaoji;

import java.awt.AlphaComposite;
import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Composite;
import java.awt.Graphics2D;
import java.awt.Paint;
import java.awt.Rectangle;
import java.awt.RenderingHints;
import java.awt.Shape;
import java.awt.geom.AffineTransform;
import java.awt.geom.Area;
import java.awt.geom.Ellipse2D;
import java.awt.geom.Path2D;
import java.awt.geom.PathIterator;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.awt.image.BufferedImage;
import java.util.ArrayList;
import java.util.List;

/**
 * 工具类：负责绘制割草完成路径覆盖效果，并提供一系列增强调优能力。
 */
public final class gecaolunjing {
    // 深绿色：用于显示割完的区域
    private static final Color COVERAGE_FILL_COLOR = new Color(0, 100, 0, 150); // 深绿色，半透明
    private static final Color COVERAGE_BORDER_COLOR = new Color(0, 80, 0, 200); // 更深的绿色边框
    private static final Color COVERAGE_PATH_COLOR = new Color(0, 90, 0, 204); // 路径颜色

    private static final double MIN_WIDTH_METERS = 0.3d;
    private static final CoverageState STATE = new CoverageState();

    private gecaolunjing() {
    }

    /**
     * 渲染割草覆盖。
     */
    public static void draw(Graphics2D g2d,
                            List<Point2D.Double> track,
                            double effectiveWidthMeters,
                            Path2D.Double boundaryPath) {
        if (g2d == null || track == null || track.size() < 2) {
            return;
        }

        double coverageWidth = effectiveWidthMeters > 0 ? effectiveWidthMeters : MIN_WIDTH_METERS;
        coverageWidth = Math.max(coverageWidth, MIN_WIDTH_METERS);
        Rectangle clipBounds = ensureClipBounds(g2d);
        if (clipBounds == null || clipBounds.isEmpty()) {
            return;
        }

        STATE.ensureBackBuffer(clipBounds, g2d.getTransform());

    CoverageUpdate update = STATE.update(track, coverageWidth, boundaryPath);

        if (update.needsRender()) {
            Graphics2D bufferGraphics = STATE.createBufferGraphics(g2d);
            if (bufferGraphics != null) {
                try {
                    STATE.renderToBuffer(bufferGraphics, boundaryPath, coverageWidth, update);
                } finally {
                    bufferGraphics.dispose();
                }
            }
        }

        STATE.flushToScreen(g2d, update.getDirtyBounds());
        drawCenterPath(g2d, STATE.getDisplayPath(), (float) coverageWidth);
    }

    private static Rectangle ensureClipBounds(Graphics2D g2d) {
        Rectangle clip = g2d.getClipBounds();
        if (clip != null) {
            return clip;
        }
        Rectangle deviceBounds = g2d.getDeviceConfiguration() != null
                ? g2d.getDeviceConfiguration().getBounds()
                : null;
        if (deviceBounds == null) {
            return null;
        }
        return deviceBounds;
    }

    private static void drawCenterPath(Graphics2D g2d, Path2D.Double path, float coverageWidth) {
        if (path == null) {
            return;
        }
        StrokeSnapshot snapshot = new StrokeSnapshot(g2d);
        g2d.setStroke(new BasicStroke(Math.max(coverageWidth, 0.1f), BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND));
        g2d.setColor(COVERAGE_PATH_COLOR);
        g2d.draw(path);
        snapshot.restoreAll(g2d);
    }

    private static double computeDeviceScale(AffineTransform transform) {
        double sx = Math.hypot(transform.getScaleX(), transform.getShearX());
        double sy = Math.hypot(transform.getScaleY(), transform.getShearY());
        if (sx <= 0.0d || sy <= 0.0d) {
            return 1.0d;
        }
        return Math.sqrt(sx * sy);
    }

    private static Rectangle transformRect(AffineTransform transform, Rectangle2D bounds) {
        if (bounds == null || transform == null) {
            return null;
        }
        Point2D.Double p1 = new Point2D.Double(bounds.getMinX(), bounds.getMinY());
        Point2D.Double p2 = new Point2D.Double(bounds.getMaxX(), bounds.getMinY());
        Point2D.Double p3 = new Point2D.Double(bounds.getMaxX(), bounds.getMaxY());
        Point2D.Double p4 = new Point2D.Double(bounds.getMinX(), bounds.getMaxY());
        Point2D tp1 = transform.transform(p1, null);
        Point2D tp2 = transform.transform(p2, null);
        Point2D tp3 = transform.transform(p3, null);
        Point2D tp4 = transform.transform(p4, null);
        double minX = Math.min(Math.min(tp1.getX(), tp2.getX()), Math.min(tp3.getX(), tp4.getX()));
        double maxX = Math.max(Math.max(tp1.getX(), tp2.getX()), Math.max(tp3.getX(), tp4.getX()));
        double minY = Math.min(Math.min(tp1.getY(), tp2.getY()), Math.min(tp3.getY(), tp4.getY()));
        double maxY = Math.max(Math.max(tp1.getY(), tp2.getY()), Math.max(tp3.getY(), tp4.getY()));
        int x = (int) Math.floor(minX);
        int y = (int) Math.floor(minY);
        int w = (int) Math.ceil(maxX - minX);
        int h = (int) Math.ceil(maxY - minY);
        return new Rectangle(x, y, Math.max(w, 1), Math.max(h, 1));
    }

    private static Rectangle2D expandBounds(Rectangle2D bounds, double padding) {
        if (bounds == null) {
            return null;
        }
        double pad = Math.max(padding, 0.05d);
        return new Rectangle2D.Double(
                bounds.getX() - pad,
                bounds.getY() - pad,
                bounds.getWidth() + pad * 2.0d,
                bounds.getHeight() + pad * 2.0d
        );
    }

    private static final class CoverageState {
        private static final double STORAGE_POINT_DISTANCE_THRESHOLD = 0.1d;
        private static final double SIMPLIFY_TOLERANCE_METERS = 0.05d;
        private static final long SIMPLIFY_INTERVAL_MS = 1_000L;

        private final List<Point2D.Double> highFrequencyPoints = new ArrayList<>();
        private final List<Point2D.Double> storagePoints = new ArrayList<>();

        private Area storageCoverageArea = new Area();
        private Area incrementalCoverageArea = new Area();
        private Area combinedCoverageArea = new Area();
        private Path2D.Double displayPath;

        private int processedRawCount;
        private long lastSimplifyTimeMillis;
        private boolean fullRedrawNeeded = true;
        private double lastCoverageWidthMeters = -1.0d;
        private PathSignature lastBoundarySignature = PathSignature.empty();

        private BufferedImage backBuffer;
        private Rectangle bufferBounds = new Rectangle();
        private AffineTransform bufferTransform = new AffineTransform();

    CoverageUpdate update(List<Point2D.Double> track,
                  double coverageWidth,
                  Path2D.Double boundaryPath) {
            long now = System.currentTimeMillis();
            if (lastSimplifyTimeMillis == 0L) {
                lastSimplifyTimeMillis = now;
            }

            PathSignature currentBoundarySignature = PathSignature.from(boundaryPath);

            if (track == null) {
                if (!combinedCoverageArea.isEmpty() || !storagePoints.isEmpty() || !highFrequencyPoints.isEmpty()) {
                    resetState();
                    lastBoundarySignature = currentBoundarySignature;
                    return CoverageUpdate.fullRedrawRequired(new Area(), true);
                }
                lastBoundarySignature = currentBoundarySignature;
                return CoverageUpdate.noChange();
            }

            if (!currentBoundarySignature.equals(lastBoundarySignature)) {
                resetState();
                lastBoundarySignature = currentBoundarySignature;
            }

            boolean widthChanged = lastCoverageWidthMeters > 0.0d
                    && Double.compare(coverageWidth, lastCoverageWidthMeters) != 0;
            if (widthChanged) {
                resetState();
            }
            lastCoverageWidthMeters = coverageWidth;

            if (track.size() < processedRawCount) {
                resetState();
            }

            if (track.isEmpty()) {
                if (!combinedCoverageArea.isEmpty()) {
                    resetState();
                    lastBoundarySignature = currentBoundarySignature;
                    return CoverageUpdate.fullRedrawRequired(new Area(), true);
                }
                displayPath = null;
                lastBoundarySignature = currentBoundarySignature;
                return CoverageUpdate.noChange();
            }

            Area boundaryArea = boundaryPath != null ? new Area(boundaryPath) : null;

            Rectangle2D dirtyBounds = null;
            boolean changed = false;

            for (int i = processedRawCount; i < track.size(); i++) {
                Point2D.Double incoming = track.get(i);
                if (!isValidPoint(incoming)) {
                    continue;
                }
                Rectangle2D segmentDirty = addHighFrequencyPoint(copyPoint(incoming), coverageWidth, boundaryArea);
                if (segmentDirty != null) {
                    dirtyBounds = unionBounds(dirtyBounds, segmentDirty);
                    changed = true;
                }
            }
            processedRawCount = track.size();

            boolean shouldSimplify = (now - lastSimplifyTimeMillis) >= SIMPLIFY_INTERVAL_MS;
            if (shouldSimplify) {
                boolean recomputed = simplifyAndRebuild(coverageWidth, boundaryArea);
                if (recomputed) {
                    dirtyBounds = unionBounds(dirtyBounds, storageCoverageArea.getBounds2D());
                    changed = true;
                    fullRedrawNeeded = true;
                }
                lastSimplifyTimeMillis = now;
            }

            displayPath = buildPath(track);

            if (!changed && !fullRedrawNeeded) {
                lastBoundarySignature = currentBoundarySignature;
                return CoverageUpdate.noChange();
            }

            Area snapshot = new Area(combinedCoverageArea);
            Rectangle2D effectiveDirty = dirtyBounds != null ? dirtyBounds : snapshot.getBounds2D();
            Rectangle2D expandedDirty = expandBounds(effectiveDirty, coverageWidth * 0.5d);
            CoverageUpdate result = CoverageUpdate.changed(snapshot, expandedDirty, fullRedrawNeeded);
            fullRedrawNeeded = false;
            lastBoundarySignature = currentBoundarySignature;
            return result;
        }

        void ensureBackBuffer(Rectangle clipBounds, AffineTransform currentTransform) {
            if (clipBounds == null || clipBounds.isEmpty()) {
                return;
            }
            if (backBuffer == null
                    || bufferBounds.width != clipBounds.width
                    || bufferBounds.height != clipBounds.height) {
                backBuffer = new BufferedImage(Math.max(1, clipBounds.width), Math.max(1, clipBounds.height), BufferedImage.TYPE_INT_ARGB);
                bufferBounds = new Rectangle(0, 0, clipBounds.width, clipBounds.height);
                fullRedrawNeeded = true;
            }
            bufferTransform = new AffineTransform(currentTransform);
        }

        Graphics2D createBufferGraphics(Graphics2D template) {
            if (backBuffer == null) {
                return null;
            }
            Graphics2D g2d = backBuffer.createGraphics();
            g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
            g2d.setRenderingHint(RenderingHints.KEY_RENDERING, RenderingHints.VALUE_RENDER_QUALITY);
            g2d.setTransform(new AffineTransform());
            g2d.setClip(null);
            return g2d;
        }

        void renderToBuffer(Graphics2D g2d,
                             Path2D.Double boundaryPath,
                             double coverageWidth,
                             CoverageUpdate update) {
            if (backBuffer == null) {
                return;
            }
            Rectangle2D dirtyWorld = update.getDirtyBounds();
            Rectangle dirtyDevice = update.isFullRedraw()
                    ? new Rectangle(0, 0, backBuffer.getWidth(), backBuffer.getHeight())
                    : transformRect(bufferTransform, dirtyWorld);
            if (dirtyDevice == null) {
                dirtyDevice = new Rectangle(0, 0, backBuffer.getWidth(), backBuffer.getHeight());
            }

            g2d.setComposite(AlphaComposite.Clear);
            g2d.fillRect(dirtyDevice.x, dirtyDevice.y, dirtyDevice.width, dirtyDevice.height);
            g2d.setComposite(AlphaComposite.SrcOver);

            Area areaSnapshot = update.getAreaSnapshot();
            if (areaSnapshot == null || areaSnapshot.isEmpty()) {
                return;
            }

            Area deviceArea = areaSnapshot.createTransformedArea(bufferTransform);
            if (boundaryPath != null) {
                Shape deviceBoundaryShape = bufferTransform.createTransformedShape(boundaryPath);
                Area deviceBoundary = new Area(deviceBoundaryShape);
                deviceArea.intersect(deviceBoundary);
            }

            Shape previousClip = g2d.getClip();
            g2d.setClip(dirtyDevice);

            float pixelCoverageWidth = (float) (coverageWidth * computeDeviceScale(bufferTransform));
            g2d.setComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, 0.35f));
            g2d.setPaint(COVERAGE_FILL_COLOR);
            g2d.fill(deviceArea);

            g2d.setComposite(AlphaComposite.SrcOver);
            float outlineWidth = Math.max(pixelCoverageWidth * 0.25f, 1.0f);
            g2d.setStroke(new BasicStroke(outlineWidth, BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND));
            g2d.setColor(COVERAGE_BORDER_COLOR);
            g2d.draw(deviceArea);

            g2d.setClip(previousClip);
        }

        void flushToScreen(Graphics2D screen, Rectangle2D dirtyWorld) {
            if (backBuffer == null) {
                return;
            }
            StrokeSnapshot snapshot = new StrokeSnapshot(screen);
            AffineTransform originalTransform = screen.getTransform();
            Shape originalClip = screen.getClip();
            try {
                screen.setTransform(new AffineTransform());
                if (dirtyWorld != null) {
                    Rectangle dirtyDevice = transformRect(bufferTransform, dirtyWorld);
                    if (dirtyDevice != null) {
                        screen.setClip(dirtyDevice);
                    }
                }
                screen.drawImage(backBuffer, bufferBounds.x, bufferBounds.y, null);
            } finally {
                screen.setTransform(originalTransform);
                screen.setClip(originalClip);
                snapshot.restoreComposite(screen);
            }
        }

        Path2D.Double getDisplayPath() {
            return displayPath;
        }

        private Rectangle2D addHighFrequencyPoint(Point2D.Double point,
                                                  double coverageWidth,
                                                  Area boundaryArea) {
            Point2D.Double previous = highFrequencyPoints.isEmpty()
                    ? (storagePoints.isEmpty() ? null : storagePoints.get(storagePoints.size() - 1))
                    : highFrequencyPoints.get(highFrequencyPoints.size() - 1);

            highFrequencyPoints.add(point);
            maybeAddToStorage(point);

            Area segmentArea = previous == null
                    ? buildSegmentArea(point, point, coverageWidth)
                    : buildSegmentArea(previous, point, coverageWidth);
            if (segmentArea == null || segmentArea.isEmpty()) {
                updateCombinedArea(boundaryArea);
                return null;
            }
            if (boundaryArea != null) {
                segmentArea.intersect(boundaryArea);
                if (segmentArea.isEmpty()) {
                    updateCombinedArea(boundaryArea);
                    return null;
                }
            }
            incrementalCoverageArea.add(segmentArea);
            updateCombinedArea(boundaryArea);
            return segmentArea.getBounds2D();
        }

        private void maybeAddToStorage(Point2D.Double point) {
            if (point == null) {
                return;
            }
            if (storagePoints.isEmpty()) {
                storagePoints.add(copyPoint(point));
                return;
            }
            Point2D.Double last = storagePoints.get(storagePoints.size() - 1);
            if (distance(last, point) >= STORAGE_POINT_DISTANCE_THRESHOLD) {
                storagePoints.add(copyPoint(point));
            }
        }

        private boolean simplifyAndRebuild(double coverageWidth, Area boundaryArea) {
            boolean merged = mergeHighFrequencyIntoStorage();
            boolean simplified = simplifyStoragePoints();
            boolean hasPendingIncremental = !incrementalCoverageArea.isEmpty();
            if (!merged && !simplified && !hasPendingIncremental) {
                return false;
            }
            storageCoverageArea = buildAreaFromPoints(storagePoints, coverageWidth, boundaryArea);
            incrementalCoverageArea = rebuildIncrementalArea(coverageWidth, boundaryArea);
            updateCombinedArea(boundaryArea);
            return true;
        }

        private boolean mergeHighFrequencyIntoStorage() {
            if (highFrequencyPoints.size() <= 1) {
                return false;
            }
            boolean modified = false;
            List<Point2D.Double> retained = new ArrayList<>();
            Point2D.Double lastStorage = storagePoints.isEmpty() ? null : storagePoints.get(storagePoints.size() - 1);
            int lastIndex = highFrequencyPoints.size() - 1;
            for (int i = 0; i < highFrequencyPoints.size(); i++) {
                Point2D.Double candidate = highFrequencyPoints.get(i);
                if (!isValidPoint(candidate)) {
                    continue;
                }
                boolean isAnchor = i == lastIndex;
                boolean stored = false;
                if (!isAnchor) {
                    double gap = distance(lastStorage, candidate);
                    if (lastStorage == null || gap >= STORAGE_POINT_DISTANCE_THRESHOLD) {
                        Point2D.Double copy = copyPoint(candidate);
                        storagePoints.add(copy);
                        lastStorage = copy;
                        modified = true;
                        stored = true;
                    }
                }
                if (isAnchor || !stored) {
                    retained.add(copyPoint(candidate));
                }
            }
            highFrequencyPoints.clear();
            highFrequencyPoints.addAll(retained);
            return modified;
        }

        private boolean simplifyStoragePoints() {
            if (storagePoints.size() < 3) {
                return false;
            }
            List<Point2D.Double> simplified = DouglasPeucker.simplify(storagePoints, SIMPLIFY_TOLERANCE_METERS);
            if (simplified.size() == storagePoints.size()) {
                boolean identical = true;
                for (int i = 0; i < simplified.size(); i++) {
                    if (!pointsEqual(storagePoints.get(i), simplified.get(i))) {
                        identical = false;
                        break;
                    }
                }
                if (identical) {
                    return false;
                }
            }
            storagePoints.clear();
            for (Point2D.Double point : simplified) {
                storagePoints.add(copyPoint(point));
            }
            return true;
        }

        private Area rebuildIncrementalArea(double coverageWidth, Area boundaryArea) {
            Area result = new Area();
            if (highFrequencyPoints.isEmpty()) {
                return result;
            }
            Point2D.Double previous = storagePoints.isEmpty()
                    ? highFrequencyPoints.get(0)
                    : storagePoints.get(storagePoints.size() - 1);

            if (storagePoints.isEmpty() && previous != null) {
                Area anchorArea = buildSegmentArea(previous, previous, coverageWidth);
                if (anchorArea != null && !anchorArea.isEmpty()) {
                    if (boundaryArea != null) {
                        anchorArea.intersect(boundaryArea);
                    }
                    if (!anchorArea.isEmpty()) {
                        result.add(anchorArea);
                    }
                }
            }

            for (Point2D.Double point : highFrequencyPoints) {
                if (previous == null || point == null) {
                    previous = point;
                    continue;
                }
                if (distance(previous, point) < 1e-6d) {
                    previous = point;
                    continue;
                }
                Area segmentArea = buildSegmentArea(previous, point, coverageWidth);
                if (segmentArea == null || segmentArea.isEmpty()) {
                    previous = point;
                    continue;
                }
                if (boundaryArea != null) {
                    segmentArea.intersect(boundaryArea);
                    if (segmentArea.isEmpty()) {
                        previous = point;
                        continue;
                    }
                }
                result.add(segmentArea);
                previous = point;
            }
            return result;
        }

        private Area buildAreaFromPoints(List<Point2D.Double> points,
                                         double coverageWidth,
                                         Area boundaryArea) {
            Area result = new Area();
            if (points.isEmpty()) {
                return result;
            }
            if (points.size() == 1) {
                Point2D.Double only = points.get(0);
                Area single = buildSegmentArea(only, only, coverageWidth);
                if (single != null && !single.isEmpty()) {
                    if (boundaryArea != null) {
                        single.intersect(boundaryArea);
                    }
                    if (!single.isEmpty()) {
                        result.add(single);
                    }
                }
                return result;
            }
            Point2D.Double previous = points.get(0);
            for (int i = 1; i < points.size(); i++) {
                Point2D.Double current = points.get(i);
                Area segmentArea = buildSegmentArea(previous, current, coverageWidth);
                if (segmentArea == null || segmentArea.isEmpty()) {
                    previous = current;
                    continue;
                }
                if (boundaryArea != null) {
                    segmentArea.intersect(boundaryArea);
                    if (segmentArea.isEmpty()) {
                        previous = current;
                        continue;
                    }
                }
                result.add(segmentArea);
                previous = current;
            }
            return result;
        }

        private void updateCombinedArea(Area boundaryArea) {
            combinedCoverageArea = new Area();
            if (!storageCoverageArea.isEmpty()) {
                Area storageCopy = new Area(storageCoverageArea);
                if (boundaryArea != null) {
                    storageCopy.intersect(new Area(boundaryArea));
                }
                combinedCoverageArea.add(storageCopy);
            }
            if (!incrementalCoverageArea.isEmpty()) {
                Area incrementalCopy = new Area(incrementalCoverageArea);
                if (boundaryArea != null) {
                    incrementalCopy.intersect(new Area(boundaryArea));
                }
                combinedCoverageArea.add(incrementalCopy);
            }
        }

        private void resetState() {
            processedRawCount = 0;
            highFrequencyPoints.clear();
            storagePoints.clear();
            storageCoverageArea = new Area();
            incrementalCoverageArea = new Area();
            combinedCoverageArea = new Area();
            displayPath = null;
            fullRedrawNeeded = true;
            lastCoverageWidthMeters = -1.0d;
            lastSimplifyTimeMillis = 0L;
        }

        private static Area buildSegmentArea(Point2D.Double start,
                                             Point2D.Double end,
                                             double coverageWidth) {
            if (start == null || end == null) {
                return null;
            }
            double halfWidth = Math.max(coverageWidth * 0.5d, 1e-6d);
            double dx = end.x - start.x;
            double dy = end.y - start.y;
            double length = Math.hypot(dx, dy);
            if (length < 1e-6d) {
                double diameter = halfWidth * 2.0d;
                return new Area(new Ellipse2D.Double(start.x - halfWidth, start.y - halfWidth, diameter, diameter));
            }
            double nx = -dy / length;
            double ny = dx / length;
            double offsetX = nx * halfWidth;
            double offsetY = ny * halfWidth;

            Path2D.Double polygon = new Path2D.Double();
            polygon.moveTo(start.x + offsetX, start.y + offsetY);
            polygon.lineTo(start.x - offsetX, start.y - offsetY);
            polygon.lineTo(end.x - offsetX, end.y - offsetY);
            polygon.lineTo(end.x + offsetX, end.y + offsetY);
            polygon.closePath();

            Area result = new Area(polygon);
            double diameter = halfWidth * 2.0d;
            result.add(new Area(new Ellipse2D.Double(start.x - halfWidth, start.y - halfWidth, diameter, diameter)));
            result.add(new Area(new Ellipse2D.Double(end.x - halfWidth, end.y - halfWidth, diameter, diameter)));
            return result;
        }

        private static boolean isValidPoint(Point2D.Double point) {
            return point != null && Double.isFinite(point.x) && Double.isFinite(point.y);
        }

        private static Point2D.Double copyPoint(Point2D.Double point) {
            if (point == null) {
                return null;
            }
            return new Point2D.Double(point.x, point.y);
        }

        private static double distance(Point2D.Double a, Point2D.Double b) {
            if (a == null || b == null) {
                return Double.POSITIVE_INFINITY;
            }
            return Math.hypot(a.x - b.x, a.y - b.y);
        }

        private static boolean pointsEqual(Point2D.Double a, Point2D.Double b) {
            if (a == b) {
                return true;
            }
            if (a == null || b == null) {
                return false;
            }
            return Double.compare(a.x, b.x) == 0 && Double.compare(a.y, b.y) == 0;
        }

        private static Rectangle2D unionBounds(Rectangle2D a, Rectangle2D b) {
            if (a == null) {
                if (b == null) {
                    return null;
                }
                return new Rectangle2D.Double(b.getX(), b.getY(), b.getWidth(), b.getHeight());
            }
            if (b == null) {
                return new Rectangle2D.Double(a.getX(), a.getY(), a.getWidth(), a.getHeight());
            }
            Rectangle2D result = new Rectangle2D.Double();
            Rectangle2D.union(a, b, result);
            return result;
        }

        private static final class PathSignature {
            private final int hash;
            private final Rectangle2D bounds;

            private PathSignature(int hash, Rectangle2D bounds) {
                this.hash = hash;
                this.bounds = bounds;
            }

            static PathSignature from(Path2D.Double path) {
                if (path == null) {
                    return empty();
                }
                Rectangle2D bounds = path.getBounds2D();
                double[] coords = new double[6];
                PathIterator iterator = path.getPathIterator(null);
                int h = 1;
                while (!iterator.isDone()) {
                    int type = iterator.currentSegment(coords);
                    h = 31 * h + type;
                    int coordCount = coordinateCount(type);
                    for (int i = 0; i < coordCount; i++) {
                        h = 31 * h + Double.hashCode(coords[i]);
                    }
                    iterator.next();
                }
                Rectangle2D boundsCopy = bounds == null
                        ? null
                        : new Rectangle2D.Double(bounds.getX(), bounds.getY(), bounds.getWidth(), bounds.getHeight());
                return new PathSignature(h, boundsCopy);
            }

            static PathSignature empty() {
                return new PathSignature(0, null);
            }

            private static int coordinateCount(int segmentType) {
                switch (segmentType) {
                    case PathIterator.SEG_MOVETO:
                    case PathIterator.SEG_LINETO:
                        return 2;
                    case PathIterator.SEG_QUADTO:
                        return 4;
                    case PathIterator.SEG_CUBICTO:
                        return 6;
                    default:
                        return 0;
                }
            }

            @Override
            public boolean equals(Object obj) {
                if (this == obj) {
                    return true;
                }
                if (!(obj instanceof PathSignature)) {
                    return false;
                }
                PathSignature other = (PathSignature) obj;
                if (hash != other.hash) {
                    return false;
                }
                if (bounds == null && other.bounds == null) {
                    return true;
                }
                if (bounds == null || other.bounds == null) {
                    return false;
                }
                return Double.compare(bounds.getX(), other.bounds.getX()) == 0
                        && Double.compare(bounds.getY(), other.bounds.getY()) == 0
                        && Double.compare(bounds.getWidth(), other.bounds.getWidth()) == 0
                        && Double.compare(bounds.getHeight(), other.bounds.getHeight()) == 0;
            }

            @Override
            public int hashCode() {
                int result = hash;
                if (bounds != null) {
                    long bits = Double.doubleToLongBits(bounds.getX());
                    result = 31 * result + (int) (bits ^ (bits >>> 32));
                    bits = Double.doubleToLongBits(bounds.getY());
                    result = 31 * result + (int) (bits ^ (bits >>> 32));
                    bits = Double.doubleToLongBits(bounds.getWidth());
                    result = 31 * result + (int) (bits ^ (bits >>> 32));
                    bits = Double.doubleToLongBits(bounds.getHeight());
                    result = 31 * result + (int) (bits ^ (bits >>> 32));
                }
                return result;
            }
        }
    }

    private static Path2D.Double buildPath(List<Point2D.Double> points) {
        if (points == null || points.size() < 2) {
            return null;
        }
        Path2D.Double path = new Path2D.Double();
        boolean started = false;
        double lastX = Double.NaN;
        double lastY = Double.NaN;
        for (Point2D.Double point : points) {
            if (point == null) {
                continue;
            }
            if (!started) {
                path.moveTo(point.x, point.y);
                lastX = point.x;
                lastY = point.y;
                started = true;
                continue;
            }
            if (Double.compare(point.x, lastX) == 0 && Double.compare(point.y, lastY) == 0) {
                continue;
            }
            path.lineTo(point.x, point.y);
            lastX = point.x;
            lastY = point.y;
        }
        return started ? path : null;
    }

    private static final class DouglasPeucker {
        private DouglasPeucker() {
        }

        static List<Point2D.Double> simplify(List<Point2D.Double> points, double epsilon) {
            if (points == null || points.size() < 3) {
                return new ArrayList<>(points);
            }
            double eps = Math.max(epsilon, 0.01d);
            boolean[] keep = new boolean[points.size()];
            keep[0] = true;
            keep[keep.length - 1] = true;
            simplifySection(points, 0, points.size() - 1, eps * eps, keep);
            List<Point2D.Double> result = new ArrayList<>();
            for (int i = 0; i < points.size(); i++) {
                if (keep[i]) {
                    result.add(points.get(i));
                }
            }
            return result;
        }

        private static void simplifySection(List<Point2D.Double> points,
                                             int start,
                                             int end,
                                             double epsilonSquared,
                                             boolean[] keep) {
            if (end <= start + 1) {
                return;
            }
            Point2D.Double a = points.get(start);
            Point2D.Double b = points.get(end);
            double maxDistance = -1.0d;
            int index = -1;
            for (int i = start + 1; i < end; i++) {
                double distance = perpendicularDistanceSquared(points.get(i), a, b);
                if (distance > maxDistance) {
                    maxDistance = distance;
                    index = i;
                }
            }
            if (maxDistance > epsilonSquared && index > 0) {
                keep[index] = true;
                simplifySection(points, start, index, epsilonSquared, keep);
                simplifySection(points, index, end, epsilonSquared, keep);
            }
        }

        private static double perpendicularDistanceSquared(Point2D.Double point,
                                                            Point2D.Double start,
                                                            Point2D.Double end) {
            double dx = end.x - start.x;
            double dy = end.y - start.y;
            double lengthSquared = dx * dx + dy * dy;
            if (lengthSquared == 0.0d) {
                double rx = point.x - start.x;
                double ry = point.y - start.y;
                return rx * rx + ry * ry;
            }
            double t = ((point.x - start.x) * dx + (point.y - start.y) * dy) / lengthSquared;
            t = Math.max(0.0d, Math.min(1.0d, t));
            double projX = start.x + t * dx;
            double projY = start.y + t * dy;
            double rx = point.x - projX;
            double ry = point.y - projY;
            return rx * rx + ry * ry;
        }
    }

    private static final class CoverageUpdate {
        private final boolean needsRender;
        private final boolean fullRedraw;
        private final Rectangle2D dirtyBounds;
        private final Area areaSnapshot;

        private CoverageUpdate(boolean needsRender,
                               boolean fullRedraw,
                               Rectangle2D dirtyBounds,
                               Area areaSnapshot) {
            this.needsRender = needsRender;
            this.fullRedraw = fullRedraw;
            this.dirtyBounds = dirtyBounds;
            this.areaSnapshot = areaSnapshot;
        }

        static CoverageUpdate noChange() {
            return new CoverageUpdate(false, false, null, null);
        }

        static CoverageUpdate fullRedrawRequired(Area area, boolean required) {
            if (!required) {
                return noChange();
            }
            Area snapshot = area == null ? new Area() : new Area(area);
            Rectangle2D bounds = snapshot.isEmpty() ? new Rectangle2D.Double(0, 0, 0, 0) : snapshot.getBounds2D();
            return new CoverageUpdate(true, true, bounds, snapshot);
        }

        static CoverageUpdate changed(Area areaSnapshot, Rectangle2D dirtyBounds, boolean fullRedraw) {
            return new CoverageUpdate(true, fullRedraw, dirtyBounds, areaSnapshot);
        }

        boolean needsRender() {
            return needsRender;
        }

        boolean isFullRedraw() {
            return fullRedraw;
        }

        Rectangle2D getDirtyBounds() {
            return dirtyBounds;
        }

        Area getAreaSnapshot() {
            return areaSnapshot;
        }
    }

    private static final class StrokeSnapshot {
        private final java.awt.Stroke originalStroke;
        private final Paint originalPaint;
        private final Composite originalComposite;

        StrokeSnapshot(Graphics2D g2d) {
            this.originalStroke = g2d.getStroke();
            this.originalPaint = g2d.getPaint();
            this.originalComposite = g2d.getComposite();
        }

        void restoreComposite(Graphics2D g2d) {
            g2d.setComposite(originalComposite);
        }

        void restoreAll(Graphics2D g2d) {
            g2d.setStroke(originalStroke);
            g2d.setPaint(originalPaint);
            g2d.setComposite(originalComposite);
        }
    }
}