递归地将立方体分解成8个更小的立方体（当立方体由一个中点和大小定义时）

Question

我很难让这个工作，所以一点帮助将不胜感激。在

简短的版本：给定一个中间点和一个立方体的大小，我需要把它分成8个更小的（2x2x2），并且可能对每一个都重复。得到的坐标是唯一需要的。在

我正在编写一些八叉树风格的代码，并试图允许它接受不同深度的输入（深度与点之间的间距有关，即2^depth，例如深度0有1个单位的网格，depth-1有0.5，depth 1有2）。我需要它能够得到一个更高深度的坐标，并把它分解成适合实际深度的立方体。在

例如，如果我的点(0,0,0)位于深度1，并且场景的深度为0，我需要将其分成8个部分，并移动每个+-0.5个单元，以使其适合旧立方体（2^(depth-1)）。在

如果场景在depth-1，我需要把它分成8个部分，然后再分成8个部分。我基本上需要它来给出8^(difference in depth)结果，这听起来很容易做到，但它完全让我为难，因为它出错了。在

#Set up structure
octreeRange = ( 1, -1 )
octreeStructure = set()
for x in octreeRange:
    for y in octreeRange:
        for z in octreeRange:
            octreeStructure.add( ( x, y, z ) )

#octreeStructure is the 8 coordinates that a cube can split into

def recursiveCoordinate( coordinate, coordinateInfo, minDepthLevel, octreeStructure ):

    newDictionary = {}

    #Turn into list if isn't already list
    if type( coordinateInfo ) != list:
        coordinateInfo = [coordinateInfo,minDepthLevel]

    coordinateDepth = coordinateInfo[1]

    #Run function again for each coordinate that has a depth too high
    if coordinateDepth > minDepthLevel:
        coordinateInfo[1] -= 1
        moveAmount = pow( 2, coordinateDepth-1 )
        for i in octreeStructure:
            newCoordinate = [i[j]*moveAmount+coordinate[j] for j in xrange( 3 )]
            newDictionary.update( recursiveCoordinate( newCoordinate, coordinateInfo, minDepthLevel, octreeStructure ) )

    else:
        newDictionary[tuple( coordinate )] = coordinateInfo

    return newDictionary

minDepthLevel = 0
grid = {}
#grid[(x, y, z)] = [block ID, depth level]
grid[(1.5,0,0)] = [1,2]

newGrid = {}
for coordinate in grid:
    newGrid.update( recursiveCoordinate( coordinate, grid[coordinate], minDepthLevel, octreeStructure ) )
print len( newGrid.keys() ) 

要想获得视觉效果，请拍下这张照片。当场景为级别0时，中点位于中间，在深度级别2定义。实心黑线是第一次迭代，虚线是第二次也是最后一次迭代。我需要虚线立方体所有中点的坐标。

我想另一种方法是根据深度计算立方体的大小，然后将其拆分为所需数量的部分，但这将需要3个嵌套循环，可能要经历数千个值，因此我希望尽可能避免使用嵌套循环方式。在

编辑：作为一个2D例子，我在绘画中做了一件很快的事情，你可以看到为什么我认为它会非常简单。3次迭代后的最终结果将生成64个坐标，这些坐标将适合场景。在

Answer 1

我还不太确定这是否是你想要的，但我想这样做 这样做：

首先，我将创建一个表示三维空间中的点的类：

class Point3D:
    """Representation of a point in 3D space."""
    def __init__(self, x, y, z):
        self.x = x
        self.y = y
        self.z = z

    def __add__(self, other):
        """Add two points.

        >>> Point3D(1, 2, 3) + Point3D(100, 200, 300)
        Point3D(101, 202, 303)
        """
        x = self.x + other.x
        y = self.y + other.y
        z = self.z + other.z
        return Point3D(x, y, z)

    def __mul__(self, a):
        """Multiply a point with a number.

        >>> Point3D(1, 2, 3) * 2
        Point3D(2, 4, 6)
        """
        x = self.x * a
        y = self.y * a
        z = self.z * a
        return Point3D(x, y, z)

    def __rmul__(self, a):
        """Multiply a number with a point.

        >>> 2 * Point3D(1, 2, 3)
        Point3D(2, 4, 6)
        """
        return self.__mul__(a)

    def __repr__(self):
        return 'Point3D({p.x}, {p.y}, {p.z})'.format(p=self)

这使得在计算 派生多维数据集。在

然后我将创建一个表示立方体的类。实例能够被分成八个部分，并且知道它们的“深度”，这对于被划分的立方体来说是减少的。在

中心点必须移动的八个方向是 使用itertools.product获得并表示为Point3D 对象的各个坐标设置为-1/+1。（我给你所说的DIR起了个短名字octreeStructure。）

多维数据集对象有一个帮助函数_divide，它向下一级，用于递归函数divide，该函数从多维数据集的深度向下到目标深度。在

请注意二维列表理解，它用于生成扁平化列表。在

^{pr2}$

你的例子是这样做的：

# minDepthLevel = 0
# grid = {}
# grid[(1.5,0,0)] = [1,2]
# not sure what this ^ 1 means

cube = Cube((1.5, 0, 0), 4, 2)
grid = {c.center: [1, c.depth] for c in cube.divide(0)}