Squarified Treemap 算法深度解析disktree 如何画出方方正正的磁盘方块图【免费下载链接】disktreeA treemap for finding and removing what fills your disk, for Omarchy. Rust GPUI.项目地址: https://gitcode.com/gh_mirrors/di/disktree磁盘空间被什么占满了du只能给你一长串数字而 disktree 这类 Treemap方块树图工具能把整个目录画成一幅面积即大小的方块马赛克——这正是开源磁盘空间可视化工具 disktree 的核心。它的布局不是简单的切条而是 Bruls、Huizing 和 van Wijk 三位学者提出的Squarified Treemap 算法让每一块都尽量接近正方形告别细长的面条条。本文就用 disktree 的真实源码把这套经典算法的每一步拆开讲清楚。为什么简单的切片切条不够用最朴素的 Treemap 布局是slice-and-dice先切片再切条第一层按大小水平切条第二层对每条垂直切分如此往复。问题在于当某一层里有一个特别大的项和一堆特别小的项时小项会被压成一条条 1~2 像素宽的细丝根本看不清也点不中。⚠️ 注由于本项目仅有一张官方截图上图已用于开头概要下文不再重复引用。Squarified 算法的目标很直白最小化所有方块中最差的那个长宽比aspect ratio让方块尽可能方方正正。Squarified 算法四步拆解算法核心可以浓缩为一句话沿着当前剩余矩形的短边摆一排方块只要最差长宽比还在变好就继续往里塞一旦变差就停手、换边再来。对照 squarify 函数 的实现四步如下第 1 步按值从大到小排序values [6, 6, 4, 3, 2, 2, 1] → 面积各自乘以统一的 scale先算出总面积得到scale 画布面积 / 总值把每个值换算成目标面积再降序排列。大项先摆小项后摆这是效果的关键前提。第 2 步沿着短边开始摆一行观察剩余区域free取它较短的一边side min(宽, 高)剩余区域是宽扁的宽 ≥ 高→ 在左侧切一条竖直窄带方块自上而下叠放剩余区域是高瘦的 → 在顶部切一条水平窄带方块自左向右排开。这一手保证了每排方块都贴着短边生长天然不容易出现长条。第 3 步worst_ratio决定是否继续加块这是算法的灵魂。假设当前行已经排了areas[start..end]行总面积为row_sum那么这一排摆下去的厚度row_sum / side排里每个方块的另一维长度面积 / 厚度每个方块的长宽比 两维的max/min取全排最大值即worst_ratio。接着试探如果再加入下一块算出候选行新的worst_ratio只要它不超过当前值就并入否则立即收手。源码见 worst_ratio 函数 与主循环里的贪心判断treemap.rs#L345-L355while end areas.len(): candidate_worst worst_ratio(候选行, side) if candidate_worst row_worst: # 变差了就停 break一个反直觉的事实这个贪心看起来会变差就回退的策略实际并不会真回退因为 worst_ratio 在行内是单峰的——一旦越过最优点就开始恶化停在最优点即可。第 4 步切掉这一排翻转方向递归剩余区域确定行数后按行总面积算出窄带宽度或高度把每块按面积 ÷ 窄带宽度算出各自的长依次落位随后从free中扣除这条窄带。由于方向随剩余区域形状自动切换竖排 ↔ 横排交替最终拼出一幅像砖墙一样紧凑的马赛克。disktree 的实战细节比教科书多做的几件事算法本身只有 80 行左右但 disktree 在 place_children 函数 里围绕它加了几层工程补丁每一条都对应一个真实的可视性问题细节解决的问题相关源码min_tile最小尺寸默认 5px小于 5 像素的块人眼无法阅读、鼠标也点不中直接丢弃treemap.rs#L244-L246max_children Others 合并默认 96一个目录里 5000 个文件超出上限的尾部合并成一块 Others面积仍被如实计入TileKind::Othersheader 名称带被展开的目录顶部预留一条色带放自己名字子方块全部排到带子下方——父目录名永远不会压在子方块上header_band 函数双层 padding顶层目录间距 3px、内部间距 1px让第一层结构先被读到细节其次LayoutOptions还有一个值得称道的取舍布局在未缩放视口的像素坐标系里跑滚轮缩放和平移只是绘制时套一层变换因此只有目录树、视口尺寸或层级变化时才需要重新布局——缩放到几万块的目录时帧率依然稳定。点击判定同样简单粗暴子方块后于父方块生成、且内缩于父块hit 函数 只要倒序找到第一个包含该点的方块就是最深的那块。用单元测试验证算法正确性算法对不对测试说了算。treemap.rs 的测试模块 用了三组经典断言铺满面积[40, 30, 20, 5, 3, 2]六块在 800×500 画布里总面积误差 1px²且每块都不越界squarify_fills_the_area长宽比上限复现论文经典样例[6, 6, 4, 3, 2, 2, 1]在 6:4 画布上断言所有方块的长宽比 ≤ 4squarify_keeps_aspect_ratios_reasonable退化解不死锁空输入、全零值、零宽画布都能安全返回squarify_survives_degenerate_input。嵌套关系同样有测试兜底layout_nests_children_inside_their_parent 断言每个子方块严格落在父方块内部父块先于子块生成——这正是倒序命中测试能成立的前提。亲手跑起来看看算法讲完了最直观的方式是亲眼看到它。disktree 用 Rust GPUI 编写布局核心全部集中在无 UI 依赖的 disktree-core 中扫描、布局、删除各自独立可测git clone https://gitcode.com/gh_mirrors/di/disktree cd disktree make install # 构建 release 并安装到 ~/.local无需 root需要 Rust 1.97。安装后运行disktree扫描家目录disktree ~/src扫描任意目录[ ]键切换展开层级滚轮向某个目录钻进去——每次缩放后你看到的都是这套 Squarified 算法在短边贪心、按长宽比收手的结果。小结Squarified 的精髓沿短边排行用worst_ratio贪心决定行的长度方向随剩余区域自动翻转工程化补丁最小块尺寸、Others 合并、名称带、像素空间布局让算法从数学上正确变成人眼上好用验证方式面积守恒 长宽比上限 嵌套包含关系三条断言足以钉住一个 Treemap 布局的正确性。下次再看到 KDirStat 风格的方块图时你就知道每个方方正正的色块背后都是一次次再加一块会不会更扁的权衡。【免费下载链接】disktreeA treemap for finding and removing what fills your disk, for Omarchy. Rust GPUI.项目地址: https://gitcode.com/gh_mirrors/di/disktree创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考