检查长方体在c ++中是否以最快的速度重叠（无迭代）

Question

我有一个长方体类，其中长方体坐标作为一组数组提供：

Cuboid3D cube_a      ({1.0f, 2.0f, 3.0f, 4.0f, 5.0f, 6.0f, 7.0f, 8.0f}, // x coordinates
                    {2.0f, 4.0f, 3.0f, 7.0f, 2.0f, 9.0f, 5.0f, 2.0f}, // y coordinates
                   {1.0f, 3.0f, 6.0f, 9.0f, 4.0f, 3.0f, 1.0f, 7.0f}); // z coordinates

  Cuboid3D cube_b      ({3.0f, 4.0f, 5.0f, 2.0f, 1.0f, 2.0f, 3.0f, 2.0f}, // x coordinates
                    {1.0f, 3.0f, 5.0f, 2.0f, 1.0f, 2.0f, 3.0f, 4.0f}, // y coordinates
                   {1.0f, 3.0f, 6.0f, 9.0f, 4.0f, 3.0f, 1.0f, 7.0f}); // z coordinates

如果多维数据集在任意点相交，我需要找到最快的方法来获得正确/错误的结果。所以典型的解决方法

 if ((cubeA.maxX > cubeB.minX)&& // Determining overlap in the x plane
    (cubeA.minX < cubeB.maxX)&&
    (cubeA.maxY > cubeB.minY)&& // Determining overlap in the y plane
    (cubeA.minY < cubeB.minY)&&
    (cubeA.maxZ > cubeB.minZ)&& // Determining overlap in the z plane 
    (cubeA.minZ < cubeB.maxZ))
        cout<<"not intersecting";

我的问题是如何在不进行迭代的情况下实现这一点，即如何比较点-如何在不进行迭代的情况下从数组中获取最大最小值。我需要它尽可能快地工作，因为它将被多次使用。

Answer 1

您想获得最小和最大此操作至少需要O（n）时间。仅当您具有特定的数据先决条件时，这才可以更改。所以你知道最小值只能是2个顶点之一。或以某种方式对数据进行了排序。

根据我的阅读，您没有这样的东西。您只会得到2个任意的长方体。因此，您必须至少查看一次每个坐标才能找到最小值或最大值。根据您的操作，您可以存储这些值，并查看是否可以重用它们。如果例如您必须将一个长方体与其他长方体进行比较。

通常，每个长方体有24个值，例如minX您必须迭代8个以上的值。在我的简短测试中，我需要92纳秒的时间（即使在较弱的硬件上，我也怀疑这将花费比一微秒更长的时间）。因此，问自己一个问题，您实际的运行时要求是什么。您是否真的需要优化纳秒级？对我来说，这确实有点像过早的优化。

从问题的复杂性来看，我将首先专注于实际解决任务。这并非微不足道，可以通过多种方式实现。如果确实需要，请稍后考虑进行此类小的优化。

我能够找到一些有关长方体重叠检查的链接：https://gamedev.stackexchange.com/questions/130408/what-is-the-fastest-algorithm-to-check-if-two-cubes-intersect-where-the-cubes-a

https://gamedevelopment.tutsplus.com/tutorials/collision-detection-using-the-separating-axis-theorem--gamedev-169