python - 递归地将立方体分解为 8 个更小的立方体(当立方体由中点和大小定义时)

Question

我在执行此操作时遇到问题，因此不胜感激。

简短版本:给定立方体的中点和大小，我需要将它分成 8 个较小的部分 (2x2x2)，并且可能对每个部分重复。生成的坐标是唯一需要的东西。

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

例如，如果我在深度 1 处有点 (0,0,0)，而场景的深度为 0，我需要将它分成 8 block ，然后移动每一个 +-0.5 单位以适应旧立方体 (2^(depth-1))。

如果场景的深度为 -1，我需要将其分成 8 block ，然后再将其分成 8 block 。我基本上需要它来给出 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 示例，我在绘画中做了一个快速的事情，你可以明白为什么我认为它会 super 简单。经过 3 次迭代后的最终结果将产生适合场景的 64 个坐标。

Answer 1

我仍然不太确定这是否是您想要的，但这是我想要的这样做:

首先，我将创建一个表示 3D 空间中的点的类:

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 从立方体的深度向下到目标深度。

注意用于生成扁平化列表的二维列表理解。

from __future__ import division
from itertools import product

class Cube:
    """Representation of a cube."""

    # directions to all eight corners of a cube
    DIR = [Point3D(*s) for s in product([-1, +1], repeat=3)]

    def __init__(self, center, size, depth=0):
        if not isinstance(center, Point3D):
            center = Point3D(*center)
        self.center = center
        self.size = size
        self.depth = depth

    def __repr__(self):
        return 'Cube(center={c.center}, size={c.size}, depth={c.depth})'.format(c=self)

    def _divide(self):
        """Divide into eight cubes of half the size and one level deeper."""
        c = self.center
        a = self.size/2
        d = self.depth - 1
        return [Cube(c + a/2*e, a, d) for e in Cube.DIR]

    def divide(self, target_depth=0):
        """Recursively divide down to the given depth and return a list of
        all 8^d cubes, where d is the difference between the depth of the
        cube and the target depth, or 0 if the depth of the cube is already
        equal to or less than the target depth.

        >>> c = Cube(center=(0, 0, 0), size=2, depth=1)
        >>> len(c.divide(0))
        8
        >>> len(c.divide(-1))
        64
        >>> c.divide(5)[0] is c
        True
        >>> c.divide(-1)[0].size
        0.5
        """
        if self.depth <= target_depth:
            return [self]
        smaller_cubes = self._divide()
        return [c for s in smaller_cubes for c in s.divide(target_depth)]

您的示例是这样完成的:

# 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)}