2f:null 30:["$","title",null,{"children":"Half-edge data structure | Claudio Esperança | Observable"}] 35: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 }; }36: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 }; }37: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); } }38:[] 33:{"id":"fc3547be5a3c6f29","slug":"half-edge-data-structure","title":"Half-edge data structure","thumbnail":"58fb8eba8eb15fd6f95f4bc32dbdd2fe83aea559b8f5be0a868fb82a491a1a3e","access_level":"public","create_time":"$D2020-08-05T20:16:44.983Z","update_time":"$D2024-12-21T17:41:34.973Z","view_time":null,"first_public_time":"$D2020-08-06T22:20:29.700Z","fork":false,"stars":6,"starred":false,"owner":{"type":"team","id":"e9fcee55f21948e0","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":"starter_2024"},"version":183,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null}],"members":[{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":3,"collection":{"id":"e0d24a292dccabae","slug":"computacao-grafica","title":"Computer Graphics","owner":{"id":"e9fcee55f21948e0","login":"esperanc","name":"Claudio Esperança"}},"type":"notebook","body":{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":109,"value":"demo.canvas","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":140,"value":"md`## Demo implementation`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":65,"value":"import {planeCoords} from \"@esperanc/archimedean-tilings\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":72,"value":"import {Vec,Vector,MBR,Matrix} from \"@esperanc/2d-geometry-utils\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":77,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":182,"value":"JSON.stringify({ positions: demoMesh.positions, faces: demoMesh.faces })","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":64,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":136,"value":"md`## Implementation`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"$37","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W38","stdlib":"1","titling":"auto"}} 34:"$33:body"