diff options
Diffstat (limited to 'public/assets/javascripts/rectangles/engine/shapes/regionlist.js')
| -rw-r--r-- | public/assets/javascripts/rectangles/engine/shapes/regionlist.js | 240 |
1 files changed, 240 insertions, 0 deletions
diff --git a/public/assets/javascripts/rectangles/engine/shapes/regionlist.js b/public/assets/javascripts/rectangles/engine/shapes/regionlist.js new file mode 100644 index 0000000..8c9e732 --- /dev/null +++ b/public/assets/javascripts/rectangles/engine/shapes/regionlist.js @@ -0,0 +1,240 @@ +// This algorithm takes the polylines from ShapeList as input and produces +// a set of Rooms which can be used by the existing V1 mover and editor. + +// The algorithm assumes that +// 1) all angles are orthogonal +// 2) all polylines are closed + +if (! ('window' in this) ) { + var Fiber = require("../../../vendor/bower_components/fiber/src/fiber.js") + var vec2 = require("../../models/vec2") + var Rect = require("../../models/rect") + var sort = require("../../util/sort") +} + +var RegionList = (function(){ + + var RegionList = {} + var regions = RegionList.regions + + // Build a list of regions from the existing shapes. + // Operates on all the shapes at once. + RegionList.build = function(){ + var segments = RegionList.getSortedSegments() + return RegionList.buildRoomsFromSegments(segments) + } + + // Build a list of regions from the individual shapes. + // Same, but operates on the shapes individually + RegionList.buildByShape = function(){ + var shapes = RegionList.getSortedSegmentsByShape() + var region_lists = shapes.map(function(shape){ + return RegionList.buildRoomsFromSegments(shape.segments) + }) + var regions = [] + return regions.concat.apply(regions, region_lists); + } + + RegionList.buildRoomsFromSegments = function(segments){ + + var rooms = [] + var seen_rooms = {} + var open_segments = [] + + var segment, open_segment, x_segment, y_segments, overlapped, seen_segments + + // first pass: generate rooms from the vertical segments only + for (var i = 0; i < segments.length; i++) { + segment = segments[i] + if (! segment.isVertical()) { + continue + } + + // check all the "open segments" we know about, i.e. rooms where we've only found + // the right wall. + overlapped = false + for (var j = 0; j < open_segments.length; j++) { + open_segment = open_segments[j] + + // if these two segments overlap each other, then there is a room between them. + if (segment.y.overlaps(open_segment.y)) { + overlapped = true + open_segments.splice(j--, 1) + + // the X part of the room will be the span between these two vertical segments' + // X components. the Y part of the room is the "split" or subdivision between + // the two horizontal vectors. + + // the split function is non-commutative, + // so we need to call A split B and B split A, + // then dedupe the segments we got back.. + x_segment = new vec2( open_segment.x.a, segment.x.b ) + y_segments = open_segment.y.split(segment.y, 0, 0) + + seen_segments = {} + + // check each of the splits.. if the two segments overlap, then we definitely + // have a room here. + y_segments.forEach(function(seg){ + seen_segments[ seg[0]+"" ] = true + var room = new Rect( x_segment, seg[0] ) + + if (seen_rooms[ room+"" ]) return + seen_rooms[ room+"" ] = true + + room.sides = 0 + + rooms.push(room) + var new_seg = new Rect( segment.x, seg[0] ) + open_segments.unshift(new_seg) + j++ + }) + + // splitting the other way.. + y_segments = segment.y.split(open_segment.y, 0, 0) + y_segments.forEach(function(seg){ + if (seen_segments[ seg[0]+"" ]) return; + var new_seg = new Rect( segment.x, seg[0] ) + open_segments.unshift(new_seg) + j++ + }) + } + } + + // if we have overlap, then re-sort the open segments Y-wise + // and (again) dedupe.. + if (overlapped) { + open_segments = open_segments.sort(function(a,b){ + if (a.y.a < b.y.a) { return -1 } + if (a.y.a == b.y.a) { return 0 } + if (a.y.a > b.y.a) { return 1 } + }) + + if (open_segments.length < 2) { continue } + + for (var k = 1; k < open_segments.length; k++) { + if (open_segments[k-1].y.containsVec(open_segments[k].y)) { + open_segments.splice(k--, 1) + } + else if (open_segments[k-1].y.overlaps(open_segments[k].y)) { + open_segments[k].y = open_segments[k].y.clone() + open_segments[k].y.a = open_segments[k-1].y.b + } + } + } + // if we don't have any overlap, then this is a new open segment. + else { + open_segments.push(segment) + } + } + + var splits, splitter + + // second pass: now that we have a bunch of rooms, assign sides to all of them. + // sides are used in the "mover" script to do bounds checking. + for (var i = 0; i < segments.length; i++) { + segment = segments[i] + var horizontal = segment.isHorizontal(), vertical = segment.isVertical() + for (var r = 0; r < rooms.length; r++){ + room = rooms[r] + + // vertical segments determine the left and right edges of the room, fairly simply. + if (vertical) { + if (segment.y.containsVec(room.y)) { + if (segment.x.a == room.x.a) { + room.sides |= LEFT + } + if (segment.x.a == room.x.b) { + room.sides |= RIGHT + } + } + } + + // horizontal segments determine the front and back edges of the room. + if (horizontal) { + if (segment.x.containsVec(room.x)) { + if (segment.y.a == room.y.a) { + room.sides |= FRONT + } + if (segment.y.a == room.y.b) { + room.sides |= BACK + } + } + + // however, since we did not split on horizontal segments, our rooms may + // only have partial overlap with these segments, in which case we need to + // split the rooms apart. + else if ((segment.y.a == room.y.a || segment.y.a == room.y.b) && room.x.overlaps(segment.x)) { + + // split the room across the segment. preserve whether or not we know the + // room borders a segment on the left or right. + splits = room.x.split(segment.x, room.sides & LEFT, room.sides & RIGHT) + rooms.splice(r--, 1) + for (var k = 0; k < splits.length; k++) { + splitter = splits[k] + var new_room = new Rect( splitter[0], room.y ) + new_room.sides = splitter[1] | ( room.sides & FRONT_BACK ) + if (segment.x.overlaps( splitter[0] )) { + if (segment.y.a == new_room.y.a) { + new_room.sides |= FRONT + } + if (segment.y.a == new_room.y.b) { + new_room.sides |= BACK + } + } + rooms.unshift(new_room) + r++ + } + } + + } + } + } + + return rooms + } + + // Gets a list of polylines from the ShapeList and sorts the segments. + RegionList.getSortedSegments = function(){ + // get a list of all segments from these polylines + var segments = shapes.getAllSegments() + + segments = segments.map(RegionList.segmentsToRects) + + return sort.rects_by_position(segments) + } + + RegionList.getSortedSegmentsByShape = function(){ + return shapes.getAllShapeSegments().map(function(shape){ + var segments = shape.map(RegionList.segmentsToRects) + return { + shape: shape, + segments: sort.rects_by_position(segments) + } + }) + } + + // re-orient a segment so it's either facing up or right and make it into a rect + RegionList.segmentsToRects = function(segment){ + // vertical + if (segment[0].a == segment[1].a) { + if (segment[0].b > segment[1].b) { + segment.push(segment.shift()) + } + } + // horizontal + else if (segment[0].b == segment[1].b) { + if (segment[0].a > segment[1].a) { + segment.push(segment.shift()) + } + } + return new Rect( segment[0].a, segment[0].b, segment[1].a, segment[1].b ) + } + + if (! ('window' in this) ) { + module.exports = RegionList + } + + return RegionList + +})()
\ No newline at end of file |