making things intersect more greedily

6 files changed, 168 insertions, 120 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..b7e7836
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,6 @@
+
+test:
+	./node_modules/.bin/mocha -R nyan
+
+.PHONY: test
+
diff --git a/public/assets/javascripts/rectangles/models/rect.js b/public/assets/javascripts/rectangles/models/rect.js
index f91e759..8b6a666 100644
--- a/public/assets/javascripts/rectangles/models/rect.js
+++ b/public/assets/javascripts/rectangles/models/rect.js
@@ -95,7 +95,8 @@
 		return this.x.containsDisc(x,r) && this.y.containsDisc(y,r)
 	}
 	Rect.prototype.intersects = function(r){
-		return this.x.intersects(r.x) && this.y.intersects(r.y)
+		var corner_intersect = (this.x.b === r.x.a && this.y.b === r.y.a)
+		return this.x.intersects(r.x) && this.y.intersects(r.y) && ! corner_intersect
 	}
 	Rect.prototype.adjacent = function(r){
 		return this.x.adjacent(r.x) && this.y.adjacent(r.y)
@@ -137,70 +138,21 @@
 	Rect.prototype.split = function(r){
 		var rz = this
 		var splits = []
-		var split_contains = 0
-		var x_intervals = [], y_intervals = []
 		var sides = this.sides
 
-		// Split vertically
-		if (this.x.contains(r.x.a) && r.x.contains(this.x.b)) {
-			x_intervals.push([ new vec2( this.x.a,    r.x.a ), LEFT  ])
-			x_intervals.push([ new vec2(    r.x.a, this.x.b ), RIGHT ])
-			split_contains |= RIGHT
-		}
-
-		else if (r.x.contains(this.x.a) && this.x.contains(r.x.b)) {
-			x_intervals.push([ new vec2( this.x.a,    r.x.b ), LEFT  ])
-			x_intervals.push([ new vec2(    r.x.b, this.x.b ), RIGHT ])
-			split_contains |= LEFT
-		}
-	
-		else if (this.x.contains(r.x.a) && this.x.contains(r.x.b)) {
-			x_intervals.push([ new vec2( this.x.a,    r.x.a ), LEFT  ])
-			x_intervals.push([ new vec2(    r.x.a, 	  r.x.b ), 0     ])
-			x_intervals.push([ new vec2(    r.x.b, this.x.b ), RIGHT ])
-			split_contains |= LEFT | RIGHT
-		}
-
-		else { // if (r.x.contains(this.x.a) && r.x.contains(r.x.b)) {
-			x_intervals.push([ new vec2( this.x.a, this.x.b ), LEFT | RIGHT ])
-			split_contains |= LEFT | RIGHT
-		}
-
-		// Split horizontally
-		if (this.y.contains(r.y.a) && r.y.contains(this.y.b)) {
-			y_intervals.push([ new vec2( this.y.a,    r.y.a ), FRONT ])
-			y_intervals.push([ new vec2(    r.y.a, this.y.b ), BACK  ])
-			split_contains |= BACK
-		}
-
-		else if (r.y.contains(this.y.a) && this.y.contains(r.y.b)) {
-			y_intervals.push([ new vec2( this.y.a,    r.y.b ), FRONT ])
-			y_intervals.push([ new vec2(    r.y.b, this.y.b ), BACK  ])
-			split_contains |= FRONT
-		}
-	
-		else if (this.y.contains(r.y.a) && this.y.contains(r.y.b)) {
-			y_intervals.push([ new vec2( this.y.a,    r.y.a ), FRONT ])
-			y_intervals.push([ new vec2(    r.y.a, 	  r.y.b ), 0     ])
-			y_intervals.push([ new vec2(    r.y.b, this.y.b ), BACK  ])
-			split_contains |= FRONT | BACK
-		}
-
-		else { // if (r.y.contains(this.y.a) && this.y.contains(r.y.b)) {
-			y_intervals.push([ new vec2( this.y.a, this.y.b ), FRONT | BACK ])
-			split_contains |= FRONT | BACK
-		}
+		var x_intervals = this.x.split( r.x, LEFT, RIGHT )
+		var y_intervals = this.y.split( r.y, FRONT, BACK )
 
 		x_intervals.forEach(function(x){
 			y_intervals.forEach(function(y){
 				var rn = new Rect(x[0], y[0])
 				rn.id = rz.id
 				rn.sides = ((x[1] | y[1]) & sides)
-				if (r.intersects(rn)) {
-					rn.sides = 0
-				}
+// 				if (r.intersects(rn)) {
+// 					rn.sides = 0
+// 				}
 				// if (r.x.b == rn.x.a) {
-// 					rn.sides &= ~LEFT
+// 						rn.sides &= ~LEFT
 // 				}
 // 				if (rn.x.b == r.x.a) {
 // 					rn.sides &= ~RIGHT
diff --git a/public/assets/javascripts/rectangles/models/vec2.js b/public/assets/javascripts/rectangles/models/vec2.js
index 9c6fd99..4480473 100644
--- a/public/assets/javascripts/rectangles/models/vec2.js
+++ b/public/assets/javascripts/rectangles/models/vec2.js
@@ -80,7 +80,7 @@
 		return clamp(n, this.a+r, this.b-r)
 	}
 	vec2.prototype.intersects = function(v){
-		if (this.a == v.a) { // || this.b == v.b || this.a == v.b || this.b == v.a) {
+		if (this.a == v.a || this.b == v.b || this.a == v.b || this.b == v.a) {
 			return true
 		}
 		else if (this.a < v.a) {
@@ -106,6 +106,43 @@
 			return new vec2( max(this.a,v.a), min(this.b, v.b) )
 		}
 	}
+
+	// given two vectors, test how they overlap
+	// return the set of overlapping segments in the initial vector, labelled with sides
+	vec2.prototype.split = function(v, left, right){
+		var intervals = []
+
+		if (this.eq(v)) {
+			intervals.push([ new vec2( this.a, this.b ), left | right ])
+		}
+		
+		// a---A===b---B  (rightways overlap)
+		else if (this.contains(v.a) && v.contains(this.b)) {
+			intervals.push([ new vec2( this.a,    v.a ), left  ])
+			intervals.push([ new vec2(    v.a, this.b ), 0 ])
+		}
+
+    // A---a===B---b  (leftways overlap)
+		else if (v.contains(this.a) && this.contains(v.b)) {
+			intervals.push([ new vec2( this.a,    v.b ), 0  ])
+			intervals.push([ new vec2(    v.b, this.b ), right ])
+		}
+	
+		// a---A===B---b  (contains v)
+		else if (this.contains(v.a) && this.contains(v.b)) {
+			intervals.push([ new vec2( this.a,    v.a ), left  ])
+			intervals.push([ new vec2(    v.a, 	  v.b ), 0     ])
+			intervals.push([ new vec2(    v.b, this.b ), right ])
+		}
+		
+		// A---a===b---B  (contained in v)
+		else { // if (v.contains(this.a) && v.contains(v.b)) {
+			intervals.push([ new vec2( this.a, this.b ), 0 ])
+		}
+		
+		return intervals
+	}
+
 	vec2.prototype.toString = function(){
 		return "[" + ~~this.a + " " + ~~this.b + "]"
 	}
diff --git a/test/test-vec2.js b/test/01-test-vec2.js
index 054d37b..054d37b 100644
--- a/test/test-vec2.js
+++ b/test/01-test-vec2.js
diff --git a/test/02-test-rect.js b/test/02-test-rect.js
new file mode 100644
index 0000000..39693f5
--- /dev/null
+++ b/test/02-test-rect.js
@@ -0,0 +1,116 @@
+var assert = require("assert")
+var vec = require("../public/assets/javascripts/rectangles/models/vec2.js")
+var Rect = require("../public/assets/javascripts/rectangles/models/rect.js")
+var FRONT = 0x1, BACK = 0x2, LEFT = 0x4, RIGHT = 0x8, FLOOR = 0x10, CEILING = 0x20
+var ALL = FRONT | BACK | LEFT | RIGHT
+
+describe('rect', function(){
+  describe('#intersects()', function(){
+		var rect = new Rect(0, 0, 10, 10)
+
+    it('intersects itself', function(){
+      assert.equal(true, rect.intersects( new Rect(0, 0, 10, 10) ));
+    })
+    it('intersects more wide', function(){
+      assert.equal(true, rect.intersects( new Rect(0, 0, 5, 10) ));
+    })
+    it('intersects less wide', function(){
+      assert.equal(true, rect.intersects( new Rect(0, 0, 15, 10) ));
+    })
+    it('intersects more tall', function(){
+      assert.equal(true, rect.intersects( new Rect(0, 0, 10, 5) ));
+    })
+    it('intersects less tall', function(){
+      assert.equal(true, rect.intersects( new Rect(0, 0, 10, 15) ));
+    })
+    it('intersects if right-adjacent', function(){
+      assert.equal(true, rect.intersects( new Rect(10, 0, 20, 10) ));
+    })
+    it('intersects if bottom-adjacent', function(){
+      assert.equal(true, rect.intersects( new Rect(0, 10, 10, 20) ));
+    })
+    it('does not intersect if to the right', function(){
+      assert.equal(false, rect.intersects( new Rect(20, 0, 40, 10) ));
+    })
+    it('does not intersect if beneath', function(){
+      assert.equal(false, rect.intersects( new Rect(0, 20, 10, 40) ));
+    })
+  /*
+    it('does not intersect if corners intersect', function(){
+      assert.equal(false, rect.intersects( new Rect(10, 10, 20, 20) ));
+    })
+  */
+
+  })
+
+	var rect       = new Rect( new vec(1,4), new vec(1,4) )
+
+	var east_in    = new Rect( new vec(2,3), new vec(1,4) )
+	var east_edge  = new Rect( new vec(2,4), new vec(1,4) )
+	var east       = new Rect( new vec(2,5), new vec(1,4) )
+
+	var south_in   = new Rect( new vec(1,4), new vec(2,3) )
+	var south_edge = new Rect( new vec(1,4), new vec(2,4) )
+	var south      = new Rect( new vec(1,4), new vec(2,5) )
+
+	var corner     = new Rect( new vec(3,5), new vec(3,5) )
+
+  function sides (s) {
+    return s.reduce(function(prev, curr){
+      return prev | curr.sides
+    }, 0)
+  }
+
+  describe('#split(rect, east)', function(){
+    var s0 = rect.split(east)
+    var s1 = east.split(rect)
+    it('splits on all 4 sides', function(){
+      assert.equal(ALL, sides(s0) | sides(s1))
+    })
+    it('rect is front/back/left', function(){
+      assert.equal(FRONT | BACK | LEFT, sides(s0))
+    })
+    it('east is front/back/right', function(){
+      assert.equal(FRONT | BACK | RIGHT, sides(s1))
+    })
+  })
+
+  describe('#split(rect, east_in)', function(){
+    var s0 = rect.split(east_in)
+    var s1 = east_in.split(rect)
+    it('splits on all 4 sides', function(){
+      assert.equal(ALL, sides(s0) | sides(s1))
+    })
+    it('rect is has all sides', function(){
+      assert.equal(ALL, sides(s0))
+    })
+    it('east_in only has front/back', function(){
+      assert.equal(FRONT | BACK, sides(s1))
+    })
+  })
+
+  describe('#split(rect, east_edge)', function(){
+    var s0 = rect.split(east_edge)
+    var s1 = east_edge.split(rect)
+
+    console.log("\n")
+    console.log(rect+"")
+    console.log(east_edge+"")
+    console.log(s0.map(function(r){ return r.toString() }))
+    console.log(s1.map(function(r){ return r.toString() }))
+
+    it('splits on all 4 sides', function(){
+      assert.equal(ALL, sides(s0) | sides(s1))
+    })
+    it('rect is front/back/left', function(){
+      assert.equal(FRONT | BACK | LEFT, sides(s0))
+    })
+    it('east is front/back/right', function(){
+      assert.equal(FRONT | BACK | RIGHT, sides(s1))
+    })
+  })
+
+})
+/*
+*/
+
diff --git a/test/test-rect.js b/test/test-rect.js
deleted file mode 100644
index 7dd7ae6..0000000
--- a/test/test-rect.js
+++ /dev/null
@@ -1,63 +0,0 @@
-var assert = require("assert")
-var vec = require("../public/assets/javascripts/rectangles/models/vec2.js")
-var Rect = require("../public/assets/javascripts/rectangles/models/rect.js")
-var FRONT = 0x1, BACK = 0x2, LEFT = 0x4, RIGHT = 0x8, FLOOR = 0x10, CEILING = 0x20
-var ALL = FRONT | BACK | LEFT | RIGHT
-
-describe('rect', function(){
-  describe('#intersects()', function(){
-		var rect = new Rect(0, 0, 10, 10)
-
-    it('intersects itself', function(){
-      assert.equal(true, rect.intersects( new Rect(0, 0, 10, 10) ));
-    })
-    it('intersects more wide', function(){
-      assert.equal(true, rect.intersects( new Rect(0, 0, 5, 10) ));
-    })
-    it('intersects less wide', function(){
-      assert.equal(true, rect.intersects( new Rect(0, 0, 15, 10) ));
-    })
-    it('intersects more tall', function(){
-      assert.equal(true, rect.intersects( new Rect(0, 0, 10, 5) ));
-    })
-    it('intersects less tall', function(){
-      assert.equal(true, rect.intersects( new Rect(0, 0, 10, 15) ));
-    })
-    it('intersects if right-adjacent', function(){
-      assert.equal(true, rect.intersects( new Rect(10, 0, 20, 10) ));
-    })
-    it('intersects if bottom-adjacent', function(){
-      assert.equal(true, rect.intersects( new Rect(0, 10, 10, 20) ));
-    })
-    it('does not intersect if to the right', function(){
-      assert.equal(false, rect.intersects( new Rect(20, 0, 40, 10) ));
-    })
-    it('does not intersect if beneath', function(){
-      assert.equal(false, rect.intersects( new Rect(0, 20, 10, 40) ));
-    })
-  /*
-    it('does not intersect if corners intersect', function(){
-      assert.equal(false, rect.intersects( new Rect(10, 10, 20, 20) ));
-    })
-  */
-
-  })
-  describe('#split()', function(){
-		var rect       = new Rect( 0,  0, 10, 10)
-		var east       = new Rect( 5,  0, 15, 10)
-		var east_in    = new Rect( 5,  0, 10, 10)
-		var east_edge  = new Rect(10,  0, 20, 10)
-		var south      = new Rect( 0,  5, 10, 15)
-		var south_in   = new Rect( 0,  5, 10, 10)
-		var south_edge = new Rect( 0, 10, 10, 15)
-		var corner     = new Rect( 5,  5, 15, 15)
-
-    it('splits east', function(){
-      var splits = rect.split(east)
-      var splits2 = east.split(rect)
-      console.log("\n")
-      console.log(rect+"")
-      console.log(splits.map(function(r){ return r.toString() }))
-    })
-  })
-})