1use crate::NQuin;
5
6#[derive(Debug, Clone, Copy, PartialEq, Eq)]
8pub enum TemporalOp {
9 Before,
10 Meets,
11 Overlaps,
12 Starts,
13 During,
14 Finishes,
15 Equals,
16}
17
18#[derive(Debug, Clone, Copy, PartialEq, Eq)]
20pub enum Rcc8Relation {
21 Disconnected,
23 ExternallyConnected,
25 PartiallyOverlapping,
27 TangentiallyProperPart,
29 TangentiallyProperPartInverse,
31 NonTangentialProperPart,
33 NonTangentialProperPartInverse,
35 Equal,
37}
38
39#[derive(Debug, Clone)]
41pub struct SpatialRegion {
42 pub region_id: u64,
43 pub boundary_points: Vec<(f64, f64)>, pub centroid: (f64, f64),
45 pub area: f64,
46}
47
48impl SpatialRegion {
49 pub fn new(region_id: u64, boundary_points: Vec<(f64, f64)>) -> Self {
51 let centroid = Self::compute_centroid(&boundary_points);
52 let area = Self::compute_area(&boundary_points);
53
54 Self {
55 region_id,
56 boundary_points,
57 centroid,
58 area,
59 }
60 }
61
62 fn compute_centroid(points: &[(f64, f64)]) -> (f64, f64) {
64 if points.is_empty() {
65 return (0.0, 0.0);
66 }
67
68 let (sum_x, sum_y) = points
69 .iter()
70 .fold((0.0, 0.0), |(sx, sy), (x, y)| (sx + x, sy + y));
71
72 (sum_x / points.len() as f64, sum_y / points.len() as f64)
73 }
74
75 fn compute_area(points: &[(f64, f64)]) -> f64 {
77 if points.len() < 3 {
78 return 0.0;
79 }
80
81 let mut area = 0.0;
82 for i in 0..points.len() {
83 let j = (i + 1) % points.len();
84 area += points[i].0 * points[j].1;
85 area -= points[j].0 * points[i].1;
86 }
87
88 area.abs() / 2.0
89 }
90
91 pub fn contains_point(&self, point: (f64, f64)) -> bool {
93 if self.boundary_points.len() < 3 {
94 return false;
95 }
96
97 let mut inside = false;
98 let (x, y) = point;
99 let n = self.boundary_points.len();
100
101 for i in 0..n {
102 let j = (i + 1) % n;
103 let (xi, yi) = self.boundary_points[i];
104 let (xj, yj) = self.boundary_points[j];
105
106 if ((yi > y) != (yj > y)) && (x < (xj - xi) * (y - yi) / (yj - yi) + xi) {
107 inside = !inside;
108 }
109 }
110
111 inside
112 }
113
114 pub fn intersects(&self, other: &SpatialRegion) -> bool {
116 let self_bounds = self.get_bounding_box();
118 let other_bounds = other.get_bounding_box();
119
120 !(self_bounds.0 > other_bounds.1
121 || self_bounds.1 < other_bounds.0
122 || self_bounds.2 > other_bounds.3
123 || self_bounds.3 < other_bounds.2)
124 }
125
126 fn get_bounding_box(&self) -> (f64, f64, f64, f64) {
128 if self.boundary_points.is_empty() {
129 return (0.0, 0.0, 0.0, 0.0);
130 }
131
132 let (min_x, max_x) = self
133 .boundary_points
134 .iter()
135 .fold((f64::INFINITY, f64::NEG_INFINITY), |(min, max), (x, _)| {
136 (min.min(*x), max.max(*x))
137 });
138
139 let (min_y, max_y) = self
140 .boundary_points
141 .iter()
142 .fold((f64::INFINITY, f64::NEG_INFINITY), |(min, max), (_, y)| {
143 (min.min(*y), max.max(*y))
144 });
145
146 (min_x, max_x, min_y, max_y)
147 }
148}
149
150pub fn evaluate_rcc8(region_a: &SpatialRegion, region_b: &SpatialRegion) -> Rcc8Relation {
152 if region_a.region_id == region_b.region_id {
154 return Rcc8Relation::Equal;
155 }
156
157 let intersects = region_a.intersects(region_b);
159
160 if !intersects {
161 return Rcc8Relation::Disconnected;
162 }
163
164 let a_inside_b = region_a
166 .boundary_points
167 .iter()
168 .all(|&point| region_b.contains_point(point));
169 let b_inside_a = region_b
170 .boundary_points
171 .iter()
172 .all(|&point| region_a.contains_point(point));
173
174 if a_inside_b && b_inside_a {
175 Rcc8Relation::Equal
176 } else if a_inside_b {
177 let boundaries_touch = check_boundary_touch(region_a, region_b);
179 if boundaries_touch {
180 Rcc8Relation::TangentiallyProperPart
181 } else {
182 Rcc8Relation::NonTangentialProperPart
183 }
184 } else if b_inside_a {
185 let boundaries_touch = check_boundary_touch(region_a, region_b);
186 if boundaries_touch {
187 Rcc8Relation::TangentiallyProperPartInverse
188 } else {
189 Rcc8Relation::NonTangentialProperPartInverse
190 }
191 } else {
192 let interior_overlap = check_boundary_touch(region_a, region_b);
199 if interior_overlap {
200 Rcc8Relation::PartiallyOverlapping
201 } else {
202 Rcc8Relation::ExternallyConnected
203 }
204 }
205}
206
207fn check_boundary_touch(region_a: &SpatialRegion, region_b: &SpatialRegion) -> bool {
209 for &point_a in ®ion_a.boundary_points {
212 if region_b.contains_point(point_a) {
213 return true;
214 }
215 }
216
217 for &point_b in ®ion_b.boundary_points {
218 if region_a.contains_point(point_b) {
219 return true;
220 }
221 }
222
223 false
224}
225
226pub const MAX_BOUNDARY_POINTS: usize = 64;
235
236const POINT_SCALE: f64 = 1_000_000.0;
238const GEO_EPS: f64 = 1e-9;
239
240pub fn pack_point(x: f64, y: f64) -> u64 {
243 let xi = (x * POINT_SCALE).round() as i32 as u32 as u64;
244 let yi = (y * POINT_SCALE).round() as i32 as u32 as u64;
245 (xi << 32) | yi
246}
247
248pub fn unpack_point(packed: u64) -> (f64, f64) {
250 let xi = (packed >> 32) as u32 as i32;
251 let yi = (packed & 0xFFFF_FFFF) as u32 as i32;
252 (xi as f64 / POINT_SCALE, yi as f64 / POINT_SCALE)
253}
254
255fn bbox(poly: &[(f64, f64)]) -> (f64, f64, f64, f64) {
258 let mut mnx = f64::INFINITY;
259 let mut mxx = f64::NEG_INFINITY;
260 let mut mny = f64::INFINITY;
261 let mut mxy = f64::NEG_INFINITY;
262 for &(x, y) in poly {
263 mnx = mnx.min(x);
264 mxx = mxx.max(x);
265 mny = mny.min(y);
266 mxy = mxy.max(y);
267 }
268 (mnx, mxx, mny, mxy)
269}
270
271fn bbox_overlap(a: &[(f64, f64)], b: &[(f64, f64)]) -> bool {
274 let (amnx, amxx, amny, amxy) = bbox(a);
275 let (bmnx, bmxx, bmny, bmxy) = bbox(b);
276 !(amnx > bmxx || amxx < bmnx || amny > bmxy || amxy < bmny)
277}
278
279fn point_in_interior(p: (f64, f64), poly: &[(f64, f64)]) -> bool {
281 if poly.len() < 3 {
282 return false;
283 }
284 let (x, y) = p;
285 let mut inside = false;
286 let n = poly.len();
287 for i in 0..n {
288 let j = (i + 1) % n;
289 let (xi, yi) = poly[i];
290 let (xj, yj) = poly[j];
291 if ((yi > y) != (yj > y)) && (x < (xj - xi) * (y - yi) / (yj - yi) + xi) {
292 inside = !inside;
293 }
294 }
295 inside
296}
297
298fn point_on_boundary(p: (f64, f64), poly: &[(f64, f64)]) -> bool {
300 let n = poly.len();
301 if n < 2 {
302 return false;
303 }
304 for i in 0..n {
305 let a = poly[i];
306 let b = poly[(i + 1) % n];
307 let cross = (b.0 - a.0) * (p.1 - a.1) - (b.1 - a.1) * (p.0 - a.0);
309 if cross.abs() <= GEO_EPS
310 && p.0 >= a.0.min(b.0) - GEO_EPS
311 && p.0 <= a.0.max(b.0) + GEO_EPS
312 && p.1 >= a.1.min(b.1) - GEO_EPS
313 && p.1 <= a.1.max(b.1) + GEO_EPS
314 {
315 return true;
316 }
317 }
318 false
319}
320
321#[inline]
323fn inside_or_on(p: (f64, f64), poly: &[(f64, f64)]) -> bool {
324 point_in_interior(p, poly) || point_on_boundary(p, poly)
325}
326
327fn all_inside_or_on(pts: &[(f64, f64)], poly: &[(f64, f64)]) -> bool {
329 !pts.is_empty() && pts.iter().all(|&p| inside_or_on(p, poly))
330}
331
332fn any_on_boundary(pts: &[(f64, f64)], poly: &[(f64, f64)]) -> bool {
335 pts.iter().any(|&p| point_on_boundary(p, poly))
336}
337
338fn interiors_overlap(a: &[(f64, f64)], b: &[(f64, f64)]) -> bool {
342 a.iter().any(|&p| point_in_interior(p, b)) || b.iter().any(|&p| point_in_interior(p, a))
343}
344
345pub fn evaluate_rcc8_points(
350 id_a: u64,
351 a: &[(f64, f64)],
352 id_b: u64,
353 b: &[(f64, f64)],
354) -> Rcc8Relation {
355 if id_a == id_b {
356 return Rcc8Relation::Equal;
357 }
358 if !bbox_overlap(a, b) {
359 return Rcc8Relation::Disconnected;
360 }
361 let a_in_b = all_inside_or_on(a, b);
362 let b_in_a = all_inside_or_on(b, a);
363 if a_in_b && b_in_a {
364 return Rcc8Relation::Equal;
365 }
366 if a_in_b {
367 return if any_on_boundary(a, b) {
368 Rcc8Relation::TangentiallyProperPart
369 } else {
370 Rcc8Relation::NonTangentialProperPart
371 };
372 }
373 if b_in_a {
374 return if any_on_boundary(b, a) {
375 Rcc8Relation::TangentiallyProperPartInverse
376 } else {
377 Rcc8Relation::NonTangentialProperPartInverse
378 };
379 }
380 if interiors_overlap(a, b) {
381 Rcc8Relation::PartiallyOverlapping
382 } else {
383 Rcc8Relation::ExternallyConnected
385 }
386}
387
388pub fn evaluate_temporal(
390 op: TemporalOp,
391 t1_start: i64,
392 t1_end: i64,
393 t2_start: i64,
394 t2_end: i64,
395) -> bool {
396 match op {
397 TemporalOp::Before => t1_end < t2_start,
398 TemporalOp::Meets => t1_end == t2_start,
399 TemporalOp::Overlaps => t1_start < t2_start && t1_end > t2_start && t1_end < t2_end,
400 TemporalOp::Starts => t1_start == t2_start && t1_end < t2_end,
401 TemporalOp::During => t1_start > t2_start && t1_end < t2_end,
402 TemporalOp::Finishes => t1_end == t2_end && t1_start > t2_start,
403 TemporalOp::Equals => t1_start == t2_start && t1_end == t2_end,
404 }
405}
406
407const SPATIAL_SCALE: f64 = 1_000.0;
412
413pub fn region_to_quin(region: &SpatialRegion, context: u64) -> NQuin {
418 let subject = region.region_id;
419 let predicate = crate::q_hash("has_spatial_region");
420
421 let cx = (region.centroid.0 * SPATIAL_SCALE).round() as u64;
424 let cy = (region.centroid.1 * SPATIAL_SCALE).round() as u64;
425 let ar = (region.area * SPATIAL_SCALE).round() as u64;
426
427 let object = ((cx & 0xFFFF) << 48) | ((cy & 0xFFFF) << 32) | (ar & 0xFFFF_FFFF);
428
429 let mut quin = NQuin {
430 subject,
431 predicate,
432 object,
433 context,
434 metadata: 0,
435 parity: 0,
436 };
437
438 quin.parity = quin.subject ^ quin.predicate ^ quin.object ^ quin.context ^ quin.metadata;
440
441 quin
442}
443
444pub fn quin_to_region(quin: &NQuin) -> Option<SpatialRegion> {
446 let centroid_x = ((quin.object >> 48) & 0xFFFF) as f64 / SPATIAL_SCALE;
448 let centroid_y = ((quin.object >> 32) & 0xFFFF) as f64 / SPATIAL_SCALE;
449 let area = (quin.object & 0xFFFF_FFFF) as f64 / SPATIAL_SCALE;
450
451 let region_id = quin.subject;
453
454 Some(SpatialRegion {
455 region_id,
456 boundary_points: vec![], centroid: (centroid_x, centroid_y),
458 area,
459 })
460}
461
462pub type Aabb = (f64, f64, f64, f64);
469
470pub fn polygon_aabb(poly: &[(f64, f64)]) -> Aabb {
472 let (mnx, mxx, mny, mxy) = bbox(poly);
473 (mnx, mny, mxx, mxy)
474}
475
476#[inline]
478pub fn aabb_overlap(a: Aabb, b: Aabb) -> bool {
479 !(a.0 > b.2 || a.2 < b.0 || a.1 > b.3 || a.3 < b.1)
480}
481
482pub fn spatial_index_query(query: Aabb, region_boxes: &[Aabb], out: &mut [usize]) -> usize {
486 let mut n = 0usize;
487 for (i, &b) in region_boxes.iter().enumerate() {
488 if aabb_overlap(query, b) {
489 if n >= out.len() {
490 break;
491 }
492 out[n] = i;
493 n += 1;
494 }
495 }
496 n
497}
498
499pub fn minkowski_interval(dt: f64, dx: f64, dy: f64, dz: f64, c: f64) -> f64 {
504 -(c * c) * dt * dt + dx * dx + dy * dy + dz * dz
505}
506
507pub fn causally_connectable(dt: f64, dx: f64, dy: f64, dz: f64, c: f64) -> bool {
511 minkowski_interval(dt, dx, dy, dz, c) <= GEO_EPS
512}
513
514pub fn heat_equation_step(u: &[f64], alpha: f64, dt: f64, dx: f64, out: &mut [f64]) -> bool {
520 let n = u.len();
521 if n < 2 || out.len() < n || dx == 0.0 {
522 return false;
523 }
524 let r = alpha * dt / (dx * dx);
525 out[0] = u[0];
526 out[n - 1] = u[n - 1];
527 for i in 1..n - 1 {
528 out[i] = u[i] + r * (u[i - 1] - 2.0 * u[i] + u[i + 1]);
529 }
530 true
531}
532
533#[cfg(test)]
534mod tests {
535 use super::*;
536
537 #[test]
538 fn test_rcc8_basic_relations() {
539 let region_a = SpatialRegion::new(1, vec![(0.0, 0.0), (2.0, 0.0), (2.0, 2.0), (0.0, 2.0)]);
540 let region_b = SpatialRegion::new(2, vec![(1.0, 1.0), (3.0, 1.0), (3.0, 3.0), (1.0, 3.0)]);
541
542 let relation = evaluate_rcc8(®ion_a, ®ion_b);
543 assert_eq!(relation, Rcc8Relation::PartiallyOverlapping);
544 }
545
546 #[test]
547 fn test_rcc8_points_zero_heap() {
548 let big = [(0.0, 0.0), (10.0, 0.0), (10.0, 10.0), (0.0, 10.0)];
550 let small = [(3.0, 3.0), (7.0, 3.0), (7.0, 7.0), (3.0, 7.0)];
551 assert_eq!(
553 evaluate_rcc8_points(1, &small, 2, &big),
554 Rcc8Relation::NonTangentialProperPart
555 );
556 assert_eq!(
557 evaluate_rcc8_points(2, &big, 1, &small),
558 Rcc8Relation::NonTangentialProperPartInverse
559 );
560
561 let far = [(20.0, 20.0), (22.0, 20.0), (22.0, 22.0), (20.0, 22.0)];
563 assert_eq!(
564 evaluate_rcc8_points(1, &big, 3, &far),
565 Rcc8Relation::Disconnected
566 );
567
568 let a = [(0.0, 0.0), (4.0, 0.0), (4.0, 4.0), (0.0, 4.0)];
570 let b = [(2.0, 2.0), (6.0, 2.0), (6.0, 6.0), (2.0, 6.0)];
571 assert_eq!(
572 evaluate_rcc8_points(1, &a, 2, &b),
573 Rcc8Relation::PartiallyOverlapping
574 );
575
576 assert_eq!(evaluate_rcc8_points(5, &a, 5, &b), Rcc8Relation::Equal);
578
579 let (x, y) = unpack_point(pack_point(-45.123456, 170.654321));
581 assert!((x + 45.123456).abs() < 1e-5 && (y - 170.654321).abs() < 1e-5);
582 }
583
584 #[test]
585 fn test_temporal_relations() {
586 assert!(evaluate_temporal(TemporalOp::Before, 0, 10, 15, 25));
587 assert!(evaluate_temporal(TemporalOp::Meets, 0, 10, 10, 20));
588 assert!(evaluate_temporal(TemporalOp::Overlaps, 0, 15, 10, 25));
589 assert!(evaluate_temporal(TemporalOp::During, 5, 15, 0, 25));
590 }
591
592 #[test]
593 fn test_region_quin_conversion() {
594 let region = SpatialRegion::new(42, vec![(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)]);
595 let quin = region_to_quin(®ion, 123);
596 let extracted = quin_to_region(&quin).unwrap();
597
598 assert_eq!(extracted.region_id, region.region_id);
599 assert_eq!(extracted.centroid, region.centroid);
600 assert_eq!(extracted.area, region.area);
601 }
602
603 #[test]
604 fn spatial_index_broad_phase() {
605 let boxes = [
607 (0.0, 0.0, 1.0, 1.0),
608 (2.0, 2.0, 3.0, 3.0),
609 (0.5, 0.5, 2.5, 2.5),
610 ];
611 let query = (0.8, 0.8, 1.2, 1.2);
612 let mut out = [0usize; 8];
613 let n = spatial_index_query(query, &boxes, &mut out);
614 assert_eq!(n, 2, "query overlaps box 0 and box 2, not box 1");
615 assert!(out[..n].contains(&0) && out[..n].contains(&2) && !out[..n].contains(&1));
616 assert_eq!(
618 polygon_aabb(&[(0.0, 0.0), (2.0, 0.0), (2.0, 1.0)]),
619 (0.0, 0.0, 2.0, 1.0)
620 );
621 }
622
623 #[test]
624 fn minkowski_light_cone_classification() {
625 let c = 1.0;
626 assert!(minkowski_interval(2.0, 1.0, 0.0, 0.0, c) < 0.0);
628 assert!(causally_connectable(2.0, 1.0, 0.0, 0.0, c));
629 assert!(minkowski_interval(1.0, 1.0, 0.0, 0.0, c).abs() < 1e-9);
631 assert!(causally_connectable(1.0, 1.0, 0.0, 0.0, c));
632 assert!(minkowski_interval(1.0, 3.0, 0.0, 0.0, c) > 0.0);
634 assert!(!causally_connectable(1.0, 3.0, 0.0, 0.0, c));
635 }
636
637 #[test]
638 fn heat_pde_step_diffuses_and_conserves() {
639 let u = [0.0, 0.0, 1.0, 0.0, 0.0];
641 let mut out = [0.0f64; 5];
642 assert!(heat_equation_step(&u, 0.25, 1.0, 1.0, &mut out));
643 assert!((out[2] - 0.5).abs() < 1e-9);
645 assert!((out[1] - 0.25).abs() < 1e-9 && (out[3] - 0.25).abs() < 1e-9);
646 assert_eq!(out[0], 0.0);
647 let sum: f64 = out.iter().sum();
649 assert!((sum - 1.0).abs() < 1e-9);
650 assert!(!heat_equation_step(&u, 0.25, 1.0, 0.0, &mut out));
652 }
653}