Effizient zwei 3D-Punktwolken miteinander vergleichen

[HeyHo26]

Hallo zusammen,

ich habe folgendes "Problem": Ich würde gerne 2 unterschiedliche Punktwolken mit einander vergleichen. Wenn Punkt aus Menge A mit Punkt aus Menge B (zzgl. eines Sicherheitsfaktors oder Suchradius r) übereinstimmt, soll die Point ID des Punktes aus Menge B abgespeichert werden. Jeder Punkt hat jeweils eine Point ID und eine x,y und z Koordinate.

Mein Skript sieht bisher so aus, dass ich eine doppelte for schleife verwende, was teilweise dann halbe Tage vor sich her rechnet, da die Mengen A und B jeweils mehrere 100k Punkte enthalten. Daher die Frage, ob es dort auch effizientere Ansätze gibt

Nachdem ich beide Mengen als Liste/ Array mit dem Header "Point ID;x;y;z" importiert habe, sieht mein Code wie folgt aus. Zudem lösche ich alle bereits gefundenen Punkte aus der Menge B raus, damit sie nicht nochmal durchsucht werden.

Code: Alles auswählen

l_result=[] #Ergebnis Liste 
 n=0
    for j in list_A:
        #Umwandeln String in float
        A_x = float(list_A[n]["x"])
        A_y = float(list_A[n]["y"])
        A_z = float(list_A[n]["z"]) 
        m=0
        for i in list_B:
		#Umwandeln String in float
            B_x = float(list_B[m]["x"])
            B_y = float(list_B[m]["y"])
            B_z = float(list_B[m]["z"]) 
			#Vergleich
            if A_x-r<=B_x and A_x+r>=B_x and A_y-r<=B_y and A_y+r>=B_y and A_z-r<=B_z and A_z+r>=B_z:
                l_result.append(str(list_B[m]["Point ID"])) 
                list_B.remove(list_B[m])
            else:
                m=m+1 
        n=n+1

Grüße und vielen Dank im voraus

[Sirius3]

Du hast was von Radius geschrieben, baust aber einen Würfel um die Punkte. Was denn nun?

Du iterierst über die Listen (`i` und `j` sind dabei sehr schlechte Variablennamen, genause wie list_A und list_B), benutzt diese aber gar nicht. Statt dessen zählst Du noch händisch einen Index mit. Das ist nicht nur umständlich und langsam, sondern auch schlechter Stil. Statt bei jeder Benutzung alles in Zahlen umzuwandeln, macht man das einmal am Anfang (also den Teil, den Du gar nicht zeigst).

Stopft man das ganze in Numpy-Arrays, könnte man die for-Schleifen deutlich beschleunigen, aber das ist nicht der richtige Weg. Besser ist es, einen Algorithmus zu benutzen, der nicht mit O(N*M) läuft, sondern O(N log(M)), indem Du einen Baum benutzt.

[__deets__]

Für solche Anwendungen gibt es die PCL: https://github.com/PointCloudLibrary/pc ... /README.md

[EyDu]

Oder alternativ das spatial-Modul aus SciPy: https://docs.scipy.org/doc/scipy/refere ... _ball_tree

[ThomasL]

Die Thematik hat mich mal interessiert und ich wollte wissen, wie schnell so etwas berechnet werden kann.
Ich erzeuge eine zufällige Punktwolke mit 1 Million ! Punkten.
In einer Kopie der Wolke werden 500k Punkte nur leicht verändert (+ 0.01 je Dimension)
die anderen 500k Punkte werden erheblich vergrößert (+ 5.0 je Dimension)
Es werden 2 KDTree Bäume erzeugt und die Funktion query_ball_tree() benötigt bei mir gerade mal 7,5 Minuten um die 500k ähnlichen Punkte zu finden.
Etwas schneller als ein "halber Tag".

Code: Alles auswählen

import numpy as np
from time import time
from scipy.spatial import KDTree

# Anzahl der Punkte pro Wolke
num_points = 1_000_000

# Erzeuge ein 2D Array Shape (1_000_000, 4) aus zufälligen Werten
vectors_a = np.random.rand(num_points, 4) * 100
# Die erste Spalte wird unser Index von 1.0 bis 1000000.0
# die Spalten 2,3,4 können als x,y,z Koordinaten betrachtet werden
vectors_a[:,0] = np.arange(1, num_points+1)

# Erzeugen der 2. Punktwolke durch kopieren der ersten
vectors_b = vectors_a.copy()
# Alle Koordinaten werden um 0.01 erhöht
vectors_b[:,1:] += 0.01
# In jeder 2. Reihe werden die Koordinaten um 5 erhöht um Abstand zu erzeugen
vectors_b[::2,1:] += 5.0
# Die 2. Punktwolke wird anhand der x-Koordinaten sortiert
vectors_b = vectors_b[vectors_b[:,1].argsort()]


# Erzeugen 2er Punktbäume
# https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.KDTree.html
tree_a = KDTree(vectors_a[:,1:])
tree_b = KDTree(vectors_b[:,1:])

# Finden der nächsten Nachbarn
min_distance = 0.01733
start = time()
neighbors = tree_b.query_ball_tree(tree_a, min_distance)
print(time()-start)
# 442.86 sec bei mir auf nem 6 Jahre alten Laptop

# Erzeugen der ID-Liste aus Wolke 2
near_ids = []
for i, value in enumerate(neighbors):
    if value:
        id1, x1, y1, z1 = vectors_a[value[0]]
        id2, x2, y2, z2 = vectors_b[i]
        near_ids.append(id2)

[ThomasL]

Code: Alles auswählen

# Erzeuge ein 2D Array Shape (1_000_000, 4) aus zufälligen Werten

Gemeint ist natürlich ein 4D Array, eine Spalte für den Index, die anderen Spalten für die 3D Punkt-Koordinaten

[HeyHo26]

Vielen lieben Dank für die ganzen Antworten, ich werde es morgen probieren umzusetzen!