2d:null 2e:["$","title",null,{"children":"Geometry Operations | John Boiles | Observable"}] 33:T433,// Detects and removes polygon lines that have flipped direction as an artifact of shrinking the polygon // TODO: This works ok for the first set of lines that invert, but not so great once the new corrected lines also themselves invert. removePolygonArtifacts = function(originalPolygon, newPolygon) { var originalLines = polygonToLines(originalPolygon); var originalLineAngles = originalLines.map(function(val){ return geometric.lineAngle(val); }); var newLines = polygonToLines(newPolygon); var newLineAngles = newLines.map(function(val){ return geometric.lineAngle(val); }); let correctedLines = [] // Process all the lines and if their slope changed, then remove it for (let i = 0; i < originalLines.length; i++) { const angleDiff = 180 - Math.abs(Math.abs(originalLineAngles[i] - newLineAngles[i]) - 180); if (angleDiff < 90) { correctedLines.push(newLines[i]); } } if (correctedLines.length != originalLines.length) { return intersectingLinesToPolygon(correctedLines); } else { return newPolygon; } }34:T6e5,// Detects and removes polygon points that are going the wrong way around the centroid as an artifact of shrinking the polygon removePolygonArtifacts2 = function(polygon, centroid) { // Remove the duplicated final point for easier processing let p = polygon.slice(0, polygon.length - 1); for (let i = 0; i < p.length; i++) { // Caluclate the angle difference between two points const p1 = p[i]; const p2 = p[(i+1)%p.length]; const a1 = geometric.lineAngle([centroid, p1]); const a2 = geometric.lineAngle([centroid, p2]); let angleDiff = a2-a1; if (angleDiff < 0) { angleDiff += 360; } // Detect any points not moving clockwise around the centroid // TODO: Assumes the points are clockwise to begin with if (angleDiff < 0 || angleDiff > 180) { // For any two points not moving clockwise, replace those two points with a more suitable intersection point based on the surrounding lines const line1 = [p[(i-1+p.length)%p.length], p1] const line2 = [p2, p[(i+2)%p.length]]; const intersect = intersection(line1, line2); if (isNaN(intersect[0]) || isNaN(intersect[1])) { console.log("Uh-oh got a bad intersection point", intersect); } // TODO: This is annoyingly complex. Probably a better programmer could make this simpler // Move backwards and reprocess the last few points to see if the intersection point needs to be changed as well if (i + 1 >= p.length) { p.splice((i+1)%p.length, 1); p.splice(i-1, 1, intersect); i = Math.max(0, i - 3); } else { p.splice((i+1)%p.length, 1); p.splice(i, 1, intersect); i = Math.max(0, i - 2); } } } p.unshift(p[p.length-1]); return p; }35:T4c2,function polygonInsetStroke(polygon, inset, fixArtifacts=false){ const lines = polygonToLines(polygon); const centroid = geometric.polygonCentroid(polygon); // Inset every line in the polygon var insetLines = [] for (let i = 0, l = lines.length; i < l; i++) { const line = lines[i]; const a = geometric.lineAngle(line); // I think this 90deg constant here makes the assumption that the polygon is clockwise const angleOffset = 90; // Determine a maximum inset based on the distance of the line to the centroid let dist = distancePointToLine(centroid, line) - 0.5 const clampedInset = inset > dist ? dist : inset; const p1new = geometric.pointTranslate(line[0], a + angleOffset, clampedInset); const p2new = geometric.pointTranslate(line[1], a + angleOffset, clampedInset); insetLines.push([p1new, p2new]); } var newPolygon = intersectingLinesToPolygon(insetLines); if (fixArtifacts) { // newPolygon = removePolygonArtifacts(polygon, newPolygon); newPolygon = removePolygonArtifacts2(newPolygon, centroid); if (isPolygonFunky(newPolygon, centroid)) { console.log("Uh-oh bad polygon", polygon, newPolygon); } } return newPolygon; }36:T7a4,// Visual test for polygonInsetStroke { const height = 300; const svg = d3.select(DOM.svg(width, height)); let points = [[115, 170], [100, 150], [130, 70], [150, 140], [120, 170], [115, 170]]; // let points = [[259.868, 195.45], [257.617, 132.058], [254.26, 194.401], [254.839, 194.083] [259.868, 195.45]]; // let points = [[404.867, 193.167], [408.141, 194.688], [392.365, 20.7389], [400.271, 195.794], [404.867, 193.167]]; // let points = [[272.8840664953974, 73.68592247094621], [271.4619475357335, 68.29058373145506], [273.7222227008603, 65.58813264863636], [279.79451433559007, 65.96787602087589], [280.1703947971889, 72.79913116506853], [274.6042130576127, 74.44806074042489], [272.8840664953974, 73.68592247094621]] // let points = [[168.82349659950347, 194.191428400823], [168.8094571282144, 200], [156.9766268961122, 200], [156.94557794695822, 193.3487155948099], [161.00222359929654, 189.70575992637566], [168.82349659950347, 194.191428400823]]; // let points = [[317.9807834279534, 12.190921790172993], [318.1112638446458, 2], [333.05929746343264, 2], [331.7517533740246, 15.548149909076693], [330.1714197946596, 16.29588660479166], [317.9807834279534, 12.190921790172993]]; // Draw centroid const centroid = geometric.polygonCentroid(points); svg.append("circle") .attr("fill", "#0F0") .attr("cx", centroid[0]) .attr("cy", centroid[1]) .attr("r", 2); var flat = points.reduce((acc, cur) => { return acc.concat(cur); }, []); let path = svg.append("path") .attr("fill", "none") .attr("stroke", "#ccc") .attr("stroke-width", 1) .attr("d", `M${flat.join(',')}`); var newPoints = polygonInsetStroke(points, inset, true); flat = newPoints.reduce((acc, cur) => { return acc.concat(cur); }, []); path = svg.append("path") .attr("fill", "none") .attr("stroke", "#F00") .attr("stroke-width", 1) .attr("d", `M${flat.join(',')}`); return svg.node(); }37:[] 31:{"id":"980334a917abac79","slug":"geometry-operations","title":"Geometry Operations","thumbnail":"49e3b8e7b5c25c76853ac31b4ed41e895e2facb91573182f4e68e995d0ccb899","access_level":"public","create_time":"$D2020-02-10T05:18:05.631Z","update_time":"$D2020-02-11T23:19:56.134Z","view_time":null,"first_public_time":"$D2020-02-10T05:24:05.677Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"38577e937a1cf9d2","login":"johnboiles","name":"John Boiles","avatar_url":"https://avatars-next.observableusercontent.com/5219c8798434a4e6a48cbd828f95274a6482d0a2cf45690520bf2a67fe7e5d64","tier":"starter_2024"},"version":421,"publish_version":421,"role":null,"authored":false,"authors":[{"type":"individual","id":"438e30968a321daa","login":"johnboiles","name":"John Boiles","avatar_url":"https://avatars-next.observableusercontent.com/5219c8798434a4e6a48cbd828f95274a6482d0a2cf45690520bf2a67fe7e5d64","tier":null}],"members":[{"type":"individual","id":"438e30968a321daa","login":"johnboiles","name":"John Boiles","avatar_url":"https://avatars-next.observableusercontent.com/5219c8798434a4e6a48cbd828f95274a6482d0a2cf45690520bf2a67fe7e5d64","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Geometry Operations","cells":[{"id":0,"value":"md`# Geometry Operations\n\nMiscellaneous geometry operations for use in [@johnboiles/voronoi-stippling](https://observablehq.com/@johnboiles/voronoi-stippling)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"geometric = require('geometric');","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"// Finds the intersection point of two lines\nfunction intersection(line1, line2){\n const a = line1[0];\n const b = line1[1];\n const c = line2[0];\n const d = line2[1];\n const det = (a[0] - b[0])*(c[1] - d[1]) - (a[1] - b[1])*(c[0] - d[0]),\n l = a[0]*b[1] - a[1]*b[0],\n m = c[0]*d[1] - c[1]*d[0],\n ix = (l*(c[0] - d[0]) - m*(a[0] - b[0])) / det,\n iy = (l*(c[1] - d[1]) - m*(a[1] - b[1])) / det\n\n return [ix, iy];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":105,"value":"// Takes an array of points representing a polygon and returns an array of lines representing their faces\npolygonToLines = function(polygon) {\n var lines = [];\n for (let i = 0, l = polygon.length; i < l - 1; i++) {\n const p1 = polygon[i];\n const p2 = polygon[i+1];\n lines.push([p1, p2]);\n }\n return lines;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":116,"value":"// Takes an array of intersecting lines and returns an array of points representing a polygon\nintersectingLinesToPolygon = function(lines) {\n var newPolygon = []\n // Intersect every inset line to find the new points\n for (let i = 0, l = lines.length; i < l; i++) {\n const line1 = lines[i];\n const line2 = lines[(i+1)%l];\n const intersect = intersection(line1, line2);\n if (isNaN(intersect[0]) || isNaN(intersect[1])) {\n console.log(\"Uh-oh got a bad intersection point\", intersect, \"on lines\", lines);\n }\n newPolygon.push(intersect);\n }\n // Close the polygon\n newPolygon.unshift(newPolygon[newPolygon.length-1]);\n return newPolygon;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":124,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":249,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":319,"value":"// Based on https://stackoverflow.com/a/1501725/163827\ndistancePointToLine = function (point, line) { \n let sqr = function(x) { return x * x }\n let dist2 = function(v, w) {\n return sqr(v[0] - w[0]) + sqr(v[1] - w[1]) \n }\n let distancePointToLineSquared = function(point, line) {\n let p = point;\n let v = line[0];\n let w = line[1];\n var l2 = dist2(v, w);\n if (l2 == 0) {\n return dist2(p, v);\n }\n var t = ((p[0] - v[0]) * (w[0] - v[0]) + (p[1] - v[1]) * (w[1] - v[1])) / l2;\n t = Math.max(0, Math.min(1, t));\n return dist2(\n p,\n [v[0] + t * (w[0] - v[0]), v[1] + t * (w[1] - v[1])]\n );\n }\n return Math.sqrt(distancePointToLineSquared(point, line))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":39,"value":"function polygonScaleOffset(polygon, offset, origin){\n if (!origin){\n origin = geometric.polygonCentroid(polygon);\n }\n\n let p = [];\n\n for (let i = 0, l = polygon.length; i < l; i++){\n const v = polygon[i],\n d = geometric.lineLength([origin, v]),\n a = geometric.lineAngle([origin, v]);\n\n p[i] = geometric.pointTranslate(origin, a, d - offset);\n }\n\n return p;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":182,"value":"isPolygonFunky = function(polygon, centroid) {\n for (let i = 0; i < polygon.length; i++) {\n const point = polygon[i];\n if (isNaN(point[0]) || isNaN(point[1])) {\n return true;\n }\n if (geometric.lineLength([centroid, point]) > 100) {\n console.log(\"Funky line length\", geometric.lineLength([centroid, point]), centroid, point);\n return true;\n }\n }\n return false;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":21,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"import {slider} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"viewof inset = slider({\n min: 0, \n max: 30, \n value: 2,\n step: 0.1,\n description: \"Amount to inset the polygons\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W37","stdlib":"1","titling":"auto"}} 32:"$31:body"