// 使用优化的 Douglas-Peucker 算法计算简化数据

interface SimplifyOptions {
    /** 简化容差值，默认为1.0 */
    tolerance?: number;
    /** 是否保留最高精度，当设置为true时将使用更精确的距离计算 */
    highQuality?: boolean;
}

/**
 * 对坐标序列进行 Douglas-Peucker 算法简化
 * 
 * @param coords - 坐标数组，格式为 [x, y, x, y, x, y, ...] 或 [[x, y], [x, y], ...]
 * @param options - 简化选项
 * @returns 简化后的坐标数组，格式与输入相同
 * 
 * @example
 * ```ts
 * // 使用坐标数组
 * const points = [0, 0, 1, 1, 2, 2, 3, 3, 4, 4];
 * const simplified = simplify(points, { tolerance: 1.0 });
 * 
 * // 使用坐标对数组
 * const pointPairs = [[0, 0], [1, 1], [2, 2], [3, 3], [4, 4]];
 * const simplifiedPairs = simplify(pointPairs, { tolerance: 1.0 });
 * ```
 */
export function simplify(
    coords: Float32Array | number[] | [number, number][],
    options?: SimplifyOptions
): Float32Array | number[] | [number, number][] {
    // 默认选项
    const opts: Required<SimplifyOptions> = {
        tolerance: 1.0,
        highQuality: false,
        ...options
    };
    
    // 处理不同类型的输入
    let flatCoords: Float32Array | number[];
    let isPointPairs = false;
    
    if (Array.isArray(coords) && coords.length > 0 && Array.isArray(coords[0])) {
        // 输入是坐标对数组 [[x,y], [x,y], ...]
        isPointPairs = true;
        flatCoords = [];
        for (const pair of coords as [number, number][]) {
            flatCoords.push(pair[0], pair[1]);
        }
    } else {
        // 输入是平铺的坐标数组 [x, y, x, y, ...]
        flatCoords = coords as Float32Array | number[];
    }
    
    // 执行简化算法
    const sqTolerance = opts.tolerance * opts.tolerance;
    const result = simplifyFlat(flatCoords, 0, (flatCoords.length / 2) - 1, sqTolerance, opts.highQuality);
    
    // 根据输入类型返回相应格式的结果
    if (isPointPairs) {
        const pointPairs: [number, number][] = [];
        for (let i = 0; i < result.length; i += 2) {
            pointPairs.push([result[i], result[i + 1]]);
        }
        return pointPairs;
    }
    
    return result;
}

/**
 * 对平铺格式的坐标序列进行 Douglas-Peucker 简化算法（非递归优化版本）
 * 
 * @param coords - 坐标数组，格式为 [x, y, x, y, x, y, ...]
 * @param first - 起始索引（坐标对的索引）
 * @param last - 结束索引（坐标对的索引）
 * @param sqTolerance - 简化容差的平方值
 * @param highQuality - 是否使用高精度计算
 * @returns 简化后的坐标数组
 */
function simplifyFlat(
    coords: Float32Array | number[], 
    first: number, 
    last: number, 
    sqTolerance: number,
    highQuality: boolean
): Float32Array | number[] {
    // 参数验证
    if (!coords || first >= last || sqTolerance < 0) {
        return Array.isArray(coords) ? [] : new Float32Array(0);
    }
    
    // 标记需要保留的点
    const keepFlags = new Uint8Array(last - first + 1);
    keepFlags[0] = 1; // 保留起始点
    keepFlags[keepFlags.length - 1] = 1; // 保留结束点
    
    // 使用预分配的数组来避免频繁的内存分配
    // 使用 Uint32Array 提高性能，因为索引通常不会超过 2^32
    const stack: Uint32Array = new Uint32Array(coords.length); // 足够大的栈空间
    let stackTop: number = 0; // 栈顶指针
    
    // 初始化栈
    stack[stackTop++] = first;
    stack[stackTop++] = last;
    
    // 使用栈模拟递归过程
    while (stackTop > 0) {
        // 从栈中取出参数（注意顺序：后进先出）
        const currentLast: number = stack[--stackTop] as number;
        const currentFirst: number = stack[--stackTop] as number;
        
        // 边界检查
        if (currentLast - currentFirst <= 1) {
            continue;
        }
        
        // 计算中点位置（使用位运算提高性能）
        const mid: number = currentFirst + ((currentLast - currentFirst) >> 1);
        
        // 初始化变量
        let maxSqDist: number = sqTolerance;
        let minPosToMid: number = currentLast - currentFirst;
        let index: number = -1;
        
        // 获取当前线段的起点和终点坐标
        const firstIdx: number = currentFirst << 1;  // 等同于 currentFirst * 2，但更快
        const lastIdx: number = currentLast << 1;    // 等同于 currentLast * 2，但更快
        
        // 预先获取起点和终点坐标，避免重复访问
        const ax: number = coords[firstIdx]!;
        const ay: number = coords[firstIdx + 1]!;
        const bx: number = coords[lastIdx]!;
        const by: number = coords[lastIdx + 1]!;
        
        // 遍历起点和终点之间的所有点，寻找距离线段最远的点
        // 从 currentFirst + 1 开始，到 currentLast - 1 结束
        for (let i: number = currentFirst + 1; i < currentLast; i++) {
            const idx: number = i << 1;  // 等同于 i * 2，但更快
            // 计算当前点到线段的平方距离
            const d: number = highQuality 
                ? getSqSegDistHighQuality(coords[idx]!, coords[idx + 1]!, ax, ay, bx, by)
                : getSqSegDist(coords[idx]!, coords[idx + 1]!, ax, ay, bx, by);
            
            // 如果当前距离大于已知最大距离
            if (d > maxSqDist) {
                index = i;
                maxSqDist = d;
                minPosToMid = Math.abs(i - mid); // 更新最小位置差
                
            // 如果距离相等，选择更靠近中点的点
            } else if (d === maxSqDist) {
                // 这是一个解决方案，确保选择靠近列表中间的枢轴，
                // 减少递归深度，针对某些退化输入
                // https://github.com/mapbox/geojson-vt/issues/104
                const posToMid: number = Math.abs(i - mid);
                if (posToMid < minPosToMid) {
                    index = i;
                    minPosToMid = posToMid;
                }
            }
        }
        
        // 如果最大距离大于容差，说明需要进一步简化
        if (maxSqDist > sqTolerance && index !== -1) {
            // 标记该点需要保留
            keepFlags[index - first] = 1;
            
            // 将子问题压入栈中（注意顺序：先压入后执行的）
            // 检查右半部分
            if (currentLast - index > 1) {
                stack[stackTop++] = index;
                stack[stackTop++] = currentLast;
            }
            // 检查左半部分
            if (index - currentFirst > 1) {
                stack[stackTop++] = currentFirst;
                stack[stackTop++] = index;
            }
        }
    }
    
    // 计算需要保留的点的数量
    let keepCount = 0;
    for (let i = 0; i < keepFlags.length; i++) {
        if (keepFlags[i]) {
            keepCount++;
        }
    }
    
    // 创建结果数组
    const ResultConstructor = Array.isArray(coords) ? Array : Float32Array;
    const result = new ResultConstructor(keepCount * 2);
    let resultIndex = 0;
    
    // 将保留的坐标复制到结果数组中
    for (let i = 0; i < keepFlags.length; i++) {
        if (keepFlags[i]) {
            const coordIndex = (first + i) << 1;
            result[resultIndex++] = coords[coordIndex]!;
            result[resultIndex++] = coords[coordIndex + 1]!;
        }
    }
    
    return result;
}

/**
 * 计算点到线段的平方距离（标准版本）
 * 
 * 使用向量投影的方法计算点到线段的最短距离
 * 
 * @param px - 目标点的x坐标
 * @param py - 目标点的y坐标
 * @param x - 线段起点x坐标
 * @param y - 线段起点y坐标
 * @param bx - 线段终点x坐标
 * @param by - 线段终点y坐标
 * @returns 点到线段的平方距离
 */
function getSqSegDist(
    px: number, 
    py: number, 
    x: number, 
    y: number, 
    bx: number, 
    by: number
): number {
    // 计算线段的方向向量
    const dx: number = bx - x;
    const dy: number = by - y;
    
    // 检查线段是否退化为点（起点和终点重合）
    if (dx !== 0 || dy !== 0) {
        // 计算投影参数 t = [(P-A) · (B-A)] / |B-A|²
        const denominator: number = dx * dx + dy * dy;
        const t: number = denominator > Number.EPSILON ? 
            ((px - x) * dx + (py - y) * dy) / denominator : 0;
        
        // 根据参数 t 的值确定线段上的最近点
        if (t > 1) {
            // t > 1: 投影点在线段延长线上，超出了终点，最近点是终点
            // 直接计算到终点的距离
            const diffX: number = px - bx;
            const diffY: number = py - by;
            return diffX * diffX + diffY * diffY;
        } else if (t > 0) {
            // 0 < t < 1: 投影点在线段内部
            const projX: number = x + dx * t;
            const projY: number = y + dy * t;
            const diffX: number = px - projX;
            const diffY: number = py - projY;
            return diffX * diffX + diffY * diffY;
        }
        // t <= 0: 投影点在线段延长线上，超出了起点，最近点是起点
        // 继续执行下面的代码计算到起点的距离
    }
    
    // 计算点到最近点的距离向量
    const diffX: number = px - x;
    const diffY: number = py - y;
    
    // 返回距离的平方值
    return diffX * diffX + diffY * diffY;
}

/**
 * 计算点到线段的平方距离（高精度版本）
 * 
 * 使用更精确的数学计算来获得更高精度的结果
 * 
 * @param px - 目标点的x坐标
 * @param py - 目标点的y坐标
 * @param x - 线段起点x坐标
 * @param y - 线段起点y坐标
 * @param bx - 线段终点x坐标
 * @param by - 线段终点y坐标
 * @returns 点到线段的平方距离
 */
function getSqSegDistHighQuality(
    px: number, 
    py: number, 
    x: number, 
    y: number, 
    bx: number, 
    by: number
): number {
    const dx = bx - x;
    const dy = by - y;
    
    if (dx === 0 && dy === 0) {
        // 线段退化为点
        const diffX = px - x;
        const diffY = py - y;
        return diffX * diffX + diffY * diffY;
    }
    
    // 使用更稳定的数值计算方法
    const t = ((px - x) * dx + (py - y) * dy) / (dx * dx + dy * dy);
    
    let tx: number;
    let ty: number;
    
    if (t <= 0) {
        tx = x;
        ty = y;
    } else if (t >= 1) {
        tx = bx;
        ty = by;
    } else {
        tx = x + t * dx;
        ty = y + t * dy;
    }
    
    const pdx = px - tx;
    const pdy = py - ty;
    
    return pdx * pdx + pdy * pdy;
}

// 性能测试
function performanceTest(): void {
    // 测试平铺数组格式
    const coords: Float32Array = new Float32Array(10000);
    for (let i: number = 0; i < coords.length; i++) {
        coords[i] = Math.random() * 1000;
    }
    
    console.time('Optimized Version - Flat Array');
    const simplified = simplify(coords, { tolerance: 1.0 });
    console.timeEnd('Optimized Version - Flat Array');
 //   console.log('Simplified coordinates (flat array):', simplified);
    console.log(`Original points: ${coords.length / 2}, Simplified points: ${simplified.length / 2}`);
    
    // 测试坐标对数组格式
    const pointPairs: [number, number][] = [];
    for (let i = 0; i < coords.length; i += 2) {
        pointPairs.push([coords[i], coords[i + 1]]);
    }
    
    console.time('Optimized Version - Point Pairs');
    const simplifiedPairs = simplify(pointPairs, { tolerance: 1.0 });
    console.timeEnd('Optimized Version - Point Pairs');
   // console.log('Simplified coordinates (point pairs):', simplifiedPairs);
    console.log(`Original points: ${pointPairs.length}, Simplified points: ${simplifiedPairs.length}`);
}

// performanceTest();