在三维空间中存储点信息

Question

我正在用Python编写一些代码（目前只是为了好玩），将一些数据存储在三维空间中的每个点上。我基本上需要一个三维矩阵对象，它可以存储允许我执行一些高级选择的任意对象，例如：

- 获取x=1，y=2，z=3处的点。 - 获取所有y=2的点。 - 获取距离位置x=1，y=2，z=3不到3个单位的所有点。 - 获取point.getType() ==“Foo”的所有点。

在上述所有情况下，我需要得到某种输出，以便给我原始的空间位置和存储在该点的数据。

显然，numpy可以做到我想要的，但它似乎高度优化用于科学计算，并且迄今为止，我无法找到如何获取所需数据的方法。

是否有更好的替代方案，或者我应该回到numpy wall？ :)

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

- Douglas Yarra

---

是的，只需使用一个三维数组，更复杂的结构仅用于在某些特定情况下优化一些操作。 - Luper Rouch

当你说“空间中的点”时，我假设x、y、z是连续变量，例如浮点数，但你的示例暗示它们是整数。如果是整数，那么稀疏矩阵就可以了。否则，请使用元组或对象。个人而言，我建议攀登numpy之墙。在另一边是绿色的牧场！ - Paul

Answer 1

这是另一种常见的方法。

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 ]

获取所有类型为"Foo"的点

[ p for p in database if type(p.data) == Foo ]

- S.Lott

---

谢谢！我在使用比必要的更复杂的数据结构时感到混乱。这个方法非常有效，让我每次都可以按照自己的意愿进行任何类型的数据选择。 - Douglas Yarra

Answer 2

如果你希望真正填满那个空间，最好使用密集的矩阵结构，基本上就是体素。

如果你不指望填满它，可以考虑一些更优化的方法。我会从八叉树开始看起，这通常用于此类事情。

- unwind

---

体素不是一种数据结构，而是一种显示三维网格的技术。 - Luper Rouch

Answer 3

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-对象映射哈希包装起来，你可以在短时间内让应用程序运行。

祝好运！

- miku

---

我曾以为ndarray只能存储数字，但它可以存储任何东西！ numpy.ndarray([w,h,d],object) 这是我目前正在烦恼的问题，但它很麻烦，所以我在这里发布，希望能得到更好的解决方案，并涉及更少的矩阵知识！ - Douglas Yarra

好的，那我的建议有点无意义，我会删除它；但是你为什么要避免“矩阵操作”呢？矩阵虽然不好玩，但有些整洁。对于切片和访问，使用“ndarray”非常方便 - 那么为什么不用呢？ - miku

实际上，这一点远非毫无意义，这是我现在采用的方法。我只是在每个点存储自己的自定义类。我不喜欢它的唯一原因是许多NumPy似乎假定你知道矩阵数学/术语，而我并不知道，这只是需要花费额外精力去学习的东西。 - Douglas Yarra

Answer 4

你可以使用numpy中的切片来执行前两个查询：

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！）并且扩展切片语法将避免你编写代码。

- Luper Rouch

Answer 5

这里有一个可能有效的方法。

每个点都是一个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 三个单位以内的点。

[ (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 ]

- S.Lott

---

这将会非常慢，用于搜索！ - Ed James

@Ed Woodcock：这是关系型数据库的工作方式，因此这种架构有先例。此外，如果数据量需要，可以添加索引。由于我们不知道数据量或查询频率，因此我们还不足以拒绝这个方案。 - S.Lott

“任意对象”要求在这里是一个小问题：如果它是不可变的，那么更改条目需要三个步骤：

1. 删除旧元组
2. 构建新元组
3. 追加新元组。

当然，如果您为数据对象使用自己的类，则不会有问题。 - RoadieRich

@RoadieRich：额外数据所属的类并不重要。我们会重新构建一堆元组。但是这些元组包含的是相同的原始对象，它们在被重新纳入到新的元组中时没有发生任何变化。所有这些元组中的基础对象都没有改变。 - S.Lott

Answer 6

如果你想使用标准库来实现相对简单的解决方案，那么使用一个以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 的引用机制，您可以更改返回的字典中的“points”，并且原始的“points”也会随之更改（我想）。

- RoadieRich

Answer 7

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

在我看来，3D数组是毫无价值的。特别是如果你的世界是动态的。你应该在BSP、四叉树或八叉树之间做出选择。BSP就可以胜任。由于你的世界是三维的，所以在分割BSP时需要平面而不是线。

干杯！

编辑

我也会有每个点在给定的3D空间中的数据，那么我猜一个稀疏矩阵不好吗？

如果你总是知道你的数据集有多大，并且它永远不会改变，即如果添加更多的点，这些点反过来又超出了边界，那么我想这样做是可以的。在这种情况下，你需要调整3D数组的大小。

- ralphtheninja

Answer 8

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

- Cruachan