package com.sundablog.clipper;

import com.sundablog.clipper.Clipper.*;
import com.sundablog.clipper.Point.DoublePoint;
import com.sundablog.clipper.Point.LongPoint;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 多边形偏移（Offset）类，用于生成多边形的扩展或收缩版本
 * 支持多种连接类型和端点处理方式，可以创建圆角、斜接或方角效果
 */
public class ClipperOffset {

    /**
     * 判断一个值是否接近零（考虑浮点精度）
     * @param val 需要判断的浮点值
     * @return 如果值接近零返回true，否则返回false
     */
    private static boolean nearZero(double val) {
        return val > -TOLERANCE && val < TOLERANCE;
    }

    // 目标多边形集合，用于存储偏移后的多边形结果
    private Paths destPolys;
    // 源多边形，当前正在处理的多边形
    private Path srcPoly;
    // 当前生成的目标多边形
    private Path destPoly;

    // 存储单位法线向量的列表
    private final List<DoublePoint> normals;
    // 偏移距离、中间计算变量、正弦和余弦值
    private double delta, inA, sin, cos;

    // 斜接限制、每弧度步数
    private double miterLim, stepsPerRad;
    // 存储最低顶点位置
    private LongPoint lowest;

    // 多边形节点树，用于存储添加的多边形及其属性
    private final PolyNode polyNodes;
    // 圆弧公差，控制圆角的精度
    private final double arcTolerance;

    // 斜接限制值
    private final double miterLimit;
    // 2π常量，用于三角函数计算
    private final static double TWO_PI = Math.PI * 2;

    // 默认圆弧公差
    private final static double DEFAULT_ARC_TOLERANCE = 0.25;
    // 浮点数计算容差
    private final static double TOLERANCE = 1.0E-20;

    /**
     * 使用默认参数创建ClipperOffset对象
     * 默认斜接限制为2.0，默认圆弧公差为0.25
     */
    public ClipperOffset() {
        this(2, DEFAULT_ARC_TOLERANCE);
    }

    /**
     * 创建ClipperOffset对象，指定斜接限制和圆弧公差
     * @param miterLimit 斜接限制，控制斜接连接的最大长度
     * @param arcTolerance 圆弧公差，控制圆角的精度，值越小精度越高
     */
    public ClipperOffset(double miterLimit, double arcTolerance) {
        this.miterLimit = miterLimit;
        this.arcTolerance = arcTolerance;
        lowest = new LongPoint();
        lowest.setX(-1L);  // 初始化为-1表示尚未设置
        polyNodes = new PolyNode();
        normals = new ArrayList<>();
    }

    /**
     * 添加一个路径到偏移处理对象
     * @param path 要处理的路径（多边形或线段）
     * @param joinType 连接类型，决定如何处理线段连接处
     * @param endType 端点类型，决定如何处理路径端点
     */
    public void addPath(Path path, JoinType joinType, EndType endType) {
        int highI = path.size() - 1;
        if (highI < 0) {
            return;  // 空路径直接返回
        }
        final PolyNode newNode = new PolyNode();
        newNode.setJoinType(joinType);
        newNode.setEndType(endType);

        // 移除路径中的重复点，并找到最低顶点的索引
        if (endType == EndType.CLOSED_LINE || endType == EndType.CLOSED_POLYGON) {
            while (highI > 0 && path.get(0) == path.get(highI)) {
                highI--;
            }
        }

        newNode.getPolygon().add(path.get(0));
        int j = 0, k = 0;  // j: 当前添加的点索引, k: 最低顶点索引
        for (int i = 1; i <= highI; i++) {
            if (newNode.getPolygon().get(j) != path.get(i)) {
                j++;
                newNode.getPolygon().add(path.get(i));
                // 更新最低顶点索引（Y坐标最大，或者Y相同但X最小的点）
                if (path.get(i).getY() > newNode.getPolygon().get(k).getY() ||
                        path.get(i).getY() == newNode.getPolygon().get(k).getY() &&
                                path.get(i).getX() < newNode.getPolygon().get(k).getX()) {
                    k = j;
                }
            }
        }
        // 对于封闭多边形，如果点数少于3个，则不添加（无法形成多边形）
        if (endType == EndType.CLOSED_POLYGON && j < 2) {
            return;
        }

        polyNodes.addChild(newNode);

        // 如果此路径的最低顶点是所有路径中最低的，则更新最低顶点记录
        if (endType != EndType.CLOSED_POLYGON) {
            return;
        }
        if (lowest.getX() < 0) {
            // 首次设置最低顶点
            lowest = new LongPoint(polyNodes.getChildCount() - 1, k);
        }
        else {
            final LongPoint ip = polyNodes.getChilds().get((int)lowest.getX()).getPolygon().get((int)lowest.getY());
            // 比较并更新最低顶点
            if (newNode.getPolygon().get(k).getY() > ip.getY() ||
                    newNode.getPolygon().get(k).getY() == ip.getY() &&
                            newNode.getPolygon().get(k).getX() < ip.getX()) {
                lowest = new LongPoint(polyNodes.getChildCount() - 1, k);
            }
        }
    }

    /**
     * 批量添加多个路径到偏移处理对象
     * @param paths 要处理的路径列表
     * @param joinType 连接类型，决定如何处理线段连接处
     * @param endType 端点类型，决定如何处理路径端点
     */
    public void addPaths(Paths paths, JoinType joinType, EndType endType) {
        for (final Path p : paths) {
            addPath(p, joinType, endType);
        }
    }

    /**
     * 清空所有添加的路径
     */
    public void clear() {
        polyNodes.getChilds().clear();
        lowest.setX(-1L);  // 重置最低顶点标记
    }

    /**
     * 创建斜接连接（Miter Join）
     * @param j 当前点索引
     * @param k 前一个点索引
     * @param r 计算系数
     */
    private void doMiter(int j, int k, double r) {
        final double q = delta / r;
        // 计算并添加斜接点
        destPoly.add(new LongPoint(
                Math.round(srcPoly.get(j).getX() + (normals.get(k).getX() + normals.get(j).getX()) * q),
                Math.round(srcPoly.get(j).getY() + (normals.get(k).getY() + normals.get(j).getY()) * q)
        ));
    }

    /**
     * 执行多边形偏移的核心方法
     * @param delta 偏移距离，正值表示向外扩展，负值表示向内收缩
     */
    private void doOffset(double delta) {
        destPolys = new Paths();
        this.delta = delta;

        // 如果偏移距离为零，直接复制封闭多边形
        if (nearZero(delta)) {
            for (int i = 0; i < polyNodes.getChildCount(); i++) {
                final PolyNode node = polyNodes.getChilds().get(i);
                if (node.getEndType() == EndType.CLOSED_POLYGON) {
                    destPolys.add(node.getPolygon());
                }
            }
            return;
        }

        // 计算斜接限制系数
        if (miterLimit > 2) {
            miterLim = 2 / (miterLimit * miterLimit);
        }
        else {
            miterLim = 0.5;
        }

        // 计算实际使用的圆弧公差
        double y;
        if (arcTolerance <= 0.0) {
            y = DEFAULT_ARC_TOLERANCE;
        }
        else if (arcTolerance > Math.abs(delta) * DEFAULT_ARC_TOLERANCE) {
            y = Math.abs(delta) * DEFAULT_ARC_TOLERANCE;
        }
        else {
            y = arcTolerance;
        }

        // 计算圆弧细分步数和相关三角函数值
        final double steps = Math.PI / Math.acos(1 - y / Math.abs(delta));
        sin = Math.sin(TWO_PI / steps);
        cos = Math.cos(TWO_PI / steps);
        stepsPerRad = steps / TWO_PI;
        if (delta < 0.0) {
            sin = -sin;  // 向内偏移时反转sin值
        }

        // 处理每个多边形节点
        for (int i = 0; i < polyNodes.getChildCount(); i++) {
            final PolyNode node = polyNodes.getChilds().get(i);
            srcPoly = node.getPolygon();
            final int len = srcPoly.size();

            // 跳过空多边形或向内偏移时的无效多边形
            if (len == 0 || delta <= 0 && (len < 3 || node.getEndType() != EndType.CLOSED_POLYGON)) {
                continue;
            }

            destPoly = new Path();

            // 处理单一点的情况（生成圆形或方形）
            if (len == 1) {
                if (node.getJoinType() == JoinType.ROUND) {
                    // 生成圆形
                    double X = 1.0, Y = 0.0;
                    for (int j = 1; j <= steps; j++) {
                        destPoly.add(new LongPoint(
                                Math.round(srcPoly.get(0).getX() + X * delta),
                                Math.round(srcPoly.get(0).getY() + Y * delta)
                        ));
                        // 使用旋转矩阵更新点坐标
                        final double X2 = X;
                        X = X * cos - sin * Y;
                        Y = X2 * sin + Y * cos;
                    }
                }
                else {
                    // 生成方形
                    double X = -1.0, Y = -1.0;
                    for (int j = 0; j < 4; ++j) {
                        destPoly.add(new LongPoint(
                                Math.round(srcPoly.get(0).getX() + X * delta),
                                Math.round(srcPoly.get(0).getY() + Y * delta)
                        ));
                        // 按顺时针方向更新方形的四个顶点
                        if (X < 0) {
                            X = 1;
                        }
                        else if (Y < 0) {
                            Y = 1;
                        }
                        else {
                            X = -1;
                        }
                    }
                }
                destPolys.add(destPoly);
                continue;
            }

            // 构建单位法线向量列表
            normals.clear();
            for (int j = 0; j < len - 1; j++) {
                normals.add(Point.getUnitNormal(srcPoly.get(j), srcPoly.get(j + 1)));
            }
            // 处理封闭路径或开放路径的最后一个法线
            if (node.getEndType() == EndType.CLOSED_LINE || node.getEndType() == EndType.CLOSED_POLYGON) {
                normals.add(Point.getUnitNormal(srcPoly.get(len - 1), srcPoly.get(0)));
            }
            else {
                normals.add(new DoublePoint(normals.get(len - 2)));
            }

            // 根据路径类型进行不同的偏移处理
            if (node.getEndType() == EndType.CLOSED_POLYGON) {
                // 处理封闭多边形
                final int[] k = new int[] { len - 1 };  // 使用数组作为引用传值
                for (int j = 0; j < len; j++) {
                    offsetPoint(j, k, node.getJoinType());
                }
                destPolys.add(destPoly);
            }
            else if (node.getEndType() == EndType.CLOSED_LINE) {
                // 处理封闭线（环）
                final int[] k = new int[] { len - 1 };
                // 正向偏移
                for (int j = 0; j < len; j++) {
                    offsetPoint(j, k, node.getJoinType());
                }
                destPolys.add(destPoly);

                // 反向偏移生成内部边界
                destPoly = new Path();
                final DoublePoint n = normals.get(len - 1);
                // 反转法线方向
                for (int j = len - 1; j > 0; j--) {
                    normals.set(j, new DoublePoint(-normals.get(j - 1).getX(), -normals.get(j - 1).getY()));
                }
                normals.set(0, new DoublePoint(-n.getX(), -n.getY(), 0));
                k[0] = 0;
                // 反向遍历路径点
                for (int j = len - 1; j >= 0; j--) {
                    offsetPoint(j, k, node.getJoinType());
                }
                destPolys.add(destPoly);
            }
            else {
                // 处理开放路径
                final int[] k = new int[1];
                // 处理中间点
                for (int j = 1; j < len - 1; ++j) {
                    offsetPoint(j, k, node.getJoinType());
                }

                LongPoint pt1;
                // 处理终点
                if (node.getEndType() == EndType.OPEN_BUTT) {
                    // 平端处理
                    final int j = len - 1;
                    pt1 = new LongPoint(
                            Math.round(srcPoly.get(j).getX() + normals.get(j).getX() * delta),
                            Math.round(srcPoly.get(j).getY() + normals.get(j).getY() * delta),
                            0
                    );
                    destPoly.add(pt1);
                    pt1 = new LongPoint(
                            Math.round(srcPoly.get(j).getX() - normals.get(j).getX() * delta),
                            Math.round(srcPoly.get(j).getY() - normals.get(j).getY() * delta),
                            0
                    );
                    destPoly.add(pt1);
                }
                else {
                    // 方端或圆端处理
                    final int j = len - 1;
                    k[0] = len - 2;
                    inA = 0;
                    normals.set(j, new DoublePoint(-normals.get(j).getX(), -normals.get(j).getY()));
                    if (node.getEndType() == EndType.OPEN_SQUARE) {
                        doSquare(j, k[0]);
                    }
                    else {
                        doRound(j, k[0]);
                    }
                }

                // 重新构建法线用于反向偏移
                for (int j = len - 1; j > 0; j--) {
                    normals.set(j, new DoublePoint(-normals.get(j - 1).getX(), -normals.get(j - 1).getY()));
                }
                normals.set(0, new DoublePoint(-normals.get(1).getX(), -normals.get(1).getY()));

                // 处理起始部分
                k[0] = len - 1;
                for (int j = k[0] - 1; j > 0; --j) {
                    offsetPoint(j, k, node.getJoinType());
                }

                // 处理起点
                if (node.getEndType() == EndType.OPEN_BUTT) {
                    pt1 = new LongPoint(
                            Math.round(srcPoly.get(0).getX() - normals.get(0).getX() * delta),
                            Math.round(srcPoly.get(0).getY() - normals.get(0).getY() * delta)
                    );
                    destPoly.add(pt1);
                    pt1 = new LongPoint(
                            Math.round(srcPoly.get(0).getX() + normals.get(0).getX() * delta),
                            Math.round(srcPoly.get(0).getY() + normals.get(0).getY() * delta)
                    );
                    destPoly.add(pt1);
                }
                else {
                    k[0] = 1;
                    inA = 0;
                    if (node.getEndType() == EndType.OPEN_SQUARE) {
                        doSquare(0, 1);
                    }
                    else {
                        doRound(0, 1);
                    }
                }
                destPolys.add(destPoly);
            }
        }
    }

    /**
     * 创建圆角连接
     * @param j 当前点索引
     * @param k 前一个点索引
     */
    private void doRound(int j, int k) {
        // 计算角度
        final double a = Math.atan2(
                inA,
                normals.get(k).getX() * normals.get(j).getX() + normals.get(k).getY() * normals.get(j).getY()
        );
        // 计算需要的步数，确保至少有1步
        final int steps = Math.max((int)Math.round(stepsPerRad * Math.abs(a)), 1);

        // 生成圆弧上的点
        double X = normals.get(k).getX(), Y = normals.get(k).getY(), X2;
        for (int i = 0; i < steps; ++i) {
            destPoly.add(new LongPoint(
                    Math.round(srcPoly.get(j).getX() + X * delta),
                    Math.round(srcPoly.get(j).getY() + Y * delta)
            ));
            // 使用旋转矩阵更新点坐标
            X2 = X;
            X = X * cos - sin * Y;
            Y = X2 * sin + Y * cos;
        }
        // 添加圆弧终点
        destPoly.add(new LongPoint(
                Math.round(srcPoly.get(j).getX() + normals.get(j).getX() * delta),
                Math.round(srcPoly.get(j).getY() + normals.get(j).getY() * delta)
        ));
    }

    /**
     * 创建方角连接
     * @param j 当前点索引
     * @param k 前一个点索引
     */
    private void doSquare(int j, int k) {
        // 提取相关坐标和法线分量
        final double nkx = normals.get(k).getX();
        final double nky = normals.get(k).getY();
        final double njx = normals.get(j).getX();
        final double njy = normals.get(j).getY();
        final double sjx = srcPoly.get(j).getX();
        final double sjy = srcPoly.get(j).getY();
        // 计算方角的偏移量
        final double dx = Math.tan(Math.atan2(inA, nkx * njx + nky * njy) / 4);
        // 添加方角的两个点
        destPoly.add(new LongPoint(
                Math.round(sjx + delta * (nkx - nky * dx)),
                Math.round(sjy + delta * (nky + nkx * dx)),
                0
        ));
        destPoly.add(new LongPoint(
                Math.round(sjx + delta * (njx + njy * dx)),
                Math.round(sjy + delta * (njy - njx * dx)),
                0
        ));
    }

    /**
     * 执行偏移操作，将结果输出到Paths对象
     * @param solution 用于存储结果的Paths对象
     * @param delta 偏移距离，正值表示向外扩展，负值表示向内收缩
     */
    public void execute(Paths solution, double delta) {
        solution.clear();
        // 修复多边形方向
        fixOrientations();
        // 执行实际偏移计算
        doOffset(delta);

        // 清理并优化结果多边形（特别是处理角落部分）
        final DefaultClipper clpr = new DefaultClipper(Clipper.REVERSE_SOLUTION);
        clpr.addPaths(destPolys, PolyType.SUBJECT, true);

        if (delta > 0) {
            // 向外偏移，使用并集操作
            clpr.execute(ClipType.UNION, solution, PolyFillType.POSITIVE, PolyFillType.POSITIVE);
        }
        else {
            // 向内偏移，需要特殊处理
            final LongRect r = destPolys.getBounds();
            // 创建一个包围盒
            final Path outer = new Path(4);
            outer.add(new LongPoint(r.left - 10, r.bottom + 10, 0));
            outer.add(new LongPoint(r.right + 10, r.bottom + 10, 0));
            outer.add(new LongPoint(r.right + 10, r.top - 10, 0));
            outer.add(new LongPoint(r.left - 10, r.top - 10, 0));

            clpr.addPath(outer, PolyType.SUBJECT, true);
            // 使用负填充规则执行并集
            clpr.execute(ClipType.UNION, solution, PolyFillType.NEGATIVE, PolyFillType.NEGATIVE);
            // 移除包围盒，只保留内部结果
            if (solution.size() > 0) {
                solution.remove(0);
            }
        }
    }

    /**
     * 执行偏移操作，将结果输出到PolyTree对象
     * @param solution 用于存储结果的PolyTree对象
     * @param delta 偏移距离，正值表示向外扩展，负值表示向内收缩
     */
    public void execute(PolyTree solution, double delta) {
        solution.Clear();
        // 修复多边形方向
        fixOrientations();
        // 执行实际偏移计算
        doOffset(delta);

        // 清理并优化结果多边形
        final DefaultClipper clpr = new DefaultClipper(Clipper.REVERSE_SOLUTION);
        clpr.addPaths(destPolys, PolyType.SUBJECT, true);

        if (delta > 0) {
            // 向外偏移，使用并集操作
            clpr.execute(ClipType.UNION, solution, PolyFillType.POSITIVE, PolyFillType.POSITIVE);
        }
        else {
            // 向内偏移，需要特殊处理
            final LongRect r = destPolys.getBounds();
            // 创建一个包围盒
            final Path outer = new Path(4);
            outer.add(new LongPoint(r.left - 10, r.bottom + 10, 0));
            outer.add(new LongPoint(r.right + 10, r.bottom + 10, 0));
            outer.add(new LongPoint(r.right + 10, r.top - 10, 0));
            outer.add(new LongPoint(r.left - 10, r.top - 10, 0));

            clpr.addPath(outer, PolyType.SUBJECT, true);
            // 使用负填充规则执行并集
            clpr.execute(ClipType.UNION, solution, PolyFillType.NEGATIVE, PolyFillType.NEGATIVE);

            // 处理PolyTree结果，移除包围盒节点
            if (solution.getChildCount() == 1 && solution.getChilds().get(0).getChildCount() > 0) {
                final PolyNode outerNode = solution.getChilds().get(0);
                // 将第一个子节点提升为solution的直接子节点
                solution.getChilds().set(0, outerNode.getChilds().get(0));
                solution.getChilds().get(0).setParent(solution);
                // 添加剩余的子节点
                for (int i = 1; i < outerNode.getChildCount(); i++) {
                    solution.addChild(outerNode.getChilds().get(i));
                }
            }
            else {
                solution.Clear();  // 如果结果无效则清空
            }
        }
    }

    /**
     * 修复多边形方向，确保所有封闭路径具有一致的方向
     * 根据最低顶点所在多边形的方向来调整所有多边形
     */
    private void fixOrientations() {
        // 如果存在最低顶点且其多边形方向不正确，修复所有封闭路径的方向
        if (lowest.getX() >= 0 && !polyNodes.childs.get((int)lowest.getX()).getPolygon().orientation()) {
            for (int i = 0; i < polyNodes.getChildCount(); i++) {
                final PolyNode node = polyNodes.childs.get(i);
                // 对于封闭多边形或方向错误的封闭线，反转点顺序
                if (node.getEndType() == EndType.CLOSED_POLYGON ||
                        (node.getEndType() == EndType.CLOSED_LINE && node.getPolygon().orientation())) {
                    Collections.reverse(node.getPolygon());
                }
            }
        }
        else {
            // 仅修复方向错误的封闭线
            for (int i = 0; i < polyNodes.getChildCount(); i++) {
                final PolyNode node = polyNodes.childs.get(i);
                if (node.getEndType() == EndType.CLOSED_LINE && !node.getPolygon().orientation()) {
                    Collections.reverse(node.getPolygon());
                }
            }
        }
    }

    /**
     * 偏移处理单个顶点
     * @param j 当前顶点索引
     * @param kV 前一个顶点索引（使用数组作为引用传值）
     * @param jointype 连接类型
     */
    private void offsetPoint(int j, int[] kV, JoinType jointype) {
        final int k = kV[0];
        // 提取相关坐标和法线分量
        final double nkx = normals.get(k).getX();
        final double nky = normals.get(k).getY();
        final double njy = normals.get(j).getY();
        final double njx = normals.get(j).getX();
        final long sjx = srcPoly.get(j).getX();
        final long sjy = srcPoly.get(j).getY();

        // 计算叉积，判断转向
        inA = nkx * njy - njx * nky;

        // 处理接近0或180度的特殊情况
        if (Math.abs(inA * delta) < 1.0) {
            // 计算点积
            final double cosA = nkx * njx + njy * nky;
            if (cosA > 0) {  // 角度接近0度
                destPoly.add(new LongPoint(
                        Math.round(sjx + nkx * delta),
                        Math.round(sjy + nky * delta),
                        0
                ));
                return;
            }
            // 否则角度接近180度
        }
        else if (inA > 1.0) {
            inA = 1.0;  // 限制范围
        }
        else if (inA < -1.0) {
            inA = -1.0;  // 限制范围
        }

        // 根据转向决定如何处理顶点
        if (inA * delta < 0) {
            // 凹顶点，添加三个点形成尖角
            destPoly.add(new LongPoint(
                    Math.round(sjx + nkx * delta),
                    Math.round(sjy + nky * delta)
            ));
            destPoly.add(srcPoly.get(j));  // 添加原始顶点
            destPoly.add(new LongPoint(
                    Math.round(sjx + njx * delta),
                    Math.round(sjy + njy * delta)
            ));
        }
        else {
            // 凸顶点，根据连接类型使用不同处理方式
            switch (jointype) {
                case MITER:
                    final double r = 1 + njx * nkx + njy * nky;
                    if (r >= miterLim) {
                        // 斜接长度在限制范围内，使用斜接连接
                        doMiter(j, k, r);
                    }
                    else {
                        // 否则降级为方角连接
                        doSquare(j, k);
                    }
                    break;
                case SQUARE:
                    // 方角连接
                    doSquare(j, k);
                    break;
                case ROUND:
                    // 圆角连接
                    doRound(j, k);
                    break;
            }
        }

        // 更新前一个顶点索引
        kV[0] = j;
    }
}