检查小方块填满较大立方体 [英] Check that smaller cubes fill bigger cube

问题描述

给定一个大立方体（轴对准和整数坐标），和许多较小的立方体（也轴线对齐和整数坐标）。我们怎样才能检查大立方体是完全填充的小立方体。

Given one large cube (axis aligned and on integer coordinates), and many smaller cubes (also axis aligned and on integer coordinates). How can we check that the large cube is perfectly filled by the smaller cubes.

目前，我们检查：

1. 对于每一个小立方体被完全包含在大型多维数据集。
2. ，它不相交，任何其他的小立方体。
3. 的小立方体的体积之和等于大立方体的体积。

这是确定小数目的立方体，但我们需要支持这种测试立方体尺寸大于2 ^ 32。即使在2 ^ 16，填补了大型立方体所需的小方块的数量足够大，第2步需要一段时间（为O（n ^ 2）检查每个立方体相交没有其他）。

This is ok for small numbers of cubes but we need to support this test of cubes with dimensions greater than 2^32. Even at 2^16 the number of small cubes required to fill the large cube is large enough that step 2 takes a while (O(n^2) checking each cube intersects no other).

有没有更好的算法？

编辑：

似乎有一些混乱这一点。我不是要一个立方体分割成更小的立方体。这是已经完成。我们的计划的一部分，将大范围的OpenCL（整数坐标轴对齐的立方体）成许多更小的范围是适合硬件的工作。

There seems to be some confusion over this. I am not trying to split a cube into smaller cubes. That's already done. Part of our program splits large OpenCL ranges (axis aligned cubes on integer coordinates) into lots of smaller ranges that fit into a hardware job.

我在做什么是挂接到这个系统，并检查其产生正确的工作覆盖了大的初始范围。我的算法上述作品，但它的速度慢，并给予测试，我们必须跑我想保持这些测试尽可能快地量。

What I'm doing is hooking into this system and checking that the jobs it produces correctly cover the large initial range. My algorithm above works, but it's slow and given the amount of tests we have to run I'd like to keep these tests as fast as possible.

推荐答案

我们都在谈论3D吗？
对于2D我们可以做一个类似（但更简单）工艺（用，我相信，为O（n log n）的运行时间的算法）。

We are talking about 3D right?
For 2D one can do a similar (but simpler) process (with, I believe, an O(n log n) running time algorithm).

的下面的基本思想是扫描线算法的

请注意该矩形交点可以通过检查任何立方体的任何角落是否包含在任何其它立方体进行。

Note that rectangle intersection can done by checking whether any corner of any cube is contained in any other cube.

您可以提高（2）如下：

• 拆分每个立方体到2矩形在YZ平面上（所以你必须通过相同的一组4（Y定义2矩形，Z）坐标，但X坐标将是矩形之间的不同）。

• Split each cube into 2 rectangles on the y-z plane (so you'd have 2 rectangles defined by the same set of 4 (y,z) coordinates, but the x coordinates will be different between the rectangles).

定义与较小的矩形的x坐标为立方体的开始和另一矩形为立方体的末端。

Define the rectangle with the smaller x-coordinate as the start of a cube and the other rectangle as the end of a cube.

排序由矩形的x坐标

有一个初始为空区间树
（每个间隔也应存储的引用，矩形它所属）

Have an initially empty interval tree
(each interval should also store a reference to the rectangle to which it belongs)

对于每一个矩形：

• 查找每个点的区间树中的矩形的y坐标。
  对于每个匹配区间，仰望它的矩形，并检查点是否也包含在z坐标内（这是所有的需要，因为树只包含x坐标在正确的范围内，我们通过做检查y坐标间隔查找）。
  如果是，我们有重叠。

• Look up the y-coordinate of each point of the rectangle in the interval tree.
  For each matching interval, look up its rectangle and check whether the point is also contained within the z-coordinates (this is all that's required because the tree only contains x-coordinates in the correct range and we check the y-coordinates by doing the interval lookup).
  If it is, we have overlap.

如果该矩形是立方体的开始，插入矩形的2 y坐标作为间隔成区间树

If the rectangle is the start of a cube, insert the 2 y-coordinates of the rectangle as an interval into the interval tree.

，运行时间为O（n）（最佳情况），并为O（n ² ）（最坏情况），这取决于有多少重叠有一个在x和y坐标（间更多的重叠是雪上加霜）。

The running time is between O(n) (best case) and O(n²) (worst case), depending on how much overlap there is in the x- and y-coordinates (more overlap is worse).

这篇关于检查小方块填满较大立方体的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！