honeycomb_kernels/splits/
edge_multiple.rs

1//! standard and no-alloc variants of the `splitn_edge` functions
2
3use honeycomb_core::cmap::{CMap2, DartIdType, EdgeIdType, NULL_DART_ID};
4use honeycomb_core::geometry::CoordsFloat;
5use honeycomb_core::stm::{
6    abort, atomically_with_err, try_or_coerce, Transaction, TransactionClosureResult,
7};
8
9use crate::splits::SplitEdgeError;
10
11#[allow(clippy::missing_errors_doc)]
12/// Split an edge into `n` segments.
13///
14/// <div class="warning">
15/// This implementation is 2D specific.
16/// </div>
17///
18/// # Arguments
19///
20/// - `cmap: &mut CMap2<T>` -- Reference to the modified map.
21/// - `edge_id: EdgeIdentifier` -- Edge to split in two.
22/// - `midpoint_vertices: I` -- Relative positions of new vertices, starting from the
23///   vertex of the dart sharing `edge_id` as its identifier.
24///
25/// ## Generics
26///
27/// - `I: Iterator<Item = T>` -- Iterator over `T` values. These should be in the `]0; 1[` open range.
28///
29/// # Return / Errors
30///
31/// This method will return:
32/// - `Ok(())` if the operation is successful & the edge was split
33/// - `Err(SplitEdgeError)` if the operation fails & the edge is left unchanged. Causes of failure
34///   are described in [`SplitEdgeError`]'s documentation.
35///
36/// # Example
37///
38/// ```
39/// # use honeycomb_core::cmap::{CMap2, CMapBuilder, NULL_DART_ID};
40/// # use honeycomb_core::geometry::Vertex2;
41/// # use honeycomb_kernels::splits::splitn_edge;
42/// // before
43/// //    <--2---
44/// //  1         2
45/// //    ---1-->
46/// let mut map: CMap2<f64> = CMapBuilder::default()
47///                             .n_darts(2)
48///                             .build()
49///                             .unwrap();
50/// map.force_link::<2>(1, 2);
51/// map.force_write_vertex(1, (0.0, 0.0));
52/// map.force_write_vertex(2, (1.0, 0.0));
53/// // split
54/// assert!(splitn_edge(&mut map, 1, [0.25, 0.50, 0.75]).is_ok());
55/// // after
56/// //    <-<-<-<
57/// //  1 -3-4-5- 2
58/// //    >->->->
59/// let new_darts = [
60///     map.beta::<1>(1),
61///     map.beta::<1>(map.beta::<1>(1)),
62///     map.beta::<1>(map.beta::<1>(map.beta::<1>(1))),
63/// ];
64/// assert_eq!(&new_darts, &[3, 4, 5]);
65/// assert_eq!(map.force_read_vertex(3), Some(Vertex2(0.25, 0.0)));
66/// assert_eq!(map.force_read_vertex(4), Some(Vertex2(0.50, 0.0)));
67/// assert_eq!(map.force_read_vertex(5), Some(Vertex2(0.75, 0.0)));
68///
69/// assert_eq!(map.beta::<1>(1), 3);
70/// assert_eq!(map.beta::<1>(3), 4);
71/// assert_eq!(map.beta::<1>(4), 5);
72/// assert_eq!(map.beta::<1>(5), NULL_DART_ID);
73///
74/// assert_eq!(map.beta::<1>(2), 6);
75/// assert_eq!(map.beta::<1>(6), 7);
76/// assert_eq!(map.beta::<1>(7), 8);
77/// assert_eq!(map.beta::<1>(8), NULL_DART_ID);
78///
79/// assert_eq!(map.beta::<2>(1), 8);
80/// assert_eq!(map.beta::<2>(3), 7);
81/// assert_eq!(map.beta::<2>(4), 6);
82/// assert_eq!(map.beta::<2>(5), 2);
83/// ```
84#[allow(clippy::cast_possible_truncation)]
85pub fn splitn_edge<T: CoordsFloat>(
86    cmap: &mut CMap2<T>,
87    edge_id: EdgeIdType,
88    midpoint_vertices: impl IntoIterator<Item = T>,
89) -> Result<(), SplitEdgeError> {
90    // check pre-allocated darts reqs
91    let midpoint_vertices = midpoint_vertices.into_iter().collect::<Vec<_>>();
92    let n_t = midpoint_vertices.len();
93
94    // base darts making up the edge
95    let base_dart1 = edge_id as DartIdType;
96    let base_dart2 = cmap.beta::<2>(base_dart1);
97
98    let new_darts = if base_dart2 == NULL_DART_ID {
99        let tmp = cmap.add_free_darts(n_t);
100        (tmp..tmp + n_t as DartIdType)
101            .chain((0..n_t).map(|_| NULL_DART_ID))
102            .collect::<Vec<_>>()
103    } else {
104        let tmp = cmap.add_free_darts(2 * n_t);
105        (tmp..tmp + 2 * n_t as DartIdType).collect::<Vec<_>>()
106    };
107    // get the first and second halves
108    let (darts_fh, darts_sh) = (&new_darts[..n_t], &new_darts[n_t..]);
109
110    atomically_with_err(|trans| {
111        inner_splitn(
112            cmap,
113            trans,
114            base_dart1,
115            darts_fh,
116            darts_sh,
117            &midpoint_vertices,
118        )
119    })
120}
121
122#[allow(clippy::missing_errors_doc)]
123/// Split an edge into `n` segments.
124///
125/// <div class="warning">
126/// This implementation is 2D specific.
127/// </div>
128///
129/// This method is a variant of [`splitn_edge`] where inline dart allocations are removed. The
130/// aim of this variant is to enhance performance by enabling the user to pre-allocate a number
131/// of darts.
132///
133/// The method follows the same logic as the regular [`splitn_edge`], the only difference being
134/// that the new darts won't be added to the map on the fly. Instead, the method uses darts
135/// passed as argument (`new_darts`) to build the new segments. Consequently, there is no
136/// guarantee that IDs will be consistent between this and the regular method.
137///
138/// # Arguments
139///
140/// - `cmap: &mut CMap2<T>` -- Reference to the modified map.
141/// - `edge_id: EdgeIdentifier` -- Edge to split in two.
142/// - `new_darts: &[DartIdentifier]` -- Dart IDs used to build the new segments.
143/// - `midpoint_vertices: &[T]` -- Relative positions of new vertices, starting from the
144///   vertex of the dart sharing `edge_id` as its identifier.
145///
146/// ## Dart IDs Requirements & Usage
147///
148/// Because of the dimension, we can easily compute the number of dart needed to perform this
149/// operation. These are the requirements for the darts:
150/// - identifiers are passed as a slice:
151///   - slice length should verify `new_darts.len() == 2 * midpoint_vertices.len()`
152/// - the first half of the slice will always be used if the operation is successful.
153/// - the second half of the slice will only be used if the original edge is made of two darts;
154///   if that is not the case, the second half IDs can all be `NULL_DART_ID`s.
155/// - all of these darts should be free
156///
157/// # Return / Errors
158///
159/// This method will return:
160/// - `Ok(())` if the operation is successful & the edge was split
161/// - `Err(SplitEdgeError)` if the operation fails & the edge is left unchanged. Causes of failure
162///   are described in [`SplitEdgeError`]'s documentation and in requirements mentionned above.
163pub fn splitn_edge_transac<T: CoordsFloat>(
164    cmap: &CMap2<T>,
165    trans: &mut Transaction,
166    edge_id: EdgeIdType,
167    new_darts: &[DartIdType],
168    midpoint_vertices: &[T],
169) -> TransactionClosureResult<(), SplitEdgeError> {
170    // check pre-allocated darts reqs
171    let n_t = midpoint_vertices.len();
172    let n_d = new_darts.len();
173    if n_d != 2 * n_t {
174        abort(SplitEdgeError::WrongAmountDarts(2 * n_t, n_d))?;
175    }
176    // FIXME: is_free should be transactional
177    if new_darts.iter().any(|d| !cmap.is_free(*d)) {
178        abort(SplitEdgeError::InvalidDarts("one dart is not free"))?;
179    }
180    // get the first and second halves
181    let darts_fh = &new_darts[..n_t];
182    let darts_sh = &new_darts[n_t..];
183
184    // base darts making up the edge
185    let base_dart1 = edge_id as DartIdType;
186    let base_dart2 = cmap.beta_transac::<2>(trans, base_dart1)?;
187
188    if darts_fh.iter().any(|d| *d == NULL_DART_ID) {
189        abort(SplitEdgeError::InvalidDarts(
190            "one dart of the first half is null",
191        ))?;
192    }
193    if base_dart2 != NULL_DART_ID && darts_sh.iter().any(|d| *d == NULL_DART_ID) {
194        abort(SplitEdgeError::InvalidDarts(
195            "one dart of the second half is null",
196        ))?;
197    }
198
199    inner_splitn(
200        cmap,
201        trans,
202        base_dart1,
203        darts_fh,
204        darts_sh,
205        midpoint_vertices,
206    )
207}
208
209// --- common inner routine
210
211fn inner_splitn<T: CoordsFloat>(
212    cmap: &CMap2<T>,
213    trans: &mut Transaction,
214    base_dart1: DartIdType,
215    darts_fh: &[DartIdType], //first half
216    darts_sh: &[DartIdType], //second half
217    midpoint_vertices: &[T],
218) -> TransactionClosureResult<(), SplitEdgeError> {
219    if midpoint_vertices
220        .iter()
221        .any(|t| (*t >= T::one()) | (*t <= T::zero()))
222    {
223        abort(SplitEdgeError::VertexBound)?;
224    }
225
226    let base_dart2 = cmap.beta_transac::<2>(trans, base_dart1)?;
227    let b1d1_old = cmap.beta_transac::<1>(trans, base_dart1)?;
228
229    let (vid1, vid2) = (
230        cmap.vertex_id_transac(trans, base_dart1)?,
231        cmap.vertex_id_transac(
232            trans,
233            if b1d1_old != NULL_DART_ID {
234                b1d1_old
235            } else if base_dart2 != NULL_DART_ID {
236                base_dart2
237            } else {
238                abort(SplitEdgeError::UndefinedEdge)?
239            },
240        )?,
241    );
242    let (Some(v1), Some(v2)) = (
243        cmap.read_vertex(trans, vid1)?,
244        cmap.read_vertex(trans, vid2)?,
245    ) else {
246        abort(SplitEdgeError::UndefinedEdge)?
247    };
248    let seg = v2 - v1;
249
250    // unsew current dart
251    if b1d1_old != NULL_DART_ID {
252        try_or_coerce!(cmap.unlink::<1>(trans, base_dart1), SplitEdgeError);
253    }
254    //
255    if base_dart2 != NULL_DART_ID {
256        try_or_coerce!(cmap.unlink::<2>(trans, base_dart1), SplitEdgeError);
257    }
258    // insert new vertices / darts on base_dart1's side
259    let mut prev_d = base_dart1;
260    for (&t, &new_d) in midpoint_vertices.iter().zip(darts_fh.iter()) {
261        let new_v = v1 + seg * t;
262        try_or_coerce!(cmap.link::<1>(trans, prev_d, new_d), SplitEdgeError);
263        cmap.write_vertex(trans, new_d, new_v)?;
264        prev_d = new_d;
265    }
266    try_or_coerce!(cmap.link::<1>(trans, prev_d, b1d1_old), SplitEdgeError);
267
268    // if b2(base_dart1) is defined, insert vertices / darts on its side too
269    if base_dart2 != NULL_DART_ID {
270        let b1d2_old = cmap.beta_transac::<1>(trans, base_dart2)?;
271        if b1d2_old != NULL_DART_ID {
272            try_or_coerce!(cmap.unlink::<1>(trans, base_dart2), SplitEdgeError);
273        }
274        let mut prev_d = base_dart2;
275        for (d, new_d) in darts_fh.iter().rev().zip(darts_sh.iter()) {
276            try_or_coerce!(cmap.link::<2>(trans, prev_d, *d), SplitEdgeError);
277            try_or_coerce!(cmap.link::<1>(trans, prev_d, *new_d), SplitEdgeError);
278            prev_d = *new_d;
279        }
280        if b1d2_old != NULL_DART_ID {
281            try_or_coerce!(cmap.link::<1>(trans, prev_d, b1d2_old), SplitEdgeError);
282        }
283        try_or_coerce!(cmap.link::<2>(trans, prev_d, base_dart1), SplitEdgeError);
284    }
285
286    Ok(())
287}
honeycomb_kernels/splits/edge_multiple.rs

honeycomb_kernels/splits/
edge_multiple.rs
