From ed5c4078fa0e0833b9e43c3a37c041c4c16e8de2 Mon Sep 17 00:00:00 2001
From: Roland Hieber <rhieber@gaffel.ibr.cs.tu-bs.de>
Date: Wed, 3 Feb 2010 03:10:25 +0100
Subject: [PATCH] box overlapping

---
 Box.cxx | 58 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 Box.hxx |  1 +
 2 files changed, 58 insertions(+), 1 deletion(-)

diff --git a/Box.cxx b/Box.cxx
index 70ab618..d421525 100644
--- a/Box.cxx
+++ b/Box.cxx
@@ -51,10 +51,66 @@ Box::Extend(const Box& box)
 {
 }
 
+bool Box::OverlapsHelper(Box b) const {
+  bool overlaps = true;
+  for(size_t i = 0; i < 3; i++) {
+    overlaps &=
+      (m_min[i] < b.min()[i] && b.min()[i] < m_max[i]) ||
+      (m_min[i] < b.max()[i] && b.min()[i] < m_max[i]) ||
+      (m_min[i] > b.min()[i] && b.min()[i] > m_max[i]) ||
+      (m_min[i] > b.max()[i] && b.min()[i] > m_max[i]);
+  }
+  return overlaps;
+}
+
 bool
 Box::Overlaps(const Box& b) const
 {
-  return false;
+  // Boxes overlap if b.m_min or b.m_max are between our m_max and m_min
+  // for all dimensions
+  bool overlaps = OverlapsHelper(b);
+
+  // if that is not enough, swap y coordinates, we could have the following
+  // (sample for 2-dimensional case):
+  //      o----------
+  //      |         |      + denotes crossing,
+  // -----+----o    |      o denotes min/max point
+  // |    |    |    |
+  // |    -----+----o
+  // |         |
+  // o----------
+  if(!overlaps) {
+    Vec3f min = b.min();
+    Vec3f max = b.max();
+    Vec3f new_min(min[0], max[1], min[2]);
+    Vec3f new_max(max[0], min[1], max[2]);
+    Box new_y_box(new_min, new_max);
+    overlaps = OverlapsHelper(new_y_box);
+
+    // and now for y and z coordinates also
+    if(!overlaps) {
+      min = new_y_box.min();
+      max = new_y_box.max();
+      new_min = Vec3f(min[0], min[1], max[2]);
+      new_max = Vec3f(max[0], max[1], min[2]);
+      Box new_yz_box(new_min, new_max);
+      overlaps = OverlapsHelper(new_yz_box);
+
+      // and now for only z coordinates
+      if(!overlaps) {
+        min = new_y_box.min();
+        max = new_y_box.max();
+        new_min = Vec3f(min[0], max[1], min[2]);
+        new_max = Vec3f(max[0], min[1], max[2]);
+        Box new_z_box(new_min, new_max);
+        overlaps = OverlapsHelper(new_z_box);
+        // at this point, we do not need to swap further, as either m_max or
+        // m_min has been tested inside b.
+      }
+    }
+  }
+
+  return overlaps;
 }
 
 void
diff --git a/Box.hxx b/Box.hxx
index 1d46e03..ce09c2b 100644
--- a/Box.hxx
+++ b/Box.hxx
@@ -29,6 +29,7 @@ public:
   const Vec3f& max() const;
 private:
   Vec3f m_min, m_max;
+  bool OverlapsHelper(Box b) const;
 };
 
 #endif
-- 
2.20.1