25:["$","title",null,{"children":"Covering a Square with Three Discs: A Gradient Descent Animation | XiongBiao | Observable"}] 49:T140f,chart = { replay; // 设置画布尺寸（也可使用 Observable 内置的 width 变量） // const width = 600; const height = 600; const margin = { top: 30, right: 30, bottom: 40, left: 50 }; const plotSize = Math.min( width - margin.left - margin.right, height - margin.top - margin.bottom ); // const plotWidth = width - margin.left - margin.right; // const plotHeight = height - margin.top - margin.bottom; // 数学坐标范围 const s = Math.sqrt(2); const r = 2 / 3; const VIEW_MARGIN = r + 0.08; const xDomain = [-VIEW_MARGIN, s + VIEW_MARGIN]; const yDomain = [-VIEW_MARGIN, s + VIEW_MARGIN]; // 比例尺（SVG坐标系y轴向下，所以yScale反置） const xScale = d3.scaleLinear() .domain(xDomain) .range([margin.left, margin.left + plotSize]); const yScale = d3.scaleLinear() .domain(yDomain) .range([margin.top + plotSize, margin.top]); // 创建 SVG 元素 const svg = d3.create("svg") .attr("viewBox", [0, 0, width, height]); // 背景：半透明正方形区域 svg.append("rect") .attr("x", xScale(0)) .attr("y", yScale(s)) .attr("width", xScale(s) - xScale(0)) .attr("height", yScale(0) - yScale(s)) .attr("fill", "rgba(184,64,48,0.08)") .attr("stroke", "#1a2e3b") .attr("stroke-width", 1.5); // 坐标轴 svg.append("g") .attr("transform", `translate(0,${yScale(0)})`) .call(d3.axisBottom(xScale).tickValues([-0.5, 0.5, 1.0, 1.5, 2.0]).tickSizeOuter(0)) .style("font", "10px system-ui"); svg.append("g") .attr("transform", `translate(${xScale(0)},0)`) .call(d3.axisLeft(yScale).tickValues([-0.5, 0.5, 1.0, 1.5, 2.0]).tickSizeOuter(0)) .style("font", "10px system-ui"); svg.append("text") .attr("x", xScale(0)) .attr("dx", "-9") .attr("y", yScale(0)) .attr("dy", "9") .attr("text-anchor", "end") .attr("dominant-baseline", "hanging") .style("font", "10px system-ui") .text("0.0"); svg.append('polyline') .call(arrow, xScale(0), yScale(0), xScale(0), yScale(s + 1.02*VIEW_MARGIN), {arrowLength:10, arrowWidth:8}) svg.append('polyline') .call(arrow, xScale(0), yScale(0), xScale(s + 1.02*VIEW_MARGIN), yScale(0), {arrowLength:10, arrowWidth:8}) // 三个圆盘的颜色 const colors = ['#e07b30', '#3a7abf', '#7a4faa']; // 轨迹折线容器 const trailG = svg.selectAll("g.trail") .data(d3.range(3)) .join("g") .attr("class", "trail"); // 圆盘容器 const discG = svg.selectAll("g.disc") .data(d3.range(3)) .join("g") .attr("class", "disc"); // 状态信息文本 const infoText = svg.append("text") .attr("x", margin.left) .attr("y", margin.top - 10) // .attr("font-size", 16) .style("font", "16px system-ui") .attr("fill", "#333"); // ---------- 消费生成器，逐帧更新画面 ---------- for (const state of discCoverageOptimization()) { // 更新轨迹 trailG.each(function(d, i) { const polyline = d3.select(this).select("polyline"); const points = state.trails[i].map(p => `${xScale(p[0])},${yScale(p[1])}`).join(" "); if (polyline.empty()) { d3.select(this).append("polyline") .attr("points", points) .attr("fill", "none") .attr("stroke", colors[i]) .attr("stroke-width", 1.3) .attr("opacity", 0.75); } else { polyline.attr("points", points); } }); // 更新圆盘 const radiusPx = r * (xScale(1) - xScale(0)); // 圆的像素半径（保持比例） discG.each(function(d, i) { const cx = state.params[i * 2]; const cy = state.params[i * 2 + 1]; const px = xScale(cx); const py = yScale(cy); let g = d3.select(this); // 填充圆 let fillCircle = g.select("circle.disc-fill"); if (fillCircle.empty()) fillCircle = g.append("circle").attr("class", "disc-fill"); fillCircle .attr("cx", px) .attr("cy", py) .attr("r", radiusPx) .attr("fill", d3.rgb(colors[i]).copy({opacity: 0.22})); // 轮廓圆 let strokeCircle = g.select("circle.disc-stroke"); if (strokeCircle.empty()) strokeCircle = g.append("circle").attr("class", "disc-stroke"); strokeCircle .attr("cx", px) .attr("cy", py) .attr("r", radiusPx) .attr("fill", "none") .attr("stroke", colors[i]) .attr("stroke-width", 1.4); // 圆心点 let centerCircle = g.select("circle.disc-center"); if (centerCircle.empty()) centerCircle = g.append("circle").attr("class", "disc-center"); centerCircle .attr("cx", px) .attr("cy", py) .attr("r", 3) .attr("fill", colors[i]); }); // 更新文字 infoText.text( `迭代: ${state.iter} | 软覆盖: ${(state.soft * 100).toFixed(3)}% | 硬覆盖: ${(state.hard * 100).toFixed(3)}% | 最佳: ${(state.bestHard * 100).toFixed(3)}%` ); // 交出当前 SVG 画面 yield svg.node(); } };4a:Tbba,discCoverageOptimization = function* () { const s = Math.sqrt(2); const r = 2 / 3; const MAX_ITER = 250; const BOUND_MIN = -r, BOUND_MAX = s + r; const GRID = 100; const samples = []; for (let i = 0; i < GRID; i++) { for (let j = 0; j < GRID; j++) { samples.push([(i + 0.5) / GRID * s, (j + 0.5) / GRID * s]); } } const TAU = 0.002; function softCov(params) { let sum = 0; for (const [px, py] of samples) { let notCov = 1; for (let k = 0; k < 3; k++) { const d2 = (px - params[k * 2]) ** 2 + (py - params[k * 2 + 1]) ** 2; notCov *= (1 - 1 / (1 + Math.exp((d2 - r * r) / TAU))); } sum += (1 - notCov); } return sum / samples.length; } function hardCov(params) { let cnt = 0; for (const [px, py] of samples) { for (let k = 0; k < 3; k++) { if ((px - params[k * 2]) ** 2 + (py - params[k * 2 + 1]) ** 2 <= r * r) { cnt++; break; } } } return cnt / samples.length; } const EPS = 1e-4; function gradient(params) { const base = softCov(params); const g = new Float64Array(6); for (let i = 0; i < 6; i++) { params[i] += EPS; g[i] = (softCov(params) - base) / EPS; params[i] -= EPS; } return g; } function clamp(v) { return Math.min(BOUND_MAX, Math.max(BOUND_MIN, v)); } // 随机初始圆心 let params = new Float64Array(6); for (let k = 0; k < 3; k++) { params[k * 2] = Math.random() * s; params[k * 2 + 1] = Math.random() * s; } // Adam 优化器状态 let m = new Float64Array(6); let v2 = new Float64Array(6); let adamT = 0; const B1 = 0.9, B2 = 0.999, ADAM_EPS = 1e-8, LR = 0.01; let curSoft = softCov(params); let curHard = hardCov(params); let best = { params: params.slice(), hard: curHard, iter: 0 }; // 轨迹记录 const trails = [[], [], []]; function pushTrail(p) { for (let k = 0; k < 3; k++) trails[k].push([p[k * 2], p[k * 2 + 1]]); } pushTrail(params); // 输出初始状态 yield { params: params.slice(), soft: curSoft, hard: curHard, bestHard: best.hard, trails: trails.map(t => [...t]), iter: 0 }; // 主优化循环 for (let iter = 1; iter <= MAX_ITER; iter++) { adamT++; const grad = gradient(params); for (let i = 0; i < 6; i++) { m[i] = B1 * m[i] + (1 - B1) * grad[i]; v2[i] = B2 * v2[i] + (1 - B2) * grad[i] ** 2; const mh = m[i] / (1 - B1 ** adamT); const vh = v2[i] / (1 - B2 ** adamT); params[i] = clamp(params[i] + LR * mh / (Math.sqrt(vh) + ADAM_EPS)); } curSoft = softCov(params); curHard = hardCov(params); if (curHard > best.hard) { best = { params: params.slice(), hard: curHard, iter }; } pushTrail(params); yield { params: params.slice(), soft: curSoft, hard: curHard, bestHard: best.hard, trails: trails.map(t => [...t]), iter }; } };4b:[] 29:{"id":"97560dc17e13e3b8","slug":null,"title":"Covering a Square with Three Discs: A Gradient Descent Animation","thumbnail":"d57ed14f854f1c39a6c13bc2b20db0bb2a6da8cb5490493006164a8467fff92d","access_level":"public","create_time":"$D2026-06-23T08:01:17.219Z","update_time":"$D2026-06-24T12:06:24.361Z","view_time":null,"first_public_time":"$D2026-06-23T08:01:17.219Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"189a68e88fe366bd","login":"xiongbiao","name":"XiongBiao","avatar_url":"https://avatars-next.observableusercontent.com/a95188709ffcb422fcc635f47420feb25f69fd7305881a42b4a9907e87d2aaf0","tier":"free_2026","bio":"","followed_by_you":false,"follows_you":false},"version":136,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"fc82b550d8112553","login":"xiongbiao","name":"XiongBiao","avatar_url":"https://avatars-next.observableusercontent.com/caf2b8f3d51ea1f56efa20730077b94beb57622ab029080cdb84a9ad89ac467d","tier":null,"bio":"","followed_by_you":false,"follows_you":false}],"members":[{"type":"team","id":"189a68e88fe366bd","login":"xiongbiao","name":"XiongBiao","avatar_url":"https://avatars-next.observableusercontent.com/a95188709ffcb422fcc635f47420feb25f69fd7305881a42b4a9907e87d2aaf0","tier":"free_2026","role":"editor"},{"type":"individual","id":"fc82b550d8112553","login":"xiongbiao","name":"XiongBiao","avatar_url":"https://avatars-next.observableusercontent.com/caf2b8f3d51ea1f56efa20730077b94beb57622ab029080cdb84a9ad89ac467d","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":{"id":"fbf598bc44941ea7","slug":"animation","title":"Animation","owner":{"id":"189a68e88fe366bd","login":"xiongbiao","name":"XiongBiao"}},"type":"notebook","body":{"titling":"auto","title":"Covering a Square with Three Discs: A Gradient Descent Animation","cells":[{"id":0,"value":"# Covering a Square with Three Discs: A Gradient Descent Animation","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":74,"value":"*Inspired by https://x.com/S_Conradi/status/2068065065840820444*","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":24,"value":"viewof replay = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"$49","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"$4a","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":82,"value":"import {arrow} from '@oberbichler/arrow'","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W4b","stdlib":"1"}} 24:null