Хранение информации о точках в 3d пространстве

Вот еще один распространенный подход

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 ]

Получение всех точек в пределах 3 единиц позиции x=1,y=2,z=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 ]

Что ж... Если вы хотите действительно заполнить это пространство, то вам, вероятно, лучше всего подойдет плотно упакованная матричная структура, в основном воксели.

Если вы не ожидаете заполнить его, поищите что-то более оптимизированное. Я бы начал с рассмотрения octrees, которые часто используются для подобных вещей.

Одним из преимуществ numpy является то, что он невероятно быстр, например. вычисление PageRank матрицы смежности 8000x8000 занимает миллисекунды. Несмотря на то, что numpy.ndarray будет принимать только числа, вы можете хранить сопоставления чисел/идентификаторов объектов во внешней хеш-таблице, то есть в словаре (который, опять же, является высокооптимизированной структурой данных).

Нарезка будет такой же простой, как нарезка списка в 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, вы можете запустить свое приложение в течение короткого периода времени.

Удачи!

Вот подход, который может сработать.

Каждая точка представляет собой 4-кортеж (x, y, z, данные), и ваша база данных выглядит следующим образом:

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 ]

Получение всех точек в пределах 3 единиц позиции 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 ]

Вы можете выполнить первые 2 запроса с нарезкой в ​​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 !) и расширенный синтаксис нарезки позволят вам не писать код.

Использование словаря с кортежами 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 вы можете изменить «точки» в возвращаемых словарях, а также изменить исходные точки (я думаю).

Когда использовать Binary Space Partitioning, Quadtree, Octree?

3D-массив imo бесполезен. Особенно, если ваш мир динамичен. Вы должны выбрать между BSP, Quadtree или Octtree. БСП вполне подойдет. Поскольку ваш мир находится в 3D, вам нужны плоскости при разделении bsp, а не линии.

Ваше здоровье !

Редактировать

У меня также будут данные для каждой точки в заданном трехмерном пространстве, поэтому я думаю, что запасная матрица — это плохо?

Я думаю, это нормально, если вы всегда знаете, насколько велик ваш набор данных и что он никогда не меняется, т. Е. Если к нему добавляется больше точек, которые, в свою очередь, выходят за пределы. В этом случае вам придется изменить размер трехмерного массива.

Это зависит от точной конфигурации вашей системы, но в приведенном вами примере вы используете целые числа и дискретные точки, поэтому, вероятно, было бы уместно рассмотреть Разреженная матрица структуры данных.