From c7e27b743eb8488ec71adaf365056ff500b458ab Mon Sep 17 00:00:00 2001 From: Julie Lala Date: Wed, 23 Jul 2014 17:03:04 -0400 Subject: preparing modules for clip test --- public/assets/javascripts/rectangles/util/sort.js | 156 ++++++++++++---------- 1 file changed, 83 insertions(+), 73 deletions(-) (limited to 'public/assets/javascripts/rectangles/util/sort.js') diff --git a/public/assets/javascripts/rectangles/util/sort.js b/public/assets/javascripts/rectangles/util/sort.js index a0665ae..c0b5d54 100644 --- a/public/assets/javascripts/rectangles/util/sort.js +++ b/public/assets/javascripts/rectangles/util/sort.js @@ -1,86 +1,96 @@ +(function(){ - -function compare_rect_position(a,b){ - if (a[0].x.a < b[0].x.a) { - return -1 - } - if (a[0].x.a > b[0].x.a) { - return 1 + function compare_rect_position(a,b){ + if (a[0].x.a < b[0].x.a) { + return -1 + } + if (a[0].x.a > b[0].x.a) { + return 1 + } + if (a[0].y.a < b[0].y.a) { + return -1 + } + if (a[0].y.a > b[0].y.a) { + return 1 + } + return 0 } - if (a[0].y.a < b[0].y.a) { - return -1 + + function compare_car_reversed (a,b){ + if (a[0] < b[0]) { + return 1 + } + if (a[0] > b[0]) { + return -1 + } + return 0 } - if (a[0].y.a > b[0].y.a) { - return 1 + function compare_car (a,b){ + if (a[0] < b[0]) { + return -1 + } + if (a[0] > b[0]) { + return 1 + } + return 0 } - return 0 -} -function compare_car_reversed (a,b){ - if (a[0] < b[0]) { - return 1 + function room_id_tuple (r){ return [r.id, r] } + 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 room_rect_tuple (r){ return [r.rect, r] } + function identity_tuple (r){ return [r, r] } + function car (r){ return r[0] } + function cdr (r){ return r[1] } + + var sort = {} + + sort.rooms_by_id = function (list){ + return list.map(room_id_tuple) + .sort(compare_car) + .map(cdr) } - if (a[0] > b[0]) { - return -1 + sort.rooms_by_height = function (list){ + return list.map(room_height_tuple) + .sort(compare_car_reversed) + .map(cdr) } - return 0 -} -function compare_car (a,b){ - if (a[0] < b[0]) { - return -1 + sort.rooms_by_position = function (list){ + return list.map(room_rect_tuple) + .sort(compare_rect_position) + .map(cdr) } - if (a[0] > b[0]) { - return 1 + sort.rooms_by_area = function (list){ + return list.map(room_area_tuple) + .sort(compare_car) + .map(cdr) } - return 0 -} - -function room_id_tuple (r){ return [r.id, r] } -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 room_rect_tuple (r){ return [r.rect, r] } -function identity_tuple (r){ return [r, r] } -function car (r){ return r[0] } -function cdr (r){ return r[1] } + sort.rects_by_position = function (list){ + return list.map(identity_tuple) + .sort(compare_rect_position) + .map(cdr) + } + sort.rects_by_area = function (list){ + return list.map(rect_area_tuple) + .sort(compare_car) + .map(cdr) + } -function sort_rooms_by_id(list){ - return list.map(room_id_tuple) - .sort(compare_car) - .map(cdr) -} -function sort_rooms_by_height(list){ - return list.map(room_height_tuple) - .sort(compare_car_reversed) - .map(cdr) -} -function sort_rooms_by_position(list){ - return list.map(room_rect_tuple) - .sort(compare_rect_position) - .map(cdr) -} -function sort_rooms_by_area(list){ - return list.map(room_area_tuple) - .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 + } + sort.compare_x = function (a,b){ + return a.rect.x.a > b.rect.x.a ? -1 : a.rect.x.a == b.rect.x.a ? 0 : 1 + } -function sort_rects_by_position(list){ - return list.map(identity_tuple) - .sort(compare_rect_position) - .map(cdr) -} -function sort_rects_by_area(list){ - return list.map(rect_area_tuple) - .sort(compare_car) - .map(cdr) -} + if ("window" in this) { + window.sort = sort + } + else { + module.exports = sort + } -function compare_z(a,b){ - return a.rect.y.a < b.rect.y.a ? -1 : a.rect.y.a == b.rect.y.a ? 0 : 1 -} -function compare_x(a,b){ - return a.rect.x.a > b.rect.x.a ? -1 : a.rect.x.a == b.rect.x.a ? 0 : 1 -} +})() -- cgit v1.2.3-70-g09d2 From 9261438f86b1faf22a0f8d9a366fb0daa3dd090d Mon Sep 17 00:00:00 2001 From: Jules Laplace Date: Thu, 24 Jul 2014 14:45:22 -0400 Subject: iterative culling algorithm --- .../javascripts/rectangles/engine/rooms/clipper.js | 22 +++++++++++++++++- .../assets/javascripts/rectangles/models/rect.js | 3 +++ .../assets/javascripts/rectangles/models/vec2.js | 13 +++++++++++ public/assets/javascripts/rectangles/util/sort.js | 7 +++++- test/03-test-clipping.js | 26 ++++++++++++++++++---- 5 files changed, 65 insertions(+), 6 deletions(-) (limited to 'public/assets/javascripts/rectangles/util/sort.js') 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) + }) + }) }) -- cgit v1.2.3-70-g09d2