{"id":"c198b7b30ade4b81","slug":"convex-hull-peeling","trashed":false,"description":"","likes":11,"publish_level":"public","forks":3,"fork_of":null,"has_importers":false,"update_time":"2020-05-02T09:05:24.117Z","first_public_version":null,"paused_version":null,"publish_time":"2019-07-08T04:15:33.099Z","publish_version":259,"latest_version":259,"thumbnail":"0f023cc34c0397c06409369792cd04825ec6ca0ad1e4522c689ae1a92e17df48","default_thumbnail":"0f023cc34c0397c06409369792cd04825ec6ca0ad1e4522c689ae1a92e17df48","roles":[],"sharing":null,"owner":{"id":"d2fd23101beb2a61","avatar_url":"https://avatars.observableusercontent.com/avatar/73f0dccc0b7fc5c845e6a52a58e01a2ae432cc529aaada0d10ab602137e603c0","login":"bryangingechen","name":"Bryan Gin-ge Chen","bio":"here to learn","home_url":"https://twitter.com/blockspins","type":"team","tier":"starter_2024"},"creator":{"id":"5c13a1a27cf52564","avatar_url":"https://avatars.observableusercontent.com/avatar/73f0dccc0b7fc5c845e6a52a58e01a2ae432cc529aaada0d10ab602137e603c0","login":"bryangingechen","name":"Bryan Gin-ge Chen","bio":"here to learn","home_url":"https://twitter.com/blockspins","tier":"public"},"authors":[{"id":"5c13a1a27cf52564","avatar_url":"https://avatars.observableusercontent.com/avatar/73f0dccc0b7fc5c845e6a52a58e01a2ae432cc529aaada0d10ab602137e603c0","name":"Bryan Gin-ge Chen","login":"bryangingechen","bio":"here to learn","home_url":"https://twitter.com/blockspins","tier":"public","approved":true,"description":""}],"collections":[{"id":"1bd9754ae5c8b895","type":"public","slug":"morsels","title":"Morsels","description":"bite-sized illustrations / explanations","update_time":"2019-04-05T13:49:52.739Z","pinned":false,"ordered":false,"custom_thumbnail":null,"default_thumbnail":"8ef8421857ea37af891c5dc386db1605c29edfc058915506c59f2a82e4dc34ed","thumbnail":"8ef8421857ea37af891c5dc386db1605c29edfc058915506c59f2a82e4dc34ed","listing_count":8,"parent_collection_count":0,"owner":{"id":"d2fd23101beb2a61","avatar_url":"https://avatars.observableusercontent.com/avatar/73f0dccc0b7fc5c845e6a52a58e01a2ae432cc529aaada0d10ab602137e603c0","login":"bryangingechen","name":"Bryan Gin-ge Chen","bio":"here to learn","home_url":"https://twitter.com/blockspins","type":"team","tier":"starter_2024"}}],"files":[],"comments":[],"commenting_lock":null,"suggestion_from":null,"suggestions_to":[],"version":259,"title":"Convex hull peeling","license":null,"copyright":"","nodes":[{"id":0,"value":"md`# Convex hull peeling\n\n*Inspired by Jeff Calder and Charles K Smart's preprint: [\"The Limit Shape of Convex Hull Peeling\"](https://arxiv.org/abs/1805.08278).*\n\nSuppose you take a bunch of [Poisson-disk-sampled](https://bost.ocks.org/mike/algorithms/) points in a region and repeatedly remove the points on the boundary of the convex hull. As the points are removed, the boundary curve will migrate inwards as follows:`","pinned":false,"mode":"js","data":null,"name":null},{"id":12,"value":"{\n  const context = DOM.context2d(width, height);\n  const radius = 1,\n    tau = 2 * Math.PI;\n\n  // sort the points once so d3.polygonHull doesn't spend too much time re-sorting\n  pDpts.sort((a, b) => a[0] - b[0]);\n\n  let pDpoints = new Set(pDpts),\n    pDhull;\n  for (const p of pDpoints) {\n    context.moveTo(p[0], p[1]);\n    context.arc(p[0], p[1], radius, 0, tau);\n  }\n  context.fill();\n\n  context.strokeStyle = 'rgb(0,0,0,0.5)';\n  context.lineWidth = 0.5;\n  while ((pDhull = d3.polygonHull([...pDpoints]))) {\n    context.beginPath();\n    for (let i = 0; i < pDhull.length; i++) {\n      const next = pDhull[i];\n      context.lineTo(...next);\n      pDpoints.delete(next);\n    }\n    context.lineTo(...pDhull[0]);\n    context.stroke();\n\n    yield context.canvas;\n  }\n}","pinned":false,"mode":"js","data":null,"name":null},{"id":152,"value":"md`Note how sharp corners tend to get smoothed out quickly and how the boundary curve tends to a circle (as long as it's not \"stretched\" between two different components of the region). This might remind you of the [curve-shortening flow](https://en.wikipedia.org/wiki/Curve-shortening_flow), where points on a plane curve move with speed proportional to the [curvature](https://en.wikipedia.org/wiki/Curvature#Curvature_of_plane_curves), but Calder and Smart showed that in the limit of a large number of random points in the region, each point on the boundary curve actually travels inwards with speed proportional to the *cube root* of the curvature! (This is apparently called the \"affine curve-shortening flow\".)\n\nIn fact, they only proved this for regions with points sampled from a [Poisson point process](https://en.wikipedia.org/wiki/Poisson_point_process) (points drawn independently and uniformly at random), not for points arising from the more eye-pleasing Poisson-disk-sampling algorithm shown above – however, their result seems to hold in this case as well: check [this fork for a direct comparison.](https://observablehq.com/d/1db3bfd95275c7e4) Calder and Smart have an analogous result for \"peeling\" 3D regions as well – I'd love to see a visualization of that process!`","pinned":false,"mode":"js","data":null,"name":null},{"id":65,"value":"viewof polygon = polygonInput({\n  value: scaledPolygon,\n  title: 'Try another polygon!',\n  description: 'Drag vertices to move, click on vertices to remove, click elsewhere to add vertices (the added vertex will split the red segment, if present).  When ready, click the \"Rescale and submit!\" button below.',\n  width: width*0.5,\n  height: height*0.5,\n})","pinned":false,"mode":"js","data":null,"name":null},{"id":75,"value":"buttons = {\n  const W = width*0.5; const H = width*0.5;\n  const reset = html`<button>Reset polygon to full square!`;\n  reset.onclick = () => {\n    mutable scaledPolygon = [[0,0], [W,0], [W,H], [0,H]];\n  }\n  const button = html`<button>Rescale and submit!`;\n  button.onclick = () => {\n    mutable scaledPolygon = scale(polygon);\n  }\n  \n  const randomSides = html`<input type=\"number\" min=\"3\" max=\"15\" value=\"${polygon.length}\" step=\"1\" style=\"width: 30px\">`;\n  const randomButton = html`<button>Generate random polygon with:`;\n  randomButton.onclick = () => {\n    const randomPoly = Array.from({length: randomSides.valueAsNumber}, () => ([Math.random()*W, Math.random()*H]));\n    mutable scaledPolygon = scale(randomPoly);\n  }\n  return html`${button}${reset}<br/>\n${randomButton} ${randomSides} sides`;\n}","pinned":false,"mode":"js","data":null,"name":null},{"id":184,"value":"md`[Click here for a permalink to this polygon!](${permalink({scaledPolygon})})`","pinned":false,"mode":"js","data":null,"name":null},{"id":202,"value":"function scale(polygon) {\n  const W = width*0.5; const H = width*0.5;\n  if (polygon.length < 3) {\n    return;\n  }\n  const [Mx, My] = polygon.reduce(([Mx,My],[x,y]) => {\n    if (x>Mx) Mx = x;\n    if (y>My) My = y;\n    return [Mx,My];\n  }, [0,0]);\n  const [mx, my] = polygon.reduce(([mx,my],[x,y]) => {\n    if (x<mx) mx = x;\n    if (y<my) my = y;\n    return [mx,my];\n  }, [Infinity,Infinity]);\n  const WW = Mx - mx + 5;\n  const HH = My - my + 5;\n  const S = Math.max(WW,HH);\n  return polygon.map(([x,y]) => ([Math.round((x-mx)*W/S),Math.round((y-my)*H/S)]));\n}","pinned":false,"mode":"js","data":null,"name":null},{"id":106,"value":"mutable scaledPolygon = params.scaledPolygon || \n  scale(Array.from({length: 3 + Math.round(Math.random()*5)}, () => ([Math.random()*width/2, Math.random()*height/2])))\n\n// [[0,0], [0.5, 0], [0.5, 0.5], [1, 0.5], [1, 1], [0, 1]]\n//   .map(([x,y]) => [Math.round(x*width*0.5), Math.round(y*width*0.5)])","pinned":false,"mode":"js","data":null,"name":null},{"id":6,"value":"R = 3","pinned":true,"mode":"js","data":null,"name":null},{"id":8,"value":"height = width","pinned":true,"mode":"js","data":null,"name":null},{"id":163,"value":"pDpts = new Poisson([width, height], R).fill().filter(([x,y]) => d3.polygonContains(scaledPolygon, [x/2, y/2]))","pinned":false,"mode":"js","data":null,"name":null},{"id":4,"value":"Poisson = require(\"https://cdn.jsdelivr.net/gh/kchapelier/poisson-disk-sampling@1.0.6/build/poisson-disk-sampling.min.js\")","pinned":false,"mode":"js","data":null,"name":null},{"id":14,"value":"d3 = require('d3@5')","pinned":false,"mode":"js","data":null,"name":null},{"id":233,"value":"md`The polygon input above arises from a fork of Harry Stevens's [Polygon Input](https://observablehq.com/@harrystevens/polygon-input) notebook where I incorporated some code from Claudio Esperança's [Smooth Polygon](https://observablehq.com/@esperanc/smooth-polygon):`","pinned":false,"mode":"js","data":null,"name":null},{"id":63,"value":"import {polygonInput} from '@bryangingechen/polygon-input'","pinned":false,"mode":"js","data":null,"name":null},{"id":182,"value":"import {params, permalink} from \"@jeffbaumes/permalink\"","pinned":false,"mode":"js","data":null,"name":null},{"id":253,"value":"md`## Thanks to:\n- (2020/04/30) Ricky Reusser for a helpful suggestion that removed bundle.run in favor of jsdelivr!\n- (2020/04/30) Philippe Rivière for a fantastic suggestion that greatly improved performance!\n`","pinned":false,"mode":"js","data":null,"name":null}],"resolutions":[],"schedule":null,"last_view_time":null}