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

Question

我无法让这个工作,所以一点帮助将不胜感激.

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

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

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

如果场景深度为-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

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

首先，我将创建一个表示 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)}