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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157

use std::fmt;
use delaunator::EMPTY;

use super::{
    Voronoi,
    Point,
    iterator::NeighborSiteIterator
};

/// Represents a Voronoi cell. This is an ergonomic way to access cell details.
///
/// Use [Voronoi::cell()] or [Voronoi::iter_cells()] to obtain an instance of this type.
#[derive(Clone)]
pub struct VoronoiCell<'v> {
    site: usize,
    voronoi: &'v Voronoi
}

impl<'v> VoronoiCell<'v> {
    #[inline]
    pub (super) fn new(site: usize, voronoi: &'v Voronoi) -> Self {
        Self {
            site,
            voronoi
        }
    }

    /// Gets a reference to the position of the site associated with this cell.
    ///
    /// # Examples
    ///
    ///```
    /// use voronoice::*;
    /// let sites = vec![Point { x: 0.0, y: 0.0 }, Point { x: 0.5, y: 0.0 }, Point { x: 0.0, y: 0.5 }];
    /// let v = VoronoiBuilder::default()
    ///     .set_sites(sites.clone())
    ///     .build()
    ///     .unwrap();
    /// // the first site generated by generate_circle_sites is at the origin
    /// assert_eq!(&sites[0], v.cell(0).site_position());
    /// assert_eq!(&sites[1], v.cell(1).site_position());
    /// assert_eq!(&sites[2], v.cell(2).site_position());
    ///```
    pub fn site_position(&self) -> &Point {
        &self.voronoi.sites[self.site]
    }

    /// Gets the index associated with the site for this cell.
    #[inline]
    pub fn site(&self) -> usize {
        self.site
    }

    /// Gets a slice of indices into [Voronoi::vertices] used to index the [Point]s representing the voronoi cell vertices.
    ///
    /// Semantically these values represent the Delaunay triangles associated with this voronoi cell.
    /// The Voronoi cell vertices are the circumcenters of the associated Delaunay triangles.
    ///
    /// If this cell is on the hull of the diagram (```cell.is_on_hull() == true```), or has had one of its edges clipped, some indices will not match to
    /// Delaunay triangles, but to virtual points added during the process of hull closing and clipping. These values will still correctly index into the [Voronoi::vertices()] vector.
    pub fn triangles(&self) -> &[usize] {
        &self.voronoi.cells[self.site]
    }

    /// Gets an iterator for the vertices of this cell.
    ///
    /// Vertices are returned in sequential counter-clockwise order.
    /// Please see [Self::triangles] and [Voronoi::vertices] for additional details regarding hull closing and clipping effects on vertices.
    #[inline]
    pub fn iter_vertices(&self) -> impl Iterator<Item = &Point> + Clone {
        self.triangles().iter().map(move |&t| &self.voronoi.circumcenters[t])
    }

    /// Gets an iterator that returns the index of each site that shared an edge with this cell/site, in a counter-clockwise manner.
    ///
    /// # Example
    ///
    ///```
    /// use voronoice::*;
    /// let sites = vec![Point { x: -0.5, y: 0.0 }, Point { x: 0.5, y: 0.0 }, Point { x: 0.0, y: 0.0 }, Point { x: 0.0, y: 0.5 }, Point { x: 0.0, y: -0.5 }];
    /// let v = VoronoiBuilder::default()
    ///     .set_sites(sites.clone())
    ///     .build()
    ///     .unwrap();
    /// let neighbors: Vec<usize> = v.cell(0).iter_neighbors().collect();
    /// assert_eq!(neighbors[0], 4);
    /// assert_eq!(neighbors[1], 2);
    /// assert_eq!(neighbors[2], 3);
    ///```
    #[inline]
    pub fn iter_neighbors(&self) -> NeighborSiteIterator {
        NeighborSiteIterator::new(self.voronoi, self.site)
    }

    /// Gets an iterator that returns the shortest path on the Voronoi diagram to the destination point, starting from the current cell.
    #[inline]
    pub fn iter_path<'p>(&self, dest: Point) ->  impl Iterator<Item = usize> + 'v {
        crate::iterator::shortest_path_iter(self.voronoi, self.site, dest)
    }

    /// Returns a boolean indicating whether this cell is on the hull (edge) of the diagram.
    ///
    /// A Voronoi cell is on the hull if its associated site is on the Delaunay hull or if clipping is enabled and the cell intersects with the bounding box.
    pub fn is_on_hull(&self) -> bool {
        // if there is no half-edge associated with the left-most edge, the edge is on the hull
        let incoming_leftmost_edge = self.voronoi.site_to_incoming_leftmost_halfedge[self.site];
        self.voronoi.triangulation.halfedges[incoming_leftmost_edge] == EMPTY
            // if the cell vertex index is higher than the # of triangles/circumcenters, it means the vertex was added either because
            // it was extending a hull cell or because of clipping (agaisnt bounding box), thus the cell is on the hull
            || self.triangles().iter().any(|&t| t > self.voronoi.number_of_triangles())
    }
}

#[allow(dead_code)]
impl<'v> fmt::Debug for  VoronoiCell<'v> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        #[derive(Debug)]
        struct Edge {
            edge: usize,
            incoming_site: usize,
            outgoing_site: usize
        }

        #[derive(Debug)]
        struct Site {
            site: usize,
            position: Point,
            is_on_hull: bool,
            leftmost_incoming_edge: Edge
        }

        #[derive(Debug)]
        struct Cellvertices {
            /// Each vertex is the circumcenter of a associated Delaunay triangle
            triangles: Vec<usize>,
            positions: Vec<Point>
        }
        let leftmost_edge = self.voronoi.site_to_incoming_leftmost_halfedge[self.site];

        f.debug_struct("VoronoiCell")
            .field("site", &Site {
                site: self.site,
                position: self.site_position().clone(),
                is_on_hull: self.is_on_hull(),
                leftmost_incoming_edge: Edge {
                    edge: leftmost_edge,
                    incoming_site: self.site,
                    outgoing_site: self.voronoi.triangulation.triangles[leftmost_edge]
                }
            })
            .field("vertices", &Cellvertices {
                triangles: self.triangles().iter().copied().collect(),
                positions: self.triangles().iter().copied().map(|t| self.voronoi.circumcenters[t].clone()).collect()
            })
            .finish()
    }
}