1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

use std::collections::BTreeSet;
use point::Point;
use edge::Edge;
use triangle::Triangle;


pub fn triangulate(seed: &[Point]) -> Vec<Triangle> {
    let mut points: Vec<Point> = seed.to_owned();

    points.sort();

    let xmin = points[0].x;
    let ymin = points[0].y;
    let xmax = points[points.len() - 1].x;
    let ymax = points[points.len() - 1].y;
    let dx = xmax - xmin;
    let dy = ymax - ymin;
    let dmax = if dx > dy { dx } else { dy };
    let xmid = (xmax - xmin) / 2.0;
    let ymid = (ymax - ymin) / 2.0;

    // Set up the super triangle, which encompasses all the sample points
    let p1 = Point::new(xmid - 2.0 * dmax, ymid - dmax);
    let p2 = Point::new(xmid + 2.0 * dmax, ymid - dmax);
    let p3 = Point::new(xmid, ymid + 2.0 * dmax);

    let supertriangle = Triangle::new(p1, p2, p3);
    let mut triangles: BTreeSet<Triangle> = BTreeSet::new();
    triangles.insert(supertriangle.clone());

    for point in &points {
        let mut bad_triangles: BTreeSet<Triangle> = BTreeSet::new();

        // First find all the triangles that are no longer valid due to the insertion.
        // for each triangle in triangulation
        //    if point is inside circumcircle of triangle
        //        add triangle to badTriangles

        for triangle in triangles.clone() {
            if triangle.contains(point.to_owned()) {
                bad_triangles.insert(triangle.clone());
            }
        }

        // Find the boundary of the polygonal hole.
        // for each triangle in badTriangles
        //     for each edge in triangle
        //         if edge is not shared by any other triangles in badTriangles
        //             add edge to polygon

        let mut polygon: BTreeSet<Edge> = BTreeSet::new();
        for triangle in &bad_triangles {
            let mut bad_edges: BTreeSet<Edge> = BTreeSet::new();

            for other_triangle in &bad_triangles {
                if !(triangle == other_triangle) {
                    bad_edges = bad_edges
                        .union(&other_triangle.edges)
                        .cloned()
                        .collect();
                }
            }

            for edge in &triangle.edges {
                if bad_edges.contains(edge) {}
                else {
                    polygon.insert(edge.clone());
                }
            }
        }

        // Remove bad triangles from the triangulation.
        // for each triangle in badTriangles
        //     remove triangle from triangulation

        triangles = triangles
            .clone()
            .into_iter()
            .filter(|triangle| !bad_triangles.contains(triangle))
            .collect();

        // Re-triangulate the polygonal hole.
        // for each edge in polygon
        //     newTri := form a triangle from edge to point
        //     add newTri to triangulation

        for edge in &polygon {
            let new_triangle = Triangle::new(
                edge.p1,
                edge.p2,
                point.clone()
            );
            triangles.insert(new_triangle);
        }
    }

    // for each triangle in triangulation
    //     if triangle contains a vertex from original super-triangle
    //         remove triangle from triangulation

    let mut result: Vec<_> = triangles
        .clone()
        .into_iter()
        .filter(|triangle| !triangle.shares_points(&supertriangle))
        .collect();

    result.dedup();
    result
}


#[cfg(test)]
mod test {
    use delaunay;
    use point::Point;

    #[test]
    fn triangulate_4_points() {
        let p1 = Point::new(0.0, 0.0);
        let p2 = Point::new(0.0, 1.0);
        let p3 = Point::new(1.0, 0.0);
        let p4 = Point::new(1.0, 1.0);

        let triangles = delaunay::triangulate(&[p1, p2, p3, p4]);

        assert_eq!(triangles.len(), 2);
    }
}