wake-up-neo.net

Entfernungsformel zwischen zwei Punkten in einer Liste

Ich muss eine Liste, die ich erstellt habe, nehmen und die nächsten zwei Punkte finden und ausdrucken. Wie kann ich jeden Punkt in der Liste vergleichen?

Es ist nicht notwendig, zu zeichnen oder irgendetwas, einfach die Punkte zu vergleichen und die nächsten zwei in der Liste zu finden.

import math # 'math' needed for 'sqrt'

# Distance function
def distance(xi,xii,yi,yii):
    sq1 = (xi-xii)*(xi-xii)
    sq2 = (yi-yii)*(yi-yii)
    return math.sqrt(sq1 + sq2)

# Run through input and reorder in [(x, y), (x,y) ...] format
oInput = ["9.5 7.5", "10.2 19.1", "9.7 10.2"] # Original input list (entered by spacing the two points).
mInput = [] # Manipulated list
fList = [] # Final list
for o in oInput:
    mInput = o.split()
    x,y = float(mInput[0]), float(mInput[1])
    fList += [(x, y)] # outputs [(9.5, 7.5), (10.2, 19.1), (9.7, 10.2)]
20
morcutt

Es ist praktischer, Ihre distance()-Funktion neu zu schreiben, um zwei (x, y)-Tupel als Parameter zu übernehmen:

def distance(p0, p1):
    return math.sqrt((p0[0] - p1[0])**2 + (p0[1] - p1[1])**2)

Jetzt möchten Sie alle Paare von Punkten aus Ihrer Liste fList durchlaufen. Die Funktion iterools.combinations() ist für diesen Zweck hilfreich:

min_distance = distance(fList[0], fList[1])
for p0, p1 in itertools.combinations(fList, 2):
    min_distance = min(min_distance, distance(p0, p1))

Alternativ können Sie distance() definieren, um das Punktepaar in einem einzigen Parameter zu akzeptieren

def distance(points):
    p0, p1 = points
    return math.sqrt((p0[0] - p1[0])**2 + (p0[1] - p1[1])**2)

und verwenden Sie den key-Parameter für die integrierte min()-Funktion:

min_pair = min(itertools.combinations(fList, 2), key=distance)
min_distance = distance(min_pair)
34
Sven Marnach

Ich stelle fest, dass es in dieser Frage Bibliotheksbeschränkungen gibt, aber zur Vollständigkeit, wenn Sie N Punkte in einem Nx2 numpy ndarray (2D-System) haben:

from scipy.spatial.distance import pdist
x = numpy.array([[9.5,7.5],[10.2,19.1],[9.7,10.2]])
mindist = numpy.min(pdist(x))

Ich versuche immer, Menschen dazu zu ermutigen, numpy/scipy zu verwenden, wenn es sich um Daten handelt, die am besten in einem numerischen Array gespeichert werden, und es ist gut zu wissen, dass die Tools zur späteren Verwendung verfügbar sind.

11
JoshAdel

Beachten Sie, dass die math.sqrt-Funktion sowohl langsam als auch in diesem Fall unnötig ist. Vergleichen Sie die Entfernung zum Quadrat, um sie zu beschleunigen (Sortierentfernungen vs. Entfernungsdistanz ergeben immer die gleiche Reihenfolge):

def distSquared(p0, p1):
    return (p0[0] - p1[0])**2 + (p0[1] - p1[1])**2
2
Aaron Dufour

Ihr fester Code. Kein effizienter Algorithmus, nur der rohe Zwang.

import math # math needed for sqrt

# distance function
def dist(p1, p2):
    return math.sqrt((p2[0] - p1[0]) ** 2 + (p2[1] - p1[1]) ** 2)

# run through input and reorder in [(x, y), (x,y) ...] format
input = ["9.5 7.5", "10.2 19.1", "9.7 10.2"] # original input list (entered by spacing the two points)
points = [map(float, point.split()) for point in input] # final list

# http://en.wikipedia.org/wiki/Closest_pair_of_points
mindist = float("inf")
for p1, p2 in itertools.combinations(points, 2):
    if dist(p1, p2) < mindist:
        mindist = dist(p1, p2)
        closestpair = (p1, p2)

print(closestpair)
2
orlp

Das könnte funktionieren:

oInput = ["9.5 7.5", "10.2 19.1", "9.7 10.2"]

# parse inputs
inp = [(float(j[0]), float(j[1])) for j in [i.split() for i in oInput]]

# initialize results with a really large value
min_distance = float('infinity')
min_pair = None

# loop over inputs
length = len(inp)
for i in xrange(length):
    for j in xrange(i+1, length):
        point1 = inp[i]
        point2 = inp[j]

        if math.hypot(point1[0] - point2[0], point1[1] - point2[0]) < min_distance:
            min_pair = [point1, point2]

sobald die Schleifen abgeschlossen sind, sollte min_pair das Paar mit der geringsten Entfernung sein.

Die Verwendung von float () zum Analysieren des Textes lässt noch Raum für Verbesserungen.

math.hypot ist etwa ein Drittel schneller als die Berechnung der Entfernung in einer handgeschriebenen Python-Funktion

1
HumanCatfood

Zunächst einige Hinweise:

a**2 # squares a
(xi - xii)**2 # squares the expression in parentheses.

mInput muss nicht vorab deklariert werden.
fList.append((x, y)) ist mehr Pythonic als +=.

Jetzt haben Sie fList. Ihre Distanzfunktion kann umgeschrieben werden, um 2 2-Tuple (Punkt) -Argumente aufzunehmen, mit denen ich mich hier nicht beschäftige.

Dann kannst du einfach schreiben:

shortest = float('inf')
for pair in itertools.combinations(fList, 2):
    shortest = min(shortest, distance(*pair))
0
nmichaels