halfedge 0.1.0

//! 多边形三角化模块
//!
//! 提供二维多边形三角化算法。

// ============================================================
// 2D 向量工具
// ============================================================

type V2 = [f64; 2];

fn v2_sub(a: V2, b: V2) -> V2 {
    [a[0] - b[0], a[1] - b[1]]
}
fn v2_cross(a: V2, b: V2) -> f64 {
    a[0] * b[1] - a[1] * b[0]
}

/// 三角形 (a,b,c) 的有向面积（正 = CCW）。
fn signed_area(a: V2, b: V2, c: V2) -> f64 {
    0.5 * ((b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1]))
}

/// 点 p 是否在三角形 (a,b,c) 内部（含边界）。
fn point_in_triangle(p: V2, a: V2, b: V2, c: V2) -> bool {
    let area = signed_area(a, b, c).abs();
    let a1 = signed_area(p, b, c).abs();
    let a2 = signed_area(a, p, c).abs();
    let a3 = signed_area(a, b, p).abs();
    (a1 + a2 + a3 - area).abs() < 1e-12 * area.max(1e-12)
}

/// 多边形是否 CCW（逆时针）。
fn is_ccw(poly: &[V2]) -> bool {
    let n = poly.len();
    if n < 3 {
        return false;
    }
    let mut sum = 0.0;
    for i in 0..n {
        let j = (i + 1) % n;
        sum += (poly[j][0] - poly[i][0]) * (poly[j][1] + poly[i][1]);
    }
    sum < 0.0
}

// ============================================================
// 扇形三角化（凸多边形）
// ============================================================

/// 扇形三角化：从第一个顶点向其余顶点连三角形。
///
/// 要求多边形为**简单凸多边形**且顶点按 CCW 顺序排列。
/// 返回 `Vec<[usize; 3]>`，每个元素是三个顶点索引。
///
/// 对凹多边形结果可能不正确（三角形可能落在多边形外部）。
pub fn fan_triangulation(polygon: &[[f64; 2]]) -> Vec<[usize; 3]> {
    let n = polygon.len();
    if n < 3 {
        return Vec::new();
    }
    let mut tris = Vec::with_capacity(n - 2);
    for i in 2..n {
        tris.push([0, i - 1, i]);
    }
    tris
}

/// 扇形三角化（3D 版本）：输入为 3D 点，假设所有点共面。
/// 投影到主平面对应的 2D 坐标系上进行扇形三角化。
pub fn fan_triangulation_3d(polygon: &[[f64; 3]]) -> Vec<[usize; 3]> {
    let n = polygon.len();
    if n < 3 {
        return Vec::new();
    }
    // 简单起见，直接按索引扇形（与其他构建器配合使用时由调用者保证共面/凸性）
    let mut tris = Vec::with_capacity(n - 2);
    for i in 2..n {
        tris.push([0, i - 1, i]);
    }
    tris
}

// ============================================================
// Ear Clipping（支持凹多边形）
// ============================================================

/// Ear Clipping 三角化：适用于任意**简单多边形**（含凹多边形）。
///
/// 顶点按 CCW 顺序排列。返回 `Vec<[usize; 3]>`。
///
/// 算法：反复寻找"耳尖"（凸顶点，且对角线与多边形不相交），
/// 剪切该耳朵后继续，直到剩余 3 个顶点。
pub fn ear_clipping(polygon: &[[f64; 2]]) -> Vec<[usize; 3]> {
    let n = polygon.len();
    if n < 3 {
        return Vec::new();
    }
    if n == 3 {
        return vec![[0, 1, 2]];
    }

    // 确保 CCW
    let mut verts: Vec<V2> = polygon.to_vec();
    if !is_ccw(&verts) {
        verts.reverse();
    }

    let mut indices: Vec<usize> = (0..n).collect();
    let mut triangles = Vec::with_capacity(n - 2);

    let mut iter_count = 0;
    while indices.len() > 3 {
        iter_count += 1;
        if iter_count > indices.len() * indices.len() {
            // 安全兜底：算法卡住时回退到扇形
            break;
        }

        let m = indices.len();
        let mut found_ear = false;

        for i in 0..m {
            let prev = if i == 0 { m - 1 } else { i - 1 };
            let next = (i + 1) % m;

            let a = verts[indices[prev]];
            let b = verts[indices[i]];
            let c = verts[indices[next]];

            // 检查顶点 i 是否为凸顶点（内角 < 180°）
            let cross = v2_cross(v2_sub(b, a), v2_sub(c, a));
            if cross <= 0.0 {
                continue; // 凹顶点或共线，跳过
            }

            // 检查三角形 (a,b,c) 内是否包含其他顶点
            let mut is_ear = true;
            for j in 0..m {
                if j == prev || j == i || j == next {
                    continue;
                }
                if point_in_triangle(verts[indices[j]], a, b, c) {
                    is_ear = false;
                    break;
                }
            }

            if is_ear {
                triangles.push([indices[prev], indices[i], indices[next]]);
                indices.remove(i);
                found_ear = true;
                break;
            }
        }

        if !found_ear {
            break; // 无耳可剪
        }
    }

    // 剩余最后一个三角形
    if indices.len() == 3 {
        triangles.push([indices[0], indices[1], indices[2]]);
    }

    triangles
}

/// Ear Clipping 三角化（3D 版本）：将 3D 点投影到最佳平面对应的 2D 坐标，
/// 执行 ear clipping，再映射回原始索引。
///
/// 自动选择法向绝对值最大的轴作为投影丢弃轴。
pub fn ear_clipping_3d(polygon: &[[f64; 3]]) -> Vec<[usize; 3]> {
    let n = polygon.len();
    if n < 3 {
        return Vec::new();
    }
    if n == 3 {
        return vec![[0, 1, 2]];
    }

    // 计算近似法向，选择丢弃轴
    let mut normal = [0.0f64; 3];
    for i in 0..n {
        let j = (i + 1) % n;
        normal[0] += (polygon[i][1] - polygon[j][1]) * (polygon[i][2] + polygon[j][2]);
        normal[1] += (polygon[i][2] - polygon[j][2]) * (polygon[i][0] + polygon[j][0]);
        normal[2] += (polygon[i][0] - polygon[j][0]) * (polygon[i][1] + polygon[j][1]);
    }

    // 选择法向绝对值最大的轴丢弃
    let drop_axis = if normal[0].abs() >= normal[1].abs() && normal[0].abs() >= normal[2].abs() {
        0 // 丢弃 x
    } else if normal[1].abs() >= normal[2].abs() {
        1 // 丢弃 y
    } else {
        2 // 丢弃 z
    };

    let poly_2d: Vec<V2> = polygon
        .iter()
        .map(|p| match drop_axis {
            0 => [p[1], p[2]],
            1 => [p[0], p[2]],
            _ => [p[0], p[1]],
        })
        .collect();

    ear_clipping(&poly_2d)
}

// ============================================================
// 单元测试
// ============================================================

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn fan_triangulation_quad() {
        let quad = [[0.0, 0.0], [1.0, 0.0], [1.0, 1.0], [0.0, 1.0]];
        let tris = fan_triangulation(&quad);
        assert_eq!(tris.len(), 2);
        assert_eq!(tris[0], [0, 1, 2]);
        assert_eq!(tris[1], [0, 2, 3]);
    }

    #[test]
    fn fan_triangulation_empty() {
        assert_eq!(fan_triangulation(&[]).len(), 0);
        assert_eq!(fan_triangulation(&[[0.0, 0.0]]).len(), 0);
    }

    #[test]
    fn ear_clipping_convex_quad() {
        let quad = [[0.0, 0.0], [1.0, 0.0], [1.0, 1.0], [0.0, 1.0]];
        let tris = ear_clipping(&quad);
        assert_eq!(tris.len(), 2);
    }

    #[test]
    fn ear_clipping_concave_l_shape() {
        let lshape = [
            [0.0, 0.0],
            [2.0, 0.0],
            [2.0, 0.5],
            [1.0, 0.5],
            [1.0, 2.0],
            [0.0, 2.0],
        ];
        let tris = ear_clipping(&lshape);
        assert_eq!(tris.len(), 4);
    }

    #[test]
    fn ear_clipping_3d_square() {
        let square = [
            [0.0, 0.0, 0.0],
            [1.0, 0.0, 0.0],
            [1.0, 1.0, 0.0],
            [0.0, 1.0, 0.0],
        ];
        let tris = ear_clipping_3d(&square);
        assert_eq!(tris.len(), 2);
    }

    #[test]
    fn ear_clipping_triangle() {
        let tri = [[0.0, 0.0], [1.0, 0.0], [0.0, 1.0]];
        assert_eq!(ear_clipping(&tri).len(), 1);
    }
}