// Merge the triangles into rhombs and compute the resulting adjacencies. // This is the computationally intensive portion. rhombs = { // How close two points should be to be considered the same let tol = 0.01; // A list to hold all the rhombs let rhombs = []; // We'll do a double loop (certainly, this could benefit from a QuadTree). // i will range over all the triangles; j will range from i+1 to triangles.length // Of course, if j>i but already matches with a previous triangle, we can cross // it off our list. That's the purpose of found_indices. let found_indices = []; for (let i = 0; i < triangles.length; i++) { let Ti = triangles[i]; let found = false; for (let j = i + 1; j < triangles.length; j++) { if (found_indices.indexOf(i) == -1) { let Tj = triangles[j]; // Two type a's could join to form a skinny rhomb if (Ti.type == 'a' && Tj.type == 'a') { if ( dist1(Ti.vertices[1], Tj.vertices[1]) + dist1(Ti.vertices[2], Tj.vertices[2]) < tol ) { found_indices.push(j); rhombs.push({ type: 's', vertices: [ Ti.vertices[2], Ti.vertices[0], Ti.vertices[1], Tj.vertices[0] ] }); found = true; break; } // Two type o's could join to form a fat rhomb. } else if (Ti.type == 'o' && Tj.type == 'o') { if ( dist1(Ti.vertices[0], Tj.vertices[0]) + dist1(Ti.vertices[2], Tj.vertices[2]) < tol ) { found_indices.push(j); rhombs.push({ type: 'f', vertices: [ Ti.vertices[2], Ti.vertices[1], Ti.vertices[0], Tj.vertices[1] ] }); found = true; break; } } } else { found = true; } } // We do see some triangles on the border that would match with // triangles outside the border. if (!found) { rhombs.push(Ti); } } // Make sure that all polygons (rhombs and triangles) are positively // oriented. Should speed up adjacency testing later. rhombs.forEach(function(r, idx) { // r.idx = idx; if ( r.type == 'a' && r.vertices.filter(v => Math.abs(v[1]) < tol).length == 2 ) { r.vertices.sort().reverse(); } else if (!leftOf(...r.vertices)) { r.vertices.reverse(); if (r.type == 'a') { let vv = r.vertices; r.vertices = [vv[1], vv[2], vv[0]]; } } }); // Use symmetry to extend the tiling. Note that a few of the triangles on the // bottom edge are 1/2 of a rhomb obtained after reflection. let bottom_half_rhombs = []; let upper_rhombs = []; rhombs.forEach(function(r) { let vv = r.vertices; // The half-rhombs are type 'o' or 'a'. if (r.type == 'o' || r.type == 'a') { // and their y-coordinates of the first and third vertices are zero if (Math.abs(vv[0][1]) < tol && Math.abs(vv[2][1]) < tol) { // if (vv.filter(v => Math.abs(v[1]) < tol).length == 2) { r.vertices.sort().reverse(); r.vertices.push([vv[1][0], -vv[1][1]]); r.vertices = vv; bottom_half_rhombs.push(r); } else { // Other 'o's and 'a's are treated more easily upper_rhombs.push(r); } } else { // All the 'f's and 's's are treated more easily upper_rhombs.push(r); } }); // The upper_rhombs can simply be reflected let new_rhombs = upper_rhombs.map(function(r) { let r2 = { type: r.type }; r2.vertices = r.vertices.map(([x, y]) => [x, -y]).reverse(); return r2; }); rhombs = rhombs.concat(new_rhombs); // Compute centroids and prepare the neighborhood rhombs.forEach(function(r, idx) { r.idx = idx; let x0 = d3.mean(r.vertices.map(d => d[0])); let y0 = d3.mean(r.vertices.map(d => d[1])); r.centroid = [x0, y0]; r.neighbors = []; r.color = Math.floor(d3.randomUniform(3)()); }); // Compute adjacencies for (let i = 0; i < rhombs.length; i++) { let p1 = rhombs[i].vertices; for (let j = i + 1; j < rhombs.length; j++) { let p2 = rhombs[j].vertices; if (adjacent(p1, p2)) { rhombs[i].neighbors.push(j); rhombs[j].neighbors.push(i); } } } return rhombs; }