class Tiling { constructor(n, face_placements) { this.n = n; this.placements_to_do = face_placements; this.tile_faces = []; this.points_array = [[]]; this.lines_array = [[]]; // dictionary of bearing to following vertex this.bearing_vertices = {}; for (let index = 0; index < 2 * this.n; index++) { this.vertices[index] = new Vertex(n, index); } // dictionary of bearing to it's edge this.bearing_edges = []; for (let index = 0; index < 2 * this.n; index++) { this.edges[index] = new Edge(n, index); } // set of tiles which haven't been placed yet this.unplaced_tiles = [] for (var i = 0; i < n; i++) { for (var j = i+1; j < n; j++) { this.unplaced_tiles.push(new Tile(this.n, i, j)); } } // dictionary from bearing to it's open line this.bearing_open_lines = [{}] for (var bearing in this.edges) { var edge = this.edges[bearing]; this.bearing_open_lines.slice(-1)[0][bearing] = new Line(this.n, edge.start, edge.end, bearing % this.n, bearing >= this.n ? this.n - 1 : 0, true); }; // which bearings are still available and adjacent this.bearing_cycle = [new BearingCycle(n)] // fill the placements_to_do into their correct places while (this.placements_to_do.length > 0) { var placement = this.placements_to_do.shift(); this.add_placement(placement); } } toString() { return "Tiling(" + this.n + ", " + this.bearing_cycle.slice(-1)[0].join(",") + ")"; } get blueprint() { return { n: this.n, placements: this.tile_faces.map(f => [f.placement.bearing_1, f.placement.bearing_2]) } } get vertices() { return this.bearing_vertices; } get points() { return this.points_array.slice(-1)[0]; } get edges() { return this.bearing_edges; } get lines() { return this.lines_array.slice(-1)[0]; } get faces() { return this.tile_faces; } get curves() { var curves = {} for (let index = 0; index < this.bearing_open_lines.length; index++) { const bearing_lines = this.bearing_open_lines[index]; for (var bearing in bearing_lines) { if (bearing_lines.hasOwnProperty(bearing)) { var line = bearing_lines[bearing] if (!curves.hasOwnProperty(bearing)) { curves[bearing] = [] } var centre_x = (line.start.x + line.end.x)/2 var centre_y = (line.start.y + line.end.y)/2 var previous_point = curves[bearing].slice(-1)[0] if (previous_point == null || centre_x != previous_point.x || centre_y != previous_point.y) { curves[bearing].push(new Point(centre_x, centre_y)) } } } } return curves; } bearing_shapes(x_scale, y_scale, edge_colour_type, edge_colour_base) { var bearing_shapes = []; for (var bearing in this.curves) { bearing = parseInt(bearing); if (this.curves.hasOwnProperty(bearing)) { var points = this.curves[bearing] if (points.length < 2) { continue; } var shape = "M " + [x_scale(points[0].x), y_scale(points[0].y)].join(",") for (let index = 1; index < points.length; index++) { const prev = points[index-1]; const next = points[index]; const centre_x = (prev.x + next.x) / 2 const centre_y = (prev.y + next.y) / 2 // shape += " T " + [x_scale(centre_x), y_scale(centre_y)].join(",") // shape += " T " + [x_scale(next.x), y_scale(next.y)].join(",") // shape += " C " + [x_scale(centre_x), y_scale(centre_y)].join(" ") + ", " + [x_scale(centre_x), y_scale(centre_y)].join(" ") + ", " + [x_scale(next.x), y_scale(next.y)].join(" ") // shape += " S " + [x_scale(centre_x), y_scale(centre_y)].join(" ") + ", " + [x_scale(next.x), y_scale(next.y)].join(" ") var prev_target = get_perpendicular(prev, next, bearing, this.n); var next_target = get_perpendicular(next, prev, (bearing + this.n) % (2 * this.n), this.n); prev_target = new Point(prev.x + prev_target.x/2, prev.y + prev_target.y/2) next_target = new Point(next.x + next_target.x/2, next.y + next_target.y/2) shape += " C " + [x_scale(prev_target.x), y_scale(prev_target.y)].join(" ") + ", " + [x_scale(next_target.x), y_scale(next_target.y)].join(" ") + ", " + [x_scale(next.x), y_scale(next.y)].join(" ") } var angle = Math.PI * (((bearing/this.n) + 1) % 2); var normal = new Point(Math.cos(angle), Math.sin(angle)); var prev_target = new Point(points[0].x + normal.x/100, points[0].y + normal.y/100) var collapsed_shape = "M " + [x_scale(points[0].x), y_scale(points[0].y)].join(",") + " L " + [x_scale(prev_target.x), y_scale(prev_target.y)].join(" ") bearing_shapes.push({ bearing: bearing, points: points, shape: shape, collapsed_shape: collapsed_shape, colour: orientation_colour(bearing % this.n, this.n, edge_colour_type, edge_colour_base), key: bearing }) } } return bearing_shapes; } get placement_hash() { return md5.hash(this.faces.map(d => d.placement).map(d => String(d.bearing_1) + "," + String(d.bearing_2)).join('|')) } get unplaced_table() { var face_table = {}; for (let index = 0; index < this.unplaced_tiles.length; index++) { const tile = this.unplaced_tiles[index]; var start_1 = new Vertex(this.n, tile.orientation_1 - 1); var end_1 = new Vertex(this.n, tile.orientation_1); var delta_1 = new Point(end_1.x - start_1.x, end_1.y - start_1.y); var start_2 = new Vertex(this.n, tile.orientation_2 - 1); var end_2 = new Vertex(this.n, tile.orientation_2); var delta_2 = new Point(end_2.x - start_2.x, end_2.y - start_2.y); var centre = new Point((delta_1.x + delta_2.x)/2, (delta_1.y + delta_2.y)/2) var points = [ new Point(0 - centre.x, 0 - centre.y), new Point(delta_1.x - centre.x, delta_1.y - centre.y), new Point(delta_1.x + delta_2.x - centre.x, delta_1.y + delta_2.y - centre.y), new Point(delta_2.x - centre.x, delta_2.y - centre.y) ] var face = new Face(this.n, new Placement(this.n, tile.orientation_1, tile.orientation_2), points, false) face_table[[tile.orientation_1, tile.orientation_2]] = face } return face_table } get unplaced_table_edges() { var face_edges = []; for (let index = 0; index < this.unplaced_tiles.length; index++) { const tile = this.unplaced_tiles[index]; var start_1 = new Vertex(this.n, tile.orientation_1 - 1); var end_1 = new Vertex(this.n, tile.orientation_1); var delta_1 = new Point(end_1.x - start_1.x, end_1.y - start_1.y); var start_2 = new Vertex(this.n, tile.orientation_2 - 1); var end_2 = new Vertex(this.n, tile.orientation_2); var delta_2 = new Point(end_2.x - start_2.x, end_2.y - start_2.y); var centre = new Point((delta_1.x + delta_2.x)/2, (delta_1.y + delta_2.y)/2) face_edges.push(new Line(this.n, new Point(delta_1.x + delta_2.x - centre.x, delta_1.y + delta_2.y - centre.y), new Point(delta_2.x - centre.x, delta_2.y - centre.y), tile.orientation_1, tile.orientation_2, false)) face_edges.push(new Line(this.n, new Point(0 - centre.x, 0 - centre.y), new Point(delta_2.x - centre.x, delta_2.y - centre.y), tile.orientation_2, tile.orientation_1, false)) } return face_edges } add_placement(placement) { // console.log(placement) var already_placed = true; for (let index = 0; index < this.unplaced_tiles.length; index++) { const tile = this.unplaced_tiles[index]; if ((tile.orientation_1 == placement.tile.orientation_1 && tile.orientation_2 == placement.tile.orientation_2) || (tile.orientation_1 == placement.tile.orientation_2 && tile.orientation_2 == placement.tile.orientation_1)) { already_placed = false; } } if (already_placed) { // console.log('invalid tiling: ' + placement + 'already used'); // console.log(this.unplaced_tiles) // throw EvalError return null } // append new data structures this.bearing_open_lines.push(clone(this.bearing_open_lines.slice(-1)[0])); this.points_array.push(clone(this.points_array.slice(-1)[0])); this.lines_array.push(clone(this.lines_array.slice(-1)[0])); this.bearing_cycle.push(clone(this.bearing_cycle.slice(-1)[0])); // create face and apply data changes try { this.bearing_cycle.slice(-1)[0].apply_placement(placement) } catch (e) { this.bearing_open_lines = this.bearing_open_lines.slice(0, -1); this.points_array = this.points_array.slice(0, -1); this.lines_array = this.lines_array.slice(0, -1); this.bearing_cycle = this.bearing_cycle.slice(0, -1); return null } var line_1 = this.bearing_open_lines.slice(-1)[0][placement.bearing_1] var line_2 = this.bearing_open_lines.slice(-1)[0][placement.bearing_2] var points = get_points_from_lines(line_1, line_2) var face = new Face(this.n, placement, points) this.tile_faces.push(face); points[3].key = this.placement_hash; this.points_array.slice(-1)[0].push(points[3]); var bearing_1_offset_x = points[2].x - points[1].x var bearing_1_offset_y = points[2].y - points[1].y var bearing_2_offset_x = points[0].x - points[1].x var bearing_2_offset_y = points[0].y - points[1].y var start_1 = new Point(this.bearing_open_lines.slice(-1)[0][placement.bearing_1].start.x + bearing_1_offset_x, this.bearing_open_lines.slice(-1)[0][placement.bearing_1].start.y + bearing_1_offset_y) var end_1 = new Point(this.bearing_open_lines.slice(-1)[0][placement.bearing_1].end.x + bearing_1_offset_x, this.bearing_open_lines.slice(-1)[0][placement.bearing_1].end.y + bearing_1_offset_y) var line_1 = new Line(this.n, start_1, end_1, placement.bearing_1 % this.n, this.bearing_open_lines.slice(-1)[0][placement.bearing_1].step + (placement.bearing_1 >= this.n ? -1 : 1), true) this.bearing_open_lines.slice(-1)[0][placement.bearing_1] = line_1 var opposing_line = this.bearing_open_lines.slice(-1)[0][(placement.bearing_1 + this.n) % (2*this.n)] if ((Math.abs(opposing_line.start.x - line_1.start.x) < 2 ** -32 && Math.abs(opposing_line.start.y - line_1.start.y) < 2 ** -32 && Math.abs(opposing_line.end.x - line_1.end.x) < 2 ** -32 && Math.abs(opposing_line.end.y - line_1.end.y) < 2 ** -32) || (Math.abs(opposing_line.start.x - line_1.end.x) < 2 ** -32 && Math.abs(opposing_line.start.y - line_1.end.y) < 2 ** -32 && Math.abs(opposing_line.end.x - line_1.start.x) < 2 ** -32 && Math.abs(opposing_line.end.y - line_1.start.y) < 2 ** -32)) { } else { this.lines_array.slice(-1)[0].push(line_1) } var start_2 = new Point(this.bearing_open_lines.slice(-1)[0][placement.bearing_2].start.x + bearing_2_offset_x, this.bearing_open_lines.slice(-1)[0][placement.bearing_2].start.y + bearing_2_offset_y) var end_2 = new Point(this.bearing_open_lines.slice(-1)[0][placement.bearing_2].end.x + bearing_2_offset_x, this.bearing_open_lines.slice(-1)[0][placement.bearing_2].end.y + bearing_2_offset_y) var line_2 = new Line(this.n, start_2, end_2, placement.bearing_2 % this.n, this.bearing_open_lines.slice(-1)[0][placement.bearing_2].step + (placement.bearing_2 >= this.n ? -1 : 1), true) this.bearing_open_lines.slice(-1)[0][placement.bearing_2] = line_2 var opposing_line = this.bearing_open_lines.slice(-1)[0][(placement.bearing_2 + this.n) % (2*this.n)] if ((Math.abs(opposing_line.start.x - line_2.start.x) < 2 ** -32 && Math.abs(opposing_line.start.y - line_2.start.y) < 2 ** -32 && Math.abs(opposing_line.end.x - line_2.end.x) < 2 ** -32 && Math.abs(opposing_line.end.y - line_2.end.y) < 2 ** -32) || (Math.abs(opposing_line.start.x - line_2.end.x) < 2 ** -32 && Math.abs(opposing_line.start.y - line_2.end.y) < 2 ** -32 && Math.abs(opposing_line.end.x - line_2.start.x) < 2 ** -32 && Math.abs(opposing_line.end.y - line_2.start.y) < 2 ** -32)) { } else { this.lines_array.slice(-1)[0].push(line_2) } for (let index = 0; index < this.unplaced_tiles.length; index++) { const tile = this.unplaced_tiles[index]; if (tile.orientation_1 == placement.tile.orientation_1 && tile.orientation_2 == placement.tile.orientation_2) { var found_index = index } } this.unplaced_tiles.splice(found_index, 1) return face } add_random_placement() { var already_placed = []; this.tile_faces.forEach(face => { already_placed.push(face.placement) }); var placement = this.bearing_cycle.slice(-1)[0].get_valid_placement(already_placed) if (placement == null) { return null } this.add_placement(placement) return this } remove_last_placement() { var lost_face = this.tile_faces.splice(this.tile_faces.length - 1)[0]; this.unplaced_tiles.push(lost_face.placement.tile) this.bearing_open_lines = this.bearing_open_lines.slice(0, -1); this.points_array = this.points_array.slice(0, -1); this.lines_array = this.lines_array.slice(0, -1); this.bearing_cycle = this.bearing_cycle.slice(0, -1); return this // // fill the placements_to_do into their correct places // while (this.placements_to_do.length > 0) { // var placement = this.placements_to_do.shift(); // this.add_placement(placement); // } // var new_placements = [] // for (let index = 0; index < this.faces.length - 1; index++) { // const face = this.faces[index]; // new_placements.push(face.placement) // } // return new Tiling(this.n, new_placements); } remove_tile(tile) { var new_placements = []; var bearings_found = new Set(); for (let index = 0; index < this.faces.length; index++) { const face = this.faces[index]; var face_tile = face.placement.tile; if ((face_tile.orientation_1 == tile.orientation_1 && face_tile.orientation_2 == tile.orientation_2) || (face_tile.orientation_1 == tile.orientation_2 && face_tile.orientation_2 == tile.orientation_1)) { bearings_found.add(face.placement.bearing_1); bearings_found.add(face.placement.bearing_2); } else { if (bearings_found.has(face.placement.bearing_1) || bearings_found.has(face.placement.bearing_2)) { console.log("skipping placement") console.log(face.placement) bearings_found.add(face.placement.bearing_1); bearings_found.add(face.placement.bearing_2); } else { new_placements.push(face.placement); } } } console.log("removed single tile") console.log(new_placements.map(p => "[" + p.bearing_1 + ',' + p.bearing_2 + "]").join(", ")) return new Tiling(this.n, new_placements); } decrease_n(new_n) { var difference = this.n - new_n; var remove_orientations = new Set() for (let remove_n = this.n - 1; remove_n > this.n - 1 - difference; remove_n--) { remove_orientations.add(remove_n); } var new_placements = [] this.tile_faces.forEach(face => { var placement = face.placement; if (remove_orientations.has(placement.bearing_1 % this.n) || remove_orientations.has(placement.bearing_2 % this.n)) { } else { var bearing_1 = placement.bearing_1 >= this.n ? placement.bearing_1 - difference : placement.bearing_1; var bearing_2 = placement.bearing_2 >= this.n ? placement.bearing_2 - difference : placement.bearing_2; var new_placement = new Placement(new_n, bearing_1, bearing_2); new_placements.push(new_placement) } }); return new Tiling(new_n, new_placements); } increase_n(new_n) { var difference = new_n - this.n; var new_placements = [] for (let step_n = new_n; step_n >= this.n + 1; step_n--) { for (let index = step_n; index < (2*step_n) - 1; index++) { var new_placement = new Placement(new_n, step_n-1, index % (2*step_n) + new_n - step_n) new_placements.push(new_placement); } } this.tile_faces.forEach(face => { var placement = face.placement; var bearing_1 = placement.bearing_1 >= this.n ? placement.bearing_1 + difference : placement.bearing_1; var bearing_2 = placement.bearing_2 >= this.n ? placement.bearing_2 + difference : placement.bearing_2; var new_placement = new Placement(new_n, bearing_1, bearing_2); new_placements.push(new_placement) }); return new Tiling(new_n, new_placements); } update_n(n) { n = parseInt(n); if (this.n < n) { return this.increase_n(n); } else { return this.decrease_n(n); } } }