2c:null 2d:["$","title",null,{"children":"Estimate the Brachistochrone using Monte Carlo Simulation V2 | Chuncheng | Observable"}] 32:T7d3,canvas = { const context = DOM.context2d(width, height); const opacityPostfix = (k = 2) => ("0" + parseInt((255 / repeat) * k).toString(16)).slice(-2); var pathPoints; // Background { // context.fillStyle = "hsl(216deg 100% 13%)"; // context.fillRect(0, 0, width, height); context.canvas.style.background = "hsl(216deg 50% 13%)"; } // Draw points { function draw(pts, yOffset = 0, radius = 5, k = 2) { const maxV = d3.max(pts, (e) => e.v); const minV = d3.min(pts, (e) => e.v); pts.map((pts) => { const { x, y, v } = pts; (context.fillStyle = d3.color(colorMap((v - minV) / (maxV - minV))).hex() + opacityPostfix(k)), context.beginPath(), context.arc( constants.xScale(x), constants.yScale(y + yOffset), radius, 0, Math.PI * 2 ), context.fill(); }); } const radius = width / constants.numX / 3; if (showGridToggle) { draw(data.points, 0, radius / 2, 3); } pathList.map((path) => { pathPoints = path.map((str) => { return data.map[str]; }); draw(pathPoints, 0, radius); }); } // Draw ground truth // { // context.strokeStyle = "#ff0000" + "80"; // context.lineWidth = 3; // context.beginPath(); // context.moveTo(constants.xScale(0), constants.yScale(0)); // // context.lineTo(constants.xScale(0.2), constants.yScale(0.3)); // const r = 1, // n = 100; // const thetaScale = d3 // .scaleLinear() // .domain([0, n * 2]) // .range([0, Math.PI * 2]); // var x, y, theta; // for (let i = 0; i < n + 1; ++i) { // theta = thetaScale(i); // x = (r * (theta - Math.sin(theta))) / Math.PI; // y = (r * (1 - Math.cos(theta))) / 2; // context.lineTo(constants.xScale(x), constants.yScale(y)); // } // context.stroke(); // } return context.canvas; }33:T44e,canvas1 = { const context = DOM.context2d(width, height); var pathPoints; // Background { // context.fillStyle = "hsl(216deg 100% 13%)"; // context.fillRect(0, 0, width, height); context.canvas.style.background = "hsl(216deg 50% 13%)"; } // Draw points { function draw(pts, yOffset = 0, radius = 5, opacityPostFix = "a0") { const maxV = d3.max(pts, (e) => e.v); const minV = d3.min(pts, (e) => e.v); pts.map((pts) => { const { x, y, v } = pts; (context.fillStyle = d3.color(colorMap((v - minV) / (maxV - minV))).hex() + opacityPostFix), context.beginPath(), context.arc( constants.xScale(x), constants.yScale(y + yOffset), radius, 0, Math.PI * 2 ), context.fill(); }); } const radius = width / constants.numX / 3; const gridFieldLst = []; for (const key in gridField) { gridFieldLst.push(gridField[key]); } draw(gridFieldLst, 0, radius, "90"); } return context.canvas; }34:T4b5,class Noise { static lerp(t, a, b) { return a + t * (b - a); } static grad2d(i, x, y) { const v = (i & 1) === 0 ? x : y; return (i & 2) === 0 ? -v : v; } constructor(octaves = 1) { this.p = new Uint8Array(512); this.octaves = octaves; this.init(); } init() { for (let i = 0; i < 512; ++i) { this.p[i] = Math.random() * 256; } } noise2d(x2d, y2d) { const X = Math.floor(x2d) & 255; const Y = Math.floor(y2d) & 255; const x = x2d - Math.floor(x2d); const y = y2d - Math.floor(y2d); const fx = (3 - 2 * x) * x * x; const fy = (3 - 2 * y) * y * y; const p0 = this.p[X] + Y; const p1 = this.p[X + 1] + Y; return Noise.lerp( fy, Noise.lerp( fx, Noise.grad2d(this.p[p0], x, y), Noise.grad2d(this.p[p1], x - 1, y) ), Noise.lerp( fx, Noise.grad2d(this.p[p0 + 1], x, y - 1), Noise.grad2d(this.p[p1 + 1], x - 1, y - 1) ) ); } noise(x, y) { let e = 1, k = 1, s = 0; for (let i = 0; i < this.octaves; ++i) { e *= 0.5; s += e * (1 + this.noise2d(k * x, k * y)) / 2; k *= 2; } return s; } }35:[] 30:{"id":"6aa1465c017e16dd","slug":"brachistochrone-using-monte-carlo-simulation-v2","title":"Estimate the Brachistochrone using Monte Carlo Simulation V2","thumbnail":"28f4b14ab8ab6353789778aee2c62aae551a416a0c1e5913ca9fe30f11a5fb7c","access_level":"public","create_time":"$D2022-11-11T02:04:32.070Z","update_time":"$D2022-11-11T03:26:45.173Z","view_time":null,"first_public_time":"$D2022-11-13T04:45:06.220Z","has_unpublished_edits":null,"fork":{"id":"2b415b1a01bd9398","slug":"estimate-the-brachistochrone-using-monte-carlo-simulatio","title":"Estimate the Brachistochrone using Monte Carlo Simulation","owner":{"id":"bcd65cef1cb4d2ed","login":"listenzcc","name":"Chuncheng"}},"stars":2,"starred":false,"owner":{"type":"team","id":"bcd65cef1cb4d2ed","login":"listenzcc","name":"Chuncheng","avatar_url":"https://avatars-next.observableusercontent.com/bb3c68e77a708a587ffc2d663bb83421f20d67991dbe6c1623c6e5d2fb73d15e","tier":"starter_2024"},"version":543,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"16328058352682a8","login":"listenzcc","name":"Chuncheng","avatar_url":"https://avatars-next.observableusercontent.com/bb3c68e77a708a587ffc2d663bb83421f20d67991dbe6c1623c6e5d2fb73d15e","tier":null}],"members":[{"type":"individual","id":"16328058352682a8","login":"listenzcc","name":"Chuncheng","avatar_url":"https://avatars-next.observableusercontent.com/bb3c68e77a708a587ffc2d663bb83421f20d67991dbe6c1623c6e5d2fb73d15e","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"bb5b16d3c3bab332","slug":"monte-carlo-simulation","title":"Monte Carlo Simulation","owner":{"id":"bcd65cef1cb4d2ed","login":"listenzcc","name":"Chuncheng"}},"type":"notebook","body":{"titling":"auto","title":"Estimate the Brachistochrone using Monte Carlo Simulation V2","cells":[{"id":0,"value":"# Estimate the Brachistochrone using Monte Carlo Simulation V2\n\n**The build applies to random field.**\n \nIt describes two things.\nThe first is that the rect grids can not simulate the system of mathematical solution.\nThe second is the Monte Carlo simulation can be used to find a comparable solution.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":261,"value":"viewof repeat = Inputs.select([10, 15, 20, 50], { label: \"Repeat\", value: 10 })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":388,"value":"viewof paraRange = Inputs.range([1, 3], {\n label: \"Simulation range\",\n step: 0.1,\n value: 2\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":107,"value":"viewof numX = Inputs.range([50, 200], { label: \"numX\", value: 100, step: 10 })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":401,"value":"viewof showGridToggle = Inputs.toggle({ label: \"Grid toggle\", value: true })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":125,"value":"viewof palette = Inputs.select(palettes, {\n label: \"Color\",\n value: \"Viridis\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":487,"value":"viewof reBuildFieldBtn = Inputs.button(\"Rebuld field\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":292,"value":"{\n repeat;\n numX;\n paraRange;\n reBuildFieldBtn;\n return html`\n

Simulation for ${repeat} times costs ${constants.simulationTime} ms

\n`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":522,"value":"

Field

","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":493,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":119,"value":"points","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":152,"value":"points = data.points","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":229,"value":"path = mkPath(mkLinks(data.points, data.map))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":244,"value":"pathList = {\n const t = new Date();\n const lst = [...new Array(repeat)];\n const pathLst = lst.map((e) => mkPath(mkLinks(data.points, data.map)));\n constants[\"simulationTime\"] = new Date() - t;\n return pathLst;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":226,"value":"function mkPath(links) {\n const { numX, numY } = constants;\n return dijkstra.find_path(links, \"0-0\", ij2str(numX, numY));\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":219,"value":"function mkLinks(points, map) {\n const links = {};\n var _pnt, s;\n points.map((pnt) => {\n const { i, j } = pnt;\n\n links[ij2str(i, j)] = {};\n\n for (let a = -1; a < 2; ++a) {\n for (let b = -1; b < 2; ++b) {\n if (a === 0 && b === 0) continue;\n\n _pnt = map[ij2str(i + a, j + b)];\n if (!_pnt) continue;\n\n s = a * b === 0 ? 1 : constants.sqrt2;\n\n links[ij2str(i, j)][ij2str(_pnt.i, _pnt.j)] =\n d3.randomUniform(1, paraRange)() * s * _pnt.dt;\n }\n }\n });\n return links;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":104,"value":"data = {\n const { numX, numY } = constants;\n\n const points = [];\n const map = {};\n\n var pnt, x, y, v, dt;\n\n // Build dataset with points and map\n for (let i = 0; i < numX + 1; ++i) {\n for (let j = 0; j < numY + 1; ++j) {\n x = i / numX;\n y = j / numY;\n const { fi, fj } = getField(i, j);\n\n pnt = {\n i,\n j,\n x,\n y,\n fi,\n fj\n };\n\n map[ij2str(i, j)] = pnt;\n\n points.push(pnt);\n }\n }\n\n // Compute v and dt for every point\n points.map((pnt, ii) => {\n const { i, j } = pnt;\n v = computeV(i, j, map);\n v = v ? v : 0;\n dt = v === 0 ? 100 : 1 / v;\n pnt.v = v;\n pnt.dt = dt;\n });\n\n return { points, map };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":165,"value":"// Convert point index to str (unique)\nfunction str2ij(str) {\n const pair = str.split(\"-\").map((e) => parseInt(e));\n return { i: pair[0], j: pair[1] };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":162,"value":"// Convert str (unique) to point index\nfunction ij2str(i, j) {\n return i + \"-\" + j;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":478,"value":"function getField(i, j) {\n var fi =\n i === 0 ? 0 : gridField[ij2str(i, j)].v - gridField[ij2str(i - 1, j)].v;\n var fj =\n j === 0 ? 0 : gridField[ij2str(i, j)].v - gridField[ij2str(i, j - 1)].v;\n\n fi = fi ? fi : 0;\n fj = fj ? fj : 0;\n\n return { fi, fj };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":444,"value":"// Compute the velocity version 2.0\nfunction computeV(i, j, map) {\n var cumFi = 0,\n cumFj = 0;\n\n const fixJ = 0;\n for (let ii = 0; ii < i; ++ii) {\n const { fi } = map[ij2str(ii + 1, fixJ)];\n cumFi += fi;\n }\n\n const fixI = i;\n for (let jj = 0; jj < j; ++jj) {\n const { fj } = map[ij2str(fixI, jj + 1)];\n cumFj += fj;\n }\n\n const v = Math.sqrt(2 * (cumFi + cumFj));\n return v;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":99,"value":"constants = {\n return {\n sqrt2: Math.sqrt(2),\n mass: 1,\n gravity: 9.8,\n numX: numX,\n numY: parseInt((numX / width) * height),\n xScale: d3.scaleLinear().domain([-0.1, 1.1]).range([0, width]),\n yScale: d3.scaleLinear().domain([-0.1, 1.1]).range([0, height])\n };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"height = (width * 9) / 16","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":123,"value":"colorMap = d3[`interpolate${palette}`]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":121,"value":"palettes = [\n \"RdBu\",\n \"PuOr\",\n \"Viridis\",\n \"Inferno\",\n \"Turbo\",\n \"Magma\",\n \"Plasma\",\n \"Cividis\",\n \"Warm\",\n \"Cool\",\n \"CubehelixDefault\",\n \"BuPu\",\n \"BuGn\",\n \"GnBu\",\n \"PuBu\",\n \"PuRd\",\n \"RdPu\",\n \"PuBuGn\",\n \"OrRd\",\n \"YlGnBu\",\n \"YlGn\",\n \"YlOrRd\",\n \"YlOrBr\"\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":142,"value":"dijkstra = require(\"https://bundle.run/dijkstrajs@1.0.2\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":91,"value":"d3 = require(\"d3\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":463,"value":"## Generate random field","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":472,"value":"period = 0.05","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":470,"value":"gridField = {\n reBuildFieldBtn;\n const noise = new Noise(3);\n const grid = {};\n const { numX, numY } = constants;\n for (let i = 0; i < numX + 1; ++i) {\n for (let j = 0; j < numY + 1; ++j) {\n grid[ij2str(i, j)] = {\n x: i / numX,\n y: j / numY,\n v: noise.noise(i * period, j * period)\n };\n }\n }\n return grid;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":465,"value":"$34","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":460,"value":"import { samples } from \"@mbostock/1d-poisson-disk-sampling\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1"}} 31:"$30:body"