一行文本该落在哪里？详解Combo Breaker的findFlowSlots槽位搜索算法-育师

一行文本该落在哪里？详解Combo Breaker的findFlowSlots槽位搜索算法

【免费下载链接】combo-breakerText layout for Compose to flow text around arbitrary shapes.项目地址: https://gitcode.com/gh_mirrors/co/combo-breaker

Combo Breaker是一款为 Jetpack Compose 打造的文字排版库，核心能力是让文本自动环绕任意形状（矩形、Path 轮廓甚至位图抠出的曲线）进行多栏布局。它的灵魂函数findFlowSlots负责回答一个关键问题：当前这一行文字，到底能放在哪些矩形区域（"槽位"）里？下面用通俗的方式拆解这套槽位搜索算法，带你快速理解文字绕图排版的底层逻辑。

一、问题背景：为什么需要"槽位"？

普通文本控件的假设很简单：每一行都是等宽的长方形，从左写到右。但一旦页面里插入了图片、徽标或装饰图形，一行文字就被切成了0 个、1 个或多个不等宽的碎片。

Combo Breaker 的排版流程把这件事拆成两步：

几何阶段：findFlowSlots根据形状算出这一行的所有可用矩形槽位；
断行阶段：逐槽位调用 ICU LineBreaker 计算能塞进多长的文字。

理解第一步，就理解了整个库 80% 的核心。

二、算法输入与输出

主入口在 FlowSlots.kt：

findFlowSlots(box, container, flowShapes) → List<RectF>

box：当前这一行文字的区域（一个横条矩形）；
container：整个栏的外边界（多栏排版时与 box 不同）；
flowShapes：所有需要绕开的形状列表，每个形状带有Path轮廓和FlowType（允许文字从哪侧流过）；
返回值：按 left 坐标排序的可用槽位矩形列表，空列表 = 这一行完全放不下文字。

三、槽位搜索的 4 个核心步骤

步骤 1：快速排除无关形状

对每个形状先用 quickReject 做 O(1) 检查：形状整体在行的上方/下方、或FlowType.None（完全不参与排版），直接跳过。绝大多数行只需要处理 1~2 个形状，这一步省掉大量无用功。

步骤 2：区间树查找与当前行相交的线段

任意Path轮廓在创建 FlowShape 时就被预先处理好了：

Path.toIntervals() 把曲线展平成一条直线段序列（容差 1px）；
每条线段按纵向范围（y0~y1）插入一棵红黑区间树。

于是"哪些线段穿过当前这一行"变成一次高效的区间重叠查询：

flowShape.intervals.findOverlaps(行区间, intervals)

这正是算法的"搜索"所在——用空间索引代替逐点扫描，复杂轮廓也能保持每行 O(log n) 级别的查找开销。

步骤 3：裁剪并求出形状的左右极值

命中的线段用 clipSegment（Liang-Barsky 裁剪）约束到行内后，取所有端点的 x 最小/最大值：

shapeMin= 本行内形状最左位置；
shapeMax= 本行内形状最右位置。

这两个数就是槽位的天然分界线：box.left ~ shapeMin是左侧安全区，shapeMax ~ box.right是右侧安全区。

步骤 4：生成槽位并做交集收缩

核心在 addReducedSlots，它按形状的FlowType决定左侧、右侧还是双侧生成候选槽位，并与已有槽位做水平交集。源码注释里的示意图非常形象：

XX ________ 右侧流动形状 → 生成左侧槽位 XX | | XX ---------- 加上左侧流动形状后，两个槽位被交集收窄： XX __________ ____ XX | | XXX | | XXX XX -------- XXX ---- XXX

直觉上：每加入一个形状，就是往现有空白上"打一个洞"，剩下的连通矩形就是槽位。若某候选槽位不与任何已有槽位重叠，则直接新增。

四、排除区规则：FlowType 如何限制文字流向

槽位生成后还要执行 applyFlowShapeExclusions，这是"文字该绕哪边"的执法环节：

FlowType	行为
`OutsideLeft`	所有槽位的右边界收缩到`hit.min`，右侧区域禁止放字
`OutsideRight`	所有槽位的左边界推后到`hit.max`，左侧区域禁止放字
`Outside`	双侧放行，槽位落在形状范围内则直接清空

FlowType 枚举还定义了OutsideStart/OutsideEnd（随 LTR/RTL 方向自动解析）和None。排除区是全局生效的——即使别的形状允许在某个区域放字，一个OutsideLeft形状也能把那里变成禁区。

如果所有形状都被排除、没有任何线段命中，算法退化为最安全的行为：整行 box 本身就是一个槽位。

五、从槽位到成行：结果如何驱动文字排版

回到调用方 TextLayout.kt：每渲染一行，就取y ~ y + lineHeight的横条去查槽位，然后按 left 从小到大遍历：

用槽位宽度作为 LineBreaker 的约束宽度重新计算断行；
若某槽位太窄放不下一行，跳过它（下一行可能又能利用）；
把文字段画进槽位，继续下一个槽位，直到整行排满。

所以一行文字可以被拆成"左窄条 + 右侧长段"这样多段渲染——这就是多栏绕图效果的全部秘密。

六、性能设计亮点：零分配复用

注意findFlowSlots的最后一个参数 FlowSlotFinderState：槽位列表、区间列表、临时点全部预分配，跨行调用只做clear()复用。因为该函数每行都会被调用一次，避免 GC 压力对流畅滚动的长列表至关重要。

七、相关文件导航

文件	职责
FlowSlots.kt	槽位搜索主算法与排除区
IntervalTree.kt	红黑区间树，线段快速检索
FlowShape.kt	形状 + 区间树 + 包围盒封装
Geometry.kt	Path 展平为线段并建树
Clipping.kt	线段裁剪
BasicTextFlow.kt	FlowType 定义与多栏槽位汇总
TextLayout.kt	逐行调用 findFlowSlots 完成排版