Das speichern von Informationen auf Punkte im 3d-Raum

Bin ich einige code schreiben (nur zum Spaß so weit) in Python, die speichern einige Daten über jeden Punkt in einem 3d-Raum. Ich bin im Grunde nach einer 3d-matrix-Objekt, das speichert willkürliche Objekte, mit denen ich zu tun, einige erweiterte Auswahl, wie:

Bekommen der Punkt, wo x=1,y=2,z=3.
Immer alle Punkte, wo y=2.
Immer alle Punkte innerhalb von 3 Einheiten der position x=1,y=2,z=3.
Immer alle Punkte, wo Punkt.getType() == "Foo"

In allen der oben genannten, ich würde müssen, um am Ende mit irgendeiner Art von Ausgabe, würde mir die Originale position in den Raum, und die gespeicherten Daten an diesem Punkt.

Offenbar numpy kann tun was ich will, aber es scheint hoch optimiert für wissenschaftliches rechnen und arbeiten heraus, wie man die Daten möchte ich über bisher entzog sich mir.

Gibt es eine bessere alternative oder sollte ich zurück, schlug mein Kopf auf die numpy Wand? 🙂

EDIT: ein paar mehr Infos zu den ersten drei Antworten, die mir klar gemacht, ich sollte mir gehören: ich bin nicht besorgt über die Leistung, dies ist lediglich ein proof-of-concept, wo ich lieber sauberen code, um eine gute Leistung. Ich habe auch Daten für jeden Punkt in der gegebenen 3d-Raum, so dass ich denke, ein Ersatz-Matrix ist schlecht?

Ja, verwenden Sie einfach ein 3D-array, komplexere Strukturen sind nur für die Optimierung für einige Vorgänge in einige konkrete Fälle.
wenn Sie sagen, "points in space", ich nehme an, dass x,y,x sind kontinuierliche Variablen, z.B. Schwimmern, aber dein Beispiel impliziert ints. Wenn ints, eine sparse-matrix ist ok. Ansonsten benutzen Sie Tupel oder Objekte. Persönlich würde ich empfehlen den Aufstieg über den numpy Wand. Es ist grüne Weide auf der anderen Seite!

InformationsquelleAutor | 2009-05-26

Hier ist eine weitere gemeinsame Ansatz

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

Schauen wir uns Ihren Einsatz-Fälle.

Bekommen der Punkt, wo x=1,y=2,z=3.

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

Immer alle Punkte, wo y=2.

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

Immer alle Punkte innerhalb von 3 Einheiten der position x=1,y=2,z=3.

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

Immer alle Punkte, wo Punkt.getType() == "Foo"

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

Danke! Ich war immer gemischt in den Datenstrukturen komplizierter, als Sie sein sollte. Das funktioniert sehr gut und ermöglicht es mir, jede Art von Daten, die Auswahl, wie ich will, zu jeder Zeit.

InformationsquelleAutor S.Lott

3

Gut ... Wenn Sie erwarten, um wirklich füllen, dass der Raum, dann sind Sie wahrscheinlich am besten aus, mit einer dicht gepackten matrix-Struktur, im Grunde voxels.

Wenn Sie nicht erwarten, um ihn zu füllen, schauen Sie in etwas ein bisschen mehr optimiert. Ich würde beginnen Sie mit octrees, die Häufig verwendet werden, für Dinge wie diese.
- voxels sind nicht eine Daten-Struktur, es ist eine Technik zur Anzeige eines 3D-Gitter.
InformationsquelleAutor unwind
1

Einer der Vorteile von numpy ist, dass es rasend schnell,
z.B. die Berechnung des pagerank einer 8000x8000 Nähe matrix dauert Millisekunden. Obwohl numpy.ndarray akzeptieren nur zahlen, Sie können die store-Nummer/id-Objekt-mappings in einer externen hash-Tabelle, D. H. Wörterbuch (wieder ein hoch optimiertes datastructure).

Dem slicing-einfach als Liste slicing in 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]]
```
Wenn Sie wickeln einige der gewünschten Funktionen (Entfernungen), um einige Kern-matrix und ein id-Objekt-mapping-hash, Sie haben könnte, Ihre Anwendung innerhalb kurzer Zeit.

Glück!
- Ich dachte ndarray konnte nur das speichern von Rufnummern zu, aber er speichert nichts! numpy.ndarray([w,h,d],Objekt), Dies ist, was ich bin derzeit kämpfen mit, aber es ist ärgerlich genug, das ich hier gepostet für bessere Lösungen, die weniger knwledge der matrix Zeug!
- ok, als mein Vorschlag ist etwas sinnlos, ich werde es löschen; aber warum wollen Sie vermeiden matrix stuff; Matrizen sind, würde ich nicht sagen Spaß, aber Recht ordentlich. und für Ihre slicing -, Zugang, die ndarray ist groß - warum also nicht nutzen?
- Tatsächlich, es ist weit von sinnlos, es ist die Methode, die ich werde mit jetzt. Ich habe gerade meine eigene benutzerdefinierte Klasse an jedem Punkt. Der einzige Grund, warum ich es nicht mag, ist, dass viele numpy scheint davon ausgehen, dass Sie wissen, mit matrix-Mathematik/Terminologie, und da weiß ich nicht, es ist einfach etwas anderes, um swot up auf.
InformationsquelleAutor miku
0

Hier ist ein Ansatz, die arbeiten dürfen.

Jeder Punkt ist ein 4-Tupel (x,y,z,Daten), und die Datenbank sieht so aus:
```
database = [ (x,y,z,data), (x,y,z,data), ... ]
```
Schauen wir uns Ihren Einsatz-Fälle.

Bekommen der Punkt, wo x=1,y=2,z=3.
```
[ (x,y,z,data) for x,y,z,data in database if (x,y,z) == (1,2,3) ]
```
Immer alle Punkte, wo y=2.
```
[ (x,y,z,data) for x,y,z,data in database if y == 2 ]
```
Immer alle Punkte innerhalb von 3 Einheiten der position 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 ]
```
Immer alle Punkte, wo Punkt.getType() == "Foo"
```
[ (x,y,z,data) for x,y,z,data in database if type(data) == Foo ]
```
- Das wird wahnsinnig langsam für die Suche!
- Waldschnepfe: Es ist, wie RDBMS der Arbeit, so gibt es einen Präzedenzfall für diese Architektur. Weitere, Indizierung Hinzugefügt werden können, wenn das Datenvolumen rechtfertigt. Da wir nicht wissen, das Volumen der Daten oder der Häufigkeit der Abfragen, die wir nicht genug wissen, um zu widersprechen, doch.
- Die "beliebigen Objekt" Anforderung ist ein kleines problem hier: wenn es unveränderlich ist, es erfordert, dass Sie drei Schritte, um einen Eintrag zu ändern: 1. entfernen Sie die alte 2-Tupel. bauen Sie neue Tupel 3. fügt neue Tupel. Natürlich, das wird kein problem sein, wenn Sie Ihre eigene Klasse für das Daten-Objekt.
- Egal, welche Klasse das zusätzliche Stück von Daten. Wir tun Wiederaufbau Trauben von Tupeln. Aber diese Tupel enthalten den gleichen ursprünglichen Objekte, unverändert, indem Sie wieder in zahlreichen neuen Tupel. Die zugrunde liegenden Objekte in all diesen Tupeln nie ändern.
InformationsquelleAutor S.Lott
0

Können Sie die ersten 2 Abfragen mit slicing in 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
```
Für die Dritte, wenn du meinst "immer alle Punkte innerhalb einer Kugel mit radius 3 und zentriert bei x=1,y=2,z=3" Sie haben zu schreiben, eine benutzerdefinierte Funktion zu tun ; wenn Sie möchten ein cube können Sie mit slicing, z.B.:
```
a[1:3, 1:3, 1:3] # The 2x2x2 array sliced from the center of 'a'
```
Für die vierte Abfrage, wenn nur die Daten gespeichert, in deinem array sind die Zellen geben, könnte man Sie verschlüsseln, wie ganze zahlen:
```
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 sieht aus wie ein gutes Programm für Sie tun, was Sie wollen, wie die Felder werden kleiner Speicher, der leicht zugänglich in C (oder noch besser, cython !) und erweiterte slicing-syntax, werden Sie zu vermeiden, code zu schreiben.

InformationsquelleAutor Luper Rouch

Verwenden ein Wörterbuch mit x,y,z Tupel als Schlüssel ist eine weitere Lösung, wenn Sie möchten, eine relativ einfache Lösung mit der standard-Bibliothek.

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

Und durch python-Referenzierung, den Sie verändern können "Punkte" in der zurückgegebenen Wörterbücher, und die ursprünglichen Punkte ändern sich auch (glaube ich).

InformationsquelleAutor

0

Wann Binary Space Partitioning, Quadtree, Octree?

3d-array imo wertlos ist. Vor allem, wenn Ihre Welt ist dynamisch. Sollten Sie sich entscheiden, zwischen BSP, Quadtree oder Octtree. BSP wäre genau richtig. Seit Sie Ihre Welt in 3d, müssen Sie Flugzeuge bei einer Aufteilung der bsp, nicht auf Zeilen.

Prost !

Bearbeiten

Will ich auch haben-Daten für jeden point
in der gegebenen 3d-Raum, so Schätze ich Sie ein
Ersatzteil Matrix ist schlecht?

Ich denke, das ist in Ordnung, wenn Sie immer wissen, wie groß Sie Daten festgelegt ist, und dass es sich nie ändert, d.h. wenn mehr Punkte Hinzugefügt werden, dass wiederum sind gebunden. Sie hätte, um die Größe des 3d-array in diesem Fall.

InformationsquelleAutor ralphtheninja
-1

Es hängt von der genauen Konfiguration Ihres Systems, aber von dem Beispiel, das Sie geben, Sie sind mit ganzen zahlen und diskreten Punkten, so wäre es wohl angebracht zu überlegen, Sparse Matrix Datenstrukturen.

InformationsquelleAutor Cruachan

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.