考虑盒子[0,1)^d环绕;例如在每个维度上为1 + .05 = .05
。
给定[0,1)^d内的一个点x
和一个正常数epsilon
(0到.5之间),我想得到[0,1)^d内所有“盒子”的向量,这些盒子是通过用最小角x - (epsilon, ..., epsilon)
和最大角x + (epsilon, ..., epsilon)
包裹盒子而产生的。
我认为一张照片帮助很大;这里是d = 2
的情况:
这里我们有9个例子,黑色的小矩形是由x
和epsilon
组成的;红色的是从环绕中产生的框。
我可以编写如下代码(我使用的是boost中的box模型,但这并不重要):
template<typename T>
void foo(point<T, 2> const& x, T const& epsilon)
{
assert(0 < epsilon && epsilon < T(1) / 2);
std::array<boost::geometry::model::box<point<double, 2>>, 4> boxes;
std::size_t box_count{};
if (x[0] - epsilon < 0)
{
if (x[1] - epsilon < 0)
{
boxes[0].min_corner() = make_point(T{}, T{});
boxes[0].max_corner() = x + make_point(epsilon, epsilon);
boxes[1].min_corner() = make_point(1 + x[0] - epsilon, T{});
boxes[1].max_corner() = make_point(T(1), x[1] + epsilon);
boxes[2].min_corner() = x + make_point(1 - epsilon, 1 - epsilon);
boxes[2].max_corner() = make_point(T(1), T(1));
boxes[3].min_corner() = make_point(T{}, 1 + x[1] - epsilon);
boxes[3].max_corner() = make_point(x[0] + epsilon, T(1));
box_count = 4;
}
else if (x[1] + epsilon >= 1)
{
boxes[0].min_corner() = make_point(T{}, x[1] - epsilon);
boxes[0].max_corner() = make_point(x[0] + epsilon, T(1));
boxes[1].min_corner() = make_point(T{}, T{});
boxes[1].max_corner() = make_point(x[0] + epsilon, x[1] + epsilon - 1);
boxes[2].min_corner() = make_point(1 + x[0] - epsilon, T{});
boxes[2].max_corner() = make_point(T(1), x[1] + epsilon - 1);
boxes[3].min_corner() = make_point(1 + x[0] - epsilon, x[1] - epsilon);
boxes[3].max_corner() = make_point(T(1), T(1));
box_count = 4;
}
else
{
boxes[0].min_corner() = make_point(T{}, x[1] - epsilon);
boxes[0].max_corner() = make_point(x[0] + epsilon, x[1] + epsilon);
boxes[1].min_corner() = make_point(1 + x[0] - epsilon, x[1] - epsilon);
boxes[1].max_corner() = make_point(T(1), x[1] + epsilon);
rbox_count = 2;
}
}
else if (x[0] + epsilon >= 1)
{
if (x[1] - epsilon < 0)
{
boxes[0].min_corner() = make_point(x[0] - epsilon, T{});
boxes[0].max_corner() = make_point(T(1), x[1] + epsilon);
boxes[1].min_corner() = make_point(x[0] - epsilon, 1 + x[0] - epsilon);
boxes[1].max_corner() = make_point(T(1), T(1));
boxes[2].min_corner() = make_point(T{}, 1 + x[1] - epsilon);
boxes[2].max_corner() = make_point(x[0] + epsilon - 1, T(1));
boxes[3].min_corner() = make_point(T{}, T{});
boxes[3].max_corner() = make_point(x[0] + epsilon - 1, x[1] + epsilon);
box_count = 4;
}
else if (x[1] + epsilon >= 1)
{
boxes[0].min_corner() = x - make_point(epsilon, epsilon);
boxes[0].max_corner() = make_point(T(1), T(1));
boxes[1].min_corner() = make_point(T{}, x[1] - epsilon);
boxes[1].max_corner() = make_point(x[0] + epsilon - 1, T(1));
boxes[2].min_corner() = make_point(T{}, T{});
boxes[2].max_corner() = make_point(x[0] + epsilon - 1, x[1] + epsilon - 1);
boxes[3].min_corner() = make_point(x[0] - epsilon, T{});
boxes[3].max_corner() = make_point(T(1), x[1] + epsilon - 1);
box_count = 4;
}
else
{
boxes[0].min_corner() = x - make_point(epsilon, epsilon);
boxes[0].max_corner() = make_point(T(1), x[1] + epsilon);
boxes[1].min_corner() = make_point(T{}, x[1] - epsilon);
boxes[1].max_corner() = make_point(x[0] + epsilon - 1, x[1] + epsilon);
box_count = 2;
}
}
else
{
if (x[1] - epsilon < 0)
{
boxes[0].min_corner() = make_point(x[0] - epsilon, T{});
boxes[0].max_corner() = x + make_point(epsilon, epsilon);
boxes[1].min_corner() = make_point(x[0] - epsilon, 1 + x[1] - epsilon);
boxes[1].max_corner() = make_point(x[0] + epsilon, T(1));
box_count = 2;
}
else if (x[1] + epsilon >= 1)
{
boxes[0].min_corner() = x - make_point(epsilon, epsilon);
boxes[0].max_corner() = make_point(x[0] + epsilon, T(1));
boxes[1].min_corner() = make_point(x[0] - epsilon, T{});
boxes[1].max_corner() = make_point(x[0] + epsilon, 1 - x[1] + epsilon);
box_count = 2;
}
else
{
boxes[0].min_corner() = x - make_point(epsilon, epsilon);
boxes[0].max_corner() = x + make_point(epsilon, epsilon);
box_count = 1;
}
}
}
如你所见,这是相当复杂的。我已经分别考虑了每种情况。我的问题是:我们怎样才能简化它,使它适用于任意维数d
?
2条答案
按热度按时间bsxbgnwa1#
我认为每个维度会分别以1或2的因子改变盒子的数量,因此,归纳起来,你可能会得到下面的结果(我尝试复制了9个二维测试用例,并添加了一个具有最大分割的三维测试用例)。
toiithl62#
你根本不需要考虑案例,如果你真的想很容易地概括,你需要正确地理解问题域。
在d维上,一个“盒子”基本上是由2 * d个坐标或原点和d个向量定义的区域的内部。
两个框的交点本身是一个框,其坐标由每条线与每个框的交点给出。
即对于每个维度
它最多应该有10行代码。
在更多伪代码中:
这将给予你交点。然后你需要把这些点转换回一个点长度表示。但我留给你,因为它是直截了当的。注意,我假设框是轴对齐。