5 files changed, 65 insertions, 6 deletions

diff --git a/public/assets/javascripts/rectangles/engine/rooms/clipper.js b/public/assets/javascripts/rectangles/engine/rooms/clipper.js
index 365ae8c..d67f6ad 100644
--- a/public/assets/javascripts/rectangles/engine/rooms/clipper.js
+++ b/public/assets/javascripts/rectangles/engine/rooms/clipper.js
@@ -52,7 +52,7 @@
 		
 			base.reset_rects()
 			base.clip_rects()
-			base.cull_rects()
+			base.cull_rects_iterative()
 
 			Rooms.regions = sort.rects_by_position(regions)
 		}
@@ -131,6 +131,26 @@
 			return regions
 		}
 
+		// Find overlapping regions and dedupe the smaller ones
+		base.cull_rects_iterative = function(){
+			regions = sort.rects_by_area( regions )
+			
+			var region_i, region_j, i, j, _len
+			
+			for (i = 0, _len = regions.length; i < _len-1; i++) {
+				region_i = regions[i]
+				for (j = i+1; j < _len; j++) {
+					region_j = regions[j]
+					if (region_j.dupe) continue;
+					if (region_i.overlaps(region_j)) {
+						region_i.dupe = true
+					}
+				}
+			}
+
+			return regions
+		}
+
 		return base
 	}
 
diff --git a/public/assets/javascripts/rectangles/models/rect.js b/public/assets/javascripts/rectangles/models/rect.js
index 3341239..590440a 100644
--- a/public/assets/javascripts/rectangles/models/rect.js
+++ b/public/assets/javascripts/rectangles/models/rect.js
@@ -94,6 +94,9 @@
 	Rect.prototype.containsDisc = function(x,y,r){
 		return this.x.containsDisc(x,r) && this.y.containsDisc(y,r)
 	}
+	Rect.prototype.overlaps = function(rect){
+		return this.x.overlaps(rect.x) && this.y.overlaps(rect.y)
+	}
 	Rect.prototype.intersects = function(r){
 		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
diff --git a/public/assets/javascripts/rectangles/models/vec2.js b/public/assets/javascripts/rectangles/models/vec2.js
index b0c88c1..ee02088 100644
--- a/public/assets/javascripts/rectangles/models/vec2.js
+++ b/public/assets/javascripts/rectangles/models/vec2.js
@@ -93,6 +93,19 @@
 			return (this.a < v.b && v.b <= this.b) || (v.a < this.b && this.b <= v.b)
 		}
 	}
+	vec2.prototype.overlaps = function(v){
+		if (this.a == v.a || this.b == v.b) {
+			return true
+		}
+		if (this.a < v.a) {
+			return (v.a < this.b && this.b < v.b) || (this.a < v.b && v.b < this.b)
+		}
+		else if (v.a < this.a) {
+			return (this.a < v.b && v.b < this.b) || (v.a < this.b && this.b < v.b)
+		}
+	}
+
+
 	vec2.prototype.adjacent = function(v){
 		if (this.a == v.a || this.b == v.b || this.a == v.b || this.b == v.a) {
 			return true
diff --git a/public/assets/javascripts/rectangles/util/sort.js b/public/assets/javascripts/rectangles/util/sort.js
index c0b5d54..3b4771c 100644
--- a/public/assets/javascripts/rectangles/util/sort.js
+++ b/public/assets/javascripts/rectangles/util/sort.js
@@ -39,6 +39,7 @@
 	function room_height_tuple (r){ return [r.height, r] }
 	function room_area_tuple (r){ return [r.rect.area(), r] }
 	function rect_area_tuple (r){ return [r.area(), r] }
+	function rect_area_tuple_larger (r){ return [-r.area(), r] }
 
 	function room_rect_tuple (r){ return [r.rect, r] }
 	function identity_tuple (r){ return [r, r] }
@@ -78,7 +79,11 @@
 							 .sort(compare_car)
 							 .map(cdr)
 	}
-
+	sort.rects_by_larger_area = function (list){
+		return list.map(rect_area_tuple_larger)
+							 .sort(compare_car)
+							 .map(cdr)
+	}
 	sort.compare_z = function (a,b){
 		return a.rect.y.a < b.rect.y.a ? -1 : a.rect.y.a == b.rect.y.a ? 0 : 1
 	}
diff --git a/test/03-test-clipping.js b/test/03-test-clipping.js
index 037b5ff..20dadb3 100644
--- a/test/03-test-clipping.js
+++ b/test/03-test-clipping.js
@@ -89,6 +89,8 @@ describe('clipper', function(){
   Rooms.add_with_rect( corner )
   Rooms.add_with_rect( peninsula )
 
+/*
+  // this method uses a tree to match areas, which tends to leave extra overlapping regions
   describe('#cull_rects(rect, corner, peninsula)', function(){
     Rooms.clipper.reset_rects()
     var regions = Rooms.clipper.clip_rects()
@@ -96,10 +98,6 @@ describe('clipper', function(){
     var culled_dupes = culled.filter(function(r){ return r.dupe })
     var culled_regions = culled.filter(function(r){ return ! r.dupe })
 
-    report(culled_dupes)
-    report([])
-    report(culled_regions)
-
     it('clipper returns 16 rects', function(){
       assert.equal(16, regions.length)
     })
@@ -110,6 +108,26 @@ describe('clipper', function(){
       assert.equal(14, culled_regions.length)
     })
   })
+*/
+
+  // this method iterates to match areas, which omits regions in some cases
+  describe('#cull_rects_iterative(rect, corner, peninsula)', function(){
+    Rooms.clipper.reset_rects()
+    var regions = Rooms.clipper.clip_rects()
+    var culled = Rooms.clipper.cull_rects_iterative()
+    var culled_dupes = culled.filter(function(r){ return r.dupe })
+    var culled_regions = culled.filter(function(r){ return ! r.dupe })
+
+    it('clipper returns 16 rects', function(){
+      assert.equal(16, regions.length)
+    })
+    it('culling marks 3 duplicate', function(){
+      assert.equal(3, culled_dupes.length)
+    })
+    it('culling marks 14 non-duplicate', function(){
+      assert.equal(13, culled_regions.length)
+    })
+  })
 
 })