cg_math/validation/

mod.rs

extern crate nalgebra as na;
use crate::geometry::{TriangleLogic, WeightedTriangle, WeightedVertex, Triangulation};
use na::Point2;
extern crate parry2d_f64 as parry;

/// Struct for storing the metrics of a triangulation
#[derive(PartialEq)]
pub struct TriangulationMetrics {
    pub area: f64,
    pub area3d: f64,
    pub c_hull: f64,
    pub epsilon: f64,
    pub num_simplices: usize,
    pub regularity: f64,
    pub runtime: f64,
}

/// Struct for storing the equality metric for two triangulations
#[derive(Debug, PartialEq)]
pub struct EqualTriangleMetric {
    pub equal_triangles: Vec<WeightedTriangle>,
    pub different_triangles: Vec<WeightedTriangle>,
    pub true_triangle_ratio: f64,

}

impl EqualTriangleMetric {
    /// Create and compute the metric for the given triangulations.
    pub fn new(triangulation: &Triangulation, baseline_triangulation: &Triangulation) -> Self {
        let mut equal_triangles: Vec<WeightedTriangle> = vec![];
        let mut different_triangles: Vec<WeightedTriangle> = vec![];

        for triangle in triangulation.triangles() {
            let mut not_in_baseline = true;
            for base_triangle in baseline_triangulation.triangles() {
                if triangle == base_triangle {
                    equal_triangles.push(*triangle);
                    not_in_baseline = false;
                    break;
                }   
            }
            if not_in_baseline {
                different_triangles.push(*triangle);
            }
        }

        let true_triangle_ratio = equal_triangles.len() as f64 / baseline_triangulation.triangles().len() as f64 * 100.0;

        Self {
            equal_triangles,
            different_triangles,
            true_triangle_ratio,
        }
    }

    /// Create an empty metric.
    pub fn empty() -> Self {
        Self {
            equal_triangles: vec![],
            different_triangles: vec![],
            true_triangle_ratio: 0.0,
        }
    }
}

/// Compute all result metrics for a given triangulation
pub fn compute_metrics(
    vertices: &Vec<WeightedVertex>,
    triangles: &Vec<WeightedTriangle>,
    epsilon: f64,
    runtime: f64,
) -> TriangulationMetrics {
    let regularity = all_globally_regular(vertices, triangles);
    let is_c_hull = is_c_hull(vertices, triangles);
    let area = summed_area(triangles);
    let area3d = summed_area3d(triangles);

    TriangulationMetrics {
        epsilon,
        num_simplices: triangles.len(),
        c_hull: is_c_hull as i32 as f64,
        regularity,
        area,
        area3d,
        runtime,
    }
}

/// Given a triangulation and the a point list, check if all triangles fulfill the empty orthogonal circle property
// TODO impl this on the triangulation struct and rename to all_empty_orthogonal_circles
// TODO more sophisticated: for each triangle take the percentage of points that it is irregular for
pub fn all_globally_regular(
    vertices: &Vec<WeightedVertex>,
    triangles: &Vec<WeightedTriangle>,
) -> f64 {
    let mut n_invalid_triangles = 0.0;

    for triangle in triangles.iter() {
        for vertex in vertices {
            if !triangle.has_vertex(vertex) && !triangle.is_regular(vertex) {
                n_invalid_triangles += 1.0;
                break;
            }
        }
    }
    1.0 - n_invalid_triangles / triangles.len() as f64
}

/// Given a triangulation and the initial point list, check if the c-hull of the points is equal to the c-hull spanned by all the triangles.
// TODO impl this on the triangulation struct
pub fn is_c_hull(vertices: &[WeightedVertex], triangles: &[WeightedTriangle]) -> bool {
    let input_points2d: Vec<Point2<f64>> =
        vertices.iter().map(|v| Point2::new(v.x(), v.y())).collect();
    let input_points_hull = parry::transformation::convex_hull(&input_points2d);

    let triangulation_border_points2d: Vec<Point2<f64>> = get_boundary_points(triangles);

    //println!("points c_hull: {:?}", input_points_hull);
    //println!("triangulation border: {:?}", triangulation_border_points2d);
    //println!("c-hull len: {} vs border points len: {}", input_points_hull.len(), triangulation_border_points2d.len());

    triangulation_border_points2d
        .iter()
        .all(|item| input_points_hull.contains(item))
}

/// Get the points on the border described by the polygon that is the union of all the triangles in the triangulations
/// Ideally this is equal to the convex hull of the polygon described by the triangulation.
fn get_boundary_points(triangulation: &[WeightedTriangle]) -> Vec<Point2<f64>> {
    // Note: very naive, inefficient implementation; for quickly getting the validation test up
    let copied_triangulation1 = triangulation.to_owned();
    let mut border_points: Vec<Point2<f64>> = vec![]; // return as Point<f64> since c-hull algo uses these

    for triangle1 in copied_triangulation1 {
        for edge1 in triangle1.edges() {
            let mut is_border_edge = true;

            let copied_triangulation2 = triangulation.to_owned();
            for triangle2 in copied_triangulation2 {
                if triangle1 != triangle2 {
                    // if the edge is part of another triangle it is not on the polygonal border
                    for edge2 in triangle2.edges() {
                        if edge1 == edge2 {
                            is_border_edge = false;
                        }
                    }
                }
            }

            if is_border_edge {
                let mut a_unique = true;
                let mut b_unique = true;
                for point in border_points.clone() {
                    if point == Point2::new(edge1.a.x(), edge1.a.y()) {
                        a_unique = false;
                    }
                    if point == Point2::new(edge1.b.x(), edge1.b.y()) {
                        b_unique = false;
                    }
                }

                if a_unique {
                    border_points.push(Point2::new(edge1.a.x(), edge1.a.y()));
                }
                if b_unique {
                    border_points.push(Point2::new(edge1.b.x(), edge1.b.y()))
                }
            }
        }
    }
    border_points
}

/// Compute the summed area of all triangles in the triangulation.
// TODO impl this on the triangulation struct
pub fn summed_area(triangulation: &[WeightedTriangle]) -> f64 {
    triangulation
        .iter()
        .fold(0.0, |sum, triangle| sum + triangle.area())
}


/// Compute the summed area of all triangles of the triangulation in 3d with z = w.
// TODO impl this on the triangulation struct
pub fn summed_area3d(triangulation: &[WeightedTriangle]) -> f64 {
    triangulation
        .iter()
        .fold(0.0, |sum, triangle| sum + triangle.area3d())
}