wordcloud/docs/ALGORITHM.md

生成算法说明

本文档描述当前代码实际算法。核心代码位于 backend/core/pipeline.py、backend/core/layout.py、backend/core/weights.py、backend/EfficientWordCloud/efficient_wordcloud/src/ewc_core.cpp。

总流程

1. 读取 Excel 名单 → pipeline.main()
2. 智能画幅计算 → mask.calculate_dynamic_dimensions()
3. 生成并归一化掩膜 → mask.prepare_mask()
4. 计算权重 → weights.extract_weights_from_df() + weights.get_stroke_complexity_batch()
5. 估算字号范围 → weights.calculate_font_by_area_model()
6. 小画布布局 → layout.OptimizedEfficientWordCloud.generate_from_frequencies()
7. C++ 按真实字形找位置并原子写入 → IntegralGrid.place_glyph_exact()
8. 二分搜索能容纳全部姓名的最大字号缩放；仍放不下则扩大画布后重排
9. 密度优化 → 探测更大字号并保留完整率不下降的候选
10. 高清精修 → render.refine_layout_with_hd_clearance() 加入隔离带局部微调
11. 输出 PNG / SVG / DB / metrics

名单与重复填充

N_REPETITIONS 决定目标词数：

total_target = len(names) * N_REPETITIONS

布局序列由 _build_layout_sequence() 生成。行为：按原名单循环追加，不是把同一个名字所有副本先放完。

[A, B, C], N_REPETITIONS=4
→ [A, B, C, A, B, C, A, B, C, A, B, C]

同名副本在同一批布局中使用相同目标字号。放置失败不会触发逐词缩字号。

权重逻辑

Excel 权重

• WEIGHT_COL_NAME 优先于 WEIGHT_COL_INDEX
• 有效权重必须是可转数字且大于 0
• REMOVE_DUPLICATES=True 时，同名权重取最大值
• REMOVE_DUPLICATES=False 时，仍按名字聚合成权重映射

笔画权重

• ENABLE_STROKE_WEIGHTS=True 时，系统渲染每个字符到 64×64 灰度图，用像素占用量估算复杂度
• 一个名字的笔画权重取其中最复杂字符的值
• 若同时存在 Excel 权重：Excel 值作为基础权重，笔画复杂度除以全体中位数后作为乘数
• 这样手动权重比例仍保留，且 Excel 权重全为 1 时笔画开关也不会失效
• ENABLE_STROKE_WEIGHTS=False 且无 Excel 权重时，所有名字权重默认为 10

字号范围估算

calculate_font_by_area_model() 使用以下输入估算 min_font / max_font：

• 可填充面积（掩膜中 0 的像素数）
• 目标填充率 TARGET_FILL_RATIO
• 打包效率 PACKING_EFFICIENCY
• 重复次数 N_REPETITIONS
• 名字长度、各名字权重

公式思想：

• 可填区域越大，字号越大
• 名字越多、重复次数越高，字号越小
• 字符越多，总字符质量越高，字号越小
• 权重越高，在 log1p(weight) 归一化后获得更高面积质量

最终 max_font = min_font × SIZE_RATIO。

字号打分

build_log_rank_scores(..., per_word=True) 按姓名权重计算固定分数，映射到展开后的重复序列。结果是：

• 同名副本目标分数相同
• 同名副本初始目标字号相同
• 权重相同时，所有姓名初始目标字号相同

SIZE_RATIO=1 时，min_font == max_font，所有同权重姓名在重试前后都保持完全相同字号。

等字号模式

SIZE_RATIO=1 时，面积估算阶段直接令 min_font = max_font。所有字号重试也只改变单一字号值。

等字号批次的特殊优化：

1. 视作整批同字号布局，使用整批字号打分（per_word=False）
2. 密度优化阶段在完整候选中比较字符级最大空洞（largest_empty_square_size），并尝试不同布局种子降低空洞
3. 高清精修阶段允许优先级回溯（把失败词提前到队列最前）

放置策略

放置顺序按字号分档：大字号先随机撒开，其余再从中心螺旋填充。 大字号需要整片空白才放得下，等螺旋填满画布就没有空间了，因此必须先放。 档内按索引顺序放置，保证同一 layout_seed 完全可复现。

每个词的放置流程：

1. 根据目标分数得到目标字号（线性插值于 min_font 到 max_font）
2. 逐词独立随机决定横排或竖排，竖排概率为 VERTICAL_RATIO（流水线以此换算 prefer_horizontal = 1 - VERTICAL_RATIO）； 当前竖排为整词旋转 90°（字符侧倒），不是字符直立的传统竖排
3. 用 PIL 渲染真实字形 bitmap，施加单侧安全边距（margin）生成碰撞 mask
4. 调用 C++ place_glyph_exact() 搜索合法位置并原子写入
5. 当前方向找不到时，只尝试同字号的另一方向
6. 任意姓名失败即视为本次整批布局不完整
7. 不逐词缩字号。Python 统一缩放整批字号范围后重新布局
8. 触及字号下限仍失败时，按 CANVAS_RETRY_GROWTH 扩大画布并整批重排
9. 将完整布局映射到高清字号和坐标
10. 高清画布进行逐词隔离带精修，局部无合法位置时扩大画布并整批重排

C++ 真实字形搜索

IntegralGrid 维护两个核心结构：

• canvas：真实占用像素（1 表示已占用或掩膜阻挡）
• data：兼容旧矩形查询的积分图；当前主路径不依赖逐词重建

place_glyph_exact() 有三种放置模式，由 layout.py 按字号分配：

大字号（placement_mode=2）：字号达到 min_font + (max_font - min_font) * 0.80 的姓名先放，随机探测取第一个合法位置。 探测受一个软半径约束：前 75% 次探测限制在质心周围 0.55 → 1.0 倍掩膜半径内，之后放开。 约束只影响落点偏好，不会排除任何合法位置，因此不影响完整率。 等字号批次中 max_font == min_font，不存在大字号档，全部走螺旋。

小字号（placement_mode=1）：先试可填区域质心，再沿费马螺旋（黄金角 2.39996，radius = 1.25 * sqrt(step)）向外搜索。 spiral_cursor 在整批姓名间持续推进。每个词以随机相位 theta_offset ∈ [0, 2π) 起扫， 使相邻两词的角距不再恒为黄金角；随机量取自按 layout_seed 派生的逐词种子，同一种子完全可复现， 不同种子给出真正不同的排布，而不只是同一图形换名字。

相位必须取满整圈。曾尝试限制在 ±60° 的窄扇区内，结果明显更差： 扇区会让词跳过边界上已经合法的位置而退到更差的位置，实测 800 词的最终墨水密度下降 31%（0.255 → 0.176）。 取满整圈则不损失密度，因为半径增长时扫描本来就会覆盖所有角度。

注意这并不会让排布显得无序：半径仍与放置顺序高度相关（Pearson r ≈ 0.98）。 中心向外且保持紧密的填充必然按半径递增推进——「有序」与「紧密」是同一件事。 要在不牺牲密度的前提下打散这种观感，需要多个螺旋原点，而不是在单一螺旋上加抖动。

兼容模式（placement_mode=0）：纯随机探测，取第一个合法位置。

三种模式共用后续步骤：

1. 随机探测失败后，从种子决定的偏移开始环形完整扫描，保证存在合法位置时一定能找到
2. 对每个候选位置逐像素比较碰撞 mask 与 C++ canvas
3. 命中后只写入真实字形，占位查询和写入在同一次 C++ 调用中完成

真实字形搜索允许透明角落和笔画间空隙安全交错，比外接矩形碰撞更密。安全边距只参与候选检查，不会被双侧累计放大。

高清精修（隔离带）

正式流水线不在低清工作网格增加边距，因为 1 个工作像素会被放大成约 5–6 个高清像素并显著损失容量。

隔离带优先作用在最终高清画布，宽度为 1px，不是用户参数。精修流程：

1. 小画布完整布局放大到高清
2. 逐词在高清画布上验证，加入 1px 隔离带
3. 碰撞时先在 max_shift=24px 内做局部微位移
4. 邻域内无解时，_find_free_placement() 以逐步放大的窗口（256 → 1024 → 全画布）在整张画布上找空位， 取离原位置最近的一个。窗口内用积分图筛选：足迹范围内完全空白的位置必定可放， 无需逐像素比较，因此绝大多数候选位置只花两次加法就被排除。 这一步把「一个词放不下就整条流水线换更大画布重来」变成一次局部搬移—— 后者是全流程中最贵的失败路径，实测会让端到端耗时翻倍且仍可能最终失败
5. 精修失败时，最多进行 1 次确定性整批优先级回溯（把失败词移到队列最前）
6. 若轮廓过窄无法容纳额外隔离带，降为精确零间隙碰撞（clearance=0）
7. 全部候选无解时，才由外层扩大画布后整批重新布局

密度搜索会保留各档完整整批候选。最高密度候选若无法在有限位置修正范围内通过高清隔离验收，则改用上一档完整整批候选；不会对碰撞姓名单独缩字号，也不会接受带重叠的高密度结果。

字号缩放二分搜索

目标是找到能放下全部姓名且轮廓覆盖最好的字号缩放。单纯追求最大字号会让费马螺旋把词压在质心圆盘内、走不到掩膜远端，于是非圆形掩膜（心形尖端、人物四肢）填成圆形。

流水线用「探测」来判定某个缩放是否可行。探测在遇到第一个放不下的姓名时立刻停止： 一个姓名只有在螺旋、随机探测和全画布穷举扫描都失败后才算放不下，所以单个失败即可证明该缩放不可行， 不必把整批跑完。这一点对速度至关重要——放不下的姓名要付出完整搜索的代价， 实测约为可放下姓名的 10 倍，把注定失败的整批跑到底是流水线中最昂贵的操作。 OptimizedEfficientWordCloud.max_failures 控制这一行为，为 None 时跑满整批并尽量多放。

搜索过程：

1. 从 scale=1.0 开始探测；失败则按 sqrt(已放置比例) 收缩再试，最多 4 次
2. 得到一个可行值后，在最大失败值与最小可行值之间二分最多 3 次，把之前收缩让掉的字号找回来
3. 相邻两个缩放取整后字号相同时停止——工作网格上字号是小整数，再细分没有意义
4. 多个可行结果中取形状覆盖度最高的那个（compute_coverage_score），覆盖度并列时才取缩放更大者

形状覆盖度

compute_coverage_score() 把可填区域切成 8×8 像素的块，只统计可填像素占比 ≥ 30% 的「区域块」，计算其中被墨迹触达的比例：

coverage = 被触达的区域块数 / 区域块总数

这是「轮廓是否被填出来」的直接度量：质心圆盘只触达中心几块，覆盖度低；铺进掩膜每个臂/尖端的布局触达各块，覆盖度高。块粒度（而非逐像素加权）让它对掩膜几何稳健——一个尖端无论宽 3px 还是 30px 都是一个块，触达它都被同等奖励。

填充率重试

一次布局完成后，compute_fill_ratio_fast() 重新渲染 layout 并计算填充率，compute_coverage_score() 计算形状覆盖度。

• 面积模型首次完整放入但明显低于 TARGET_FILL_RATIO 时，进入双向密度优化：每轮同时探测「加大字号」和「减小字号」两个方向，取覆盖度更高的候选。减小字号让费马螺旋走更远、触达掩膜远端，即使填充率略降也能提升覆盖度——这正是纠正「填成圆形」的关键方向。覆盖度与填充率都无提升时停止
• 整批未完整放入时，流水线不会输出半成品：先整批等比例调整字号；触及最小字号仍失败时按 CANVAS_RETRY_GROWTH 扩大画布并重新生成

字号硬约束

• 不存在逐词缩字号、gap filling 或大字号自动压缩路径
• USER_MIN_FONT_SIZE 和 USER_MAX_FONT_SIZE 是不可越过的边界；冲突时直接报错
• SIZE_RATIO=1 在面积估算、整批重试和高清放大阶段始终保持单一字号
• 完整名单不可关闭；放不下时只能整批重排、整批等比例调整或扩大画布

空洞优化（等字号模式）

等字号模式下，字符级最大空洞（largest_empty_square_size）用于判断是否存在"可放字符级空洞"：

• 当前 largest_empty_square ≥ ceil(font_size * 1.25) 时视为存在字符级空洞
• 流水线会在同一字号档位尝试最多 3 种不同布局种子（按人数递减预算）
• 目标是最小化最大空洞尺寸，不改变任何字号

自动画幅

calculate_dynamic_dimensions() 先对 BASE_HD_WIDTH × BASE_HD_HEIGHT 做一次 probe 掩膜，计算可填比例 free_ratio，再用以下公式扩展：

area_per_word = (MIN_READABLE_HEIGHT_PX²) × avg_len × 1.05
required_area  = num_words × area_per_word × N_REPETITIONS / TARGET_FILL_RATIO
required_area /= free_ratio
scale_factor   = √(required_area / current_area)
new_w = clamp(base_w × scale_factor, max_edge=6000)

• 扩展后宽高向上取整到最近的 100
• 最大边长限制为 6000px，避免 SVG/PNG 过度膨胀
• 掩膜只生成一次，扩展后复用

性能：按字符缓存

一份中文名单里不同字符的数量远小于不同姓名的数量——750 个三字姓名通常只含约 34 个不同字符。 两处最重的工作因此按字符而不是按姓名缓存：

• SVG 轮廓（layout._char_shape）：每个 (字符, 字号, 方向) 只取一次字形轮廓并格式化一次路径字符串。 一个姓名由若干字符路径拼成，字符在词内的位置放进元素的 transform 平移量， 所以缓存的路径字符串被逐字节复用，不需要重新解析或平移坐标。 导出时每个字形输出一个 <path>，几何结果与整词单路径完全一致（已逐点验证）。
• 高清字形位图（render._word_ink）：隔离精修与独立的重叠审计会在相同字号下光栅化相同姓名， 两者共用一份缓存。

_path_bbox() 只在每个字符首次构建时调用一次，词的包围盒由各字符包围盒平移后取并集算出， 不再对生成好的路径字符串做正则重解析。

零重叠保证

输出前 count_layout_overlap_pixels() 会独立重渲染整个 layout 并统计被两个及以上词占用的像素。 该值必须为 0，否则 placement_ok 为假，流水线拒绝输出而不是交付带重叠的结果。 这项校验独立于隔离精修，即使精修逻辑有误也能兜住。