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

Question

Я пишу некоторый код (пока просто для развлечения) на Python, который будет хранить некоторые данные в каждой точке 3d-пространства.В основном мне нужен объект 3d matrix, в котором хранятся произвольные объекты, которые позволят мне выполнять некоторые расширенные выборки, например:

• Найдите точку, где x = 1, y = 2, z = 3.
• Получаем все точки, где y= 2.
• Получение всех точек в пределах 3 единиц от позиции x = 1,y = 2, z = 3.
• Получение всех точек, где point.GetType() == "Foo"

Во всем вышеперечисленном мне нужно было бы в конечном итоге получить какой-то вывод, который дал бы мне исходное положение в пространстве и данные, сохраненные в этой точке.

По-видимому, numpy может делать то, что я хочу, но он кажется высоко оптимизированным для научных вычислений, и разработка того, как получить данные, как я хочу выше, до сих пор ускользала от меня.

Есть ли лучшая альтернатива или мне следует вернуться к битью головой о дурацкую стену?:)

Редактировать:еще немного информации первые три ответа заставили меня понять, что я должен включить:Я не беспокоюсь о производительности, это чисто проверка концепции, где я бы предпочел чистый код хорошей производительности.У меня также будут данные для каждой точки в данном 3d-пространстве, так что, я думаю, Запасная матрица - это плохо?

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 ]

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

Answer 2

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

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

Answer 3

Одним из преимуществ numpy является то, что он невероятно быстр, напримервычисление pagerank матрицы смежности размером 8000x8000 занимает миллисекунды.Даже несмотря на то , что numpy.ndarray будет принимать только числа, вы можете хранить сопоставления number / id-object во внешней хэш-таблице, т.е.словарь (который, опять же, является высокооптимизированной структурой данных).

Нарезка была бы такой же простой, как нарезка списка в 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]]

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

Удачи вам!

Answer 4

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

Каждая точка представляет собой 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 ]

Answer 5

Вы можете выполнить первые 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'

Для четвертого запроса, если единственными данными, хранящимися в вашем массиве, является тип cells, вы могли бы закодировать их в виде целых чисел:

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

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

Answer 7

Когда использовать разбиение двоичного пространства, Quadtree, Octree?

3d массив imo ничего не стоит.Особенно, если ваш мир динамичен.Вы должны выбрать между BSP, Quadtree или Octree.BSP подошел бы просто отлично.Поскольку ваш мир выполнен в 3d, при разделении bsp вам нужны плоскости, а не линии.

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

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

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

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

Answer 8

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