rgeometry/data/
intersection_set.rs

1use crate::data::IndexEdge;
2use crate::data::PointId;
3use crate::utils::SparseIndex;
4use crate::utils::SparseVec;
5
6use rand::Rng;
7use std::ops::{Index, IndexMut};
8
9#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd)]
10#[non_exhaustive]
11pub struct IndexIntersection {
12  pub min: IndexEdge,
13  pub max: IndexEdge,
14}
15
16impl std::fmt::Debug for IndexIntersection {
17  fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
18    f.debug_tuple("IndexIntersection")
19      .field(&self.min)
20      .field(&self.max)
21      .finish()
22  }
23}
24
25impl IndexIntersection {
26  pub fn new(a: IndexEdge, b: IndexEdge) -> IndexIntersection {
27    IndexIntersection {
28      min: std::cmp::min(a, b),
29      max: std::cmp::max(a, b),
30    }
31  }
32}
33
34impl From<Isect> for IndexIntersection {
35  fn from(isect: Isect) -> IndexIntersection {
36    IndexIntersection::new(isect.edge0.into(), isect.edge1.into())
37  }
38}
39
40pub struct IndexIntersectionSet {
41  vertices: usize,
42  // This may grow to N^2 at the most (where N = number of vertices).
43  by_idx: SparseVec<Isect>,
44  by_edge: Vec<Option<SparseIndex>>,
45}
46
47impl IndexIntersectionSet {
48  /// O(n^2)
49  pub fn new(vertices: usize) -> IndexIntersectionSet {
50    let size = vertices * (vertices - 1);
51    let by_edge = vec![None; size];
52    IndexIntersectionSet {
53      vertices,
54      by_idx: SparseVec::new(),
55      by_edge,
56    }
57  }
58
59  // O(1)
60  pub fn push(&mut self, isect: IndexIntersection) {
61    let idx = self.by_idx.push(Isect::new(isect));
62
63    for &edge in &[isect.min, isect.max] {
64      if let Some(loc) = self[edge] {
65        assert_ne!(loc, idx);
66        self.by_idx[loc][edge].prev = Some(idx);
67        self.by_idx[idx][edge].next = Some(loc);
68      }
69      self[edge] = Some(idx);
70    }
71  }
72
73  // O(1)
74  fn remove(&mut self, idx: SparseIndex) {
75    let isect = self.by_idx.remove(idx);
76
77    // eprintln!("Removing intersection: {:?}", isect);
78
79    for &edge in &[isect.edge0, isect.edge1] {
80      match edge.prev {
81        Some(prev) => self.by_idx[prev][IndexEdge::from(edge)].next = edge.next,
82        None => self[IndexEdge::from(edge)] = edge.next,
83      }
84      if let Some(next) = edge.next {
85        self.by_idx[next][IndexEdge::from(edge)].prev = edge.prev;
86      }
87    }
88  }
89
90  // O(n) where N is the number of removed intersections.
91  pub fn remove_all(&mut self, edge: impl Into<IndexEdge>) {
92    let key = edge.into();
93    while let Some(idx) = self[key] {
94      self.remove(idx)
95    }
96  }
97
98  // O(1)
99  pub fn random<R>(&mut self, rng: &mut R) -> Option<IndexIntersection>
100  where
101    R: Rng + ?Sized,
102  {
103    let idx = self.by_idx.random(rng)?;
104    let isect = self.by_idx[idx];
105    Some(IndexIntersection::new(
106      IndexEdge::new(isect.edge0.vertex0, isect.edge0.vertex1),
107      IndexEdge::new(isect.edge1.vertex0, isect.edge1.vertex1),
108    ))
109  }
110
111  pub fn iter(&self) -> impl Iterator<Item = IndexIntersection> + '_ {
112    self.by_idx.iter().map(|&isect| isect.into())
113  }
114}
115
116impl IndexMut<IndexEdge> for IndexIntersectionSet {
117  fn index_mut(&mut self, index: IndexEdge) -> &mut Option<SparseIndex> {
118    self
119      .by_edge
120      .index_mut(index.max.usize() + self.vertices * index.min.usize())
121  }
122}
123
124impl Index<IndexEdge> for IndexIntersectionSet {
125  type Output = Option<SparseIndex>;
126  fn index(&self, index: IndexEdge) -> &Option<SparseIndex> {
127    self
128      .by_edge
129      .index(index.max.usize() + self.vertices * index.min.usize())
130  }
131}
132
133impl PartialEq<IndexEdge> for IsectEdge {
134  fn eq(&self, other: &IndexEdge) -> bool {
135    self.vertex0 == other.min && self.vertex1 == other.max
136  }
137}
138
139impl PartialEq for IsectEdge {
140  fn eq(&self, other: &IsectEdge) -> bool {
141    self.vertex0 == other.vertex0 && self.vertex1 == other.vertex1
142  }
143}
144
145// Invariants:
146//   Edge0 < Edge1
147//   Edge.0 < Edge.1
148#[derive(Clone, Copy, Debug)]
149// FIXME: Should not be pub.
150struct Isect {
151  edge0: IsectEdge,
152  edge1: IsectEdge,
153}
154
155impl Default for Isect {
156  fn default() -> Isect {
157    Isect {
158      edge0: IsectEdge {
159        vertex0: PointId::INVALID,
160        vertex1: PointId::INVALID,
161        next: None,
162        prev: None,
163      },
164      edge1: IsectEdge {
165        vertex0: PointId::INVALID,
166        vertex1: PointId::INVALID,
167        next: None,
168        prev: None,
169      },
170    }
171  }
172}
173
174impl Isect {
175  fn new(intersection: IndexIntersection) -> Isect {
176    Isect {
177      edge0: IsectEdge::new(intersection.min),
178      edge1: IsectEdge::new(intersection.max),
179    }
180  }
181}
182
183impl IndexMut<IsectEdge> for Isect {
184  fn index_mut(&mut self, index: IsectEdge) -> &mut IsectEdge {
185    if self.edge0 == index {
186      &mut self.edge0
187    } else {
188      assert_eq!(self.edge1, index);
189      &mut self.edge1
190    }
191  }
192}
193
194impl Index<IsectEdge> for Isect {
195  type Output = IsectEdge;
196  fn index(&self, index: IsectEdge) -> &IsectEdge {
197    if self.edge0 == index {
198      &self.edge0
199    } else {
200      assert_eq!(self.edge1, index);
201      &self.edge1
202    }
203  }
204}
205
206impl IndexMut<IndexEdge> for Isect {
207  fn index_mut(&mut self, index: IndexEdge) -> &mut IsectEdge {
208    if self.edge0 == index {
209      &mut self.edge0
210    } else {
211      assert_eq!(self.edge1, index);
212      &mut self.edge1
213    }
214  }
215}
216
217impl Index<IndexEdge> for Isect {
218  type Output = IsectEdge;
219  fn index(&self, index: IndexEdge) -> &IsectEdge {
220    if self.edge0 == index {
221      &self.edge0
222    } else {
223      assert_eq!(self.edge1, index);
224      &self.edge1
225    }
226  }
227}
228
229#[derive(Clone, Copy, Debug)]
230// FIXME: Should not be pub
231struct IsectEdge {
232  vertex0: PointId,
233  vertex1: PointId,
234  next: Option<SparseIndex>,
235  prev: Option<SparseIndex>,
236}
237
238impl IsectEdge {
239  // FIXME: Sort vertex0 and vertex1
240  fn new(edge: IndexEdge) -> IsectEdge {
241    IsectEdge {
242      vertex0: edge.min,
243      vertex1: edge.max,
244      next: None,
245      prev: None,
246    }
247  }
248}
249
250impl From<IsectEdge> for IndexEdge {
251  fn from(e: IsectEdge) -> IndexEdge {
252    IndexEdge::new(e.vertex0, e.vertex1)
253  }
254}
rgeometry/data/intersection_set.rs

rgeometry/data/
intersection_set.rs
