25:["$","title",null,{"children":"PolyLabel Animation | XiongBiao | Observable"}] 49:T1f77,chart1 = { replay; const polygon = test_poly; const precision = 1 const xs = polygon.map(p => p[0]); const ys = polygon.map(p => p[1]); const minX = Math.min(...xs); const maxX = Math.max(...xs); const minY = Math.min(...ys); const maxY = Math.max(...ys); const width = maxX - minX; const height = maxY - minY; const svgWidth = width < height ? width : height * Math.ceil(width / height); const svgHeight = height < width ? height : width * Math.ceil(height / width); const padding = { top: 20, bottom: 20, left: 20, right: 20 }; const svg = d3.create("svg") .attr("width", svgWidth + padding.left + padding.right) .attr("height", svgHeight + padding.top + padding.bottom); // 新增：显示计数器的文本元素（置于顶层） const counterText = svg.append("text") .attr("x", (svgWidth + padding.left + padding.right) / 2) .attr("y", 14) .attr("text-anchor", "middle") .attr("fill", "black") .attr("font-size", "14px") .attr("font-family", "sans-serif"); const mainGroup = svg.append("g") .attr("transform", `translate(${padding.left}, ${padding.top})`); // 绘制多边形 const gPoly = mainGroup.append("g"); const pathData = polygon.map((p, i) => (i === 0 ? `M ${p[0]} ${p[1]}` : `L ${p[0]} ${p[1]}`)).join(' ') + ' Z'; gPoly.append("path") .attr("d", pathData) .attr("fill", "#f0ded5") .attr("stroke", "black") .attr("stroke-width", 1); // 分组：单元格、当前圆、最佳圆、最佳圆心标记 const gCell = mainGroup.append("g"); const gCurrentCircle = mainGroup.append("g"); const gBestCircle = mainGroup.append("g"); const gBestPoint = mainGroup.append("g"); const cellSize = Math.min(width, height); let h = cellSize / 2; // Cell 构造函数：计算距离并绘制矩形（带生长动画） function Cell(x, y, h, polygon) { this.x = x; this.y = y; this.h = h; this.d = pointToPolygonDist(x, y, polygon); this.max = this.d + this.h * Math.SQRT2; // 绘制单元格边框（仅当 h>0 时可见） if (h > 0) { gCell.append("rect") .attr("x", x - h) .attr("y", y - h) .attr("width", 1e-6) .attr("height", 1e-6) .transition() .attr("width", h * 2) .attr("height", h * 2) .attr("fill-opacity", "0") .attr("stroke", "black") .attr("stroke-width", 0.5); } } // 计算质心单元格 function getCentroidCell(polygon) { let [area, x, y] = [0, 0, 0]; const points = polygon[0]; for (let i = 0, len = points.length, j = len - 1; i < len; j = i++) { const [a, b] = [points[i], points[j]]; const f = a[0] * b[1] - b[0] * a[1]; x += (a[0] + b[0]) * f; y += (a[1] + b[1]) * f; area += f * 3; } if (area === 0) { return new Cell(points[0][0], points[0][1], 0, polygon); } return new Cell(x / area, y / area, 0, polygon); } // 逐步处理队列 async function processQueue() { // 优先队列（按 max 降序） const cellQueue = new TinyQueue(undefined, (a, b) => b.max - a.max); // 用初始单元格覆盖 bounding box for (let x = minX; x < maxX; x += cellSize) { for (let y = minY; y < maxY; y += cellSize) { cellQueue.push(new Cell(x + h, y + h, h, [polygon])); } } // 暂停 200ms 以便观察 await new Promise(resolve => setTimeout(resolve, 1000)); // 初始最佳点（质心） let bestCell = getCentroidCell([polygon]); // 绘制最佳圆心标记（小红点） gBestPoint.append("circle") .attr("fill", "red") .attr("stroke", "none") .attr("cx", bestCell.x) .attr("cy", bestCell.y) .attr("r", 1e-6) .transition() .attr("r", 1.5); // 绘制最佳内切圆 gBestCircle.append("circle") .attr("fill", "rgba(255,0,0,0.2)") .attr("stroke", "red") .attr("stroke-width", 1) .attr("cx", bestCell.x) .attr("cy", bestCell.y) .attr("r", 1e-6) .transition() .attr("r", bestCell.d > 0 ? bestCell.d : 0); // 检查 bbox 中心是否更优 const bboxCell = new Cell(minX + width / 2, minY + height / 2, 0, [polygon]); if (bboxCell.d > bestCell.d) { bestCell = bboxCell; updateBestVisual(); } let numProbes = cellQueue.length; while (cellQueue.length) { const cell = cellQueue.pop(); await new Promise(resolve => setTimeout(resolve, 500)); // 显示当前单元格的候选圆（蓝色） gCurrentCircle.selectAll("*").remove(); gCurrentCircle.append("circle") .attr("fill", "rgba(0,0,255,0.2)") .attr("stroke", "blue") .attr("stroke-width", 1) .attr("cx", cell.x) .attr("cy", cell.y) .attr("r", 1e-6) .transition() .attr("r", cell.d > 0 ? cell.d : 0); gCurrentCircle.append("circle") .attr("fill", "blue") .attr("stroke", "none") .attr("cx", cell.x) .attr("cy", cell.y) .attr("r", 1e-6) .transition() .attr("r", 1.5); // 若当前单元格更优，更新最佳点 if (cell.d > bestCell.d) { // 暂停 200ms 以便观察 await new Promise(resolve => setTimeout(resolve, 500)); bestCell = cell; updateBestVisual(); counterText.text(`found best ${Math.round(1e4 * cell.d) / 1e4} after ${numProbes} probes`); } // 暂停 200ms 以便观察 await new Promise(resolve => setTimeout(resolve, 500)); // 若仍有提升潜力，分裂为四个子单元格 if (cell.max - bestCell.d > precision) { const newH = cell.h / 2; cellQueue.push(new Cell(cell.x - newH, cell.y - newH, newH, [polygon])); cellQueue.push(new Cell(cell.x + newH, cell.y - newH, newH, [polygon])); cellQueue.push(new Cell(cell.x - newH, cell.y + newH, newH, [polygon])); cellQueue.push(new Cell(cell.x + newH, cell.y + newH, newH, [polygon])); numProbes += 4; } else { gCell.append("rect") .attr("x", cell.x - cell.h) .attr("y", cell.y - cell.h) .attr("width", cell.h * 2) .attr("height", cell.h * 2) .attr("fill", "black") .attr("stroke", "black") .attr("stroke-width", 0.5) .attr("fill-opacity", "0") .transition() .attr("fill-opacity", ".2") } // 暂停 200ms 以便观察 await new Promise(resolve => setTimeout(resolve, 500)); } // 处理完毕，可清除当前圆（可选） gCurrentCircle.selectAll("*").remove(); console.log("计算完成"); // 更新最佳点可视化（圆心标记 + 内切圆） function updateBestVisual() { gBestPoint.selectAll("circle").remove(); gBestPoint.append("circle") .attr("fill", "red") .attr("stroke", "none") .attr("cx", bestCell.x) .attr("cy", bestCell.y) .attr("r", 1.5); gBestCircle.selectAll("circle").remove(); gBestCircle.append("circle") .attr("fill", "rgba(255,0,0,0.2)") .attr("stroke", "red") .attr("stroke-width", 1) .attr("cx", bestCell.x) .attr("cy", bestCell.y) .attr("r", bestCell.d > 0 ? bestCell.d : 0); } } // 启动逐步可视化 processQueue(); return svg.node(); }4a:T8e1,/*ISC License Copyright (c) 2017, Vladimir Agafonkin Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above copyright notice and this permission notice appear in all copies. THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ class TinyQueue { constructor(data = [], compare = (a, b) => (a < b ? -1 : a > b ? 1 : 0)) { this.data = data; this.length = this.data.length; this.compare = compare; if (this.length > 0) { for (let i = (this.length >> 1) - 1; i >= 0; i--) { this._down(i); } } } push(item) { this.data.push(item); this._up(this.length++); } pop() { if (this.length === 0) { return undefined; } const top = this.data[0]; const bottom = this.data.pop(); if (--this.length > 0) { this.data[0] = bottom; this._down(0); } return top; } peek() { return this.data[0]; } _up(pos) { const { data, compare } = this; const item = data[pos]; while (pos > 0) { const parent = (pos - 1) >> 1; const current = data[parent]; if (compare(item, current) >= 0) { break; } data[pos] = current; pos = parent; } data[pos] = item; } _down(pos) { const { data, compare } = this; const halfLength = this.length >> 1; const item = data[pos]; while (pos < halfLength) { let bestChild = (pos << 1) + 1; // initially it is the left child const right = bestChild + 1; if (right < this.length && compare(data[right], data[bestChild]) < 0) { bestChild = right; } if (compare(data[bestChild], item) >= 0) { break; } data[pos] = data[bestChild]; pos = bestChild; } data[pos] = item; } }4b:[{"id":"a9027f7d4504e84999fbd7bba8797eaae5f876a9b5b5162d5dad1af7160774ef22bc59b49d036aca3f65ae7423da1d1bc7cf7dbea3d82ae9424d16a5cd9fb8bc","href":"https://static.observableusercontent.com/files/a9027f7d4504e84999fbd7bba8797eaae5f876a9b5b5162d5dad1af7160774ef22bc59b49d036aca3f65ae7423da1d1bc7cf7dbea3d82ae9424d16a5cd9fb8bc","name":"中华人民共和国topo.json","type":"application/json","lastModified":1773284172958.76,"size":159754}] 29:{"id":"b8471dc155b926cc","slug":null,"title":"PolyLabel Animation","thumbnail":"4f29960537bb3dc925d38788d28748098c637441d5cab202772e8f302386dd31","access_level":"public","create_time":"$D2026-03-12T02:44:33.634Z","update_time":"$D2026-03-13T12:20:49.225Z","view_time":null,"first_public_time":"$D2026-03-12T02:44:33.634Z","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":376,"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":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":{"id":"7475f6cf2b719359","slug":"algorithm","title":"Algorithm","owner":{"id":"189a68e88fe366bd","login":"xiongbiao","name":"XiongBiao"}},"type":"notebook","body":{"titling":"auto","title":"PolyLabel Animation","cells":[{"id":0,"value":"# PolyLabel Animation","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":30,"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":232,"value":"viewof test_poly = Inputs.radio(new Map([[\"Simple convex polygon\", scaled_convex_polygon],\n [\"Simple concave polygon\", scaled_concave_polygon],\n [\"Beijing\", beijing_scaledPoly]]), {value: beijing_scaledPoly, label: \"测试多边形\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":197,"value":"$49","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":82,"value":"---\n## 测试数据","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":242,"value":"beijing_scaledPoly = scalePolygonUniformFlipY(beijing_poly, 600, true)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":227,"value":"beijing_poly = china_feat.features[0].geometry.coordinates[0]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":223,"value":"china_feat = topojson.feature(china_topo, {\"type\": \"GeometryCollection\",\n \"geometries\": china_topo.objects[\"中华人民共和国\"].geometries.slice(0, 1)})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":220,"value":"china_topo = FileAttachment(\"中华人民共和国topo.json\").json()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":262,"value":"scaled_convex_polygon = scalePolygonUniformFlipY(convex_polygon, 300)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":253,"value":"convex_polygon = [\n [0, 0],\n [10, 0],\n [10, 10],\n [0, 10]\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":56,"value":"scaled_concave_polygon = scalePolygonUniformFlipY(concave_polygon, 300)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":36,"value":"concave_polygon = [\n [105000, 14000],\n [116000, 9000],\n [121000, 0],\n [110000, 5000],\n [101000, 3000]\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":79,"value":"---\n## 辅助函数","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":53,"value":"function scalePolygonUniformFlipY(poly, targetMax = 300, flipY = false) {\n const xs = poly.map(p => p[0]);\n const ys = poly.map(p => p[1]);\n\n const minX = Math.min(...xs);\n const maxX = Math.max(...xs);\n const minY = Math.min(...ys);\n const maxY = Math.max(...ys);\n\n const rangeX = maxX - minX;\n const rangeY = maxY - minY;\n const scale = targetMax / Math.max(rangeX, rangeY, 1); // 防止除零\n\n return !flipY ? poly.map(([x, y]) => [(x - minX) * scale, (y - minY) * scale])\n : poly.map(([x, y]) => [(x - minX) * scale, (maxY - y) * scale]);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"$4a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"function pointToPolygonDist(x, y, polygon) {\n let inside = false;\n let minDistSq = Infinity;\n\n for (let k = 0; k < polygon.length; k++) {\n const ring = polygon[k];\n\n for (let i = 0, len = ring.length, j = len - 1; i < len; j = i++) {\n const [a, b] = [ring[i], ring[j]];\n if (\n a[1] > y !== b[1] > y &&\n x < ((b[0] - a[0]) * (y - a[1])) / (b[1] - a[1]) + a[0]\n ) {\n inside = !inside;\n }\n minDistSq = Math.min(minDistSq, getSegDistSq(x, y, a, b));\n }\n }\n return minDistSq === 0 ? 0 : (inside ? 1 : -1) * Math.sqrt(minDistSq);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":21,"value":"function getSegDistSq(px, py, a, b) {\n let [x, y] = [a[0], a[1]];\n let [dx, dy] = [b[0] - x, b[1] - y];\n\n if (dx !== 0 || dy !== 0) {\n const t = ((px - x) * dx + (py - y) * dy) / (dx * dx + dy * dy);\n if (t > 1) {\n x = b[0];\n y = b[1];\n } else if (t > 0) {\n x += dx * t;\n y += dy * t;\n }\n }\n dx = px - x;\n dy = py - y;\n return dx * dx + dy * dy;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W4b","stdlib":"1"}} 24:null