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(|(a, b)| vec![*a, *b])
15        .collect::<Vec<_>>();
16
17    for left_index in 0..segments.len() {
18        for right_index in left_index + 1..segments.len() {
19            let (a1, a2) = segments[left_index];
20            let (b1, b2) = segments[right_index];
21
22            match segment_intersection(a1, a2, b1, b2, precision) {
23                Some(SegmentIntersection::Point(point)) => {
24                    push_split_point(&mut split_points[left_index], point, precision);
25                    push_split_point(&mut split_points[right_index], point, precision);
26                }
27                Some(SegmentIntersection::Overlap(start, end)) => {
28                    for point in [start, end] {
29                        if point_on_segment(point, a1, a2, precision) {
30                            push_split_point(&mut split_points[left_index], point, precision);
31                        }
32                        if point_on_segment(point, b1, b2, precision) {
33                            push_split_point(&mut split_points[right_index], point, precision);
34                        }
35                    }
36                }
37                None => {}
38            }
39        }
40    }
41
42    let mut lines_out = Vec::new();
43    for ((a, b), points) in segments.iter().zip(split_points.iter_mut()) {
44        sort_along_segment(points, *a, *b);
45        dedup_points(points, precision);
46
47        for pair in points.windows(2) {
48            if !precision.same_coord(pair[0], pair[1]) {
49                lines_out.push(LineString::new(vec![pair[0], pair[1]]));
50            }
51        }
52    }
53
54    NodedLinework { lines: lines_out }
55}
56
57fn input_segments(lines: &[LineString], precision: PrecisionModel) -> Vec<(Coord, Coord)> {
58    lines
59        .iter()
60        .flat_map(|line| precision.snap_line(line).segments().collect::<Vec<_>>())
61        .filter(|(a, b)| !precision.same_coord(*a, *b))
62        .collect()
63}
64
65fn push_split_point(points: &mut Vec<Coord>, point: Coord, precision: PrecisionModel) {
66    let snapped = precision.snap_coord(point);
67    if !points
68        .iter()
69        .any(|existing| precision.same_coord(*existing, snapped))
70    {
71        points.push(snapped);
72    }
73}
74
75fn sort_along_segment(points: &mut [Coord], a: Coord, b: Coord) {
76    let use_x = (b.x - a.x).abs() >= (b.y - a.y).abs();
77    points.sort_by(|left, right| {
78        let left_value = if use_x { left.x } else { left.y };
79        let right_value = if use_x { right.x } else { right.y };
80        left_value
81            .partial_cmp(&right_value)
82            .unwrap_or(std::cmp::Ordering::Equal)
83    });
84}
85
86fn dedup_points(points: &mut Vec<Coord>, precision: PrecisionModel) {
87    let mut deduped = Vec::with_capacity(points.len());
88    for point in points.iter().copied() {
89        if deduped
90            .last()
91            .is_none_or(|last| !precision.same_coord(*last, point))
92        {
93            deduped.push(point);
94        }
95    }
96    *points = deduped;
97}
geometry_kernel/noding.rs

geometry_kernel/
noding.rs
