Wie kann der euklidische Abstand mit NumPy berechnet werden?

Question

Ich habe zwei Punkte in 3D:

(xa, ya, za)
(xb, yb, zb)

Und ich möchte, um den Abstand berechnen:

dist = sqrt((xa-xb)^2 + (ya-yb)^2 + (za-zb)^2)

Was ist der beste Weg, dies im Allgemeinen mit NumPy oder mit Python zu tun? Ich habe:

a = numpy.array((xa ,ya, za))
b = numpy.array((xb, yb, zb))

Answer 1

Verwenden Sie numpy.linalg.norm :

dist = numpy.linalg.norm(a-b)

Answer 2

Es gibt eine Funktion für das in SciPy. Es heißt euklidischen .

Beispiel:

from scipy.spatial import distance
a = (1, 2, 3)
b = (4, 5, 6)
dst = distance.euclidean(a, b)

Answer 3

Für alle Interessierten bei der Berechnung auf einmal mehrere Entfernungen, ich habe ein wenig Vergleich gemacht mit perfplot ( ein kleines Projekt von mir). Es stellt sich heraus, dass

a_min_b = a - b
numpy.sqrt(numpy.einsum('ij,ij->i', a_min_b, a_min_b))

berechnet die Abstände der Reihen in a und b schnellsten. Dies gilt eigentlich gilt für nur eine Zeile, wie gut!

---

Code, um das Grundstück zu reproduzieren:

import matplotlib
import numpy
import perfplot
from scipy.spatial import distance


def linalg_norm(data):
    a, b = data
    return numpy.linalg.norm(a-b, axis=1)


def sqrt_sum(data):
    a, b = data
    return numpy.sqrt(numpy.sum((a-b)**2, axis=1))


def scipy_distance(data):
    a, b = data
    return list(map(distance.euclidean, a, b))


def mpl_dist(data):
    a, b = data
    return list(map(matplotlib.mlab.dist, a, b))


def sqrt_einsum(data):
    a, b = data
    a_min_b = a - b
    return numpy.sqrt(numpy.einsum('ij,ij->i', a_min_b, a_min_b))


perfplot.show(
    setup=lambda n: numpy.random.rand(2, n, 3),
    n_range=[2**k for k in range(20)],
    kernels=[linalg_norm, scipy_distance, mpl_dist, sqrt_sum, sqrt_einsum],
    logx=True,
    logy=True,
    xlabel='len(x), len(y)'
    )

Answer 4

Ein weiteres Beispiel von Die Lösung dieses Problems Methode :

def dist(x,y):   
    return numpy.sqrt(numpy.sum((x-y)**2))

a = numpy.array((xa,ya,za))
b = numpy.array((xb,yb,zb))
dist_a_b = dist(a,b)

Answer 5

Ich möchte auf die einfache Antwort mit verschiedenen Leistungs Notizen erklären. np.linalg.norm tun wird vielleicht mehr als Sie brauchen:

dist = numpy.linalg.norm(a-b)

Zum einen - ist diese Funktion entwickelt, um eine Liste zu arbeiten, immer und alle Werte zurückgeben, z.B. den Abstand von pA auf den Satz von Punkten zu vergleichen sP:

sP = set(points)
pA = point
distances = np.linalg.norm(sP - pA, ord=2, axis=1.)  # 'distances' is a list

Denken Sie daran, mehrere Dinge:

• Python Funktionsaufrufe sind teuer.
• [Standard] Python nicht Name Lookups zwischenspeichern.

So

def distance(pointA, pointB):
    dist = np.linalg.norm(pointA - pointB)
    return dist

ist nicht so unschuldig, wie es aussieht.

>>> dis.dis(distance)
  2           0 LOAD_GLOBAL              0 (np)
              2 LOAD_ATTR                1 (linalg)
              4 LOAD_ATTR                2 (norm)
              6 LOAD_FAST                0 (pointA)
              8 LOAD_FAST                1 (pointB)
             10 BINARY_SUBTRACT
             12 CALL_FUNCTION            1
             14 STORE_FAST               2 (dist)

  3          16 LOAD_FAST                2 (dist)
             18 RETURN_VALUE

Zum einen - jedes Mal, wenn wir es nennen, haben wir eine globale Suche für „np“ zu tun hat, ein scoped-Suche für „linalg“ und ein scoped-Suche nach „Norm“, und der Overhead von nur Aufruf kann die Funktion, um Dutzende von python Anweisungen zu.

Schließlich verloren wir zwei Operationen auf das Ergebnis zu speichern und legen Sie es für die Rückkehr ...

Erster Durchgang auf einer Verbesserung: den Nachschlag schneller machen, lassen Sie die Speicher

def distance(pointA, pointB, _norm=np.linalg.norm):
    return _norm(pointA - pointB)

Wir bekommen die weit straffere:

>>> dis.dis(distance)
  2           0 LOAD_FAST                2 (_norm)
              2 LOAD_FAST                0 (pointA)
              4 LOAD_FAST                1 (pointB)
              6 BINARY_SUBTRACT
              8 CALL_FUNCTION            1
             10 RETURN_VALUE

Der Funktionsaufruf Overhead beträgt weiterhin etwas Arbeit, aber. Und Sie werden Benchmarks tun wollen, um zu bestimmen, ob Sie vielleicht besser wäre, zu tun, die Mathematik selbst:

def distance(pointA, pointB):
    return (
        ((pointA.x - pointB.x) ** 2) +
        ((pointA.y - pointB.y) ** 2) +
        ((pointA.z - pointB.z) ** 2)
    ) ** 0.5  # fast sqrt

Auf einigen Plattformen ist **0.5 schneller als math.sqrt. Ihre Ergebnisse können variieren.

**** Erweiterte Leistungs Noten.

Warum Berechnen Sie Abstand? Wenn der einzige Zweck ist es angezeigt,

 print("The target is %.2fm away" % (distance(a, b)))

entlang bewegen. Aber wenn Sie Entfernungen sind zu vergleichen, Bereichsprüfungen tun, usw., ich möchte einige nützliche Leistung Beobachtungen hinzuzufügen.

Lassen Sie uns zwei Fälle nehmen. Nach Entfernung sortieren oder eine Liste zu Artikel Culling, die eine Reihe Einschränkung erfüllen

# Ultra naive implementations. Hold onto your hat.

def sort_things_by_distance(origin, things):
    return things.sort(key=lambda thing: distance(origin, thing))

def in_range(origin, range, things):
    things_in_range = []
    for thing in things:
        if distance(origin, thing) <= range:
            things_in_range.append(thing)

Das erste, was wir uns erinnern müssen ist, dass wir Pythagoras verwenden die zur Berechnung Abstand (dist = sqrt(x^2 + y^2 + z^2)), so sind wir viele sqrt Anrufe. Math 101:

dist = root ( x^2 + y^2 + z^2 )
:.
dist^2 = x^2 + y^2 + z^2
and
sq(N) < sq(M) iff M > N
and
sq(N) > sq(M) iff N > M
and
sq(N) = sq(M) iff N == M

Kurz gesagt:., Bis wir tatsächlich den Abstand in einer Einheit von X benötigen anstatt X ^ 2, können wir den schwierigsten Teil der Berechnungen eliminieren

# Still naive, but much faster.

def distance_sq(left, right):
    """ Returns the square of the distance between left and right. """
    return (
        ((left.x - right.x) ** 2) +
        ((left.y - right.y) ** 2) +
        ((left.z - right.z) ** 2)
    )

def sort_things_by_distance(origin, things):
    return things.sort(key=lambda thing: distance_sq(origin, thing))

def in_range(origin, range, things):
    things_in_range = []

    # Remember that sqrt(N)**2 == N, so if we square
    # range, we don't need to root the distances.
    range_sq = range**2

    for thing in things:
        if distance_sq(origin, thing) <= range_sq:
            things_in_range.append(thing)

Großer, beide Funktionen nichtmehr keine teueren Quadratwurzeln tun. Das wird viel schneller. Wir können auch in_range verbessern, indem sie an einen Generator Umwandlung:

def in_range(origin, range, things):
    range_sq = range**2
    yield from (thing for thing in things
                if distance_sq(origin, thing) <= range_sq)

Dies hat insbesondere Vorteile, wenn Sie tun so etwas wie:

if any(in_range(origin, max_dist, things)):
    ...

Aber wenn schon am nächsten, was Sie erfordert eine Entfernung tun werden,

for nearby in in_range(origin, walking_distance, hotdog_stands):
    print("%s %.2fm" % (nearby.name, distance(origin, nearby)))

betrachten Nachgeben Tupeln:

def in_range_with_dist_sq(origin, range, things):
    range_sq = range**2
    for thing in things:
        dist_sq = distance_sq(origin, thing)
        if dist_sq <= range_sq: yield (thing, dist_sq)

Dies kann besonders nützlich sein, wenn Sie Kettenbereichsprüfungen könnten ( ‚Dinge, die in der Nähe von X und innerhalb Nm von Y‘, da Sie den Abstand wieder nicht berechnen müssen).

Aber was ist, wenn wir eine wirklich große Liste von things sind und wir erwarten eine Menge von ihnen nicht eine Überlegung wert zu sein?

Es ist eigentlich eine sehr einfache Optimierung:

def in_range_all_the_things(origin, range, things):
    range_sq = range**2
    for thing in things:
        dist_sq = (origin.x - thing.x) ** 2
        if dist_sq <= range_sq:
            dist_sq += (origin.y - thing.y) ** 2
            if dist_sq <= range_sq:
                dist_sq += (origin.z - thing.z) ** 2
                if dist_sq <= range_sq:
                    yield thing

Ob dies sinnvoll ist von der Größe der ‚Dinge‘ abhängen wird.

def in_range_all_the_things(origin, range, things):
    range_sq = range**2
    if len(things) >= 4096:
        for thing in things:
            dist_sq = (origin.x - thing.x) ** 2
            if dist_sq <= range_sq:
                dist_sq += (origin.y - thing.y) ** 2
                if dist_sq <= range_sq:
                    dist_sq += (origin.z - thing.z) ** 2
                    if dist_sq <= range_sq:
                        yield thing
    elif len(things) > 32:
        for things in things:
            dist_sq = (origin.x - thing.x) ** 2
            if dist_sq <= range_sq:
                dist_sq += (origin.y - thing.y) ** 2 + (origin.z - thing.z) ** 2
                if dist_sq <= range_sq:
                    yield thing
    else:
        ... just calculate distance and range-check it ...

Und wieder, denken Sie daran was die dist_sq. Unser Hotdog Beispiel wird dann:

# Chaining generators
info = in_range_with_dist_sq(origin, walking_distance, hotdog_stands)
info = (stand, dist_sq**0.5 for stand, dist_sq in info)
for stand, dist in info:
    print("%s %.2fm" % (stand, dist))

Answer 6

Ich finde einen ‚dist‘ -Funktion in matplotlib.mlab, aber ich glaube nicht, dass genug handlich ist.

Ich poste es hier nur als Referenz.

import numpy as np
import matplotlib as plt

a = np.array([1, 2, 3])
b = np.array([2, 3, 4])

# Distance between a and b
dis = plt.mlab.dist(a, b)

Answer 7

Es kann wie die folgenden durchgeführt werden. Ich weiß nicht, wie schnell es ist, aber es ist nicht mit NumPy.

from math import sqrt
a = (1, 2, 3) # Data point 1
b = (4, 5, 6) # Data point 2
print sqrt(sum( (a - b)**2 for a, b in zip(a, b)))

Answer 8

Sie können nur die Vektoren subtrahieren und dann innerproduct.

Im Anschluss an Ihrem Beispiel

a = numpy.array((xa, ya, za))
b = numpy.array((xb, yb, zb))

tmp = a - b
sum_squared = numpy.dot(tmp.T, tmp)
result sqrt(sum_squared)

Es ist einfach Code und ist leicht zu verstehen.

Answer 9

Ich mag np.dot (dot product):

a = numpy.array((xa,ya,za))
b = numpy.array((xb,yb,zb))

distance = (np.dot(a-b,a-b))**.5

Answer 10

Starten Python 3.8, die math Modul liefert direkt die dist Funktion, die den euklidischen Abstand zwischen zwei Punkten zurückgibt (als Tupel gegebenen von Koordinaten):

from math import dist

dist((1, 2, 6), (-2, 3, 2)) # 5.0990195135927845

Wenn Sie mit Listen anstelle von Tupeln arbeiten:

dist(tuple([1, 2, 6]), tuple([-2, 3, 2]))

Answer 11

Mit a und b, wie Sie sie definiert, können Sie auch:

distance = np.sqrt(np.sum((a-b)**2))

Answer 12

Ein schöner Einzeiler:

dist = numpy.linalg.norm(a-b)

Wenn jedoch die Geschwindigkeit ein Anliegen würde ich das Experimentieren auf Ihrer Maschine empfehlen. Ich fand, dass für den Platz der math Bibliothek sqrt mit dem ** Operator ist viel schneller auf meiner Maschine als die Einzeiler NumPy Lösung.

Ich ließ meine Tests dieses einfache Programm mit:

#!/usr/bin/python
import math
import numpy
from random import uniform

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

def math_calc_dist(p1,p2):
    return math.sqrt(math.pow((p2[0] - p1[0]), 2) +
                     math.pow((p2[1] - p1[1]), 2) +
                     math.pow((p2[2] - p1[2]), 2))

def numpy_calc_dist(p1,p2):
    return numpy.linalg.norm(numpy.array(p1)-numpy.array(p2))

TOTAL_LOCATIONS = 1000

p1 = dict()
p2 = dict()
for i in range(0, TOTAL_LOCATIONS):
    p1[i] = (uniform(0,1000),uniform(0,1000),uniform(0,1000))
    p2[i] = (uniform(0,1000),uniform(0,1000),uniform(0,1000))

total_dist = 0
for i in range(0, TOTAL_LOCATIONS):
    for j in range(0, TOTAL_LOCATIONS):
        dist = fastest_calc_dist(p1[i], p2[j]) #change this line for testing
        total_dist += dist

print total_dist

Auf meinem Rechner math_calc_dist läuft viel schneller als numpy_calc_dist. 1,5 Sekunden im Vergleich zu 23,5 Sekunden

Um einen messbaren Unterschied zwischen fastest_calc_dist bekommen und math_calc_dist musste ich bis TOTAL_LOCATIONS bis 6000. Dann fastest_calc_dist nimmt ~ 50 Sekunden , während math_calc_dist nimmt ~ 60 Sekunden .

Sie können auch mit numpy.sqrt und numpy.square experimentieren obwohl beide langsamer waren als die math Alternativen auf meinem Rechner.

Meine Tests wurden mit Python 2.6.6.

Answer 13

Hier einige kurzen Code für euklidische Distanz in Python gegeben zwei Punkte als Listen in Python dargestellt.

def distance(v1,v2): 
    return sum([(x-y)**2 for (x,y) in zip(v1,v2)])**(0.5)

Answer 14

import numpy as np
from scipy.spatial import distance
input_arr = np.array([[0,3,0],[2,0,0],[0,1,3],[0,1,2],[-1,0,1],[1,1,1]]) 
test_case = np.array([0,0,0])
dst=[]
for i in range(0,6):
    temp = distance.euclidean(test_case,input_arr[i])
    dst.append(temp)
print(dst)

Answer 15

import math

dist = math.hypot(math.hypot(xa-xb, ya-yb), za-zb)

Answer 16

Sie können leicht die Formel verwenden

distance = np.sqrt(np.sum(np.square(a-b)))

was tut eigentlich nichts mehr als nach Satz des Pythagoras berechnet den Abstand, mit Addition der Quadrate von Ax, Ay und Az und Verwurzelung des Ergebnisses aus.

Answer 17

Berechne den euklidischen Abstand für mehrdimensionalen Raum:

 import math

 x = [1, 2, 6] 
 y = [-2, 3, 2]

 dist = math.sqrt(sum([(xi-yi)**2 for xi,yi in zip(x, y)]))
 5.0990195135927845

Answer 18

Suche Differenz zweier Matrizen zuerst. Dann Element weise Multiplikation mit numpy des mehrfach Befehl anzuwenden. Danach finden Summierung des Elements weise neue Matrix multipliziert. Schließlich Quadratwurzel aus der Summe finden.

def findEuclideanDistance(a, b):
    euclidean_distance = a - b
    euclidean_distance = np.sum(np.multiply(euclidean_distance, euclidean_distance))
    euclidean_distance = np.sqrt(euclidean_distance)
    return euclidean_distance