31:T68b,demo = { let [w, h] = [width, Math.floor((width * 9) / 16)]; let margin = 30; let ctx = DOM.context2d(w, h, 1); let { positions, ds } = demoMesh; let { min, max } = new MBR(...positions); w -= margin * 2; h -= margin * 2; let s = Math.min(w / (max.x - min.x), h / (max.y - min.y)); let [dw, dh] = [w - (max.x - min.x) * s, h - (max.y - min.y) * s]; let modelview = Matrix.translate(dw / 2 + margin, dh / 2 + margin).mult( Matrix.scale(s, s).mult(Matrix.translate(-min.x, -min.y)) ); function draw(he) { ctx.clearRect(0, 0, ctx.canvas.width, ctx.canvas.height); ctx.fillStyle = ctx.strokeStyle = "black"; ctx.lineWidth = 1; for (let f = 0; f < ds.face.length; f++) { if (!ds.face[f]) continue; // Skip removed faces let polygon = [...ds.faceCirculator(f)].map((he) => positions[he.v]); ctx.beginPath(); let p = modelview.apply(polygon[0]); ctx.moveTo(p.x, p.y); for (let q of polygon .slice(1) .concat([polygon[0]]) .map((p) => modelview.apply(p))) ctx.lineTo(q.x, q.y); ctx.stroke(); } let q = modelview.apply(positions[he.v]); let p = modelview.apply(positions[ds.halfedge[he.twin].v]); let v = Matrix.rotate((5 * Math.PI) / 6).apply(q.sub(p).scale(0.2)); let a = q.add(v); let u = Matrix.rotate((4 * Math.PI) / 6).apply(v.scale(0.5)); let b = a.add(u); ctx.fillStyle = ctx.strokeStyle = "red"; ctx.lineWidth = 2; ctx.beginPath(); ctx.moveTo(p.x, p.y); ctx.lineTo(q.x, q.y); ctx.lineTo(a.x, a.y); ctx.lineTo(b.x, b.y); ctx.fill(); ctx.stroke(); } return { canvas: ctx.canvas, draw }; }32:T6d0,demoMesh = { let tilingFaces = [ [ [0, 0, 0, 0], [0, 0, 1, 0], [-1, 0, 1, 0] ], [ [1, 0, -1, -1], [2, 0, -1, -1], [2, 0, -1, 0], [1, 0, -1, 0] ], [ [1, 0, -1, -1], [1, 0, -1, 0], [1, -1, -1, 0] ], [ [1, 0, -1, 0], [2, 0, -1, 0], [2, 0, 0, 0], [1, 0, 1, 0], [0, 0, 1, 0], [0, 0, 0, 0] ], [ [2, 0, -1, -1], [3, 0, -1, -1], [3, 0, -1, 0], [2, 0, -1, 0] ], [ [2, 0, -1, 0], [3, 0, -1, 0], [2, 0, 0, 0] ], [ [2, 0, -1, -2], [3, 0, -1, -2], [3, 0, -1, -1], [2, 0, -1, -1] ], [ [2, 0, 0, 0], [2, 1, 0, 0], [1, 1, 1, 0], [1, 0, 1, 0] ], [ [3, 0, -1, -2], [3, 1, -1, -2], [3, 0, -1, -1] ], [ [3, 0, -1, 0], [3, 1, -1, 0], [2, 1, 0, 0], [2, 0, 0, 0] ], [ [2, 1, 0, 0], [2, 2, 0, 0], [1, 2, 1, 0], [1, 1, 1, 0] ], [ [3, 1, -1, -2], [3, 2, -1, -2], [3, 2, -1, -1], [3, 1, -1, 0], [3, 0, -1, 0], [3, 0, -1, -1] ], [ [3, 1, -1, 0], [3, 2, -1, 0], [2, 2, 0, 0], [2, 1, 0, 0] ], [ [3, 2, -1, -2], [4, 2, -1, -2], [4, 2, -1, -1], [3, 2, -1, -1] ] ]; let V = {}; let positions = [], faces = []; for (let T of tilingFaces) { let face = []; for (let L of T) { if (V[L] === undefined) { V[L] = positions.length; positions.push(planeCoords(L)); } face.push(V[L]); } faces.push(face); } return { positions, ds: HalfedgeDS.fromFaces(faces), faces }; }33:T1065,/** * A Halfedge data structure. */ class HalfedgeDS { /** * Constructor. Builds an empty data structure. */ constructor () { Object.assign(this,{halfedge : [], // Array of all halfedges vertex: [], // Array containing one halfedge per vertex face : [], // Array containing one halfedge per face border: new Set() // set of border faces }) } /** * Returns a new HalfedgeDS from a list of faces (vertex circulations) * @param {array} faceCirculations - array of arrays of indices (each index represents a vertex) */ static fromFaces(faceCirculations) { let ds = new HalfedgeDS(); let {halfedge,vertex,face,border} = ds; let edgeLookup = {}; for (let fc of faceCirculations) { let iface = face.length; let faceHe = fc.map (ivertex => { let ihalfedge = halfedge.length; let he = new Halfedge (ihalfedge, ivertex, iface); halfedge[ihalfedge] = he; if (!vertex[ivertex]) vertex[ivertex] = he; // A Halfedge for this vertex return he; }); face.push(faceHe[0]); // A halfedge for this face faceHe.forEach((he,i) => { // Link the next and prev indices he.prev = faceHe[(i+faceHe.length-1)%faceHe.length].i; he.next = faceHe[(i+faceHe.length+1)%faceHe.length].i; let vprev = halfedge[he.prev].v; let edgeKey = [vprev,he.v]; if (edgeLookup [edgeKey]) throw Error (`Edge ${edgeKey} defined twice`) edgeLookup[edgeKey] = he; let twin = edgeLookup[[he.v,vprev]]; if (twin) { // The twin of this halfedge was seen before: bind them. he.twin = twin.i; twin.twin = he.i; } }) } // Close border faces and mark them for (let circ of ds._borderCirculations()) { border.add(ds._closeBorderCirculation(circ)) } return ds; } /** * Returns an array of halfedge circulations without twins. */ _borderCirculations () { let circulations = [] let vertexLookup = new Map(); for (let he of this.halfedge) { if (he.twin === undefined) vertexLookup.set(he.v,he); } while (vertexLookup.size > 0) { let [v,he] = vertexLookup.entries().next().value; let circ = [he]; circulations.push(circ); vertexLookup.delete(v); for (;;) { let vprev = this.halfedge[he.prev].v; if (vertexLookup.has(vprev)) { he = vertexLookup.get(vprev); circ.push(he); vertexLookup.delete(vprev) } else { break; } } } return circulations } /** * Closes off a border circulation such as the ones returned by the borderCirculations() method. * A new face is then added to the data structure, whose index is returned. * Note that calling borderCirculations() again should remove this circulation from the result. * @returns the index of the closed face **/ _closeBorderCirculation(circulation) { let {halfedge,vertex,face} = this; let n = circulation.length; let iface = face.length; let faceHe = circulation.map ((he,i) => { let ihalfedge = halfedge.length; let twin = new Halfedge(ihalfedge, circulation[(i+1)%n].v,iface,undefined,undefined,he.i); he.twin = ihalfedge; halfedge.push(twin) return twin }) face.push(faceHe[0]); // A halfedge for this face faceHe.forEach((he,i) => { // Link the next and prev indices he.prev = faceHe[(i+faceHe.length-1)%faceHe.length].i; he.next = faceHe[(i+faceHe.length+1)%faceHe.length].i; }) return iface; } /** * Generates all halfedges incident on vertex ivertex **/ *vertexCirculator (ivertex) { let he = this.vertex[ivertex], start = he; do { yield he; he = this.halfedge[he.twin]; he = this.halfedge[he.prev]; } while (he != start); } /** * Generates all halfedges around face iface **/ *faceCirculator (iface) { let he = this.face[iface], start = he; do { yield he; he = this.halfedge[he.next] } while (he != start); } }34:[] 2f:{"title":"Half-edge data structure","cells":[{"id":0,"value":"md`# Half-edge data structure\n\nThis is a simplified implementation of a Half-edge data structure. It is loosely based on [CGAL's excellent implementation](https://doc.cgal.org/latest/HalfedgeDS/index.html), although considerably less ambitious.\n\n

\n\n Here I use the term 'twin' to refer to what CGAL calls the 'opposite' halfedge, influenced by [Tim Henning's implementation](https://observablehq.com/@2talltim/mesh-data-structures-traversal), which contains a very good discussion of mesh data structures. The demo below uses as example an [Archimedean tiling](https://observablehq.com/@esperanc/archimedean-tilings) containing faces that are not necessarily triangles.\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":112,"value":"{\n let ds = demoMesh.ds;\n let he = ds.halfedge[0];\n let next = html``;\n next.onclick = () => {\n he = ds.halfedge[he.next];\n demo.draw(he);\n };\n let prev = html``;\n prev.onclick = () => {\n he = ds.halfedge[he.prev];\n demo.draw(he);\n };\n let twin = html``;\n twin.onclick = () => {\n he = ds.halfedge[he.twin];\n demo.draw(he);\n };\n let join = html``;\n join.onclick = () => {\n const next = ds.halfedge[he.next];\n if (removeEdge(ds, he)) {\n he = next;\n demo.draw(he);\n } else console.log(\"fail\");\n };\n demo.draw(he);\n return html`${next}${prev}${twin}${join}`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":109,"value":"demo.canvas","pinned":false,"hidden":false,"mode":"ojs"},{"id":140,"value":"md`## Demo implementation`\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":65,"value":"import {planeCoords} from \"@esperanc/archimedean-tilings\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":72,"value":"import {Vec,Vector,MBR,Matrix} from \"@esperanc/2d-geometry-utils\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":77,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":182,"value":"JSON.stringify({ positions: demoMesh.positions, faces: demoMesh.faces })","pinned":true,"hidden":false,"mode":"ojs"},{"id":64,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":162,"value":"//\n// Euler operation that removes an edge and joins 2 adjacent faces\n//\nfunction removeEdge(hds, he) {\n const heprev = hds.halfedge[he.prev];\n const henext = hds.halfedge[he.next];\n if (!he.twin) {\n console.log(\"no twin\");\n return false;\n }\n const twin = hds.halfedge[he.twin];\n if (he.f == twin.f) {\n console.log(\"same face\");\n return false;\n }\n const twinprev = hds.halfedge[twin.prev];\n const twinnext = hds.halfedge[twin.next];\n // join the two circulations\n const twinface = twin.f;\n for (let fhe of hds.faceCirculator(twin.f)) fhe.f = he.f;\n hds.face[twinface] = null;\n twinprev.next = henext.i;\n henext.prev = twinprev.i;\n heprev.next = twinnext.i;\n twinnext.prev = heprev.i;\n hds.halfedge[he.i] = null;\n hds.halfedge[twin.i] = null;\n return true;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":136,"value":"md`## Implementation`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2,"value":"/**\n * A Halfedge.\n */\nclass Halfedge {\n /**\n * Constructor\n * @param {number} i - Index of this halfedge in the Halfedge table\n * @param {number} v - Index of the vertex this halfedge points to \n * @param {number} f - Index of the face this halfedge bounds (use -1 for a boundary edge)\n * @param {number} next - Index of the next halfedge in the face circulation\n * @param {number} prev - Index of the previous halfedge in the face circulation\n * @param {number} twin - Index of the twin halfedge \n */\n constructor (i,v,f,next,prev,twin) {\n Object.assign(this,{i,v,f,next,prev,twin})\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":11,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}