// DDA 算法实现
function drawLineDDA(x0, y0, x1, y1) {
    // 1. 计算差分 dx 和 dy
    let dx = x1 - x0,
        dy = y1 - y0;
    // 2. 确定步数 steps 为 max(|dx|, |dy|)
    let steps = Math.max(Math.abs(dx), Math.abs(dy));
    // 3. 计算增量 incX = dx / steps, incY = dy / steps
    let incX = dx / steps,
        incY = dy / steps;
    // 4. 从起点开始，循环 steps 次，每次累加增量并绘制像素
    let x = x0,
        y = y0;
    for (let i = 0; i <= steps; i++) {
        ctx.fillRect(Math.round(x), Math.round(y), 1, 1); // 绘制像素点
        x += incX;
        y += incY;
    }
}
// 优点：简单直观，易实现
// 缺点：浮点运算，开销大

// Bresenham 算法实现
function drawLineBresenham(x0, y0, x1, y1) {
    // 1. 计算 dx 和 dy 的绝对值
    let dx = Math.abs(x1 - x0),
        dy = Math.abs(y1 - y0);
    // 2. 确定方向 sx 和 sy
    let sx = x0 < x1 ? 1 : -1,
        sy = y0 < y1 ? 1 : -1;
    // 3. 初始化误差 err = dx - dy
    let err = dx - dy;
    // 4. 循环绘制像素，根据误差调整 x 和 y
    let x = x0,
        y = y0;
    while (true) {
        ctx.fillRect(x, y, 1, 1); // 绘制像素
        if (x === x1 && y === y1) break;
        let e2 = 2 * err;
        if (e2 > -dy) {
            err -= dy;
            x += sx;
        }
        if (e2 < dx) {
            err += dx;
            y += sy;
        }
    }
}
// 5. 使用整数运算，避免浮点
// 优点：高效，纯整数运算
// 缺点：仅适用于 |dx| >= |dy| 的情况

// 改进 Bresenham 算法实现
function drawLineImprovedBresenham(x0, y0, x1, y1) {
    // 1. 初始化误差 e = 2*dy - dx
    let dx = Math.abs(x1 - x0),
        dy = Math.abs(y1 - y0);
    let sx = x0 < x1 ? 1 : -1,
        sy = y0 < y1 ? 1 : -1;
    let e = 2 * dy - dx;
    // 2. 循环 dx 次，每次 x 增 1
    let x = x0,
        y = y0;
    for (let i = 0; i <= dx; i++) {
        ctx.fillRect(x, y, 1, 1); // 绘制像素
        // 3. 根据 e 判断是否调整 y
        if (e < 0) {
            e += 2 * dy;
        } else {
            y += sy;
            e += 2 * (dy - dx);
        }
        // 4. 更新误差 e
        x += sx;
    }
}
// 优点：更简洁的整数累加，广泛用于硬件
// 缺点：需要处理方向

// 扫描线填充算法实现
function scanlineFill(poly) {
    // 1. 构建边表 ET，按 ymin 分桶存储边信息
    const ET = {};
    for (let i = 0; i < poly.length; i++) {
        const p1 = poly[i],
            p2 = poly[(i + 1) % poly.length];
        let ymin = Math.min(p1.y, p2.y),
            ymax = Math.max(p1.y, p2.y);
        if (ymin === ymax) continue;
        let x = p1.y < p2.y ? p1.x : p2.x;
        let invSlope = (p2.x - p1.x) / (p2.y - p1.y);
        if (!ET[ymin]) ET[ymin] = [];
        ET[ymin].push({ ymax, x, invSlope });
    }
    // 2. 初始化有效边表 AET
    let AET = [];
    const ymin = Math.min(...poly.map((p) => p.y));
    const ymax = Math.max(...poly.map((p) => p.y));
    // 3. 对每条扫描线 y：
    for (let y = ymin; y <= ymax; y++) {
        // - 插入新边到 AET
        if (ET[y]) AET.push(...ET[y]);
        // - 删除过期边
        AET = AET.filter((edge) => edge.ymax > y);
        // - 计算交点并排序
        const intersections = AET.map((edge) => ({ x: edge.x })).sort((a, b) => a.x - b.x);
        // - 两两配对填充区间
        for (let i = 0; i < intersections.length; i += 2) {
            const xStart = Math.ceil(intersections[i].x);
            const xEnd = Math.floor(intersections[i + 1].x);
            for (let x = xStart; x <= xEnd; x++) {
                ctx.fillRect(x, y, 1, 1); // 填充像素
            }
        }
        // - 更新边的 x 坐标
        AET.forEach((edge) => (edge.x += edge.invSlope));
    }
}
// 优点：高效，适合复杂多边形
// 缺点：需要预处理边表

// 中点 Bresenham 画圆算法实现
function drawCircleMidpoint(R, xc, yc) {
    // 1. 初始化 x=0, y=R, d=1-R
    let x = 0,
        y = R;
    let d = 1 - R;
    // 2. 绘制八分对称点
    plotCirclePoints(xc, yc, x, y);
    // 3. 循环直到 x >= y：
    while (x < y) {
        // - 根据 d 判断是否减 y
        if (d < 0) {
            d += 2 * x + 3;
        } else {
            d += 2 * (x - y) + 5;
            y--;
        }
        // - 更新 d
        // - x++
        x++;
        // - 绘制对称点
        plotCirclePoints(xc, yc, x, y);
    }
}
function plotCirclePoints(xc, yc, x, y) {
    const pts = [
        [xc + x, yc + y],
        [xc - x, yc + y],
        [xc + x, yc - y],
        [xc - x, yc - y],
        [xc + y, yc + x],
        [xc - y, yc + x],
        [xc + y, yc - x],
        [xc - y, yc - x],
    ];
    pts.forEach((p) => ctx.fillRect(p[0], p[1], 1, 1));
}
// 优点：纯整数运算，高效
// 缺点：需要对称映射

// 中点 Bresenham 椭圆算法实现
function drawEllipseMidpoint(a, b, xc, yc) {
    // 1. 初始化 x=0, y=b, 计算 a2, b2
    let x = 0,
        y = b;
    let a2 = a * a,
        b2 = b * b;
    let d1 = b2 - a2 * b + 0.25 * a2;
    let dx = 2 * b2 * x,
        dy = 2 * a2 * y;
    // 2. 区域1：斜率 <=1，以 x 为主
    while (dx < dy) {
        plotEllipsePoints(xc, yc, x, y);
        // - 根据 d1 判断是否减 y
        if (d1 < 0) {
            x++;
            dx += 2 * b2;
            d1 += dx + b2;
        } else {
            x++;
            y--;
            dx += 2 * b2;
            dy -= 2 * a2;
            d1 += dx - dy + b2;
        }
        // - 更新 d1
    }
    // 3. 区域2：斜率 >1，以 y 为主
    let d2 = b2 * (x + 0.5) * (x + 0.5) + a2 * (y - 1) * (y - 1) - a2 * b2;
    while (y >= 0) {
        plotEllipsePoints(xc, yc, x, y);
        // - 根据 d2 判断是否增 x
        if (d2 > 0) {
            y--;
            dy -= 2 * a2;
            d2 += a2 - dy;
        } else {
            x++;
            y--;
            dx += 2 * b2;
            dy -= 2 * a2;
            d2 += dx - dy + a2;
        }
        // - 更新 d2
    }
}
function plotEllipsePoints(xc, yc, x, y) {
    const pts = [
        [xc + x, yc + y],
        [xc - x, yc + y],
        [xc + x, yc - y],
        [xc - x, yc - y],
    ];
    pts.forEach((p) => ctx.fillRect(p[0], p[1], 1, 1));
}
// 4. 绘制四象限对称点
// 优点：整数运算，高效
// 缺点：复杂，需要两个区域