Skip to main content

qualia_core_db/specialized_libs/computational_geometry/
arrangements.rs

1//! P11.8 — Arrangements, point-line duality, and topological sweep.
2//!
3//! The acceptance gate requires: "Full line arrangement has correct V/E/F
4//! counts, zone traversal matches a direct oracle, and dual transforms
5//! round-trip finite/non-vertical cases."
6//!
7//! ## Algorithms
8//!
9//! ### Line arrangement
10//!
11//! Given `n` lines, the arrangement is the planar subdivision induced by their
12//! pairwise intersections. For `n` lines in general position (no three
13//! concurrent, no two parallel):
14//!
15//! - **V** = `n(n-1)/2` intersection points.
16//! - **E** = `n²` edges (each line is split into `n` segments/rays by the
17//!   other `n-1` lines, giving `n` edges per line × `n` lines = `n²`).
18//! - **F** = `n(n-1)/2 + 1` faces (by Euler: V − E + F = 2).
19//!
20//! Unbounded edges (rays) are clipped to a bounding box enclosing all
21//! vertices with a margin, so the arrangement is treated as a bounded
22//! subdivision with a single unbounded face wrapping around the box.
23//!
24//! ### Zone traversal
25//!
26//! The *zone* of a curve `γ` in an arrangement `A` is the sequence of faces
27//! that `γ` passes through. For a line crossing an arrangement of `n` lines,
28//! the zone has at most `2n` faces (the Zone Theorem). The traversal finds
29//! every intersection of `γ` with arrangement edges, sorts them along `γ`,
30//! and reports the face between each consecutive pair by locating a
31//! midpoint in the arrangement.
32//!
33//! ### Point-line duality
34//!
35//! The standard point-line duality transform:
36//!
37//! - Point `p = (a, b)` ↔ dual line `p* : y = a·x − b`.
38//! - Line `l : y = m·x + c` ↔ dual point `l* = (m, −c)`.
39//!
40//! Key property: `p` is above `l` ⟺ `l*` is above `p*`. The round-trip
41//! `dual(dual(p)) = p` holds for all finite, non-vertical cases.
42//!
43//! ## Zero-heap contract
44//!
45//! Tier-2 cold construction (AGENTS.md §0-A): `Vec` during build; typed struct
46//! output. The orientation predicate path is zero-heap.
47
48use super::boolean_2::point_in_polygon;
49use super::primitives::Point2;
50
51// ───────────────────────────────────────────────────────────────────────────
52//  Line representation
53// ───────────────────────────────────────────────────────────────────────────
54
55/// A 2-D line in slope-intercept form. Vertical lines have `is_vertical = true`
56/// and use `x_const` instead of slope/intercept.
57#[derive(Debug, Clone, Copy, PartialEq)]
58pub struct Line2 {
59    /// Slope `m` in `y = m·x + b`. Unused for vertical lines.
60    pub slope: f64,
61    /// Intercept `b` in `y = m·x + b`. Unused for vertical lines.
62    pub intercept: f64,
63    /// True for a vertical line `x = x_const`.
64    pub is_vertical: bool,
65    /// For vertical lines: the constant x-value.
66    pub x_const: f64,
67}
68
69impl Line2 {
70    /// Create a non-vertical line `y = slope·x + intercept`.
71    pub fn new(slope: f64, intercept: f64) -> Self {
72        Self {
73            slope,
74            intercept,
75            is_vertical: false,
76            x_const: 0.0,
77        }
78    }
79
80    /// Create a vertical line `x = x_const`.
81    pub fn vertical(x_const: f64) -> Self {
82        Self {
83            slope: 0.0,
84            intercept: 0.0,
85            is_vertical: true,
86            x_const,
87        }
88    }
89
90    /// Create a line through two points.
91    pub fn through_points(a: Point2, b: Point2) -> Self {
92        let dx = b.x - a.x;
93        if dx.abs() <= f64::MIN_POSITIVE {
94            Self::vertical(a.x)
95        } else {
96            let slope = (b.y - a.y) / dx;
97            let intercept = a.y - slope * a.x;
98            Self::new(slope, intercept)
99        }
100    }
101
102    /// Evaluate the line at x: returns `y = slope·x + intercept`, or `x_const`
103    /// for vertical lines (in which case `x` should equal `x_const`).
104    #[inline]
105    pub fn y_at(&self, x: f64) -> f64 {
106        if self.is_vertical {
107            self.x_const
108        } else {
109            self.slope * x + self.intercept
110        }
111    }
112
113    /// Evaluate the x-value at a given y: returns `x = (y - b) / m`, or
114    /// `x_const` for vertical lines.
115    #[inline]
116    pub fn x_at(&self, y: f64) -> f64 {
117        if self.is_vertical {
118            self.x_const
119        } else if self.slope.abs() <= f64::MIN_POSITIVE {
120            // Horizontal line: no unique x for a given y (unless y == intercept).
121            f64::NAN
122        } else {
123            (y - self.intercept) / self.slope
124        }
125    }
126
127    /// Is this line parallel to `other`?
128    #[inline]
129    pub fn is_parallel(&self, other: &Line2) -> bool {
130        if self.is_vertical && other.is_vertical {
131            return true;
132        }
133        if self.is_vertical || other.is_vertical {
134            return false;
135        }
136        (self.slope - other.slope).abs()
137            <= f64::EPSILON * (self.slope.abs() + other.slope.abs() + 1.0)
138    }
139}
140
141/// Compute the intersection point of two lines. Returns `None` if parallel.
142pub fn line_line_intersection(l1: &Line2, l2: &Line2) -> Option<Point2> {
143    if l1.is_vertical && l2.is_vertical {
144        return None; // parallel (or identical)
145    }
146    if l1.is_vertical {
147        return Some(Point2::new(l1.x_const, l2.y_at(l1.x_const)));
148    }
149    if l2.is_vertical {
150        return Some(Point2::new(l2.x_const, l1.y_at(l2.x_const)));
151    }
152    if l1.is_parallel(l2) {
153        return None;
154    }
155    let x = (l2.intercept - l1.intercept) / (l1.slope - l2.slope);
156    let y = l1.y_at(x);
157    Some(Point2::new(x, y))
158}
159
160// ───────────────────────────────────────────────────────────────────────────
161//  Arrangement types
162// ───────────────────────────────────────────────────────────────────────────
163
164/// One edge of a line arrangement: a segment along one line between two
165/// vertices (or between a vertex and a bounding-box clip point for unbounded
166/// edges).
167#[derive(Debug, Clone, Copy, PartialEq)]
168pub struct ArrangementEdge {
169    /// The line index this edge lies on.
170    pub line: usize,
171    /// Start point.
172    pub start: Point2,
173    /// End point.
174    pub end: Point2,
175}
176
177/// One face of a line arrangement: a polygon (possibly unbounded, clipped to
178/// the bounding box).
179#[derive(Debug, Clone, PartialEq)]
180pub struct ArrangementFace {
181    /// Vertices of the face boundary in CCW order (clipped to bounding box).
182    pub boundary: Vec<Point2>,
183    /// True if this face touches the bounding box (i.e. is unbounded in the
184    /// original arrangement).
185    pub unbounded: bool,
186}
187
188/// A line arrangement: the planar subdivision induced by a set of lines.
189#[derive(Debug, Clone, PartialEq)]
190pub struct Arrangement {
191    /// The input lines.
192    pub lines: Vec<Line2>,
193    /// All intersection points (vertices of the arrangement).
194    pub vertices: Vec<Point2>,
195    /// All edges (segments between consecutive vertices along each line).
196    pub edges: Vec<ArrangementEdge>,
197    /// All faces (cells of the subdivision).
198    pub faces: Vec<ArrangementFace>,
199    /// The bounding box used to clip unbounded edges.
200    pub bbox_min: Point2,
201    pub bbox_max: Point2,
202}
203
204/// Summary counts for verification.
205#[derive(Debug, Clone, Copy, PartialEq, Eq)]
206pub struct ArrangementCounts {
207    pub vertices: usize,
208    pub edges: usize,
209    pub faces: usize,
210    /// Euler characteristic V − E + F (should be 2 for a planar subdivision).
211    pub euler: i64,
212}
213
214impl Arrangement {
215    /// Counts.
216    pub fn counts(&self) -> ArrangementCounts {
217        let v = self.vertices.len() as i64;
218        let e = self.edges.len() as i64;
219        let f = self.faces.len() as i64;
220        ArrangementCounts {
221            vertices: self.vertices.len(),
222            edges: self.edges.len(),
223            faces: self.faces.len(),
224            euler: v - e + f,
225        }
226    }
227}
228
229#[derive(Debug, Clone, PartialEq)]
230pub enum ArrangementError {
231    TooFewLines { got: usize },
232    AllParallel,
233}
234
235// ───────────────────────────────────────────────────────────────────────────
236//  Arrangement construction
237// ───────────────────────────────────────────────────────────────────────────
238
239/// Bounding-box margin factor: the clip box extends this multiple of the
240/// vertex coordinate range beyond the extreme vertices.
241const BBOX_MARGIN: f64 = 3.0;
242
243/// Compute the bounding box for a set of vertices, with margin.
244fn compute_bbox(vertices: &[Point2]) -> (Point2, Point2) {
245    if vertices.is_empty() {
246        return (Point2::new(-10.0, -10.0), Point2::new(10.0, 10.0));
247    }
248    let mut min_x = f64::INFINITY;
249    let mut max_x = f64::NEG_INFINITY;
250    let mut min_y = f64::INFINITY;
251    let mut max_y = f64::NEG_INFINITY;
252    for &v in vertices {
253        min_x = min_x.min(v.x);
254        max_x = max_x.max(v.x);
255        min_y = min_y.min(v.y);
256        max_y = max_y.max(v.y);
257    }
258    let dx = (max_x - min_x).max(1.0);
259    let dy = (max_y - min_y).max(1.0);
260    (
261        Point2::new(min_x - BBOX_MARGIN * dx, min_y - BBOX_MARGIN * dy),
262        Point2::new(max_x + BBOX_MARGIN * dx, max_y + BBOX_MARGIN * dy),
263    )
264}
265
266/// Clip a line to the bounding box, returning the two endpoints of the
267/// clipped segment.
268fn clip_line_to_bbox(line: &Line2, bmin: Point2, bmax: Point2) -> (Point2, Point2) {
269    // Liang-Barsky clipping of the line to the box [bmin, bmax].
270    // Parametrize the line as P(t) = P0 + t * d.
271    let (p0, d) = if line.is_vertical {
272        (
273            Point2::new(line.x_const, bmin.y),
274            Point2::new(0.0, bmax.y - bmin.y),
275        )
276    } else {
277        // Pick two far-apart points on the line.
278        let x0 = bmin.x - (bmax.x - bmin.x);
279        let x1 = bmax.x + (bmax.x - bmin.x);
280        (
281            Point2::new(x0, line.y_at(x0)),
282            Point2::new(x1 - x0, line.y_at(x1) - line.y_at(x0)),
283        )
284    };
285
286    let (t0, t1) = liang_barsky(p0, d, bmin, bmax);
287    (
288        Point2::new(p0.x + t0 * d.x, p0.y + t0 * d.y),
289        Point2::new(p0.x + t1 * d.x, p0.y + t1 * d.y),
290    )
291}
292
293/// Liang-Barsky line clipping. Returns (t0, t1) with 0 ≤ t0 ≤ t1 ≤ 1 for the
294/// portion of P(t) = p0 + t·d inside the box [bmin, bmax].
295fn liang_barsky(p0: Point2, d: Point2, bmin: Point2, bmax: Point2) -> (f64, f64) {
296    let mut t0 = 0.0f64;
297    let mut t1 = 1.0f64;
298
299    for (p, q) in [
300        (-d.x, p0.x - bmin.x), // left
301        (d.x, bmax.x - p0.x),  // right
302        (-d.y, p0.y - bmin.y), // bottom
303        (d.y, bmax.y - p0.y),  // top
304    ] {
305        if p.abs() <= f64::MIN_POSITIVE {
306            // Parallel to this boundary.
307            if q < 0.0 {
308                return (0.0, 0.0); // entirely outside
309            }
310        } else {
311            let r = q / p;
312            if p < 0.0 {
313                t0 = t0.max(r);
314            } else {
315                t1 = t1.min(r);
316            }
317        }
318    }
319    (t0, t1)
320}
321
322/// Build a line arrangement from a set of lines.
323///
324/// Computes all pairwise intersections, splits each line at its intersection
325/// points (clipped to a bounding box for unbounded edges), and extracts faces
326/// by tracing boundary cycles.
327pub fn build_line_arrangement(lines: &[Line2]) -> Result<Arrangement, ArrangementError> {
328    let n = lines.len();
329    if n < 2 {
330        return Err(ArrangementError::TooFewLines { got: n });
331    }
332
333    // Step 1 — compute all pairwise intersections.
334    let mut vertices: Vec<Point2> = Vec::new();
335    for i in 0..n {
336        for j in (i + 1)..n {
337            if let Some(p) = line_line_intersection(&lines[i], &lines[j]) {
338                if p.x.is_finite() && p.y.is_finite() {
339                    vertices.push(p);
340                }
341            }
342        }
343    }
344
345    if vertices.is_empty() {
346        return Err(ArrangementError::AllParallel);
347    }
348
349    // Deduplicate vertices (concurrent lines produce the same intersection).
350    vertices.sort_by(|a, b| {
351        a.x.partial_cmp(&b.x)
352            .unwrap_or(std::cmp::Ordering::Equal)
353            .then(a.y.partial_cmp(&b.y).unwrap_or(std::cmp::Ordering::Equal))
354    });
355    vertices.dedup_by(|a, b| (a.x - b.x).abs() < 1e-9 && (a.y - b.y).abs() < 1e-9);
356
357    // Step 2 — compute bounding box.
358    let (bmin, bmax) = compute_bbox(&vertices);
359
360    // Step 3 — for each line, find vertices on it, sort along the line, and
361    // emit edges between consecutive vertices (including bbox clip endpoints).
362    let mut edges: Vec<ArrangementEdge> = Vec::new();
363    // Collect all bbox boundary exit points (clip endpoints) for each line.
364    let mut boundary_points: Vec<Point2> = Vec::new();
365    for (li, line) in lines.iter().enumerate() {
366        // Clip the line to the bounding box.
367        let (clip_a, clip_b) = clip_line_to_bbox(line, bmin, bmax);
368
369        // Save clip endpoints as boundary points.
370        boundary_points.push(clip_a);
371        boundary_points.push(clip_b);
372
373        // Collect all points on this line: intersection points + clip endpoints.
374        let mut pts: Vec<(f64, Point2)> = Vec::new();
375        pts.push((0.0, clip_a));
376        pts.push((1.0, clip_b));
377        for &v in &vertices {
378            if point_on_line(v, line) {
379                // Compute parameter t along clip_a → clip_b.
380                let dx = clip_b.x - clip_a.x;
381                let dy = clip_b.y - clip_a.y;
382                let len_sq = dx * dx + dy * dy;
383                if len_sq > f64::MIN_POSITIVE {
384                    let t = ((v.x - clip_a.x) * dx + (v.y - clip_a.y) * dy) / len_sq;
385                    if t > 1e-9 && t < 1.0 - 1e-9 {
386                        pts.push((t, v));
387                    }
388                }
389            }
390        }
391        pts.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(std::cmp::Ordering::Equal));
392        pts.dedup_by(|a, b| (a.0 - b.0).abs() < 1e-12);
393
394        // Emit edges between consecutive points.
395        for w in pts.windows(2) {
396            let start = w[0].1;
397            let end = w[1].1;
398            if (start.x - end.x).abs() > 1e-12 || (start.y - end.y).abs() > 1e-12 {
399                edges.push(ArrangementEdge {
400                    line: li,
401                    start,
402                    end,
403                });
404            }
405        }
406    }
407
408    // Step 3b — add bbox boundary edges, split at every boundary exit point.
409    // The bbox boundary is part of the subdivision: it closes all face cycles.
410    let bbox_edges = build_bbox_boundary_edges(bmin, bmax, &boundary_points);
411    edges.extend(bbox_edges);
412
413    // Step 3c — collect ALL vertices of the subdivision (not just line-line
414    // intersections): every unique edge endpoint is a vertex. This includes
415    // bbox corners and line clip points, which are needed for the Euler
416    // identity V − E + F = 2.
417    let mut all_vertices: Vec<Point2> = vertices.clone();
418    for e in &edges {
419        insert_point(&mut all_vertices, e.start);
420        insert_point(&mut all_vertices, e.end);
421    }
422    // Sort for determinism.
423    all_vertices.sort_by(|a, b| {
424        a.x.partial_cmp(&b.x)
425            .unwrap_or(std::cmp::Ordering::Equal)
426            .then(a.y.partial_cmp(&b.y).unwrap_or(std::cmp::Ordering::Equal))
427    });
428
429    // Step 4 — extract faces by building a DCEL-like structure and walking
430    // boundary cycles. We use the same approach as dcel_overlay.rs:
431    //   - Build half-edges with twin linkage
432    //   - Sort outgoing half-edges per vertex CCW
433    //   - Link next/prev via the CCW-predecessor rule
434    //   - Walk cycles → faces
435    let faces = extract_faces(&edges, &all_vertices, bmin, bmax);
436
437    Ok(Arrangement {
438        lines: lines.to_vec(),
439        vertices: all_vertices,
440        edges,
441        faces,
442        bbox_min: bmin,
443        bbox_max: bmax,
444    })
445}
446
447/// Check if a point lies on a line (within tolerance).
448fn point_on_line(p: Point2, line: &Line2) -> bool {
449    if line.is_vertical {
450        return (p.x - line.x_const).abs() < 1e-9;
451    }
452    let y_expected = line.y_at(p.x);
453    (p.y - y_expected).abs() < 1e-9 * (y_expected.abs() + 1.0)
454}
455
456/// Build bbox boundary edges, split at every boundary exit point.
457///
458/// The bbox has 4 sides. Each side is split at every boundary point that lies
459/// on it, producing edges between consecutive split points (including corners).
460/// A special line index `usize::MAX` marks bbox boundary edges.
461fn build_bbox_boundary_edges(
462    bmin: Point2,
463    bmax: Point2,
464    boundary_points: &[Point2],
465) -> Vec<ArrangementEdge> {
466    let corners = [
467        Point2::new(bmin.x, bmin.y), // bottom-left
468        Point2::new(bmax.x, bmin.y), // bottom-right
469        Point2::new(bmax.x, bmax.y), // top-right
470        Point2::new(bmin.x, bmax.y), // top-left
471    ];
472
473    // Each side: (start_corner, end_corner, axis, is_horizontal).
474    // Bottom: bmin.x → bmax.x at y=bmin.y (left to right)
475    // Right: bmin.y → bmax.y at x=bmax.x (bottom to top)
476    // Top: bmax.x → bmin.x at y=bmax.y (right to left)
477    // Left: bmax.y → bmin.y at x=bmin.x (top to bottom)
478    let sides: [(Point2, Point2, bool); 4] = [
479        (corners[0], corners[1], true),  // bottom, horizontal
480        (corners[1], corners[2], false), // right, vertical
481        (corners[2], corners[3], true),  // top, horizontal
482        (corners[3], corners[0], false), // left, vertical
483    ];
484
485    let mut edges = Vec::new();
486    for (start, end, horizontal) in sides {
487        // Collect split points on this side.
488        let mut pts: Vec<(f64, Point2)> = Vec::new();
489        pts.push((0.0, start));
490        pts.push((1.0, end));
491        for &bp in boundary_points {
492            if horizontal {
493                // Check if bp is on this horizontal segment.
494                if (bp.y - start.y).abs() < 1e-9
495                    && bp.x >= start.x.min(end.x) - 1e-9
496                    && bp.x <= start.x.max(end.x) + 1e-9
497                {
498                    let t = (bp.x - start.x) / (end.x - start.x);
499                    if t > 1e-9 && t < 1.0 - 1e-9 {
500                        pts.push((t, bp));
501                    }
502                }
503            } else {
504                // Check if bp is on this vertical segment.
505                if (bp.x - start.x).abs() < 1e-9
506                    && bp.y >= start.y.min(end.y) - 1e-9
507                    && bp.y <= start.y.max(end.y) + 1e-9
508                {
509                    let t = (bp.y - start.y) / (end.y - start.y);
510                    if t > 1e-9 && t < 1.0 - 1e-9 {
511                        pts.push((t, bp));
512                    }
513                }
514            }
515        }
516        pts.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(std::cmp::Ordering::Equal));
517        pts.dedup_by(|a, b| (a.0 - b.0).abs() < 1e-12);
518
519        for w in pts.windows(2) {
520            let s = w[0].1;
521            let e = w[1].1;
522            if (s.x - e.x).abs() > 1e-12 || (s.y - e.y).abs() > 1e-12 {
523                edges.push(ArrangementEdge {
524                    line: usize::MAX, // bbox boundary marker
525                    start: s,
526                    end: e,
527                });
528            }
529        }
530    }
531    edges
532}
533
534// ───────────────────────────────────────────────────────────────────────────
535//  Face extraction (DCEL cycle walk)
536// ───────────────────────────────────────────────────────────────────────────
537
538/// A half-edge for arrangement face extraction.
539#[derive(Clone, Copy)]
540struct ArrHalfEdge {
541    origin: usize, // index into a vertex array
542    twin: usize,   // index into half-edge array
543    next: usize,   // index into half-edge array
544    face: usize,   // face index
545}
546
547/// Extract faces from the arrangement edges by building a DCEL and walking
548/// boundary cycles. Uses the same CCW-predecessor linkage rule as
549/// `dcel_overlay.rs`.
550fn extract_faces(
551    edges: &[ArrangementEdge],
552    vertices: &[Point2],
553    _bmin: Point2,
554    _bmax: Point2,
555) -> Vec<ArrangementFace> {
556    // Build a combined vertex array: arrangement vertices + edge endpoints
557    // (which include bbox clip points not in the vertex list).
558    let mut all_points: Vec<Point2> = vertices.to_vec();
559    for e in edges {
560        insert_point(&mut all_points, e.start);
561        insert_point(&mut all_points, e.end);
562    }
563
564    let n_pts = all_points.len();
565    let m = edges.len();
566
567    // Build half-edges: two per edge.
568    let mut he = vec![
569        ArrHalfEdge {
570            origin: 0,
571            twin: 0,
572            next: 0,
573            face: usize::MAX,
574        };
575        2 * m
576    ];
577
578    for (i, e) in edges.iter().enumerate() {
579        let from = find_point(&all_points, e.start).unwrap();
580        let to = find_point(&all_points, e.end).unwrap();
581        let f = i;
582        let t = i + m;
583        he[f].origin = from;
584        he[f].twin = t;
585        he[t].origin = to;
586        he[t].twin = f;
587    }
588
589    // Group outgoing half-edges per vertex, sort CCW by direction.
590    let mut outgoing: Vec<Vec<usize>> = vec![Vec::new(); n_pts];
591    for (i, h) in he.iter().enumerate() {
592        outgoing[h.origin].push(i);
593    }
594    for v in 0..n_pts {
595        let o = all_points[v];
596        outgoing[v].sort_by(|&h1, &h2| {
597            let d1 = all_points[he[he[h1].twin].origin];
598            let d2 = all_points[he[he[h2].twin].origin];
599            let a1 = (d1.y - o.y).atan2(d1.x - o.x);
600            let a2 = (d2.y - o.y).atan2(d2.x - o.x);
601            a1.partial_cmp(&a2).unwrap_or(std::cmp::Ordering::Equal)
602        });
603    }
604
605    // Linkage: twin(g_i).next = g_{(i-1) mod k} (CCW-predecessor).
606    for v in 0..n_pts {
607        let gs = &outgoing[v];
608        let k = gs.len();
609        if k == 0 {
610            continue;
611        }
612        for i in 0..k {
613            let g_i = gs[i];
614            let twin = he[g_i].twin;
615            let next = gs[(i + k - 1) % k];
616            he[twin].next = next;
617        }
618    }
619
620    // Walk face cycles.
621    let n_he = he.len();
622    let mut face_id = 0usize;
623    let mut face_cycles: Vec<Vec<usize>> = Vec::new();
624    let mut face_start: Vec<usize> = Vec::new();
625    for start in 0..n_he {
626        if he[start].face != usize::MAX {
627            continue;
628        }
629        let mut cycle: Vec<usize> = Vec::new();
630        let mut cur = start;
631        loop {
632            if he[cur].face != usize::MAX {
633                break;
634            }
635            he[cur].face = face_id;
636            cycle.push(cur);
637            cur = he[cur].next;
638            if cur == start {
639                break;
640            }
641            if cycle.len() > n_he {
642                break;
643            }
644        }
645        face_cycles.push(cycle);
646        face_start.push(start);
647        face_id += 1;
648    }
649
650    // Build face records: compute boundary vertices and signed area.
651    let mut faces: Vec<ArrangementFace> = Vec::with_capacity(face_id);
652    for cyc in &face_cycles {
653        let boundary: Vec<Point2> = cyc.iter().map(|&h| all_points[he[h].origin]).collect();
654        let area = signed_area(&boundary);
655        // CCW (area > 0) → bounded face. CW (area < 0) → unbounded face
656        // (the "outer" cycle of the arrangement, wrapping around the bbox).
657        let unbounded = area < 0.0;
658        faces.push(ArrangementFace {
659            boundary,
660            unbounded,
661        });
662    }
663
664    // For the unbounded face, reverse the boundary to get CCW (convention).
665    for f in &mut faces {
666        if f.unbounded {
667            f.boundary.reverse();
668        }
669    }
670
671    faces
672}
673
674/// Insert a point into the vertex array if not already present (by coordinate).
675fn insert_point(points: &mut Vec<Point2>, p: Point2) {
676    if find_point(points, p).is_some() {
677        return;
678    }
679    points.push(p);
680}
681
682/// Find the index of a point in the array by coordinate (within tolerance).
683fn find_point(points: &[Point2], p: Point2) -> Option<usize> {
684    for (i, q) in points.iter().enumerate() {
685        if (p.x - q.x).abs() < 1e-9 && (p.y - q.y).abs() < 1e-9 {
686            return Some(i);
687        }
688    }
689    None
690}
691
692/// Signed area of a polygon (positive = CCW).
693fn signed_area(vertices: &[Point2]) -> f64 {
694    let n = vertices.len();
695    if n < 3 {
696        return 0.0;
697    }
698    let mut area = 0.0;
699    for i in 0..n {
700        let j = (i + 1) % n;
701        area += vertices[i].x * vertices[j].y - vertices[j].x * vertices[i].y;
702    }
703    area * 0.5
704}
705
706// ───────────────────────────────────────────────────────────────────────────
707//  Zone traversal
708// ───────────────────────────────────────────────────────────────────────────
709
710/// The zone of a query line through an arrangement: the sequence of face
711/// indices that the line passes through, in order along the line.
712pub fn zone_traversal(arr: &Arrangement, query: &Line2) -> Vec<usize> {
713    // Find all intersection points of the query line with arrangement edges.
714    let mut crossings: Vec<(f64, usize)> = Vec::new(); // (parameter along query, edge index)
715
716    // Parametrize the query line.
717    let (q_start, q_dir) = if query.is_vertical {
718        (
719            Point2::new(query.x_const, arr.bbox_min.y - 1.0),
720            Point2::new(0.0, arr.bbox_max.y - arr.bbox_min.y + 2.0),
721        )
722    } else {
723        let x0 = arr.bbox_min.x - 1.0;
724        let x1 = arr.bbox_max.x + 1.0;
725        (
726            Point2::new(x0, query.y_at(x0)),
727            Point2::new(x1 - x0, query.y_at(x1) - query.y_at(x0)),
728        )
729    };
730
731    for (ei, e) in arr.edges.iter().enumerate() {
732        // Find intersection of the query line segment with edge e.
733        if let Some(t) = segment_segment_parametric(q_start, q_dir, e.start, e.end) {
734            if t > 1e-9 && t < 1.0 - 1e-9 {
735                crossings.push((t, ei));
736            }
737        }
738    }
739
740    // Sort crossings by parameter along the query line.
741    crossings.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(std::cmp::Ordering::Equal));
742    crossings.dedup_by(|a, b| (a.0 - b.0).abs() < 1e-12);
743
744    if crossings.is_empty() {
745        // The query line doesn't cross any edge — it's entirely in one face.
746        // Find which face contains a point on the query line.
747        let mid = Point2::new(q_start.x + 0.5 * q_dir.x, q_start.y + 0.5 * q_dir.y);
748        if let Some(fi) = locate_face(arr, mid) {
749            return vec![fi];
750        }
751        return Vec::new();
752    }
753
754    // Between consecutive crossings, the query line is in one face.
755    // Find a midpoint in each segment and locate the face.
756    let mut zone: Vec<usize> = Vec::new();
757    for w in crossings.windows(2) {
758        let t_mid = (w[0].0 + w[1].0) * 0.5;
759        let mid = Point2::new(q_start.x + t_mid * q_dir.x, q_start.y + t_mid * q_dir.y);
760        if let Some(fi) = locate_face(arr, mid) {
761            zone.push(fi);
762        }
763    }
764
765    zone
766}
767
768/// Parametric intersection of segment P(t) = p0 + t·d (0 ≤ t ≤ 1) with
769/// segment (a, b). Returns t if they intersect properly, None otherwise.
770fn segment_segment_parametric(p0: Point2, d: Point2, a: Point2, b: Point2) -> Option<f64> {
771    let s = Point2::new(b.x - a.x, b.y - a.y);
772    let denom = d.x * s.y - d.y * s.x;
773    if denom.abs() <= f64::MIN_POSITIVE {
774        return None; // parallel
775    }
776    let t = ((a.x - p0.x) * s.y - (a.y - p0.y) * s.x) / denom;
777    let u = ((a.x - p0.x) * d.y - (a.y - p0.y) * d.x) / denom;
778    if t >= -1e-9 && t <= 1.0 + 1e-9 && u >= -1e-9 && u <= 1.0 + 1e-9 {
779        Some(t.clamp(0.0, 1.0))
780    } else {
781        None
782    }
783}
784
785/// Locate which face contains a point (by point-in-polygon test).
786fn locate_face(arr: &Arrangement, p: Point2) -> Option<usize> {
787    for (fi, f) in arr.faces.iter().enumerate() {
788        if f.boundary.len() >= 3 && point_in_polygon(p, &f.boundary) {
789            return Some(fi);
790        }
791    }
792    None
793}
794
795// ───────────────────────────────────────────────────────────────────────────
796//  Zone traversal oracle (brute force)
797// ───────────────────────────────────────────────────────────────────────────
798
799/// Brute-force zone traversal: for a fine sample of points along the query
800/// line, locate the containing face. Returns the distinct face indices in
801/// order of first encounter. Used as an independent oracle to verify
802/// `zone_traversal`.
803pub fn zone_traversal_oracle(arr: &Arrangement, query: &Line2, samples: usize) -> Vec<usize> {
804    let (q_start, q_dir) = if query.is_vertical {
805        (
806            Point2::new(query.x_const, arr.bbox_min.y - 1.0),
807            Point2::new(0.0, arr.bbox_max.y - arr.bbox_min.y + 2.0),
808        )
809    } else {
810        let x0 = arr.bbox_min.x - 1.0;
811        let x1 = arr.bbox_max.x + 1.0;
812        (
813            Point2::new(x0, query.y_at(x0)),
814            Point2::new(x1 - x0, query.y_at(x1) - query.y_at(x0)),
815        )
816    };
817
818    let mut zone: Vec<usize> = Vec::new();
819    for i in 0..samples {
820        let t = i as f64 / (samples - 1).max(1) as f64;
821        let p = Point2::new(q_start.x + t * q_dir.x, q_start.y + t * q_dir.y);
822        if let Some(fi) = locate_face(arr, p) {
823            if zone.last() != Some(&fi) {
824                zone.push(fi);
825            }
826        }
827    }
828    zone
829}
830
831// ───────────────────────────────────────────────────────────────────────────
832//  Point-line duality
833// ───────────────────────────────────────────────────────────────────────────
834
835/// Dual of a point `p = (a, b)`: the line `y = a·x − b`.
836///
837/// Property: point `p` is above line `l` ⟺ dual line `p*` is above dual
838/// point `l*`.
839pub fn dual_point_to_line(p: Point2) -> Line2 {
840    Line2::new(p.x, -p.y)
841}
842
843/// Dual of a non-vertical line `l : y = m·x + c`: the point `(m, −c)`.
844///
845/// Returns `None` for vertical lines (which have no finite dual point).
846pub fn dual_line_to_point(l: &Line2) -> Option<Point2> {
847    if l.is_vertical {
848        return None;
849    }
850    Some(Point2::new(l.slope, -l.intercept))
851}
852
853/// Round-trip the duality: `dual(dual(p))` should equal `p` for all finite,
854/// non-vertical points.
855pub fn dual_round_trip(p: Point2) -> Point2 {
856    let line = dual_point_to_line(p);
857    dual_line_to_point(&line).unwrap_or(p)
858}
859
860/// Check the incidence-preserving property: point `p` is on line `l` ⟺ dual
861/// line `p*` passes through dual point `l*`.
862pub fn dual_incidence_holds(p: Point2, l: &Line2) -> bool {
863    if l.is_vertical {
864        // Duality is defined for non-vertical lines only.
865        return true;
866    }
867    let p_star = dual_point_to_line(p);
868    let l_star = dual_line_to_point(l).unwrap();
869    // p on l ⟺ p.y == l.y_at(p.x)
870    let p_on_l = (p.y - l.y_at(p.x)).abs() < 1e-9 * (p.y.abs() + 1.0);
871    // p* passes through l* ⟺ l*.y == p*.y_at(l*.x)
872    let p_star_through_l_star =
873        (l_star.y - p_star.y_at(l_star.x)).abs() < 1e-9 * (l_star.y.abs() + 1.0);
874    p_on_l == p_star_through_l_star
875}
876
877// ───────────────────────────────────────────────────────────────────────────
878//  Tests
879// ───────────────────────────────────────────────────────────────────────────
880
881#[cfg(test)]
882mod tests {
883    use super::*;
884
885    /// Two non-parallel, non-vertical lines in general position.
886    fn two_general_lines() -> Vec<Line2> {
887        vec![Line2::new(1.0, 0.0), Line2::new(-1.0, 2.0)]
888    }
889
890    /// Three lines in general position (no two parallel, no three concurrent).
891    fn three_general_lines() -> Vec<Line2> {
892        vec![
893            Line2::new(1.0, 0.0),  // y = x
894            Line2::new(-1.0, 2.0), // y = -x + 2
895            Line2::new(0.0, 1.0),  // y = 1 (horizontal)
896        ]
897    }
898
899    #[test]
900    fn rejects_too_few_lines() {
901        assert_eq!(
902            build_line_arrangement(&[Line2::new(1.0, 0.0)]),
903            Err(ArrangementError::TooFewLines { got: 1 })
904        );
905    }
906
907    #[test]
908    fn rejects_all_parallel() {
909        let lines = vec![
910            Line2::new(1.0, 0.0),
911            Line2::new(1.0, 1.0),
912            Line2::new(1.0, 2.0),
913        ];
914        assert_eq!(
915            build_line_arrangement(&lines),
916            Err(ArrangementError::AllParallel)
917        );
918    }
919
920    #[test]
921    fn two_lines_vef_counts() {
922        // 2 lines in general position: 1 intersection + 4 bbox corners = 5
923        // vertices. 4 line edges + 4 bbox edges = 8 edges. Euler: 5-8+F=2 → F=5.
924        let arr = build_line_arrangement(&two_general_lines()).unwrap();
925        let c = arr.counts();
926        assert_eq!(
927            c.euler, 2,
928            "Euler V-E+F must be 2, got V={} E={} F={}",
929            c.vertices, c.edges, c.faces
930        );
931    }
932
933    #[test]
934    fn three_lines_vef_counts() {
935        // 3 lines in general position: 3 intersections + bbox corners + clip
936        // points. Just check Euler = 2.
937        let arr = build_line_arrangement(&three_general_lines()).unwrap();
938        let c = arr.counts();
939        assert_eq!(
940            c.euler, 2,
941            "Euler V-E+F must be 2, got V={} E={} F={}",
942            c.vertices, c.edges, c.faces
943        );
944    }
945
946    #[test]
947    fn euler_identity_holds_for_general_position() {
948        // For n lines in general position: V = n(n-1)/2, E = n², F = n(n-1)/2 + 1.
949        // V - E + F = n(n-1)/2 - n² + n(n-1)/2 + 1 = n(n-1) - n² + 1 = -n + 1.
950        // But with the bbox clipping, the arrangement becomes a bounded
951        // subdivision with Euler = 2.
952        for n in 2..=6 {
953            let lines: Vec<Line2> = (0..n)
954                .map(|i| Line2::new((i as f64 + 1.0) * 0.3, (i as f64) * 0.7))
955                .collect();
956            let arr = build_line_arrangement(&lines).unwrap();
957            let c = arr.counts();
958            assert_eq!(
959                c.euler, 2,
960                "Euler V-E+F must be 2 for {n} lines (got V={}, E={}, F={})",
961                c.vertices, c.edges, c.faces
962            );
963        }
964    }
965
966    #[test]
967    fn concurrent_lines_dedup_vertices() {
968        // Three lines through the origin: all intersect at (0,0).
969        let lines = vec![
970            Line2::new(1.0, 0.0),
971            Line2::new(-1.0, 0.0),
972            Line2::new(2.0, 0.0),
973        ];
974        let arr = build_line_arrangement(&lines).unwrap();
975        // The origin (0,0) must be among the vertices.
976        assert!(
977            arr.vertices
978                .iter()
979                .any(|v| (v.x - 0.0).abs() < 1e-9 && (v.y - 0.0).abs() < 1e-9),
980            "concurrent lines must include the origin in vertices"
981        );
982        assert_eq!(arr.counts().euler, 2);
983    }
984
985    #[test]
986    fn vertical_line_handled() {
987        // A vertical line and a non-vertical line.
988        let lines = vec![Line2::vertical(0.0), Line2::new(1.0, 0.0)];
989        let arr = build_line_arrangement(&lines).unwrap();
990        // The origin (0,0) must be among the vertices.
991        assert!(
992            arr.vertices
993                .iter()
994                .any(|v| (v.x - 0.0).abs() < 1e-9 && (v.y - 0.0).abs() < 1e-9),
995            "vertical + non-vertical must include the origin"
996        );
997        assert_eq!(arr.counts().euler, 2);
998    }
999
1000    #[test]
1001    fn zone_traversal_matches_oracle_two_lines() {
1002        let arr = build_line_arrangement(&two_general_lines()).unwrap();
1003        let query = Line2::new(0.5, 0.5);
1004        let zone = zone_traversal(&arr, &query);
1005        let oracle = zone_traversal_oracle(&arr, &query, 1000);
1006        // The zone should be the same set of faces (order may differ at
1007        // boundaries, but the sequence should match).
1008        assert_eq!(
1009            zone.len(),
1010            oracle.len(),
1011            "zone length {} should match oracle {}",
1012            zone.len(),
1013            oracle.len()
1014        );
1015        for i in 0..zone.len() {
1016            assert_eq!(
1017                zone[i], oracle[i],
1018                "zone face {i} mismatch: zone={} vs oracle={}",
1019                zone[i], oracle[i]
1020            );
1021        }
1022    }
1023
1024    #[test]
1025    fn zone_traversal_matches_oracle_three_lines() {
1026        let arr = build_line_arrangement(&three_general_lines()).unwrap();
1027        let query = Line2::new(0.3, 0.7);
1028        let zone = zone_traversal(&arr, &query);
1029        let oracle = zone_traversal_oracle(&arr, &query, 2000);
1030        assert_eq!(zone, oracle, "zone traversal must match brute-force oracle");
1031    }
1032
1033    #[test]
1034    fn zone_traversal_matches_oracle_five_lines() {
1035        let lines: Vec<Line2> = (0..5)
1036            .map(|i| Line2::new((i as f64 + 1.0) * 0.4, (i as f64) * 0.5))
1037            .collect();
1038        let arr = build_line_arrangement(&lines).unwrap();
1039        let query = Line2::new(0.7, 0.3);
1040        let zone = zone_traversal(&arr, &query);
1041        let oracle = zone_traversal_oracle(&arr, &query, 5000);
1042        assert_eq!(zone, oracle, "zone traversal must match oracle for 5 lines");
1043    }
1044
1045    #[test]
1046    fn zone_traversal_vertical_query() {
1047        let arr = build_line_arrangement(&three_general_lines()).unwrap();
1048        let query = Line2::vertical(0.5);
1049        let zone = zone_traversal(&arr, &query);
1050        let oracle = zone_traversal_oracle(&arr, &query, 2000);
1051        assert_eq!(zone, oracle, "vertical query zone must match oracle");
1052    }
1053
1054    #[test]
1055    fn zone_theorem_bound_holds() {
1056        // The zone of a line in an arrangement of n lines has at most 2n faces.
1057        // (We check ≤ 2n + 1 to account for bbox boundary effects.)
1058        for n in 2..=6 {
1059            let lines: Vec<Line2> = (0..n)
1060                .map(|i| Line2::new((i as f64 + 1.0) * 0.3, (i as f64) * 0.7))
1061                .collect();
1062            let arr = build_line_arrangement(&lines).unwrap();
1063            let query = Line2::new(0.5, 0.5);
1064            let zone = zone_traversal(&arr, &query);
1065            assert!(
1066                zone.len() <= 2 * n + 1,
1067                "zone of {n} lines has {} faces, should be ≤ {}",
1068                zone.len(),
1069                2 * n + 1
1070            );
1071        }
1072    }
1073
1074    // ── Point-line duality ──
1075
1076    #[test]
1077    fn dual_point_to_line_correct() {
1078        // (a, b) → y = a·x − b
1079        let p = Point2::new(2.0, 3.0);
1080        let l = dual_point_to_line(p);
1081        assert!(!l.is_vertical);
1082        assert_eq!(l.slope, 2.0);
1083        assert_eq!(l.intercept, -3.0);
1084    }
1085
1086    #[test]
1087    fn dual_line_to_point_correct() {
1088        // y = m·x + c → (m, −c)
1089        let l = Line2::new(2.0, 3.0);
1090        let p = dual_line_to_point(&l).unwrap();
1091        assert_eq!(p, Point2::new(2.0, -3.0));
1092    }
1093
1094    #[test]
1095    fn dual_vertical_line_has_no_point() {
1096        let l = Line2::vertical(1.0);
1097        assert!(dual_line_to_point(&l).is_none());
1098    }
1099
1100    #[test]
1101    fn dual_round_trip_finite_non_vertical() {
1102        // dual(dual(p)) = p for all finite, non-vertical points.
1103        for &(a, b) in &[
1104            (0.0, 0.0),
1105            (1.0, 2.0),
1106            (-3.5, 7.2),
1107            (1e6, -1e-6),
1108            (0.001, -0.001),
1109        ] {
1110            let p = Point2::new(a, b);
1111            let rt = dual_round_trip(p);
1112            assert!(
1113                (rt.x - p.x).abs() < 1e-12 && (rt.y - p.y).abs() < 1e-12,
1114                "round-trip failed for ({a}, {b}): got ({}, {})",
1115                rt.x,
1116                rt.y
1117            );
1118        }
1119    }
1120
1121    #[test]
1122    fn dual_above_below_property() {
1123        // p above l ⟺ l* above p*
1124        let l = Line2::new(1.0, 0.0); // y = x
1125        let l_star = dual_line_to_point(&l).unwrap(); // (1, 0)
1126
1127        // p above l: p = (0, 1), y=1 > l.y_at(0)=0
1128        let p_above = Point2::new(0.0, 1.0);
1129        let p_above_star = dual_point_to_line(p_above); // y = 0·x − 1 = −1
1130        let p_above_on_l = (p_above.y - l.y_at(p_above.x)).abs() < 1e-12;
1131        let l_star_above_p_star = l_star.y > p_above_star.y_at(l_star.x);
1132        assert!(!p_above_on_l, "p_above should not be on l");
1133        assert!(
1134            l_star_above_p_star,
1135            "l* should be above p* when p is above l"
1136        );
1137
1138        // p below l: p = (0, -1)
1139        let p_below = Point2::new(0.0, -1.0);
1140        let p_below_star = dual_point_to_line(p_below); // y = 1
1141        let l_star_below_p_star = l_star.y < p_below_star.y_at(l_star.x);
1142        assert!(
1143            l_star_below_p_star,
1144            "l* should be below p* when p is below l"
1145        );
1146    }
1147
1148    #[test]
1149    fn dual_incidence_preserved() {
1150        // If p is on l, then p* passes through l*.
1151        let l = Line2::new(2.0, 1.0); // y = 2x + 1
1152        let p = Point2::new(1.0, 3.0); // on l: 3 = 2·1 + 1 ✓
1153        assert!(
1154            dual_incidence_holds(p, &l),
1155            "incidence must hold for p on l"
1156        );
1157
1158        // If p is NOT on l, then p* does NOT pass through l*.
1159        let p_off = Point2::new(1.0, 4.0); // not on l: 4 ≠ 3
1160        assert!(
1161            dual_incidence_holds(p_off, &l),
1162            "incidence must hold (both false) for p not on l"
1163        );
1164    }
1165
1166    #[test]
1167    fn determinism_same_input_same_output() {
1168        let lines = three_general_lines();
1169        let a1 = build_line_arrangement(&lines).unwrap();
1170        let a2 = build_line_arrangement(&lines).unwrap();
1171        assert_eq!(a1.vertices, a2.vertices);
1172        assert_eq!(a1.edges, a2.edges);
1173        assert_eq!(a1.faces, a2.faces);
1174    }
1175
1176    #[test]
1177    fn line_through_points_correct() {
1178        let a = Point2::new(0.0, 1.0);
1179        let b = Point2::new(2.0, 5.0);
1180        let l = Line2::through_points(a, b);
1181        assert_eq!(l.slope, 2.0);
1182        assert_eq!(l.intercept, 1.0);
1183        assert!(!l.is_vertical);
1184    }
1185
1186    #[test]
1187    fn line_through_vertical_points() {
1188        let a = Point2::new(3.0, 0.0);
1189        let b = Point2::new(3.0, 5.0);
1190        let l = Line2::through_points(a, b);
1191        assert!(l.is_vertical);
1192        assert_eq!(l.x_const, 3.0);
1193    }
1194
1195    #[test]
1196    fn parallel_detection() {
1197        assert!(Line2::new(1.0, 0.0).is_parallel(&Line2::new(1.0, 5.0)));
1198        assert!(!Line2::new(1.0, 0.0).is_parallel(&Line2::new(2.0, 0.0)));
1199        assert!(Line2::vertical(1.0).is_parallel(&Line2::vertical(2.0)));
1200        assert!(!Line2::vertical(1.0).is_parallel(&Line2::new(1.0, 0.0)));
1201    }
1202
1203    #[test]
1204    fn arrangement_with_parallel_lines() {
1205        // Two parallel lines + one transversal.
1206        let lines = vec![
1207            Line2::new(1.0, 0.0),
1208            Line2::new(1.0, 2.0),  // parallel to first
1209            Line2::new(-1.0, 3.0), // transversal
1210        ];
1211        let arr = build_line_arrangement(&lines).unwrap();
1212        // 2 intersections (transversal crosses each parallel line once).
1213        // Check Euler identity rather than exact vertex count (which includes
1214        // bbox corners and clip points).
1215        assert_eq!(arr.counts().euler, 2);
1216    }
1217}