wowlab_types/types/sim/encounter/
geometry.rs

1// #t(file: rust_magic_numbers) literals express polygon topology and planar geometry formulas
2// #t(file: rust_unchecked_indexing) ring length is validated before vertex and edge indexing
3
4use super::{EncounterValidationError, GEOMETRY_EPSILON, Position2, invalid};
5
6// #t(fn: rust_cyclomatic_complexity) validation enumerates independent ring topology invariants
7// #t(fn: rust_alloc_in_loop) validation allocates a precise diagnostic only on invalid construction input
8pub(super) fn validate_ring(
9    ring: &[Position2],
10    path: &str,
11) -> Result<(), EncounterValidationError> {
12    if ring.len() < 4 || ring.first() != ring.last() {
13        return Err(invalid(
14            path,
15            "ring must be closed and contain at least three vertices",
16        ));
17    }
18
19    for point in ring {
20        point
21            .validate()
22            .map_err(|error| invalid(path, format!("ring coordinates must be finite: {error}")))?;
23    }
24
25    let mut distinct = Vec::<Position2>::with_capacity(ring.len().saturating_sub(1));
26
27    for point in &ring[..ring.len() - 1] {
28        if !distinct
29            .iter()
30            .any(|seen| seen.distance(*point) <= GEOMETRY_EPSILON)
31        {
32            distinct.push(*point);
33        }
34    }
35
36    if distinct.len() < 3 || signed_area(ring).abs() <= GEOMETRY_EPSILON {
37        return Err(invalid(path, "ring geometry is degenerate"));
38    }
39
40    for index in 0..ring.len() - 1 {
41        if ring[index].distance(ring[index + 1]) <= GEOMETRY_EPSILON {
42            return Err(invalid(path, "ring contains a zero-length edge"));
43        }
44    }
45
46    let segment_count = ring.len() - 1;
47
48    for left in 0..segment_count {
49        for right in left + 1..segment_count {
50            let adjacent = right == left + 1 || (left == 0 && right == segment_count - 1);
51
52            if !adjacent
53                && segments_intersect(ring[left], ring[left + 1], ring[right], ring[right + 1])
54            {
55                return Err(invalid(path, "ring self-intersects"));
56            }
57        }
58    }
59
60    Ok(())
61}
62
63fn signed_area(ring: &[Position2]) -> f64 {
64    ring.windows(2)
65        .map(|edge| edge[0].x * edge[1].y - edge[1].x * edge[0].y)
66        .sum::<f64>()
67        / 2.0
68}
69
70fn cross(a: Position2, b: Position2, c: Position2) -> f64 {
71    (b.x - a.x).mul_add(c.y - a.y, -(b.y - a.y) * (c.x - a.x))
72}
73
74pub(super) fn point_on_segment(point: Position2, start: Position2, end: Position2) -> bool {
75    cross(start, end, point).abs() <= GEOMETRY_EPSILON
76        && point.x >= start.x.min(end.x) - GEOMETRY_EPSILON
77        && point.x <= start.x.max(end.x) + GEOMETRY_EPSILON
78        && point.y >= start.y.min(end.y) - GEOMETRY_EPSILON
79        && point.y <= start.y.max(end.y) + GEOMETRY_EPSILON
80}
81
82fn segments_intersect(a: Position2, b: Position2, c: Position2, d: Position2) -> bool {
83    let ab_c = cross(a, b, c);
84    let ab_d = cross(a, b, d);
85    let cd_a = cross(c, d, a);
86    let cd_b = cross(c, d, b);
87
88    ((ab_c > GEOMETRY_EPSILON && ab_d < -GEOMETRY_EPSILON)
89        || (ab_c < -GEOMETRY_EPSILON && ab_d > GEOMETRY_EPSILON))
90        && ((cd_a > GEOMETRY_EPSILON && cd_b < -GEOMETRY_EPSILON)
91            || (cd_a < -GEOMETRY_EPSILON && cd_b > GEOMETRY_EPSILON))
92        || point_on_segment(c, a, b)
93        || point_on_segment(d, a, b)
94        || point_on_segment(a, c, d)
95        || point_on_segment(b, c, d)
96}
97
98pub(super) fn rings_intersect(left: &[Position2], right: &[Position2]) -> bool {
99    left.windows(2).any(|a| {
100        right
101            .windows(2)
102            .any(|b| segments_intersect(a[0], a[1], b[0], b[1]))
103    })
104}
105
106pub(super) fn point_in_or_on_ring(point: Position2, ring: &[Position2]) -> bool {
107    ring.windows(2)
108        .any(|edge| point_on_segment(point, edge[0], edge[1]))
109        || point_strictly_in_ring(point, ring)
110}
111
112pub(super) fn point_strictly_in_ring(point: Position2, ring: &[Position2]) -> bool {
113    let mut inside = false;
114
115    for edge in ring.windows(2) {
116        let a = edge[0];
117        let b = edge[1];
118
119        if (a.y > point.y) != (b.y > point.y) {
120            let crossing_x = (b.x - a.x) * (point.y - a.y) / (b.y - a.y) + a.x;
121
122            if point.x < crossing_x {
123                inside = !inside;
124            }
125        }
126    }
127
128    inside
129}
wowlab_types/types/sim/encounter/geometry.rs

wowlab_types/types/sim/encounter/
geometry.rs
