一维标签布局 · 1-D Label Placement
图表 y 轴旁的注记、时间线上的事件说明、地铁图边上的站名——这类「每个标签都有一个想放的位置」的场景，一旦数据挤成一团，标签就会互相重叠。约束很朴素：相邻标签至少隔开间距 s、全部落在
[pmin, pmax] 内、顺序不能乱；难的是目标——在所有合法摆法里，挑**「被挪得最远的那个标签，挪得最近」**的一种 (minimise the maximum displacement)。
Kate Morley 给出了一个简洁的
解法：把挤在一起的标签看成一个 cluster（一段实际位置恰好两两相隔 s 的连续标签），用四个操作 shift / balance / limit / merge 维护一个 cluster 栈——新标签进入时若与栈顶冲突，就弹栈合并、合并后居中，一遍扫描即得最优解。本页自上而下逐步拆解，每节都可单步观察。
1 · 标签密集时，如何均衡地摆放
每个标签都有一个想放的位置 p（轴上的圆点）：y 轴注记想贴着自己的刻度、时间线说明想贴着自己的事件。标签盒子有高度，所以相邻两个的实际位置至少要隔开间距 s，还都得待在 [pmin, pmax] 里、不能交换顺序。数据一挤，这些诉求就互相冲突——必然有标签要偏离原位。
于是需要决定：让哪个标签偏移、偏移多远？一个合理的目标是均衡——记每个标签的位移
，我们要在所有合法摆法里，把 max |Δ|（偏移最大的那个）压到最小。下面同一组输入、三种摆法并排对比。
左：直接放,q = p 原样照搬——盒子互相压住（红），不合法，这正说明了为什么需要算法。中：顺序下推，从上往下扫，放不下就往下推 q = max(p, 上一个 + s)——合法了，但位移全部累积到挤压区下游的标签。右：本算法 (PLACE)，把一组标签当整体、向两头均摊位移。对比三者的 max |Δ|。
顺序下推为什么不均衡？它永远只往一个方向让路：k 个标签挤在一起时，第一个原地不动、最后一个被推走约
。而最优解会让这一组整体居中——上半部往上移、下半部往下移，max |Δ| 大约减半。试试预设「一团挤在中间」：下推的 max |Δ| 约是 PLACE 的两倍。
合法的前提。n 个标签至少占 的高度，所以必须 才放得下；原文还约定输入已排序且位置为整数（本节输入会自动排序、取整）。cluster 四操作拆解算法的基本构件：cluster 与它的四个操作。
2 · 积木：cluster 与 shift / balance / limit / merge
算法的核心抽象是 cluster：一段「实际位置恰好两两相隔 s」的连续标签——既然挤在一起的标签彼此无法分开，就当作一个整体移动。一个 cluster 只需 4 个字段即可完整描述：首尾位置 start / end（中间成员的位置由 s 推出），加上成员位移的区间
omin / omax（位移 = 实际 − 想放）。
四个操作都只是几行算术：SHIFT 整体平移（四个字段同加一个数）;BALANCE 居中——把位移区间的中点 trunc((omin + omax) / 2) 移回零，使 max(|omin|, |omax|) 最小；LIMIT 越界则拉回 [pmin, pmax];MERGE
合并两个相邻的 cluster——先把上方那个贴到下方那个上侧（相距 s），区间取并集，再 BALANCE。下面单步观察两个标签从「冲突」到「均摊位移」的过程。
**为什么 BALANCE 要「向零取整」？**位移区间是
时，中点 −0.5——四舍五入或向下取整都会平移 1 格：区间变成 (0, 1),max |Δ| 并未改善，却让所有标签多移动了一格。Math.trunc 向零取整得 0，保持原位。只有区间确实偏出一格以上时才值得平移。
**MERGE 之后为什么紧跟 BALANCE?**贴上去的那一刻，上方 cluster 的成员都被推动了一段（位移偏负），下方的仍停在原位（位移 0）——整体偏向一侧。BALANCE 把这段位移平摊到两头：上半部少移一些，下半部分担一些。正是这一步让最终解做到「最大位移最小」，而非顺序下推那样「全部累积到一侧」。
3 · 组装：一个栈 + 一遍扫描 = O(n) 最优解
有了 cluster 四操作，主流程就很简洁：从上往下扫描每个想放的位置，把它包成单元素 cluster。只要它与栈顶间距不足(栈顶.end + s > 新.start)，就弹栈 merge；合并后可能越界，由 LIMIT 拉回；拉回后可能再次与新的栈顶冲突——回到 while
继续合并。直到不再冲突，才把当前 cluster 压栈。
扫描完成后，栈中是一列互不冲突的 cluster；把每个从 start 起按步长 s 展开，即得全部标签的实际位置。下面单步跟随栈的伸缩，右侧栈面板与轴上的虚线包络同步变化。
形式上像 O(n²)，实际是 O(n)。外层 n 个标签，内层 while 看似能把前面所有 cluster 再合并一遍。但关键在于：每个 cluster 一旦被弹栈合并就不再单独存在——它已并入一个更大的 cluster。全程总共只创建 n 个单元素 cluster，每合并一次就减少一个，所以合并次数 ≤ n−1。把所有 while 的迭代累加起来仍是 O(n)——这是摊还分析（与 two-pointer 中「指针不回退」属于同一类论证）。
为什么 LIMIT 之后要回到 while 重新判断？把一个 cluster 拉回 pmax 之内，它的 start 会变小，因而可能重新与新的栈顶冲突（甚至重叠）。所以 merge → limit 必须放在同一个 while 中循环，直到当前 cluster 与栈顶真正分开为止。可用预设「顶部撞 pmin」观察这种连锁反应。
4 · 变宽标签：间距从常数 s 推广到逐对 gaps[i]
PLACE 假定相邻标签恰好相隔常数 s（等高刻度注记）。但很多场景里标签宽度逐个不同——水平轴上长短不一的文字、占比条上方的说明。此时相邻两个的最小间距是逐对的 gaps[i]（label i 与
i+1 的最小距离，通常 = widths[i] + 留白），不再是一个常数。
算法本身几乎不变：cluster 内部成员仍「两两恰好相隔各自的 gap」刚性排布，shift / balance / merge 不依赖 s 可原样复用；只把标量 s 换成数组 gaps、越界 clamp 算上末尾 label 自身宽度即可。仍是一遍扫描
的最大位移最小解。下面用占比条上方的标签演示：每个标签想居中在自己那一段上方，中间几段越窄就越挤，看 PLACE 如何把位移向两端均摊。
上排 各自居中：每个标签都想正对自己那段的中心——窄段上方的标签会互相重叠（红，叠合处更深）。下排 PLACE（变间距）：把挤成一团的标签当整体居中，相邻恰好隔开 widths[i] + 留白；牵引线指回各自所属的段。
复用得这么干净，是因为 balance 和 merge 根本不看 s。balance 只对「位移（实际 − 想放）」居中，merge 里 s 仅用于「把左 cluster 平移到贴住右 cluster」这一步——把它换成那一对的
gap 即可。真正要改的只有展开（positions 按 gaps 累加而非 += s）与越界 clamp（末尾 label 的远端 = end + widths[hi]）。
居中 vs 左对齐。本节标签中心对准段中心，所以 prefs[i] = 段中心 − 宽/2、gaps[i] = widths[i] + 留白。若想让标签左边缘贴齐段首，只需把 prefs[i] 换成段起点，其余不变，placeVariable 本身不用动。
相关链接
- Vertical label placement iamkate.com 本页的出处:Kate Morley 的原文 (CC0),含伪代码与 Rust 参考实现的链接。本页把它翻成 JS 并做成可单步的演示。
- Automatic label placement wikipedia.org 更一般的「自动标签布局」问题(地图制图里的经典难题,二维情形是 NP-hard);本页处理的是它在一维轴上的特例(竖直或水平)——这个特例存在线性时间的精确解。
- two-pointer · 双指针 vega · playground 同属「一遍扫描 + 摊还分析」:PLACE 看似嵌套循环,但每个 cluster 至多被合并一次,总工作量 O(n)——与双指针「i 不回退」是同一类摊还论证。