检查线是否影响n维立方体

Question

我试图确定两个端点start = (x, y, z, ...), end = (x, y, z, ...)给出的一行是否与n维立方体或矩形相交，我将其存储为相反的端点bottom_most = (x, y, z, ...), top_most= (x, y, z, ...)。

我已经找到了solutions in 3D，但不是泛化n维的。

我目前的解决办法是：

dimensions = 3


def check_intersects(start, end, cube):
    num_intersections = 0
    for dim in range(dimensions):
        if cube[dim] <= start[dim] <= cube[self.dimensions + dim] or start[dim] <= cube[dim] <= end[dim]:
            num_intersections += 1

    if num_intersections >= dimensions:
        return True

    return False


start, end = (0, 0, 0), (30, 30, 30)
cube = (10, 10, 10, 20, 20, 20)
print(check_intersects(start, end, cube))
start, end = (0, 0, 0), (0, 10, 20)
print(check_intersects(start, end, cube))

但是，在某些情况下，这些线是从某些角度进入的，这似乎就会被打破。

是否有更好的解决方案或库可以为我做到这一点？

Answer 1

如果你想到一个对轴对齐的三维立方体：

考虑x轴，比方说，立方体从x=2到x= 4。所以你可以想到一个空间的“切片”，在x=2和x=4的平行平面的范围内；

然后考虑y轴，从(比方说)y=3到y=5有一个“片”，在z中有一个切片，并且(如果你把它扩展到更高的维数)每个对应维中的一个切片；

然后你可以把立方体看作是这些切片的交集--所有的点都同时属于所有的切片。

如果将直线的任何点定义为

pt = start + k * (end - start)

然后，对于每个维度，您可以找到min_k和max_k，在这两个维度中，直线进入并离开该维度的切片，

但是要通过(超)立方体，必须有一定的k值，它同时属于所有的切片，即

max(min_k_x, min_k_y, min_k_z, ...) <= min(max_k_x, max_k_y, max_k_z, ...)