geometry_overlay/turn/
get_turns.rs

1//! OVL2.T2 / OVL2.T3 — collect the turns between two rings, and
2//! between two polygons.
3//!
4//! Mirrors `boost/geometry/algorithms/detail/overlay/get_turns.hpp`,
5//! which drives the segment-intersection kernel over every segment pair
6//! of the two inputs and records a turn per intersection. The port
7//! keeps the same shape: a doubly-nested walk over the ring segments,
8//! calling [`segment_intersection`](fn@crate::predicate::segment_intersection::segment_intersection)
9//! and pushing a [`Turn`] for each hit.
10//!
11//! This task does **not** classify the turns beyond the raw
12//! segment-intersection outcome — that is OVL2.T4
13//! ([`classify`](super::classify)). Here
14//! every turn is emitted with [`Method::None`] and unset operations,
15//! carrying only the point and the two [`SegmentId`]s.
16
17use alloc::vec::Vec;
18
19use geometry_coords::CoordinateScalar;
20use geometry_model::Segment;
21use geometry_trait::{Point, PointMut, Polygon as PolygonTrait, Ring as RingTrait};
22
23use super::info::{Method, Operation, RingKind, SegmentId, Turn};
24use crate::predicate::segment_intersection::{SegmentIntersection, segment_intersection};
25use crate::turn::classify::set_from_outcome;
26
27/// The point bound shared by every `get_turns` entry point: the point
28/// must be constructible (for the intersection point Boost returns in
29/// the input type) and cheaply copyable so segments can be built from
30/// vertex pairs. Blanket-implemented for every qualifying point type;
31/// callers never name it directly.
32pub trait TurnPoint: PointMut + Default + Copy {}
33impl<P: PointMut + Default + Copy> TurnPoint for P {}
34
35/// Collect the turns between two rings.
36///
37/// Iterates every segment of `r1` against every segment of `r2`, calls
38/// the segment-intersection kernel, and pushes a classified [`Turn`]
39/// per intersection. `source1` / `source2` label which input each ring
40/// is (`0` / `1`), and `ring1` / `ring2` record which ring of that
41/// input it is — so the resulting [`SegmentId`]s are globally unique.
42///
43/// Mirrors the ring-pair inner loop of Boost's `get_turns`
44/// (`get_turns.hpp`). Collinear-overlap intersections contribute their
45/// two delimiting points as two turns, matching Boost recording a turn
46/// at each end of a collinear stretch.
47///
48/// # Examples
49///
50/// ```
51/// use geometry_cs::Cartesian;
52/// use geometry_model::{Point2D, Ring};
53/// use geometry_overlay::turn::{get_turns_ring_ring, RingKind};
54///
55/// type P = Point2D<f64, Cartesian>;
56/// // Two squares overlapping at a corner — their boundaries cross
57/// // at two points.
58/// let a: Ring<P> = Ring::from_vec(vec![
59///     P::new(0.0, 0.0), P::new(2.0, 0.0), P::new(2.0, 2.0), P::new(0.0, 2.0), P::new(0.0, 0.0),
60/// ]);
61/// let b: Ring<P> = Ring::from_vec(vec![
62///     P::new(1.0, 1.0), P::new(3.0, 1.0), P::new(3.0, 3.0), P::new(1.0, 3.0), P::new(1.0, 1.0),
63/// ]);
64/// let turns = get_turns_ring_ring(&a, 0, RingKind::Exterior, &b, 1, RingKind::Exterior);
65/// assert_eq!(turns.len(), 2);
66/// ```
67#[must_use]
68pub fn get_turns_ring_ring<R1, R2, P>(
69    r1: &R1,
70    source1: usize,
71    ring1: RingKind,
72    r2: &R2,
73    source2: usize,
74    ring2: RingKind,
75) -> Vec<Turn<P>>
76where
77    R1: RingTrait<Point = P>,
78    R2: RingTrait<Point = P>,
79    P: TurnPoint,
80    P::Scalar: CoordinateScalar + Into<f64>,
81{
82    let segs1 = ring_segments(r1);
83    let segs2 = ring_segments(r2);
84    let mut turns = Vec::new();
85    collect_pair(&segs1, source1, ring1, &segs2, source2, ring2, &mut turns);
86    turns
87}
88
89/// Collect the turns between two polygons.
90///
91/// Generalises [`get_turns_ring_ring`] over every `(exterior, interior)`
92/// ring pair of the two polygons: exterior×exterior, exterior×hole,
93/// hole×exterior, and hole×hole. Mirrors the ring-walk in Boost's
94/// `get_turns` for areal inputs (`get_turns.hpp`).
95///
96/// # Examples
97///
98/// ```
99/// use geometry_cs::Cartesian;
100/// use geometry_model::{polygon, Point2D, Polygon};
101/// use geometry_overlay::turn::get_turns_polygon_polygon;
102///
103/// type P = Point2D<f64, Cartesian>;
104/// let a: Polygon<P> = polygon![[(0.0, 0.0), (2.0, 0.0), (2.0, 2.0), (0.0, 2.0), (0.0, 0.0)]];
105/// let b: Polygon<P> = polygon![[(1.0, 1.0), (3.0, 1.0), (3.0, 3.0), (1.0, 3.0), (1.0, 1.0)]];
106/// let turns = get_turns_polygon_polygon(&a, &b);
107/// assert_eq!(turns.len(), 2);
108/// ```
109#[must_use]
110pub fn get_turns_polygon_polygon<G1, G2, P>(g1: &G1, g2: &G2) -> Vec<Turn<P>>
111where
112    G1: PolygonTrait<Point = P>,
113    G2: PolygonTrait<Point = P>,
114    P: TurnPoint,
115    P::Scalar: CoordinateScalar + Into<f64>,
116{
117    let mut turns = Vec::new();
118
119    // Every ring of g1 (source 0) against every ring of g2 (source 1).
120    let rings1 = rings_of(g1);
121    let rings2 = rings_of(g2);
122    for &(ring1, r1) in &rings1 {
123        let segs1 = ring_segments(r1);
124        for &(ring2, r2) in &rings2 {
125            let segs2 = ring_segments(r2);
126            collect_pair(&segs1, 0, ring1, &segs2, 1, ring2, &mut turns);
127        }
128    }
129    turns
130}
131
132/// Intersect every segment of the first ring against every segment of
133/// the second, classify each hit at emission, and append the resulting
134/// turns to `out`.
135///
136/// A collinear overlap contributes a turn at each end of the shared
137/// stretch, matching Boost recording a turn at both ends of a collinear
138/// run.
139#[allow(clippy::too_many_arguments)]
140fn collect_pair<P>(
141    segs1: &[(P, P)],
142    source1: usize,
143    ring1: RingKind,
144    segs2: &[(P, P)],
145    source2: usize,
146    ring2: RingKind,
147    out: &mut Vec<Turn<P>>,
148) where
149    P: TurnPoint,
150    P::Scalar: CoordinateScalar + Into<f64> + PartialEq,
151{
152    for (i1, &(a1, b1)) in segs1.iter().enumerate() {
153        let s1 = Segment::new(a1, b1);
154        for (i2, &(a2, b2)) in segs2.iter().enumerate() {
155            let s2 = Segment::new(a2, b2);
156            let id1 = SegmentId {
157                source_index: source1,
158                ring: ring1,
159                segment_index: i1,
160            };
161            let id2 = SegmentId {
162                source_index: source2,
163                ring: ring2,
164                segment_index: i2,
165            };
166            let outcome = segment_intersection::<Segment<P>, P>(&s1, &s2);
167            match outcome {
168                SegmentIntersection::Disjoint | SegmentIntersection::OutOfRange => {}
169                SegmentIntersection::Single(point) => {
170                    out.push(classified(point, id1, id2, &outcome, &a1, &b1, &a2, &b2));
171                }
172                SegmentIntersection::Collinear { from, to } => {
173                    out.push(classified(from, id1, id2, &outcome, &a1, &b1, &a2, &b2));
174                    out.push(classified(to, id1, id2, &outcome, &a1, &b1, &a2, &b2));
175                }
176            }
177        }
178    }
179}
180
181/// Build a turn at `point` and classify it from the intersection
182/// outcome and the four segment endpoints.
183#[allow(clippy::too_many_arguments)]
184fn classified<P>(
185    point: P,
186    id1: SegmentId,
187    id2: SegmentId,
188    outcome: &SegmentIntersection<P>,
189    a0: &P,
190    a1: &P,
191    b0: &P,
192    b1: &P,
193) -> Turn<P>
194where
195    P: Point,
196    P::Scalar: PartialEq,
197{
198    let mut turn = Turn {
199        point,
200        method: Method::None,
201        operations: [Operation::new(id1), Operation::new(id2)],
202        touch_only: false,
203    };
204    set_from_outcome(&mut turn, outcome, a0, a1, b0, b1);
205    turn
206}
207
208/// The ordered list of `(start, end)` vertex pairs making up a ring's
209/// segments. A closed ring (the default) repeats its first vertex as
210/// its last, so consecutive pairs already close the ring; an unclosed
211/// ring gets the wrap-around segment appended.
212fn ring_segments<R, P>(ring: &R) -> Vec<(P, P)>
213where
214    R: RingTrait<Point = P>,
215    P: Copy + Point,
216{
217    let pts: Vec<P> = ring.points().copied().collect();
218    let mut segs = Vec::new();
219    if pts.len() < 2 {
220        return segs;
221    }
222    for w in pts.windows(2) {
223        segs.push((w[0], w[1]));
224    }
225    // Close the ring if the source did not repeat the first vertex.
226    let first = pts[0];
227    let last = pts[pts.len() - 1];
228    if !same_point(&first, &last) {
229        segs.push((last, first));
230    }
231    segs
232}
233
234/// Coordinate equality on two points (their `Cs` phantom blocks a
235/// derived `PartialEq`, so compare x and y directly).
236fn same_point<P: Point>(a: &P, b: &P) -> bool
237where
238    P::Scalar: PartialEq,
239{
240    a.get::<0>() == b.get::<0>() && a.get::<1>() == b.get::<1>()
241}
242
243/// Every ring of a polygon, tagged with its [`RingKind`]: the exterior
244/// first, then each interior ring in order.
245fn rings_of<G, P>(g: &G) -> Vec<(RingKind, &G::Ring)>
246where
247    G: PolygonTrait<Point = P>,
248    P: Point,
249{
250    let mut out: Vec<(RingKind, &G::Ring)> = Vec::new();
251    out.push((RingKind::Exterior, g.exterior()));
252    for (i, r) in g.interiors().enumerate() {
253        out.push((RingKind::Interior(i), r));
254    }
255    out
256}
257
258#[cfg(test)]
259mod tests {
260    //! OVL2.T2 / T3 done-when: turn counts against hand-checked ring
261    //! and polygon pairs. Mirrors the count assertions in
262    //! `test/algorithms/overlay/get_turns.cpp`.
263
264    use super::{get_turns_polygon_polygon, get_turns_ring_ring};
265    use crate::turn::info::RingKind;
266    use geometry_cs::Cartesian;
267    use geometry_model::{Point2D, Ring, polygon};
268
269    type P = Point2D<f64, Cartesian>;
270
271    fn square(x: f64, y: f64, s: f64) -> Ring<P> {
272        Ring::from_vec(vec![
273            P::new(x, y),
274            P::new(x + s, y),
275            P::new(x + s, y + s),
276            P::new(x, y + s),
277            P::new(x, y),
278        ])
279    }
280
281    #[test]
282    fn overlapping_squares_two_turns() {
283        let a = square(0.0, 0.0, 2.0);
284        let b = square(1.0, 1.0, 2.0);
285        let turns = get_turns_ring_ring(&a, 0, RingKind::Exterior, &b, 1, RingKind::Exterior);
286        assert_eq!(turns.len(), 2);
287    }
288
289    #[test]
290    fn disjoint_squares_no_turns() {
291        let a = square(0.0, 0.0, 1.0);
292        let b = square(5.0, 5.0, 1.0);
293        let turns = get_turns_ring_ring(&a, 0, RingKind::Exterior, &b, 1, RingKind::Exterior);
294        assert!(turns.is_empty());
295    }
296
297    #[test]
298    fn polygon_pair_two_turns() {
299        use geometry_model::Polygon;
300        let a: Polygon<P> = polygon![[(0.0, 0.0), (2.0, 0.0), (2.0, 2.0), (0.0, 2.0), (0.0, 0.0)]];
301        let b: Polygon<P> = polygon![[(1.0, 1.0), (3.0, 1.0), (3.0, 3.0), (1.0, 3.0), (1.0, 1.0)]];
302        let turns = get_turns_polygon_polygon(&a, &b);
303        assert_eq!(turns.len(), 2);
304    }
305
306    #[test]
307    fn each_turn_names_both_sources() {
308        let a = square(0.0, 0.0, 2.0);
309        let b = square(1.0, 1.0, 2.0);
310        let turns = get_turns_ring_ring(&a, 0, RingKind::Exterior, &b, 1, RingKind::Exterior);
311        for t in &turns {
312            assert_eq!(t.operations[0].seg_id.source_index, 0);
313            assert_eq!(t.operations[1].seg_id.source_index, 1);
314        }
315    }
316}
geometry_overlay/turn/get_turns.rs

geometry_overlay/turn/
get_turns.rs
