利用同质性进行可行性驱动的多边形填充

对 Vanilla Sparrow 求解器的扩展

首先，我要感谢 Kaggle 举办了这样一场充满挑战却又精彩的比赛，并向 Jeroen Gardeyn 致敬（他是 sparrow 的作者，顺便提一下，他也参加了本次比赛并排名第 6），感谢他开发了如此精致而强大的求解器包。

这里提出的解决方案很大程度上是原版 sparrow 求解器的扩展，专门针对本次比赛中的同质设置（所有物品都是相同的简单多边形）。主要主题是： aggressively 利用同质性——在碰撞评估、种子生成和候选生成中。

本求解器的亮点（作为对原版 sparrow 的补充）：

1. 使用 SAT LUT（加上 AABB 早期拒绝）的快速碰撞严重性内核。
2. 低差异 + 硬核稀疏化 (Low-discrepancy + hard-core thinning) 以生成更好的可行种子（快速早期进展）。
3. 模体挖掘 (Motif mining)：显式地学习并重用重复的局部模式（结构重用）。

---

问题回顾与指标

对于每个组大小 \(N\)，你必须放置 \(N\) 个相同的“圣诞树”多边形（平移 + 旋转），要求无重叠（允许接触），评分依据是并集的最小轴对齐包围正方形的面积除以 \(N\)。总分是所有组的总和。具体来说，对于组 \(N\)：

• 计算并集边界 \([x_{\min}, x_{\max}] \times [y_{\min}, y_{\max}]\)
• 令 \(S_N = \max(x_{\max}-x_{\min},\, y_{\max}-y_{\min})\)
• 最终：\(\text{score} = \sum_N \text{score}_N\)，其中 \(\text{score}_N = S_N^2 / N\)

官方指标还要求：无重叠（但允许接触），且 \(x,y \in [-100,100]\)。

---

基线：Sparrow 框架及其为何适合此任务

基线框架继承了 Sparrow 的核心思想：与其直接在硬非重叠约束下优化组合/连续目标，不如在 (a) 缩小容器（或以其他方式收紧目标）和 (b) 通过暂时允许重叠并迭代地“分离”物品直到恢复可行性来解决诱导的可行性问题之间交替进行。这是有效的，因为可行区域极其受限：纯粹的可行到可行局部移动通常无法取得有意义的进展，而受控的不可行性 excursion 允许在遥远的可行配置之间遍历。Sparrow 明确提出了这种松弛策略，并将其组织为探索和压缩阶段。

在每个缩小步骤中，核心子程序是一个分离过程：

• 为当前配置 \(\mathbf{s}\) 维护一个标量“不可行性”度量 \(e(\mathbf{s})\)，由碰撞严重性之和（以及可能的墙壁违规）形成。
• 重复选择碰撞物品，并通过在容器周围/内部采样候选变换来搜索改进的位置。
• 使用引导式局部搜索 (GLS)：持久或严重的碰撞获得增加的权重，这逐渐迫使搜索解决它们或执行破坏性移动以逃离局部最小值。Sparrow 详细描述了这种机制，并强调了为什么连续碰撞严重性对于指导至关重要。

这个基线在许多不规则条带填充问题上已经表现非常出色，但同质实例暴露了两个瓶颈：

1. 几何成本占主导地位：重复评估相同形状之间的碰撞严重性成为主要的运行时开销。
2. 缺乏“规律性重用”：在同质设置中，好的解决方案通常由多次重复的小簇组成，而 Sparrow“缺乏重复它们的机制”，限制了其利用这种结构的能力。

本写作的其余部分侧重于直接解决这些瓶颈的三个补充。

---

1) 碰撞（严重性）内核：专用于一个多边形的 SAT LUT

动机

Sparrow 的分离循环需要一个碰撞严重性信号——连续的、廉价的，且“足够好”以指导搜索。它不需要是真实的有符号距离。Sparrow 论文明确指出，许多有效的碰撞量化器本质上是1D 指标（“穿透深度导数”）。它还指出，取平方根可以将“类面积”的重叠代理转换为类 1D 指标。因此，这里的目标是：为这一个树形形状构建一个极快的类 1D 严重性指标。

关键思想：预计算你能预计算的一切（同质性！）

因为每个物品都是相同的多边形：

• SAT 轴集是固定的（直到旋转）。
• 两个树之间的相对方向是离散的（我们使用固定数量的角度箱，例如 4096）。
• 因此，我们可以构建一个由相对角度索引的投影查找表。

SAT LUT 包含的内容（实现要素）

1. 4 部分凸分解
   原始树多边形是凹的，但它可以分解为 4 个凸部分（层 + 树干）。这使得 SAT 便宜且鲁棒，因为：

   • 凸 SAT 很简单，
   • 我们可以使用部分 AABB 早期拒绝部分对。

2. 唯一法线集（约 8 个轴）
   从凸部分提取唯一的边法线，归一化 + 去重。

3. 按相对角度的投影 LUT
   对于每个相对角度箱 \(\Delta a\)，以及每个部分和轴，预计算区间：

   \[ [\min_{v \in \text{part}} u\cdot v,\; \max_{v \in \text{part}} u\cdot v] \]

   因此在运行时，我们只应用来自平移的偏移。

• AABB 早期拒绝

  • 树级 AABB 拒绝
  • 在该部分对上执行 SAT 之前的每部分 AABB 拒绝

运行时严重性："SAT 违规”作为平滑的 1D 惩罚

对于部分对和测试轴 \(u\)，你在应用平移偏移后计算投影区间的重叠；如果任何轴分离，则该部分对没有碰撞。

在代码中（简化自 convex_parts_violation_sat + trees_severity），关键是：

• 计算重叠 \(= \min(\text{hi}) - \max(\text{lo})\)
• 添加 eps_gap 以便你可以要求小的分离余量
• 如果 v <= 0：分离
• 否则 v 是该部分对的“穿透式缺陷”

然后使用可选择的范数聚合所有违规部分对：

• L1 (和), L∞ (最大), L2 (RSS), L4 (平滑最大)

在实践中，发现在我们的设置中 L1 比其他更有效。

代码摘录 (SAT LUT 构建 + 严重性)

// (1) 为所有相对角度预计算投影，每部分对和轴。
for rel in 0..sat.k {
    let d = (rel as Real) * sat.step;
    let (cd, sd) = d.cos_sin();

    for pb in 0..K_PARTS {
        for pa in 0..K_PARTS {
            for k in 0..sat.axes {
                let ax = sat.axis_local[k as usize];
                let wx = cd.mul_add(ax.x, -sd * ax.y);
                let wy = sd.mul_add(ax.x, cd * ax.y);

                // 将 B (旋转 rel) 投影到 A 的轴 k 上
                let (mn, mx) = interval_for_axis(&sat.part_verts[pb], wx, wy);
                sat.proj[row + pb * axes + k] = Interval { mn, mx };
            }
        }
    }
}

// (2) 运行时：对于每个重叠的部分对，找到最小轴违规 (SAT 缺陷)
if let Some(v) = convex_parts_violation_sat(...) {
    match sat.severity_agg {
        SatSeverityAgg::L1 => acc += v,
        SatSeverityAgg::Linf => acc = acc.max(v),
        // ...
    }
}

---

2) 初始放置的低差异种子 (QMC + 硬核稀疏化)

动机：让第一次缩小“美好”

直观地说，当缩小容器后，诱导的不可行性如下时，sparrow 效果最好：

• 分散的（许多小重叠），
• 不太深（避免极端纠缠），
• 局部可解决的。

随机种子倾向于产生：

• 团块 + 大空洞，
• 第一次缩小后的深度互锁，
• 以及大量浪费的分离工作。

因此，想法是使用低差异流来快速获得均匀覆盖，但硬可行性（无重叠）是首选，因为求解器假设从可行开始。

实际“混合”想法，数学上连贯：

1. 生成低差异流 \(u_k \in [0,1]^2\)。

2. 映射到正方形：

   \[ p_k \in [-L/2, L/2]^2 \]

3. 仅当 \(p_k\) 距离所有先前接受的中心至少 \((2R+\eta)\) 时才接受 \(p_k\)：

\[ \|p_k - p_i\|_2 \ge 2R + \eta \]

这是泊松圆盘/硬核稀疏化。

如果你还需要方向，将变换视为 3D：

\[ (x,y,\theta)\in [-L/2,L/2]^2 \times \Theta \]

并在 \([0,1]^3\) 中使用低差异集，其中第三个坐标选择离散角度桶。由此产生的一个想法是，从一开始就强制同质角度模仿了大 \(N\) 通常青睐的“晶格”模式。但伪随机角度初始化目前来说已经足够好了。经验上，这改善了早期收敛：求解器花更少的时间“解开混乱”，更多时间收紧。我还单独分析了“差异与空间填充”的权衡（主要思想：硬核过滤器破坏了完美的 QMC 结构，但你保留了很多均匀性，同时改善了覆盖率和可行性）。

实现：Owen 打乱的 Sobol + 距离过滤器

在代码中，这是作为 CPU 方法 LdsHybrid 实现的：

• 使用 Owen 打乱的 Sobol 点 (sobol_burley) 作为低差异生成器。

• 从树顶点计算保守的“边界圆半径” \(R\)。

• 强制执行最小间距：

  \[ \text{min\_sep} = 2R + \text{eps\_gap} + \eta \]

• 如果在 max_samples 后未能放置所有树，我们用稍大的边 (side_growth) 重启，最多 max_restarts 次。

代码摘录 (核心种子循环)

let r = tree_bounding_radius(sat);
let gap = solver.search.eps_gap.max(0.0);
let eta = p.eta.max(0.0);
let min_sep = 2.0 * r + gap + eta;
let min_sep2 = min_sep * min_sep;

for _ in 0..p.max_samples {
    let [u0, u1, u2] = seq.next3();
    let x = (u0 * 2.0 - 1.0) * half;
    let y = (u1 * 2.0 - 1.0) * half;

    // 硬核过滤器
    if poses.iter().any(|q| (x-q.x).powi(2) + (y-q.y).powi(2) < min_sep2) {
        continue;
    }

    // 来自第三个坐标的离散角度
    let ai = ((u2 * (m as Real)) as usize).min(m - 1);
    set_angle_idx(&mut pose, allowed_angles[ai], sat);

    poses.push(pose);
    if poses.len() == n { return poses; }
}

---

3) 模体挖掘：显式学习并重用重复的局部结构

动机 (这是那个同质性技巧)

Sparrow 自己的论文指出了同质实例上的一个“盲点”：

“它缺乏重复它们的机制”

在同质填充中，好的解决方案通常由以下组成：

• 少量紧密的局部簇，
• 以相同的相对变换重复多次。

因此，与其希望求解器“偶然”在各处重新创建相同的微观结构，我添加了一种机制来挖掘重复的局部变换并在采样期间将它们注入为候选提议。

模体表示 (便携式构建块)

模体是从锚树 \(j\) 到邻居 \(i\) 的相对变换，在锚的局部帧中表示：

• 相对平移：

  \[ \begin{aligned} \Delta x &= \cos\theta_j (x_i-x_j) + \sin\theta_j (y_i-y_j) \\ \Delta y &= -\sin\theta_j (x_i-x_j) + \cos\theta_j (y_i-y_j) \end{aligned} \]

• 相对角度 (离散箱)：

  \[ \Delta a = a_i - a_j \quad \text{(wrapped)} \]

这种“锚局部”选择很重要：

• 模体不绑定到全局轴，
• 它们在模式级别是旋转不变的，
• 它们可以干净地转移到任何其他锚。

挖掘模体 (局部模式的廉价直方图)

在 solver/sampling.rs::mine_motifs 中：

• 对于每个锚 \(j\)，从宽相网格查询附近的候选（不是 \(O(n^2)\)）。
• 保留 motif_neighbors 个最近的邻居（近似 KNN）。
• 将 \((\Delta x,\Delta y)\) 量化为大小为 motif_bin_xy 的箱，并可选地通过 motif_bin_da 量化 \(\Delta a\)。
• 构建以 (qx, qy, da) 为键的直方图。
• 保留前 motif_max 个箱（优先选择计数 ≥ motif_min_count 的箱）。
• 存储每个箱的平均 dx/dy（减少量化偏差）。

在采样期间使用模体 (结构化候选)

模体作为单独的候选家族注入 (t_motif 每个移动的样本)， alongside：

• 多样化 (均匀)，
• 聚焦 (当前周围的高斯)，
• 基于接触的提议，
• 仅角度和微平移逃逸。

在移动树 idx 期间：

• 选择一个锚邻居 j (偏向碰撞锚)

• 要么：

  • 将当前相对变换“匹配”到最佳模体 (motif_p_match)，或
  • 按频率加权采样模体

• 实例化：

  \[ p_i \leftarrow p_j \oplus (\Delta x,\Delta y,\Delta a) \]

• 可选地抖动并拒绝，如果容器夹紧会过度扭曲它 (motif_clamp_reject_eps)

• 评估能量，保留顶级候选，然后细化

代码摘录 (挖掘 + 提议)

挖掘关键循环 (修剪)：

// 对于每个锚 j，从网格查询中保留 k 个最近的邻居，
// 并在锚局部坐标中对相对变换进行直方图统计。
for j in 0..n {
    // 在扩展的 AABB 中查询网格，按 r^2 保留 k 个最近的
    // ...
    for &(_, i) in knn.iter() {
        let dxl = pj.cosv.mul_add(dxw, pj.sinv * dyw);
        let dyl = (-pj.sinv).mul_add(dxw, pj.cosv * dyw);
        let qx = (dxl / bin_xy).round() as i32;
        let qy = (dyl / bin_xy).round() as i32;
        let da = quantized_angle_delta(pi.a, pj.a, motif_bin_da);

        let e = hist.entry((qx, qy, da)).or_default();
        e.cnt += 1;
        e.sum_dx += dxl;
        e.sum_dy += dyl;
    }
}

提议注入 (修剪)：

let anchor_idx = pick_anchor(&anchors, &colliding_anchors, rng, prefer_colliding_p);
let pj = sol.poses[anchor_idx];

// 选择模体：匹配 vs 加权随机
let m = if rng.uniform01() < motif_p_match { best_match(...) }
        else { extras.pick_motif_weighted(rng) };

let new_a = pj.a.wrapping_add(m.da as u32);
set_angle_idx(&mut p, new_a, sat);

// 锚局部 (dx,dy) -> 世界
let dxw = pj.cosv.mul_add(m.dx, -pj.sinv * m.dy);
let dyw = pj.sinv.mul_add(m.dx, pj.cosv * m.dy);
p.x = pj.x + dxw;
p.y = pj.y + dyw;

---

这三个想法在实际求解器循环中如何配合

查看最终求解器的一种实用方式是：

• 引导 一个可行种子 (LDS 混合)。

• 重复：

  • 缩小 容器边一点

  • 运行 分离：移动碰撞物品直到可行（或停滞）

  • 每个移动使用候选采样：

    • 随机 (多样化/聚焦)
    • 结构化 (模体/接触)
    • 逃逸移动 (仅角度 / 微平移)

  • 每个候选由快速加权能量评分：

    \[ E = \sum_{\text{walls}} w_{\text{wall}} \cdot v_{\text{wall}} \;+\; \sum_{j \in \text{neighbors}} w_{ij} \cdot \text{sev}(i,j) \]

    其中 sev(i,j) 是 SAT-LUT 严重性。

总之，SAT LUT 是使这一切变得负担得起的“引擎”；LDS 种子使前几次缩小表现良好；模体挖掘有助于在整个布局中维持/重现结构，而不是从头开始重新发现它。