iron_shapes_booleanop/
connectivity_extraction.rs

1// SPDX-FileCopyrightText: 2022 Thomas Kramer
2//
3// SPDX-License-Identifier: AGPL-3.0-or-later
4
5//! Extract the connectivity graph of polygons.
6
7use iron_shapes::prelude::*;
8
9use std::fmt::Debug;
10
11use crate::sweep_line::intersection::subdivide_segments;
12use crate::sweep_line::sweep_event::SweepEvent;
13use crate::PolygonSemantics;
14use std::collections::{BinaryHeap, HashMap, HashSet};
15use std::hash::Hash;
16use std::rc::Rc;
17
18/// Extract a connectivity of a set of polygons.
19/// The polygons are supplied in the form of an interator over the polygon edges. If the supplied edges are inconsistent, e.g. don't form closed polygon shapes,
20/// then the result is undefined.
21///
22/// Each edge must be labelled with the identifier of the polygon it belongs to.
23/// Connectivity is encoded as an iterator over multi-graph edges.
24/// Each consists of the IDs of the two touching polygons and a location where the both polygons touch.
25/// Edges can appear many times.
26///
27/// # Examples
28/// ```
29/// use iron_shapes::prelude::*;
30/// use iron_shapes::traits::Translate;
31/// use iron_shapes_booleanop::connectivity_extraction::*;
32/// use iron_shapes_booleanop::*;
33/// use std::collections::HashSet;
34///
35/// let p0 = Polygon::from(vec![(0f64, 0.), (2., 0.), (2., 2.), (0., 2.)]);
36/// let p1 = p0.translate((1., 1.).into());
37/// let p2 = p0.translate((0., 100.).into()); // Far away, not touching anything.
38///
39/// let polygons = vec![p0, p1, p2];
40///
41/// // Convert the polygons into edges labelled with an identifier of their polygon.
42/// let polygon_edges = polygons
43///     .iter()
44///     .enumerate()
45///     .flat_map(|(id, polygon)| polygon.all_edges_iter().map(move |e| (e, id)));
46///
47/// let connectivity_graph = extract_connectivity_graph(
48///     edge_intersection_float,
49///     polygon_edges,
50///     PolygonSemantics::Union,
51/// );
52///
53/// // p0 and p1 are connected.
54/// assert_eq!(connectivity_graph.get(&0), Some(&HashSet::from([1])));
55/// assert_eq!(connectivity_graph.get(&1), Some(&HashSet::from([0])));
56///
57/// // p2 is not connected to any other polygon.
58/// assert_eq!(connectivity_graph.get(&2), None);
59/// ```
60pub fn extract_connectivity<'a, I, T, ID>(
61    edge_intersection: I,
62    polygon_edges: impl Iterator<Item = (Edge<T>, ID)>,
63    polygon_semantics: PolygonSemantics,
64) -> impl Iterator<Item = (ID, ID, Point<T>)>
65where
66    I: Fn(&Edge<T>, &Edge<T>) -> EdgeIntersection<T, T, Edge<T>>,
67    T: CoordinateType + Debug + 'a,
68    ID: Clone + Hash + Eq,
69{
70    // Prepare the event queue.
71    let mut event_queue: BinaryHeap<Rc<SweepEvent<_, Counter<ID>, ID>>> =
72        crate::init_events::fill_queue(polygon_edges);
73
74    // Compute the edge intersections, the result is a set of sorted non-intersecting edges stored
75    // as events.
76    let sorted_events = subdivide_segments(edge_intersection, &mut event_queue, |event, prev| {
77        update_counter(event, prev)
78    });
79
80    // Extract connectivity graph.
81    {
82        // Take left events only.
83        let left_events = sorted_events.into_iter().filter(|e| e.is_left_event());
84
85        // Check if an edge count signals the inside or the outside of a polygon.
86        let is_inside = move |count: i32| -> bool {
87            match polygon_semantics {
88                PolygonSemantics::Union => count != 0,
89                PolygonSemantics::XOR => count % 2 != 0,
90            }
91        };
92
93        // Create iterator of graph edges.
94        // Edges may appear multiple times. Each edge comes with a point which indicates the location of the connectivity.
95        let multi_graph_edges = left_events.flat_map(move |current_event| {
96            // Get connectivity of this event.
97
98            debug_assert!(current_event.is_left_event());
99            let shape_id = current_event.property.as_ref().unwrap().clone(); // Left event must have the property.
100            let point = current_event.p; // Location of connectivity.
101
102            // Take counter from event to own it.
103            // This destroys the structure of the sweep events.
104            let counter =
105                current_event.with_counter_mut(|ctr| std::mem::replace(ctr, Default::default()));
106
107            // Look at edge counts and find shapes enclosing the current event.
108            let shape_id_clone = shape_id.clone();
109            let connected_ids = counter
110                .counters
111                .into_iter()
112                .filter(move |(id, _count)| id != &shape_id_clone) // Look only at other polygons.
113                .filter(move |(_id, count)| is_inside(*count))
114                .map(|(id, _)| id);
115
116            connected_ids.map(move |id| (shape_id.clone(), id, point))
117        });
118
119        multi_graph_edges
120    }
121}
122
123/// Extract a connectivity graph of a set of polygons.
124pub fn extract_connectivity_graph<'a, I, T, ID>(
125    edge_intersection: I,
126    polygon_edges: impl Iterator<Item = (Edge<T>, ID)>,
127    polygon_semantics: PolygonSemantics,
128) -> HashMap<ID, HashSet<ID>>
129where
130    I: Fn(&Edge<T>, &Edge<T>) -> EdgeIntersection<T, T, Edge<T>>,
131    T: CoordinateType + Debug + 'a,
132    ID: Clone + Hash + Eq,
133{
134    let multi_graph_edges =
135        extract_connectivity(edge_intersection, polygon_edges, polygon_semantics);
136
137    let mut graph: HashMap<ID, HashSet<ID>> = Default::default();
138    // Insert graph edges.
139    for (id_a, id_b, _point) in multi_graph_edges {
140        graph
141            .entry(id_a.clone())
142            .or_insert(Default::default())
143            .insert(id_b.clone());
144        // Insert reverse edge.
145        graph.entry(id_b).or_insert(Default::default()).insert(id_a);
146    }
147
148    graph
149}
150
151#[derive(Clone)]
152struct Counter<K> {
153    counters: HashMap<K, i32>,
154}
155
156impl<K> Default for Counter<K> {
157    fn default() -> Self {
158        Self {
159            counters: Default::default(),
160        }
161    }
162}
163
164fn update_counter<T, ID>(
165    event: &Rc<SweepEvent<T, Counter<ID>, ID>>,
166    maybe_prev: Option<&Rc<SweepEvent<T, Counter<ID>, ID>>>,
167) where
168    T: CoordinateType,
169    ID: Clone + Hash + Eq,
170{
171    debug_assert!(event.is_left_event());
172
173    // Update counter.
174    event.with_counter_mut(|ctr| {
175        let edge_id = event.property.as_ref().unwrap(); // Property must be set for all left events.
176
177        // Clone counters of previous edge.
178        let prev_counter = maybe_prev
179            .as_ref()
180            .map(|prev| {
181                debug_assert!(prev.is_left_event());
182                prev.with_counter(|ctr| ctr.clone())
183            })
184            .unwrap_or(Default::default());
185
186        *ctr = prev_counter;
187
188        // Increment counter.
189        {
190            let edge_weight = event.edge_weight();
191            let current_counter = ctr.counters.entry(edge_id.clone()).or_insert(0);
192            *current_counter += edge_weight;
193
194            // Remove counter if it is zero.
195            if *current_counter == 0 {
196                ctr.counters.remove(edge_id);
197            };
198        }
199    });
200}
iron_shapes_booleanop/connectivity_extraction.rs

iron_shapes_booleanop/
connectivity_extraction.rs
