5

我正在用 Python 编写一些代码（到目前为止只是为了好玩），它将在 3d 空间中的每个点上存储一些数据。我基本上是在存储任意对象的 3d 矩阵对象之后，这些对象将允许我进行一些高级选择，例如：

  • 得到 x=1,y=2,z=3 的点。
  • 获取 y=2 的所有点。
  • 获取位置 x=1,y=2,z=3 的 3 个单位内的所有点。
  • 获取 point.getType() == "Foo" 的所有点

在上述所有内容中，我需要最终得到某种输出，以提供空间中的原始位置以及该点存储的数据。

显然 numpy 可以做我想做的事，但它似乎对科学计算进行了高度优化，并且到目前为止我还没有弄清楚如何获得我想要的数据。

有没有更好的选择，还是我应该回到把头撞在麻木墙上？:)

编辑：前三个答案的更多信息让我意识到我应该包括：我不担心性能，这纯粹是一个概念验证，我更喜欢干净的代码而不是良好的性能。我还将拥有给定 3d 空间中每个点的数据，所以我猜备用矩阵不好？

4

8 回答 8

6

这是另一种常见的方法

class Point( object ):
    def __init__( self, x, y, z, data ):
        self.x, self.y, self.z = x, y, z
        self.data = data
    def distFrom( self, x, y, z )
        return math.sqrt( (self.x-x)**2 + (self.y-y)**2 + (self.z-z)**2 )

database = [ Point(x,y,z,data), Point(x,y,z,data), ... ]

让我们看看您的用例。

得到 x=1,y=2,z=3 的点。

[ p for p in database if (p.x, p.y, p.z) == ( 1, 2, 3 ) ]

获取 y=2 的所有点。

[ p for p in database if p.y == 2 ]

获取位置 x=1,y=2,z=3 的 3 个单位内的所有点。

[ p for p in database if p.distFrom( 1, 2, 3 ) <= 3.0 ]

获取 point.getType() == "Foo" 的所有点

[ p for p in database if type(p.data) == Foo ]
于 2009-05-26T15:30:30.423 回答
3

嗯...如果您希望真正填充该空间，那么您可能最好使用密集的矩阵状结构，基本上是体素。

如果您不希望填充它，请研究一些更优化的东西。我将从查看octrees开始，它们通常用于此类事情。

于 2009-05-26T14:20:43.713 回答
1

numpy 的一个优点是它非常快，例如计算 8000x8000 邻接矩阵的 pagerank 需要几毫秒。即使numpy.ndarray只接受数字，您也可以将数字/id-对象映射存储在外部哈希表中，即字典（这又是一个高度优化的数据结构）。

切片就像 python 中的列表切片一样简单：

>>> from numpy import arange

>>> the_matrix = arange(64).reshape(4, 4, 4)
>>> print the_matrix[0][1][2]
    6
>>> print the_matrix[0][1]
    [4 5 6 7]
>>> print the_matrix[0]
    [[ 0  1  2  3]
    [ 4  5  6  7]
    [ 8  9 10 11]
    [12 13 14 15]]

如果你将一些你想要的函数（距离）包裹在一些核心矩阵和一个 id-object-mapping 哈希上，你可以让你的应用程序在很短的时间内运行。

祝你好运！

于 2009-05-26T14:50:21.453 回答
0

您可以在 numpy 中使用切片进行前 2 个查询：

a = numpy.zeros((4, 4, 4))
a[1, 2, 3] # The point at x=1,y=2,z=3
a[:, 2, :] # All points where y=2

对于第三个，如果您的意思是“获取半径为 3 且以 x=1,y=2,z=3 为中心的球体内的所有点”，您将必须编写一个自定义函数来执行此操作；如果你想要一个立方体，你可以继续切片，例如：

a[1:3, 1:3, 1:3] # The 2x2x2 array sliced from the center of 'a'

对于第四个查询，如果存储在数组中的唯一数据是单元格类型，则可以将其编码为整数：

FOO = 1
BAR = 2
a = numpy.zeros((4, 4, 4), dtype="i")
a[1, 2, 3] = FOO
a[3, 2, 1] = BAR
def filter(a, type_code):
    coords = []
    for z in range(4):
        for y in range(4):
            for x in range(4):
                if a[x, y, z] == type_code:
                    coords.append((x, y, z))
    return coords
filter(a, FOO) # => [(1, 2, 3)]

numpy 看起来是做你想做的事的好工具，因为数组在内存中会更小，在 C 中很容易访问（甚至更好，cython！）并且扩展的切片语法将避免你编写代码。

于 2009-05-26T14:40:16.157 回答
0

这是一种可能有效的方法。

每个点都是一个 4 元组 (x,y,z,data)，您的数据库如下所示：

database = [ (x,y,z,data), (x,y,z,data), ... ]

让我们看看您的用例。

得到 x=1,y=2,z=3 的点。

[ (x,y,z,data) for x,y,z,data in database if (x,y,z) == (1,2,3) ]

获取 y=2 的所有点。

[ (x,y,z,data) for x,y,z,data in database if y == 2 ]

获取位置 x=1,y=2,z=3 的 3 个单位内的所有点。

[ (x,y,z,data) for x,y,z,data in database if math.sqrt((x-1)**2+(y-2)**2+(z-3)**2)<=3.0 ]

获取 point.getType() == "Foo" 的所有点

[ (x,y,z,data) for x,y,z,data in database if type(data) == Foo ]
于 2009-05-26T14:51:03.653 回答
0

何时使用二进制空间分区、四叉树、八叉树？

3d 数组 imo 毫无价值。特别是如果你的世界是动态的。您应该在 BSP、四叉树或八叉树之间做出选择。BSP 会做得很好。由于您的世界是 3d 的，因此在拆分 bsp 时需要平面，而不是线。

干杯！

编辑

我还将拥有给定 3d 空间中每个点的数据，所以我猜备用矩阵不好？

我想如果总是知道你的数据集有多大并且它永远不会改变，那就没问题了，即如果更多的点被添加到它又超出了界限。在这种情况下，您必须调整 3d 数组的大小。

于 2009-05-26T15:59:24.310 回答
0

如果您想要一个使用标准库的相对简单的解决方案，则使用带有 x,y,z 元组作为键的字典是另一种解决方案。

import math

#use indexing to get point at (1,2,3): points[(1,2,3)]
get_points(points, x=None, y=None, x=None):
    """returns dict of all points with given x,y and/or z values.  Call using keywords (eg get_points(points, x=3)"""
    filteredPoints = points.items()
    if x:
        filteredPoints = [p for p in filteredPoints if p[0][0] == x]
    if y:
        filteredPoints = [p for p in filteredPoints if p[0][1] == y]
    if z:
        filteredPoints = [p for p in filteredPoints if p[0][0] == x]
    return dict(filteredPoints)

get_point_with_type(points, type_):
    """returns dict of points with point.getType() == type_"""
    filteredPoints = points.items()
    return dict((position,data) for position,data in points.iterItems() if data.getType == type_)

get_points_in_radius(points,x,y,z,r):
    """Returns a dict of points within radius r of point (x,y,z)"""
    def get_dist(x1,y1,z1,x2,y2,z3):
        return math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2))
    return dict((position,data) for position,data in points.iterItems() if get_dist(x,y,z, *position) <= r))

而且由于python引用，您可以更改返回字典中的“点”，并且原始点也可以更改（我认为）。

于 2009-05-26T17:06:27.560 回答
-1

这取决于系统的精确配置，但从您给出的示例中，您使用的是整数和离散点，因此考虑稀疏矩阵数据结构可能是合适的。

于 2009-05-26T14:27:14.277 回答