Armazenando informações sobre os pontos em um espaço 3D

Question

Estou a escrever algum código (apenas para se divertir até agora) em Python que irá armazenar alguns dados em todos os pontos em um espaço 3D. Sou basicamente depois de um objeto de matriz 3d que armazena arbitrária objetos que permita-me a fazer algumas seleções avançadas, como:

• Obter o ponto em que x = 1, y = 2, z = 3.
• Obter todos os pontos onde y = 2.
• Obtendo todos os pontos dentro de 3 unidades de posição x = 1, y = 2, z = 3.
• Obter todos os pontos onde point.getType () == "Foo"

Em todas as opções acima, eu preciso acabar com algum tipo de saída que me daria a posição original no espaço, e os dados armazenados nesse ponto.

Aparentemente numpy pode fazer o que eu quero, mas parece altamente otimizado para computação científica e trabalhar para fora como para obter os dados que eu quero acima, até agora, me iludiu.

Existe uma alternativa melhor ou devo voltar a bater com a cabeça na parede numpy? :)

EDIT: mais algumas informações as três primeiras respostas me fez perceber que eu deveria incluir: Eu não estou preocupado com o desempenho, isso é puramente uma prova de conceito, onde eu prefiro código limpo para uma boa performance. Eu também terá dados para cada ponto no espaço dado 3d, então eu acho que a Matrix Spare é ruim?

Answer 1

Aqui está outra abordagem comum

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), ... ]

Vamos olhar seus casos de uso.

Obter o ponto em que x = 1, y = 2, z = 3.

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

Obter todos os pontos onde y = 2.

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

Getting todos os pontos dentro de 3 unidades de posição x = 1, y = 2, z = 3.

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

Obter todos os pontos onde point.getType () == "Foo"

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

Answer 2

Bem ... Se você espera para realmente preenchimento que o espaço, então você é provavelmente melhor fora com uma densamente matriz-como estrutura, basicamente, voxels .

Se você não esperar para preenchê-lo, olhar para algo um pouco mais otimizado. Gostaria de começar por olhar para octrees , que muitas vezes são usados ??para coisas como esta.

Answer 3

Uma das vantagens de numpy é que ele é incrivelmente rápido, por exemplo. calcular o pagerank de uma matriz 8000x8000 adjacência leva milissegundos. Embora numpy.ndarray só aceita números, é possível armazenar os mapeamentos de número / id de objectos numa tabela de hash externo i.e. dicionário (que por sua vez é uma estrutura de dados altamente optimizado).

O corte seria tão fácil como lista de corte em 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]]

Se você quebrar algumas de suas funções desejadas (distâncias) em torno de alguma matriz núcleo e um hash id-de mapeamento de objetos, você poderia ter o seu aplicativo em execução dentro de um curto período de tempo.

Boa sorte!

Answer 4

Aqui está uma abordagem que pode funcionar.

Cada ponto é um 4-tupla (x, y, z, de dados), e sua aparência de banco de dados como este:

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

Vamos olhar seus casos de uso.

Obter o ponto em que x = 1, y = 2, z = 3.

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

Obter todos os pontos onde y = 2.

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

Getting todos os pontos dentro de 3 unidades de posição 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 ]

Obter todos os pontos onde point.getType () == "Foo"

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

Answer 5

Você pode fazer as 2 primeiras consultas com corte no 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

Para o terceiro se você quer dizer "recebendo todos os pontos dentro de uma esfera de raio 3 e centrado em x = 1, y = 2, z = 3", você terá que escrever uma função personalizada para fazer isso; se você quiser um cubo você pode prosseguir com o corte, por exemplo:.

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

Para a quarta consulta se os únicos dados armazenados em sua matriz é o tipo de células, você pode codificá-lo como inteiros:

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)]

aparência numpy como a ferramenta boa para fazer o que quiser, como as matrizes serão menores na memória, facilmente acessíveis em C (ou melhor ainda, Cython !) e sintaxe corte prolongado vai evitar que você escrever código.

Answer 6

Usando um dicionário com x, y, z tuplas como chaves é uma outra solução, se você quiser uma solução relativamente simples com a biblioteca padrão.

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))

E devido a referenciação python, você pode alterar os "pontos" nos dicionários devolvidos, e têm os pontos originais mudar também (eu acho).

Answer 7

Quando usar Binary Space Partitioning, Quadtree, Octree?

array 3d imo é inútil. Especialmente se o seu mundo é dinâmico. Você deve decidir entre BSP, Quadtree ou Octtree. BSP faria muito bem. Desde o seu mundo é em 3D, você precisa de aviões quando a divisão do bsp, não linhas.

Felicidades!

Editar

Eu também terá dados para cada ponto em determinado espaço 3D, então eu acho que um Spare Matrix é ruim?

Eu acho que isso é tudo bem se sempre sabem como grande conjunto de dados que você é e que nunca muda, ou seja, se mais pontos são adicionados a ele que por sua vez estão fora do limite. Você teria que redimensionar a matriz 3d nesse caso.

Answer 8

Ela depende da configuração precisa do seu sistema, mas a partir do exemplo que você dá você estiver usando números inteiros e pontos discretos, então provavelmente seria apropriado considerar estruturas de dados Sparse Matrix .