1use super::boolean_2::point_in_polygon;
49use super::primitives::Point2;
50
51#[derive(Debug, Clone, Copy, PartialEq)]
58pub struct Line2 {
59 pub slope: f64,
61 pub intercept: f64,
63 pub is_vertical: bool,
65 pub x_const: f64,
67}
68
69impl Line2 {
70 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 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 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 #[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 #[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 f64::NAN
122 } else {
123 (y - self.intercept) / self.slope
124 }
125 }
126
127 #[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
141pub fn line_line_intersection(l1: &Line2, l2: &Line2) -> Option<Point2> {
143 if l1.is_vertical && l2.is_vertical {
144 return None; }
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#[derive(Debug, Clone, Copy, PartialEq)]
168pub struct ArrangementEdge {
169 pub line: usize,
171 pub start: Point2,
173 pub end: Point2,
175}
176
177#[derive(Debug, Clone, PartialEq)]
180pub struct ArrangementFace {
181 pub boundary: Vec<Point2>,
183 pub unbounded: bool,
186}
187
188#[derive(Debug, Clone, PartialEq)]
190pub struct Arrangement {
191 pub lines: Vec<Line2>,
193 pub vertices: Vec<Point2>,
195 pub edges: Vec<ArrangementEdge>,
197 pub faces: Vec<ArrangementFace>,
199 pub bbox_min: Point2,
201 pub bbox_max: Point2,
202}
203
204#[derive(Debug, Clone, Copy, PartialEq, Eq)]
206pub struct ArrangementCounts {
207 pub vertices: usize,
208 pub edges: usize,
209 pub faces: usize,
210 pub euler: i64,
212}
213
214impl Arrangement {
215 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
235const BBOX_MARGIN: f64 = 3.0;
242
243fn 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
266fn clip_line_to_bbox(line: &Line2, bmin: Point2, bmax: Point2) -> (Point2, Point2) {
269 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 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
293fn 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), (d.x, bmax.x - p0.x), (-d.y, p0.y - bmin.y), (d.y, bmax.y - p0.y), ] {
305 if p.abs() <= f64::MIN_POSITIVE {
306 if q < 0.0 {
308 return (0.0, 0.0); }
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
322pub 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 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 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 let (bmin, bmax) = compute_bbox(&vertices);
359
360 let mut edges: Vec<ArrangementEdge> = Vec::new();
363 let mut boundary_points: Vec<Point2> = Vec::new();
365 for (li, line) in lines.iter().enumerate() {
366 let (clip_a, clip_b) = clip_line_to_bbox(line, bmin, bmax);
368
369 boundary_points.push(clip_a);
371 boundary_points.push(clip_b);
372
373 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 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 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 let bbox_edges = build_bbox_boundary_edges(bmin, bmax, &boundary_points);
411 edges.extend(bbox_edges);
412
413 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 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 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
447fn 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
456fn 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), Point2::new(bmax.x, bmin.y), Point2::new(bmax.x, bmax.y), Point2::new(bmin.x, bmax.y), ];
472
473 let sides: [(Point2, Point2, bool); 4] = [
479 (corners[0], corners[1], true), (corners[1], corners[2], false), (corners[2], corners[3], true), (corners[3], corners[0], false), ];
484
485 let mut edges = Vec::new();
486 for (start, end, horizontal) in sides {
487 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 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 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, start: s,
526 end: e,
527 });
528 }
529 }
530 }
531 edges
532}
533
534#[derive(Clone, Copy)]
540struct ArrHalfEdge {
541 origin: usize, twin: usize, next: usize, face: usize, }
546
547fn extract_faces(
551 edges: &[ArrangementEdge],
552 vertices: &[Point2],
553 _bmin: Point2,
554 _bmax: Point2,
555) -> Vec<ArrangementFace> {
556 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 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 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 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 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 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 let unbounded = area < 0.0;
658 faces.push(ArrangementFace {
659 boundary,
660 unbounded,
661 });
662 }
663
664 for f in &mut faces {
666 if f.unbounded {
667 f.boundary.reverse();
668 }
669 }
670
671 faces
672}
673
674fn 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
682fn 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
692fn 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
706pub fn zone_traversal(arr: &Arrangement, query: &Line2) -> Vec<usize> {
713 let mut crossings: Vec<(f64, usize)> = Vec::new(); 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 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 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 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 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
768fn 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; }
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
785fn 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
795pub 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
831pub fn dual_point_to_line(p: Point2) -> Line2 {
840 Line2::new(p.x, -p.y)
841}
842
843pub 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
853pub 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
860pub fn dual_incidence_holds(p: Point2, l: &Line2) -> bool {
863 if l.is_vertical {
864 return true;
866 }
867 let p_star = dual_point_to_line(p);
868 let l_star = dual_line_to_point(l).unwrap();
869 let p_on_l = (p.y - l.y_at(p.x)).abs() < 1e-9 * (p.y.abs() + 1.0);
871 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#[cfg(test)]
882mod tests {
883 use super::*;
884
885 fn two_general_lines() -> Vec<Line2> {
887 vec![Line2::new(1.0, 0.0), Line2::new(-1.0, 2.0)]
888 }
889
890 fn three_general_lines() -> Vec<Line2> {
892 vec![
893 Line2::new(1.0, 0.0), Line2::new(-1.0, 2.0), Line2::new(0.0, 1.0), ]
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 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 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 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 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 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 let lines = vec![Line2::vertical(0.0), Line2::new(1.0, 0.0)];
989 let arr = build_line_arrangement(&lines).unwrap();
990 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 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 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 #[test]
1077 fn dual_point_to_line_correct() {
1078 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 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 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 let l = Line2::new(1.0, 0.0); let l_star = dual_line_to_point(&l).unwrap(); let p_above = Point2::new(0.0, 1.0);
1129 let p_above_star = dual_point_to_line(p_above); 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 let p_below = Point2::new(0.0, -1.0);
1140 let p_below_star = dual_point_to_line(p_below); 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 let l = Line2::new(2.0, 1.0); let p = Point2::new(1.0, 3.0); assert!(
1154 dual_incidence_holds(p, &l),
1155 "incidence must hold for p on l"
1156 );
1157
1158 let p_off = Point2::new(1.0, 4.0); 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 let lines = vec![
1207 Line2::new(1.0, 0.0),
1208 Line2::new(1.0, 2.0), Line2::new(-1.0, 3.0), ];
1211 let arr = build_line_arrangement(&lines).unwrap();
1212 assert_eq!(arr.counts().euler, 2);
1216 }
1217}