计算多维数组和正方形交集体积的无大小写方法

Question

我有一个多维数组，在遍历它的每个元素时，如果维度大于 3，我需要计算正方形、立方体或其他相应对象的体积，在每个元素中，大小为 2r .如果我遍历数组边界附近的元素，square/cube 的一部分将粘在数组之外 - 我需要数组和对象之间的交集的体积。

这是问题在 2D 中的样子 - 我需要计算红色区域。

到目前为止我知道两种方法：

案例和 if 语句。对于 2D，我可以计算交点角的坐标，但由于这不是严格意义上的 2D 问题，而是多维问题，其中维数在输入、案例和 if 语句以及随后的硬编码中给出没问题。
手动遍历正方形中的每个元素并检查它是否属于数组。虽然这很容易做到，但它也非常慢，即使在 2D 中也是如此，因为我正在迭代 n 维数组，并且在每次迭代中，我再次执行 n 次循环，大小为 2r^n。半径越大，执行越慢。

有什么方法可以让我快速计算出这些路口的体积吗？

Answer 1

如果我对你的问题理解正确，你想计算两个轴对齐的超矩形之间的交集体积。

第一个矩形（您的数组）由其下角的位置（arrayLower，一个 nD 向量）及其大小（arraySize，又是一个 nD 向量）定义。第二个矩形由其中心（p，一个 nD 向量）和每个方向 r 个单位的范围定义。

对于给定的维度 d，这可以以非常结构化的方式完成，因为您只需要乘以每个维度的范围：

volume = 1
for each d:
    lower = max(p[d] - r, arrayLower[d])
    upper = min(p[d] + r, arrayLower[d] + arraySize[d])
    if(lower > upper)
        volume = 0   //no intersection
    else
        volume *= upper - lower

计算多维数组和正方形交集体积的无大小写方法

Caseless way of calculating volume of an intersection between an array and a square in multiple dimensions

arrays

math

geometry

computational-geometry