{"id":"1db3bfd95275c7e4","slug":"convex-hull-peeling-ii","trashed":false,"description":"","likes":2,"publish_level":"public","forks":0,"fork_of":{"id":"c198b7b30ade4b81","slug":"convex-hull-peeling","title":"Convex hull peeling","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"},"version":173},"has_importers":false,"update_time":"2020-05-02T09:24:30.407Z","first_public_version":null,"paused_version":null,"publish_time":"2019-07-08T04:16:35.660Z","publish_version":284,"latest_version":284,"thumbnail":"95ee540792127fd15af9d1e30f6e4964a3a4dbd973eeeb355d35214da38ef02e","default_thumbnail":"95ee540792127fd15af9d1e30f6e4964a3a4dbd973eeeb355d35214da38ef02e","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":284,"title":"Convex hull peeling II","license":null,"copyright":"","nodes":[{"id":0,"value":"md`# Convex hull peeling II\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).* See [the parent notebook](https://observablehq.com/@bryangingechen/convex-hull-peeling) for more discussion.\n\nSuppose you take a bunch of [Poisson-disk-sampled](https://bost.ocks.org/mike/algorithms/) points (blue) and a bunch of points drawn from the [Poisson point process](https://en.wikipedia.org/wiki/Poisson_point_process) (green) in a region and repeatedly remove the boundaries of their convex hulls.\n\nThe following animation shows the evolution of those boundaries:\n`","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  pts.sort((a, b) => a[0] - b[0]);\n\n  let points = new Set(pts),\n    hull = d3.polygonHull([...points]);\n  context.fillStyle = 'rgb(0,255,0)';\n  for (const p of points) {\n    context.beginPath();\n    context.arc(p[0], p[1], radius, 0, tau);\n    context.fill();\n  }\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 = d3.polygonHull([...pDpoints]);\n  context.fillStyle = 'rgb(0,0,255)';\n  for (const p of pDpoints) {\n    context.beginPath();\n    context.arc(p[0], p[1], radius, 0, tau);\n    context.fill();\n  }\n  while (hull || pDhull) {\n    const p = Math.random();\n    if (hull) {\n      context.strokeStyle = 'rgb(0,128,0,0.25)';\n      context.lineWidth = 0.5;\n      context.beginPath();\n      for (let i = 0; i < hull.length; i++) {\n        const next = hull[i];\n        context.lineTo(...next);\n        points.delete(next);\n      }\n      context.lineTo(...hull[0]);\n      context.stroke();\n      hull = d3.polygonHull([...points]);\n    }\n    if (pDhull) {\n      context.strokeStyle = 'rgb(0,0,128,0.25)';\n      context.lineWidth = 0.5;\n      context.beginPath();\n      context.moveTo(pDhull[0][0], pDhull[0][1]);\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      pDhull = d3.polygonHull([...pDpoints]);\n    }\n\n    yield context.canvas;\n  }\n}","pinned":false,"mode":"js","data":null,"name":null},{"id":152,"value":"md`I've tuned the intensity of the Poisson process by hand so that the speed of the evolution of the green / blue curves is roughly the same.`","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":185,"value":"md`[Permalink!](${permalink({scaledPolygon})})`","pinned":false,"mode":"js","data":null,"name":null},{"id":232,"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":false,"mode":"js","data":null,"name":null},{"id":8,"value":"height = width","pinned":false,"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":10,"value":"pts = {\n  const p = [];\n  const N = 68600/75800 * height*width/(R*R*1.58); // magic density?\n  for (let j = 0; j < N; j++) {\n    const pt = [Math.random()*width, Math.random()*height];\n    if (d3.polygonContains(scaledPolygon, [pt[0]/2,pt[1]/2])) p.push(pt);\n  }\n  return p;\n}","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":271,"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":279,"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}