如何简化任意维度下[0,1)^d环绕盒的分割实现？

我们需要处理带环绕特性的[0, 1)^d盒（每个维度满足1 + .05 = .05的循环运算规则）：给定[0,1)^d内的点x，以及取值范围0 < ε < 0.5的常数ε，要生成原始盒（最小顶点为x - (ε, ..., ε)，最大顶点为x + (ε, ..., ε)）经环绕后，所有落在[0,1)^d内的子盒集合。

当d=2时共有9种情况：黑色小矩形是由x和ε生成的原始盒，红色矩形是经环绕处理后得到的子盒。

你当前的实现针对d=2逐个分支处理，逻辑复杂且无法扩展到更高维度。以下是通用化的简化方案：

核心思路 #

每个维度的区间状态是独立的：对于任意维度i，原始区间[x_i - ε, x_i + ε]经环绕后只会有1段或2段有效区间（因ε < 0.5，不会出现跨0和1同时覆盖整个[0,1]的情况）。最终所有子盒就是各维度有效区间的笛卡尔积——每个维度选一段区间，组合起来就是一个合法的子盒。

通用实现代码 #

#include <vector>
#include <cassert>
#include <boost/geometry/model/box.hpp>
#include <boost/geometry/model/point.hpp>

namespace bg = boost::geometry;

// 定义d维点和盒类型
template<typename T, std::size_t D>
using Point = bg::model::point<T, D, bg::cs::cartesian>;
template<typename T, std::size_t D>
using Box = bg::model::box<Point<T, D>>;

// 计算单个维度的有效区间段
template<typename T>
std::vector<std::pair<T, T>> get_dimension_intervals(T x_i, T epsilon) {
    std::vector<std::pair<T, T>> intervals;
    const T low = x_i - epsilon;
    const T high = x_i + epsilon;

    if (low >= 0 && high < 1) {
        // 区间完全落在[0,1)内，仅一段
        intervals.emplace_back(low, high);
    } else if (low < 0) {
        // 区间左边界跨0，拆成[0, high]和[1+low, 1]两段
        intervals.emplace_back(T(0), high);
        intervals.emplace_back(T(1) + low, T(1));
    } else if (high >= 1) {
        // 区间右边界跨1，拆成[low, 1]和[0, high-1]两段
        intervals.emplace_back(low, T(1));
        intervals.emplace_back(T(0), high - T(1));
    }
    return intervals;
}

// 递归生成所有维度区间的笛卡尔积，构造子盒
template<typename T, std::size_t D>
void generate_boxes(
    const std::vector<std::vector<std::pair<T, T>>>& all_intervals,
    std::size_t current_dim,
    Point<T, D>& curr_min,
    Point<T, D>& curr_max,
    std::vector<Box<T, D>>& result
) {
    if (current_dim == D) {
        // 所有维度处理完毕，添加当前盒到结果
        Box<T, D> box;
        box.min_corner() = curr_min;
        box.max_corner() = curr_max;
        result.push_back(box);
        return;
    }

    // 遍历当前维度的所有区间段，递归处理下一个维度
    for (const auto& interval : all_intervals[current_dim]) {
        curr_min.set<current_dim>(interval.first);
        curr_max.set<current_dim>(interval.second);
        generate_boxes(all_intervals, current_dim + 1, curr_min, curr_max, result);
    }
}

// 对外接口：获取所有环绕后的子盒
template<typename T, std::size_t D>
std::vector<Box<T, D>> get_wrapped_boxes(const Point<T, D>& x, T epsilon) {
    assert(epsilon > T(0) && epsilon < T(1)/2);

    // 收集每个维度的有效区间
    std::vector<std::vector<std::pair<T, T>>> all_dim_intervals;
    for (std::size_t i = 0; i < D; ++i) {
        all_dim_intervals.push_back(get_dimension_intervals(x.get<i>(), epsilon));
    }

    std::vector<Box<T, D>> result;
    Point<T, D> current_min, current_max;
    generate_boxes(all_dim_intervals, 0, current_min, current_max, result);

    return result;
}

代码说明 #

1. 维度区间计算：get_dimension_intervals函数根据单个维度的x_i和ε，生成该维度的所有有效区间段，逻辑简洁且利用ε < 0.5的条件避免了冗余判断。
2. 笛卡尔积生成：generate_boxes通过递归遍历所有维度的区间组合，自动生成所有合法子盒，无需硬编码任何维度相关的分支。
3. 通用接口：get_wrapped_boxes作为对外入口，支持任意维度d，只需传入对应维度的点和ε即可返回所有子盒。

内容的提问来源于stack exchange，提问作者0xbadf00d