如何将重叠的 AABB 集合细分为非重叠的 AABB 集合？
Her*_*und 5 algorithm computational-geometry
我有一组 3D AABB。每个 AABB 都跟踪另一个数组中的索引。我想找到这些 AABB 并将其细分为更小的 AABB，无论它们在哪里相交。创建的每个新 AABB 都需要跟踪不同拆分 AABB 之间的索引并集。请参阅下面的 2D 图像示例：
我希望左边的 3 个重叠的 AABB 变成右边的 9 个不重叠的 AABB。
我将如何实现这一目标？
小智 7
第 1 部分 - 细分区间
当您将维数限制为 1 时，盒子只是一个区间。考虑一个名为“check_point”的数据结构：
struct check_point {
float value;
bool start; // true if this is the start of an interval, false otherwise.
int id; // The id of the interval that is starting or ending at this value.
}
首先将 1d 间隔的起点和终点转换为数组中的值。迭代这个数组，每两个连续的检查点创建一个新的间隔。您在迭代检查点时维护一组当前开放的间隔 ID。每当遇到“开始”检查点时，都会将 id 添加到集合中，每当遇到“结束”检查点时，都会从集合中删除 id。每次创建新间隔时，都会将当前 id 集分配给创建的间隔。这看起来如下图所示。
第 2 部分 - 细分框
现在让我们采用第 1 部分中的逻辑并将其调整为更高的维度。首先将框分解为 x、y 和 z 区间（即 2d 中的 x 和 y）。如果您从 n 个盒子开始，那么最终应该有 n 个 x 间隔、y 间隔和 z 间隔。将第 1 部分中的算法分别应用于 x、y 和 z 间隔集，这将为您提供 3 组输出间隔。
现在我们必须将这些一维间隔转换回盒子。
对于给定的 x、y 和 z 输出间隔组合，仅当所有 3 个间隔（x、y 和 z）的索引集的交集不是空集时，才应创建一个框。您忽略没有共同索引的 xyz 区间组合。这将为您提供一组细分的框。
下图展示了 2d 中的示例。虚线显示了 x 和 y 间隔的所有可能组合。标有“x”的组合将被忽略，因为它们没有任何共同的索引。转换成方框的组合中有一个复选标记。同样的逻辑也应该适用于 3 个或更多维度。
注意：此算法为您提供了比示例中更多的框（尺寸更小）。但这更具确定性，无需遵循细分框的任意约定。您始终可以根据您的具体需求修改算法以创建更少的盒子。例如，您可以沿着第二个图像中显示的网格移动，以沿 x 或 y 或两者合并框。
按 y（然后是 x 来打破平局）坐标对矩形的所有角进行排序。在一次迭代中处理每个角。
- 如果它是左上角，请将新矩形添加到列表中并更新重叠状态。
- 如果它是右上角，则从列表中删除当前矩形并更新状态。
- 如果它是左下角，请将其添加到列表中。
- 如果当前矩形是右下角，则从列表中删除它。
在此过程中，您需要保持列表中所有矩形的重叠状态。