2e:null 2f:["$","title",null,{"children":"Minkowski sum of polygons: an elliptical pen on a Bezier curve | Theo Honohan | Observable"}] 34:T8a9,class Path { constructor(points) { this.points = points; this.current = 0; this.set_active(0); } in_range(bearing) { let range = this.active_range(); let start = range[0]; let end = range[1]; console.log("start, end, bearing: ", start, end, bearing); if ((start >= bearing && bearing >= end) || ((start <= end) && (bearing <= start)) || ((start <= end) && (bearing >= end))) return true; else return false; } active_range() { return [br(this.points[py_mod(this.current-1, this.points.length)], this.points[this.current]), br(this.points[this.current], this.points[py_mod(this.current+1, this.points.length)])]; } set_active(bearing) { while (!this.in_range(bearing)) { console.log("setting active range") this.forward() } console.log("active vertex set to:", this.current); return this.points[this.current]; } shift_active(bearing) { console.log("shift: target bearing is ", bearing, ", current active range is ", this.active_range()); if (this.in_range(bearing)) { console.log("in range"); return false; } let range = this.active_range(); let start = range[0]; let end = range[1]; if (clockwise(bearing, end)) { console.log("shifting forward"); this.forward(); } else if (!clockwise(bearing, start)) { console.log("shifting back"); this.back() } else console.log("bearing error"); return true; } slope() { return br(this.points[this.current], this.points[py_mod(this.current+1, this.points.length)]) } forward() { this.current = py_mod(this.current+1, this.points.length); } back() { this.current = py_mod(this.current-1, this.points.length); } get() { return this.points[this.current]; } at_end() { return this.current == this.points.length -1; } }35:[] 32:{"id":"8fd3f32d69a15501","slug":"minkowski-sum-of-polygons-an-elliptical-pen-on-a-bezier-curv","title":"Minkowski sum of polygons: an elliptical pen on a Bezier curve","thumbnail":"07a04a2858b6ea2323004a3bf6737329aef13c78f2becc1e4eb81e5a55210da6","access_level":"public","create_time":"$D2021-06-17T18:44:37.925Z","update_time":"$D2021-12-13T20:22:52.593Z","view_time":null,"first_public_time":"$D2021-06-17T21:22:48.921Z","has_unpublished_edits":null,"fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"5e87216687e9e987","login":"theohonohan","name":"Theo Honohan","avatar_url":"https://avatars-next.observableusercontent.com/540b56e88e996da74166cc9a7f19d675ab61466950968a722a034b91d9772da7","tier":"starter_2024"},"version":438,"publish_version":438,"role":null,"authored":false,"authors":[{"type":"individual","id":"d8b135b8c3311b20","login":"theohonohan","name":"Theo Honohan","avatar_url":"https://avatars-next.observableusercontent.com/540b56e88e996da74166cc9a7f19d675ab61466950968a722a034b91d9772da7","tier":null}],"members":[{"type":"individual","id":"d8b135b8c3311b20","login":"theohonohan","name":"Theo Honohan","avatar_url":"https://avatars-next.observableusercontent.com/540b56e88e996da74166cc9a7f19d675ab61466950968a722a034b91d9772da7","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":3,"collection":null,"type":"notebook","body":{"title":"Minkowski sum of polygons: an elliptical pen on a Bezier curve","cells":[{"id":0,"value":"# Minkowski sum of polygons: an elliptical pen on a Bezier curve","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":257,"value":"Work in progress. \n\nThe algorithm comes from this paper https://keithp.com/~keithp/talks/cairo2003.pdf and is based on ideas from the 80s, specifically the concepts of tracings and convolutions described by Guibas, Ramshaw and Stolfi in *A kinetic framework for computational geometry* (1983): https://ieeexplore.ieee.org/document/4568066. \n\nThis implementation depends on https://github.com/mattdesl/adaptive-bezier-curve and https://github.com/memononen/tess2.js.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":389,"value":"viewof angle = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":45,"value":"{\n const canvas = context.canvas;\n context.clearRect(0, 0, width, height);\n\n for (var j = 0; j < result.elements.length; j += 2) {\n let element_start = result.elements[j];\n let num_elements = result.elements[j+1];\n // console.log(\"Elements at offset: \", num_elements, element_start);\n for (var i = 0; i < num_elements; i += 1){\n if (i !== num_elements-1) {\n let vertex_offset = i*2 + element_start*2;\n drawLine(result.vertices[vertex_offset], \n result.vertices[vertex_offset+1], \n result.vertices[vertex_offset+2], \n result.vertices[vertex_offset+3]);\n } else {\n let first_offset = i*2 + element_start*2;\n let second_offset = element_start*2;\n drawLine(result.vertices[first_offset], \n result.vertices[first_offset+1], \n result.vertices[second_offset], \n result.vertices[second_offset+1]);\n }\n }\n }\n// drawPath(contour)\n return canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"function br(p1, p2) {\n // console.log(\"BR: \", p1, p2, Math.atan2(p2[1]-p1[1],p2[0]-p1[0]));\n return Math.atan2(p2[1]-p1[1],p2[0]-p1[0]);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"function point_add(p1, p2) {\n return [p1[0] + p2[0], p1[1] + p2[1]];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":"function clockwise(currentAngle, targetAngle) {\n if (targetAngle < 0)\n targetAngle += Math.PI*2;\n if (currentAngle < 0)\n currentAngle += Math.PI*2;\n if (targetAngle < currentAngle) \n targetAngle += Math.PI*2;\n\n if ((targetAngle - currentAngle) < Math.PI)\n return true;\n else \n return false;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"function py_mod(a, b) {\n return ((a%b)+b) % b;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"function convolve(shape, pen) {\n let conv = [];\n let final = false;\n let v = shape.get();\n let a = pen.set_active(shape.slope());\n\n for (let i=0; i < 9000; i++) {\n conv.push(point_add(v, a));\n\n if (pen.shift_active(shape.slope()))\n {\n console.log(\"Shifted pen\");\n a = pen.get();\n } else {\n if (final == true && shape.current == 0)\n break;\n shape.forward();\n console.log(\"moved to next shape vertex\");\n v = shape.get();\n if (shape.at_end())\n final = true;\n }\n }\n return conv;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":150,"value":"shape = new Path(c);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":46,"value":"pen = new Path(ellipse(0.6, 1.5, angle, 30));","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":68,"value":"function radians(t) {\n return(Math.PI * (t/180));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":65,"value":"function ellipse(a, b, phi, size) {\n let result = [];\n let p = radians(phi);\n a *= size;\n b *= size;\n \n for (let theta = 0; theta < 360; theta += 10) {\n let t = radians(theta);\n let x = a * Math.cos(t) * Math.cos(p) - b * Math.sin(t) * Math.sin(p);\n let y = a * Math.cos(t) * Math.sin(p) + b * Math.sin(t) * Math.cos(p);\n \n result.push([x,y]);\n }\n result.reverse();\n return result;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":401,"value":"function square(a, b, phi, size) {\n let result = [];\n let p = radians(phi);\n a *= size;\n b *= size;\n \n for (let theta = 0; theta <= 360; theta += 90) {\n let t = radians(theta);\n let x = a * Math.cos(t) * Math.cos(p) - a * Math.sin(t) * Math.sin(p);\n let y = a * Math.cos(t) * Math.sin(p) + a * Math.sin(t) * Math.cos(p);\n \n result.push([x,y]);\n }\n result.reverse();\n return result;\n}\n \n ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":54,"value":"width = 800","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":55,"value":"height = 600","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":51,"value":"context = DOM.context2d(800, 600);","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":75,"value":"contour = convolve(shape, pen);","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":223,"value":"function drawLine(x1, y1, x2, y2)\n {\n\n\n // context.clearRect(0, 0, width, height); \n // console.log(\"Drawline: \", x1, y1, \" to \", x2, y2);\n \n context.beginPath();\n context.moveTo(x1, y1);\n context.lineTo(x2, y2);\n // context.clip();\n context.stroke();\n }","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":60,"value":"function drawSegs(p) {\n for (let i = 0; i < p.length; i += 1) {\n console.log(\"drawSegs: \", p[i][0], \" to \", p[i][1]);\n context.beginPath();\n context.moveTo(p[i][0][0], p[i][0][1]);\n context.lineTo(p[i][1][0], p[i][1][1]);\n context.stroke();\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":58,"value":"function drawPath(p) {\n context.beginPath();\n context.moveTo(p[0][0], p[0][1]);\n for (let i = 1; i < p.length; i++) {\n // console.log(\"drawPath: \", x1, y1, \" to \", x2, y2);\n context.lineTo(p[i][0], p[i][1]);\n // context.clip();\n }\n // context.closePath();\n context.stroke();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":142,"value":"bezier = require('https://bundle.run/adaptive-bezier-curve@1.0.3')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":144,"value":"b = bezier([200,200],[900,500],[-400,500],[600,250]);","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":162,"value":"c = roundtrip(b);","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":157,"value":"function roundtrip(polyline) {\n let new_array = [...polyline];\n let fwd_array = [...new_array];\n new_array.reverse();\n let ret_array = fwd_array.concat(new_array.slice(1,-1));\n return ret_array;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":209,"value":"Tess2 = require('https://bundle.run/tess2@1.0.0')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":213,"value":"flatten(contour)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":216,"value":"function flatten(a) {\n let result = [];\n for(let i = 0; i < a.length; i++) {\n result.push(a[i][0], a[i][1]);\n }\n return result;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":211,"value":"result = { \n let contours = [flatten(contour)];\n\n // Tesselate\n let res = Tess2.tesselate({\n\t contours: contours,\n\t windingRule: Tess2.WINDING_NEGATIVE,\n\t elementType: Tess2.BOUNDARY_CONTOURS,\n\t polySize: 3,\n\t vertexSize: 2\n });\n\n return res;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 33:"$32:body"