30:T48f,md`To visualize a hypercube in ${tex`n \ge 2`} dimensions, we can project it into the 2-dimensional plane with orthogonal local unit vectors: ${tex.block` \begin{aligned} \mathbf{u} &\simeq \left( ${P.u.map(x=>Math.round(x*1000)/1000)} \right) \\ \mathbf{v} &\simeq \left( ${P.v.map(x=>Math.round(x*1000)/1000)} \right) \\ \end{aligned} `} with components ${tex`i=0,2,\ldots,n-1`} calculated as ${tex.block` u_i = (-1)^i \cos\left(\pi i/n\right) / \sqrt{n/2} \quad, \quad v_i = (-1)^i \sin\left(\pi i/n\right) / \sqrt{n/2} \; . `} All ${C.ndim}-dimensional points ${tex`\mathbf{x}`} on this 2-dimensional plane are now specified by two numbers ${tex`(p,q)`} as: ${tex.block` \mathbf{x} = \mathbf{a} + p\,\mathbf{u} + q\,\mathbf{v} `} where ${tex`\mathbf{a}=\left( ${d3.range(ndim).map(i=>"a_"+i)} \right)`} defines the plane's origin which we take to be the origin here. The vertices and edges in the 2-dimensional projection below are styled to show how the ${ndim}-dimensional hypercube is composed of a pair of ${ndim-1}-dimensional hypercubes (colored green and blue) that are offset along the last dimension (edges along this dimension are dotted gray lines): `31:T4f0,{ const {min,max,abs,PI} = Math; // Initialize a square drawing canvas. const [size,pad]=[500,20]; const c=DOM.context2d(size,size); // Project vertices. const V=C.vertex.map(v=>P.local(v)); // Scale canvas to the range of vertices with aspect ratio 1. const lim=max(...V.map(v=>max(...v.map(abs)))); const scale=d3.scaleLinear().domain([-lim,+lim]).range([pad,size-pad]); // Map projected vertices to canvas pixels. const XY=V.map(v=>v.map(scale)); // Label vertices based on the coordinate of their last dimension. const label=C.vertex.map(v=>v[v.length-1]<=0); // Draw projected vertices. c.strokeStyle="blue"; c.fillStyle="green"; XY.forEach(([x,y],i) => { c.beginPath(); if(label[i]) { c.arc(x, y, 6, 0, 2*PI); c.stroke(); } else { c.arc(x, y, 4, 0, 2*PI); c.fill(); } }); // Draw projected edges. C.edge.forEach(([from,to])=>{ c.beginPath(); const [x1,y1]=XY[from]; const [x2,y2]=XY[to]; c.moveTo(x1,y1); c.lineTo(x2,y2); if(label[from]==label[to]) { c.strokeStyle=label[from]?"blue":"green"; c.setLineDash([]); } else { c.strokeStyle="lightgray"; c.setLineDash([2,2]); } c.stroke(); }); return c.canvas; }32:T1c8e,class Projector { // Project n-dimensional space into the 2D plane defined above. // The dimension is determined by the length of the origin vector a. constructor(a) { const {PI,cos,sin,sqrt}=Math; this.a=a; this.ndim=a.length; this.norm=sqrt(this.ndim/2); this.arg=Array.from({length:this.ndim},(_,i)=>[(-1)**i/this.norm,PI*i/this.ndim]); this.u=this.arg.map(([s,a])=>s*cos(a)); this.v=this.arg.map(([s,a])=>s*sin(a)); } local(x) { // Calculate projected local coords [p,q] within the 2D subspace spanned by u,v. const dx=x.map((xi,i)=>xi-this.a[i]); return [dot(dx,this.u),dot(dx,this.v)]; } global(p,q) { return Array.from({length:this.ndim}, (_,i)=>this.a[i]+p*this.u[i]+q*this.v[i]); } hyperplane(i,c,s) { const {sqrt}=Math; // Return projected local coords [p,q] for the point on the line where the // hyperplane defined by x[i]=c intersects our 2D subspace, at signed distance // s from the line's closest approach from the origin. // Get coefs A,B,C of the equation of the line of intersection A p + B q = C // in the local coordinates (p,q) of our subspace. const [A,B,C]=[this.u[i],this.v[i],c-this.a[i]]; // Calculate point of closest approach on this line. const N2=A**2+B**2; const [p0,q0]=[A*C/N2,B*C/N2]; // Calculate the unit vector along the line in the positive direction. const N=sqrt(N2); const [dp,dq]=[B/N,-A/N]; // Return the point at distance s. return [p0+s*dp,q0+s*dq]; } intersection(i1,i2,c1,c2) { // Compute quantities associated with the intersection of the 2 hyperplanes // x[i1]=c1 & x[i2]=c2 with our 2D subspace. // Get coefs [A,B,C] of the equation of the line of intersection A p + B q = C // in the local coordinates (p,q) of our subspace for each hyperplane. const [A1,B1,C1]=[this.u[i1],this.v[i1],c1-this.a[i1]]; const [A2,B2,C2]=[this.u[i2],this.v[i2],c2-this.a[i2]]; // Solve for the intersection point [p,q] of the projected lines. const det=A1*B2-B1*A2; if(det==0) throw new Error("lines do not intersect"); const [p,q]=[(B2*C1-B1*C2)/det,(A1*C2-A2*C1)/det]; // Calculate the corresponding global point in ndim. const x=this.global(p,q); // Ensure that there is no round-off error on the 2 fixed components. x[i1]=c1; x[i2]=c2; return {local:[p,q], global:x}; } pairs(p1,p2,q1,q2,{pad=0,onlyVisible=true}={}) { // Calculate all intersections of pairs of hyperplanes xi=ci & xj=cj with // our 2D subspace that are visible with the local window [p1,p2]x[q1,q2]. // Calculate global coords in each corner. const corners=d3.cross([p1,p2],[q1,q2]).map(([p,q])=>this.global(p,q)); // Get range jlo <= j <= jhi] for each xi=j+1/2 hyperplane that crosses our view. const jrange=d3.transpose(corners).map(v=>d3.extent(v)) .map(([lo,hi])=>d3.range(Math.round(Math.ceil(lo-0.5))-pad,Math.round(Math.floor(hi-0.5))+pad+1)); // Loop over all possible pairwise hyperplane intersections within our view. const intersects=[]; for(let i1=0;i1p2)||(qq2)); if(onlyVisible && !visible) continue; intersects.push({ local:[p,q], global, h1:[i1,j1].toString(), h2:[i2,j2].toString(), visible:visible}); } } } } return intersects; } tiling(p1,p2,q1,q2) { const pairs=this.pairs(p1,p2,q1,q2,{pad:1,onlyVisible:false}); const vertices=new Map(); const edges=new Map(); const faces=[]; pairs.forEach(pair=>{ // Find this intersection's vertices on the integer lattice. const lattice=latticeNeighbors(pair.global); // Generate a string key for each lattice point. const keys=lattice.map(n=>n.toString()); // Update the vertex list. keys.forEach((key,k)=>{ if(vertices.has(key)) return; const [p,q]=this.local(lattice[k]); vertices.set(key,{ global:lattice[k], local:[p,q], visible:!((pp2)||(qq2)), faces:[], }); }); // Count the number of visible vertices for this rhombus. const nvisible=keys.filter(key=>vertices.get(key).visible).length; if(nvisible==0) return; // Record that this rhombus' vertices are used. const self=faces.length; keys.forEach(key=>{vertices.get(key).faces.push(self)}); pair.edges=[]; // Record this rhombus' edges. for(let i=0;i<4;i++) { let [k1,k2]=[keys[i],keys[(i+1)%4]]; if(k2{if(faces.length==0) vertices.delete(key)}); // Identify the faces adjacent to each face. faces.forEach((face,i)=>{ face.adjacent=[]; face.edges.forEach(ekey=>{ const efaces=edges.get(ekey).faces; if(efaces.length == 1) { if(efaces[0] != i) throw new Error('???'); face.adjacent.push(-1); } else if(efaces.length == 2) { if(efaces[0]==i) face.adjacent.push(efaces[1]); else if(efaces[1]==i) face.adjacent.push(efaces[0]); else throw new Error('!!!'); } else { throw new Error('!?!'); } }); }); // Use a greedy algorithm to assign a color label to each face. let [lastColor,maxColors]=[0,5]; faces.forEach(face=>{ const neighborColors=face.adjacent.filter(i=>i>=0).map(i=>faces[i].color); for(let colorOffset=0;colorOffsetc==face.color).length==0) break; } lastColor=face.color; }); return {vertices:vertices, edges:edges, faces:faces}; } lattice(p1,p2,q1,q2) { const pairs=this.pairs(p1,p2,q1,q2); const pts=pairs.map(({global:x})=>latticeNeighbors(x)).flat(); const unique=new Set(pts.map(p=>p.toString())); return new Map([...unique].map(key=>{ const global=JSON.parse("["+key+"]"); const local=this.local(global); return [key,{local:local, global:global}]; })); } }33:[] 2e:{"title":"Hypercubes","cells":[{"id":325,"value":"md`# Hypercubes\n\nA *hypercube* is the generalization of a 2-dimensional square and 3-dimensional cube to an arbitrary number of dimensions ${tex`n`}:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":126,"value":"viewof ndim=Inputs.range([2,9], {value:3, step:1, label:\"Dimension:\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":181,"value":"md`The ${ndim}-dimensional hypercube has ${C.vertex.length} vertices, ${C.edge.length} edges and ${C.face.length} faces. A hypercube whose vertex coordinates are all ${tex`\\pm 1`} is centered on the origin (you may need to scroll down to see all ${C.vertex.length} vertices):`","pinned":false,"hidden":false,"mode":"ojs"},{"id":348,"value":"{\n const vtable=C.vertex.map(v=>Object.fromEntries(v.map((x,i)=>[\"x\"+i,x])));\n return Inputs.table(vtable, {width:50*ndim});\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":380,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":433,"value":"Inputs.bind(Inputs.range([2,9], {label:\"Dimension:\"}), viewof ndim)","pinned":false,"hidden":false,"mode":"ojs"},{"id":107,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":452,"value":"md`The ${C.face.length} faces of a ${ndim}-dimensional hypercube consist of 4 vertices\n${tex`\\mathbf{z}_0,\\mathbf{z}_1,\\mathbf{z}_2,\\mathbf{z}_3`} connected by four edges:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":130,"value":"viewof faceIndex=Inputs.range([0,C.face.length-1],{value:0, step:1, label:\"Face index:\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":457,"value":"tex.block`\n \\begin{aligned}\n \\mathbf{z}_0 &= \\left( ${C.vertex[C.face[faceIndex][0]]} \\right) \\quad &, \\quad\n \\mathbf{z}_1 &= \\left( ${C.vertex[C.face[faceIndex][1]]} \\right) \\\\\n \\mathbf{z}_2 &= \\left( ${C.vertex[C.face[faceIndex][2]]} \\right) \\quad &, \\quad\n \\mathbf{z}_3 &= \\left( ${C.vertex[C.face[faceIndex][3]]} \\right) \\\\\n \\end{aligned}\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":490,"value":"md`When projected into the same plane, each face appears as a rhombus, shown in red below. Use the slider above to display different faces and note how there are only a few different rhombus shapes:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":493,"value":"{\n const {min,max,abs,PI} = Math;\n // Initialize a square drawing canvas.\n const [size,pad]=[500,20];\n const c=DOM.context2d(size,size);\n // Project vertices.\n const V=C.vertex.map(v=>P.local(v));\n // Scale canvas to the range of vertices with aspect ratio 1.\n const lim=max(...V.map(v=>max(...v.map(abs))));\n const scale=d3.scaleLinear().domain([-lim,+lim]).range([pad,size-pad]);\n // Map projected vertices to canvas pixels.\n const XY=V.map(v=>v.map(scale));\n // Draw projected edges.\n c.strokeStyle=\"lightgray\";\n C.edge.forEach(([from,to])=>{\n c.beginPath();\n const [x1,y1]=XY[from];\n const [x2,y2]=XY[to];\n c.moveTo(x1,y1);\n c.lineTo(x2,y2);\n c.stroke();\n });\n c.setLineDash([]);\n // Draw the selected face in projection.\n c.fillStyle=c.strokeStyle=\"red\";\n const faceVertices=C.face[faceIndex].map(i => XY[i]);\n c.beginPath();\n c.moveTo(...faceVertices[faceVertices.length-1]);\n faceVertices.forEach(v=>c.lineTo(...v));\n c.globalAlpha=0.5, c.fill();\n return c.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":508,"value":"Inputs.bind(Inputs.range([2,9], {label:\"Dimension:\"}), viewof ndim)","pinned":false,"hidden":false,"mode":"ojs"},{"id":88,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs"},{"id":289,"value":"P=new Projector(Array.from({length:ndim},()=>0))","pinned":false,"hidden":false,"mode":"ojs"},{"id":8,"value":"C = hypercube({ndim:ndim})","pinned":false,"hidden":false,"mode":"ojs"},{"id":521,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs"},{"id":250,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":565,"value":"latticeNeighbors=function(x) {\n // Find all points (n1,n2,...) on the integer lattice with |xi-ni| <= 1/2.\n // The number of such points is 2^N where N is the number of half-integer coordinates xi.\n const {abs,floor,ceil,round}=Math;\n const lattice=[];\n x.forEach(xi=>{\n if(abs(xi%1)==0.5) {\n // xi is exactly half way between two lattice points so we include them both.\n lattice.push([floor(xi),ceil(xi)]);\n }\n else {\n lattice.push([round(xi)]);\n }\n });\n let neighbors=d3.cross(...lattice);\n // If we have exactly 4 neighbors, order them so they can be filled.\n if(neighbors.length==4) neighbors=[neighbors[0],neighbors[1],neighbors[3],neighbors[2]];\n return neighbors;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":95,"value":"dot = (a,b) => a.reduce((dprod, ai, i) => dprod+ai*b[i],0)","pinned":false,"hidden":false,"mode":"ojs"},{"id":6,"value":"hypercube = function({lo=-1, hi=1, ndim=2}={}) {\n // Start with a 1D hypercube (line segment).\n let geom = { ndim:1, vertex: [[lo],[hi]], edge: [[0,1]], face: [] };\n // Recursively lift it into higher dimensions.\n const lift = ({ndim:n,vertex,edge,face}) => {\n const nv=vertex.length;\n face.slice().forEach(([v1,v2,v3,v4]) => face.push([v4+nv,v3+nv,v2+nv,v1+nv]));\n edge.slice().forEach(([from,to],i) => {\n edge.push([from+nv,to+nv]);\n face.push([from,to,to+nv,from+nv]);\n });\n vertex.slice().forEach((p,i) => {\n const newvtx = p.slice();\n newvtx.splice(n, 0, hi);\n vertex.push(newvtx);\n vertex[i].splice(n, 0, lo);\n edge.push([i,i+nv]);\n });\n return {ndim:n+1, vertex:vertex, edge:edge, face:face};\n };\n while(--ndim) geom = lift(geom);\n return geom;\n}","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}