geo_booleanop/boolean/
subdivide_segments.rs

1use super::compare_segments::compare_segments;
2use super::compute_fields::compute_fields;
3use super::helper::{BoundingBox, Float};
4use super::possible_intersection::possible_intersection;
5use super::sweep_event::SweepEvent;
6use super::Operation;
7use crate::splay::SplaySet;
8use std::collections::BinaryHeap;
9use std::rc::Rc;
10
11#[cfg(feature = "debug-booleanop")]
12use super::sweep_event::JsonDebug;
13
14pub fn subdivide<F>(
15    event_queue: &mut BinaryHeap<Rc<SweepEvent<F>>>,
16    sbbox: &BoundingBox<F>,
17    cbbox: &BoundingBox<F>,
18    operation: Operation,
19) -> Vec<Rc<SweepEvent<F>>>
20where
21    F: Float,
22{
23    let mut sweep_line = SplaySet::<Rc<SweepEvent<F>>, _>::new(compare_segments);
24    let mut sorted_events: Vec<Rc<SweepEvent<F>>> = Vec::new();
25    let rightbound = sbbox.max.x.min(cbbox.max.x);
26
27    while let Some(event) = event_queue.pop() {
28        #[cfg(feature = "debug-booleanop")]
29        {
30            println!("\n{{\"processEvent\": {}}}", event.to_json_debug());
31        }
32        sorted_events.push(event.clone());
33
34        if operation == Operation::Intersection && event.point.x > rightbound
35            || operation == Operation::Difference && event.point.x > sbbox.max.x
36        {
37            break;
38        }
39
40        if event.is_left() {
41            sweep_line.insert(event.clone());
42
43            let maybe_prev = sweep_line.prev(&event);
44            let maybe_next = sweep_line.next(&event);
45
46            compute_fields(&event, maybe_prev, operation);
47
48            if let Some(next) = maybe_next {
49                #[cfg(feature = "debug-booleanop")]
50                {
51                    println!("{{\"seNextEvent\": {}}}", next.to_json_debug());
52                }
53                if possible_intersection(&event, &next, event_queue) == 2 {
54                    // Recompute fields for current segment and the one above (in bottom to top order)
55                    compute_fields(&event, maybe_prev, operation);
56                    compute_fields(&next, Some(&event), operation);
57                }
58            }
59
60            if let Some(prev) = maybe_prev {
61                #[cfg(feature = "debug-booleanop")]
62                {
63                    println!("{{\"sePrevEvent\": {}}}", prev.to_json_debug());
64                }
65                if possible_intersection(&prev, &event, event_queue) == 2 {
66                    let maybe_prev_prev = sweep_line.prev(&prev);
67                    // Recompute fields for current segment and the one below (in bottom to top order)
68                    compute_fields(&prev, maybe_prev_prev, operation);
69                    compute_fields(&event, Some(prev), operation);
70                }
71            }
72        } else if let Some(other_event) = event.get_other_event() {
73            // This debug assert is only true, if we compare segments in the sweep line
74            // based on identity (curently), and not by value (done previously).
75            debug_assert!(
76                sweep_line.contains(&other_event),
77                "Sweep line misses event to be removed"
78            );
79            if sweep_line.contains(&other_event) {
80                let maybe_prev = sweep_line.prev(&other_event).cloned();
81                let maybe_next = sweep_line.next(&other_event).cloned();
82
83                if let (Some(prev), Some(next)) = (maybe_prev, maybe_next) {
84                    #[cfg(feature = "debug-booleanop")]
85                    {
86                        println!("Possible post intersection");
87                        println!("{{\"sePostNextEvent\": {}}}", next.to_json_debug());
88                        println!("{{\"sePostPrevEvent\": {}}}", prev.to_json_debug());
89                    }
90                    possible_intersection(&prev, &next, event_queue);
91                }
92
93                #[cfg(feature = "debug-booleanop")]
94                {
95                    println!("{{\"removing\": {}}}", other_event.to_json_debug());
96                }
97                sweep_line.remove(&other_event);
98            }
99        }
100    }
101
102    sorted_events
103}
geo_booleanop/boolean/subdivide_segments.rs

geo_booleanop/boolean/
subdivide_segments.rs
