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

Question

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

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

Во всем вышеперечисленном мне нужно получить какой-то вывод, который даст мне исходную позицию в пространстве и данные, хранящиеся в этой точке.

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

Есть ли лучшая альтернатива, или я должен вернуться к стуку головой в стену? :)

РЕДАКТИРОВАТЬ: дополнительная информация о первых трех ответах дала мне понять, что я должен включить: я не беспокоюсь о производительности, это просто подтверждение концепции, где я предпочел бы чистый код хорошей производительности. У меня также будут данные для каждой точки в данном трехмерном пространстве, так что я думаю, что запасная матрица плохая?

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

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

Использование словаря с кортежами 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 5

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

3D массив ИМО бесполезен. Особенно, если ваш мир динамичен. Вы должны выбрать между BSP, Quadtree или Octtree. BSP будет хорошо. Так как ваш мир находится в 3d, вам нужно плоскости, чтобы разделить BSP, а не линии.

Ура!

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

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

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

Answer 6

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

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

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

Вы можете сделать первые 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», вам придется написать пользовательскую функцию для этого; если вам нужен куб, вы можете продолжить нарезку, например ::1004

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

Answer 8

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