Безусловный способ расчета объема пересечения между массивом и квадратом в нескольких измерениях

Question

У меня есть многомерный массив, и, перебирая каждый его элемент, мне нужно вычислить объем квадрата, куба или других соответствующих объектов в случае размеров, превышающих 3, в каждом элементе размером 2r.Если я перебираю элементы рядом с границами массива, часть этого квадрата / куба выйдет за пределы массива - и мне нужен объем пересечения между массивом и объектом.

ЭтоВот как выглядит проблема в 2D - мне нужно вычислить красную область.

Я знаю два способа сделать это:

1. Случаи и операторы if.Для 2D я мог бы вычислить координаты углов пересечения, но так как это не строго 2D проблема, а многомерная, где число измерений дается на входе, case и if-операторы и последующее жесткое кодированиевне вопроса.
2. Вручную итерируя по каждому элементу в квадрате и проверяя, принадлежит ли он массиву.Хотя это легко сделать, это также невероятно медленно, даже в 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