Abstand von Koordinaten in 2d

[mathematik]

Hallo zusammen,

ich komme leider bei meinem Problem nicht weiter und bräuchte Hilfe.
Was ich machen will ist folgendes:
Ich habe zwei Liste (x und y) von Koordinaten im 2d Raum (x enthält meine x-Koordinaten und y meine y-Koordinaten eines jeden Punktes). Nun möchte ich zu jedem Punkt dieser Liste (also zb zu jedem (x[0],y[0])) die Punkte, die maximal den konstanten Abstand d haben.
Hierfür hatte ich mir folgendes überlegt:

Code: Alles auswählen

k1=[]
i=0
for j in range(len(x)-1):
    if (sqrt((x[i]-x[j])**2+(y[i]-y[j])**2))<d:
        k1.append((i,j))
        if j==(len(x)-1):
            if i<range(len(x)-1):
                i=i+1 
            else:
                break
        else:
            j=j+1
    else:
        if j<range(len(x)-1):
            j=j+1
        else:
            if j==(len(x)-1):
                if i<range(len(x)-1):
                    i=i+1 
                else:
                    break

Das Problem dabei ist jetzt, dass in k1 nur Elemente der Form (0,j) enthält. Warum wird i+1 nicht ausgeführt?
Wär super, wenn mir jemand helfen könnte!
Danke!

[BlackJack]

@mathematik: Das wird entweder nie oder immer ausgeführt je nachdem ob der „kleiner”-Vergleich zwischen einer Zahl und einer Liste (was drin ist, ist vollkommen egal) ausgeht. Was hattest Du denn von ``i < range(len(x))`` erwartet?

Das ist ja alles superkompliziert geschrieben und die Aufgabenstellung ist mir auch nicht so klar, beziehungsweise das was ich aus der Aufgabenstellung herauslese kann keine flache Liste als Ergebnis haben, sondern eine Liste für jeden Punkt.

Ich würde als erstes mal die Daten für die Punkte nicht in verschiedenen Listen speichern. Daten die zusammen gehören sollten auch in *einer* Datenstruktur zusammengefasst werden und nicht auf verschiedene verteilt werden. Am besten schreibt man sich eine `Point`-Klasse dafür.

Und was möchtest Du denn nun als Ergebnis haben? Eine Liste für jeden Punkt? oder nur eine Liste für einen Punkt? Oder tatsächlich alles in einer Liste? Mit Wiederholungen? Oder doch eher eine Menge (`set()`)? Wie sieht es mit der Reihenfolge aus?

Falls Du übrigens das Kreuzprodukt von ``range(len(x))`` und ``range(len(y))`` bilden wolltest mit diesen ganzen verschachtelten ``if``/``else``, dann solltest Du Dir mal das `itertools`-Modul anschauen. Für so etwas gibt es schon Funktionen.

Eine Funktion die alle Punkte aus einem iterierbaren Objekt `points` filtert, die näher als `distance` zu einem gegebenen `point` sind (aber nicht dieser Punkt selbst) könnte so aussehen:

Code: Alles auswählen

def points_within_distance(point, points, distance):
    return [
        p for p in points if p is not point and p.distance(point) < distance
    ]

Warum hast Du eigentlich immer 1 von ``len(x)`` und ``len(y)`` abgezogen? Soll der letzte Punkt nicht berücksichtigt werden?

[EyDu]

Code: Alles auswählen

>>> import numpy
>>> import scipy.spatial
>>> points = numpy.random.random((10,2))
>>> tree = scipy.spatial.KDTree(points)
>>> tree.query_ball_tree(tree, 0.3)
[[0], [1, 4], [2], [3, 6, 9], [1, 4], [5], [3, 6, 7, 8], [6, 7, 8], [6, 7, 8], [3, 9]]

oder

Code: Alles auswählen

>>> balls = [[] for _ in xrange(points.shape[0])]
>>> for source, target in tree.query_pairs(0.3):
...     balls[source].append(target)
...     balls[target].append(source)
...                                                                                                                        
>>> balls                                                                                                                  
[[], [4], [], [9, 6], [1], [], [7, 8, 3], [6, 8], [6, 7], [3]]

oder

Code: Alles auswählen

>>> import collections                                                                          
>>> balls = collections.defaultdict(list)                                                                          
>>> for source, target in tree.query_pairs(0.3):                                                       
...     balls[source].append(target)                                                             
...     balls[target].append(source)                                                             
...                                                                                                                        
>>> balls                                                                                                                  
defaultdict(<type 'list'>, {1: [4], 3: [9, 6], 4: [1], 6: [7, 8, 3], 7: [6, 8], 8: [6, 7], 9: [3]})

[mathematik]

Super - DANKE!!
Jetzt hab ichs geschafft