geometry_kernel/
noding.rs

1use crate::precision::PrecisionModel;
2use crate::predicates::{point_on_segment, segment_intersection, SegmentIntersection};
3use crate::types::{Coord, LineString};
4
5#[derive(Debug, Clone, PartialEq)]
6pub struct NodedLinework {
7    pub lines: Vec<LineString>,
8}
9
10pub fn node_lines(lines: &[LineString], precision: PrecisionModel) -> NodedLinework {
11    let segments = input_segments(lines, precision);
12    let mut split_points = segments
13        .iter()
14        .map(|segment| vec![segment.start, segment.end])
15        .collect::<Vec<_>>();
16    let mut segment_order = (0..segments.len()).collect::<Vec<_>>();
17    segment_order.sort_by(|left, right| {
18        segments[*left]
19            .min_x
20            .partial_cmp(&segments[*right].min_x)
21            .unwrap_or(std::cmp::Ordering::Equal)
22    });
23
24    for (order_index, &left_index) in segment_order.iter().enumerate() {
25        let left = segments[left_index];
26        for &right_index in &segment_order[order_index + 1..] {
27            let right = segments[right_index];
28            if right.min_x > left.max_x + precision.epsilon() {
29                break;
30            }
31            if left.bbox_disjoint(right, precision) {
32                continue;
33            }
34
35            match segment_intersection(left.start, left.end, right.start, right.end, precision) {
36                Some(SegmentIntersection::Point(point)) => {
37                    push_split_point(&mut split_points[left_index], point, precision);
38                    push_split_point(&mut split_points[right_index], point, precision);
39                }
40                Some(SegmentIntersection::Overlap(start, end)) => {
41                    for point in [start, end] {
42                        if point_on_segment(point, left.start, left.end, precision) {
43                            push_split_point(&mut split_points[left_index], point, precision);
44                        }
45                        if point_on_segment(point, right.start, right.end, precision) {
46                            push_split_point(&mut split_points[right_index], point, precision);
47                        }
48                    }
49                }
50                None => {}
51            }
52        }
53    }
54
55    let mut lines_out = Vec::new();
56    for (segment, points) in segments.iter().zip(split_points.iter_mut()) {
57        sort_along_segment(points, segment.start, segment.end);
58        dedup_points(points, precision);
59
60        for pair in points.windows(2) {
61            if !precision.same_coord(pair[0], pair[1]) {
62                lines_out.push(LineString::new(vec![pair[0], pair[1]]));
63            }
64        }
65    }
66
67    NodedLinework { lines: lines_out }
68}
69
70#[derive(Debug, Clone, Copy)]
71struct Segment {
72    start: Coord,
73    end: Coord,
74    min_x: f64,
75    min_y: f64,
76    max_x: f64,
77    max_y: f64,
78}
79
80impl Segment {
81    fn new(start: Coord, end: Coord) -> Self {
82        Self {
83            start,
84            end,
85            min_x: start.x.min(end.x),
86            min_y: start.y.min(end.y),
87            max_x: start.x.max(end.x),
88            max_y: start.y.max(end.y),
89        }
90    }
91
92    fn bbox_disjoint(self, other: Self, precision: PrecisionModel) -> bool {
93        let eps = precision.epsilon();
94        self.min_x > other.max_x + eps
95            || other.min_x > self.max_x + eps
96            || self.min_y > other.max_y + eps
97            || other.min_y > self.max_y + eps
98    }
99}
100
101fn input_segments(lines: &[LineString], precision: PrecisionModel) -> Vec<Segment> {
102    lines
103        .iter()
104        .flat_map(|line| precision.snap_line(line).segments().collect::<Vec<_>>())
105        .filter(|(a, b)| !precision.same_coord(*a, *b))
106        .map(|(start, end)| Segment::new(start, end))
107        .collect()
108}
109
110fn push_split_point(points: &mut Vec<Coord>, point: Coord, precision: PrecisionModel) {
111    let snapped = precision.snap_coord(point);
112    if !points
113        .iter()
114        .any(|existing| precision.same_coord(*existing, snapped))
115    {
116        points.push(snapped);
117    }
118}
119
120fn sort_along_segment(points: &mut [Coord], a: Coord, b: Coord) {
121    let use_x = (b.x - a.x).abs() >= (b.y - a.y).abs();
122    points.sort_by(|left, right| {
123        let left_value = if use_x { left.x } else { left.y };
124        let right_value = if use_x { right.x } else { right.y };
125        left_value
126            .partial_cmp(&right_value)
127            .unwrap_or(std::cmp::Ordering::Equal)
128    });
129}
130
131fn dedup_points(points: &mut Vec<Coord>, precision: PrecisionModel) {
132    let mut deduped = Vec::with_capacity(points.len());
133    for point in points.iter().copied() {
134        if deduped
135            .last()
136            .is_none_or(|last| !precision.same_coord(*last, point))
137        {
138            deduped.push(point);
139        }
140    }
141    *points = deduped;
142}
geometry_kernel/noding.rs

geometry_kernel/
noding.rs
