honeycomb_kernels/grisubal/routines/
process_intersecs_data.rs

1//! Step 2 implementation
2//!
3//! The main goal of this step is tp precompute information to:
4//! - parallelize step 3
5//! - make step 3 and step 4 independent from each other
6
7// ------ IMPORTS
8
9use std::collections::HashMap;
10
11use honeycomb_core::cmap::{CMap2, DartIdType, EdgeIdType, NULL_DART_ID};
12use honeycomb_core::geometry::CoordsFloat;
13
14use super::{DartSlices, IntersectionsPerEdge};
15
16// ------ CONTENT
17
18pub(crate) fn group_intersections_per_edge<T: CoordsFloat>(
19    cmap: &mut CMap2<T>,
20    intersection_metadata: Vec<(DartIdType, T)>,
21) -> (IntersectionsPerEdge<T>, DartSlices) {
22    // group intersection data per edge, and associate an ID to each
23    let mut edge_intersec: HashMap<EdgeIdType, Vec<(usize, T, DartIdType)>> = HashMap::new();
24    intersection_metadata
25        .into_iter()
26        .filter(|(_, t)| !t.is_nan())
27        .enumerate()
28        .for_each(|(idx, (dart_id, mut t))| {
29            // classify intersections per edge_id & adjust t if  needed
30            let edge_id = cmap.edge_id(dart_id);
31            // condition works in 2D because edges are 2 darts at most
32            if edge_id != dart_id {
33                t = T::one() - t;
34            }
35            if let Some(storage) = edge_intersec.get_mut(&edge_id) {
36                // not the first intersection with this given edge
37                storage.push((idx, t, dart_id));
38            } else {
39                // first intersection with this given edge
40                edge_intersec.insert(edge_id, vec![(idx, t, dart_id)]);
41            }
42        });
43
44    // sort per t for later
45    for vs in edge_intersec.values_mut() {
46        // panic unreachable because t s.t. t == NaN have been filtered previously
47        vs.sort_by(|(_, t1, _), (_, t2, _)| t1.partial_cmp(t2).expect("E: unreachable"));
48    }
49
50    // prealloc darts that will be used for vertex insertion
51    let n_darts_per_seg: Vec<_> = edge_intersec.values().map(|vs| 2 * vs.len()).collect();
52    let n_tot: usize = n_darts_per_seg.iter().sum();
53    let tmp = cmap.add_free_darts(n_tot) as usize;
54    // the prefix sum gives an offset that corresponds to the starting index of each slice, minus
55    // the location of the allocated dart block (given by `tmp`)
56    // end of the slice is deduced using these values and the number of darts the current seg needs
57    let prefix_sum: Vec<usize> = n_darts_per_seg
58        .iter()
59        .scan(0, |state, &n_d| {
60            *state += n_d;
61            Some(*state - n_d) // we want an offset, not the actual sum
62        })
63        .collect();
64
65    #[allow(clippy::cast_possible_truncation)]
66    let dart_slices: Vec<Vec<DartIdType>> = n_darts_per_seg
67        .iter()
68        .zip(prefix_sum.iter())
69        .map(|(n_d, start)| {
70            ((tmp + start) as DartIdType..(tmp + start + n_d) as DartIdType).collect::<Vec<_>>()
71        })
72        .collect();
73
74    (edge_intersec, dart_slices)
75}
76
77pub(crate) fn compute_intersection_ids<T: CoordsFloat>(
78    n_intersec: usize,
79    edge_intersec: &IntersectionsPerEdge<T>,
80    dart_slices: &DartSlices,
81) -> Vec<DartIdType> {
82    let mut res = vec![NULL_DART_ID; n_intersec];
83    for ((edge_id, vs), new_darts) in edge_intersec.iter().zip(dart_slices.iter()) {
84        // order should be consistent between collection because of the sort_by call
85        let hl = new_darts.len() / 2; // half-length; also equal to n_intermediate
86        let fh = &new_darts[..hl]; // first half;  used for the side of edge id
87        let sh = &new_darts[hl..]; // second half; used for the opposite side
88        for (i, (id, _, old_dart_id)) in vs.iter().enumerate() {
89            // readjust according to intersection side
90            res[*id] = if *old_dart_id == *edge_id {
91                fh[i]
92            } else {
93                sh[hl - 1 - i]
94            };
95        }
96    }
97    res
98}
honeycomb_kernels/grisubal/routines/process_intersecs_data.rs

honeycomb_kernels/grisubal/routines/
process_intersecs_data.rs
