Finden Sie die Entfernung zwischen 2 Punkten auf Raster

Question

Im Finden der Entfernung zwischen zwei Punkten, gegeben departure = [x,y] und destination = [x,y]. Mit x oder y ist einer immer ein float und der andere ein int, also immer auf einer Linie. Sie müssen auf den Gitternetzlinien bleiben, um zum Zielpunkt zu gelangen, und es gibt keine Satzinkrementierung. Ich habe keine anderen Beiträge über das Finden von Entfernungen auf einem Gitter gesehen, die sich mit dem Mix aus Ints und Floats befassen, also bin ich hier.

Dies ist mein Code:

def perfectCity(departure, destination): 
    return abs(destination[0]-departure[0]) + abs(destination[1]-departure[1]) 

Ein Beispiel departure = [0.4, 1] und destination = [0.9, 3] wäre, sollte es 2,7 gleich, aber ich bekomme 2,5

Beispiel: Sie gehen [0.4, 1]-[1, 1] zu [1, 3]-[0.9, 3] für eine Gesamtdifferenz von 2,7. Es ist, als würde man die Manhattan-Distanz berechnen, aber anstatt an Gitterpunkten zu beginnen und zu enden, könnte man einen halben Block entlang beginnen und/oder enden.

Answer 1

Wenn man sich die verschiedenen Kombinationen aussehen, wie es scheint Der naive Manhattan-Abstand funktioniert, außer, wenn Ihr Pfad eine "C" -Form annimmt (wie im Beispiel angegeben). Dies geschieht genau dann, wenn Ihre beiden Gleitkommawerte beide x-Koordinaten sind oder die y-Koordinaten und den gleichen ganzzahligen Teil haben.

könnte ein Versuch wie folgt aussehen:

def minimum_distance(p1, p2): 

    i1, i2 = int(p1[0]), int(p2[0]) 

    # if both x-coordinates are floats and they have the same integer part 
    if i1 != p1[0] and i2 != p2[0] and i1 == i2: 

     # find the decimal parts 
     d1, d2 = p1[0] - i1, p2[0] - i2 

     # find the smaller "C" 
     x = min(d1 + d2, (1-d1) + (1-d2)) 

     # add the y distance to the "C" distance 
     return abs(p1[1] - p2[1]) + x 

    # repeat with the "y-coordinates are floats" case 
    i1, i2 = int(p1[1]), int(p2[1]) 
    if i1 != p1[1] and i2 != p2[1] and i1 == i2: 
     d1, d2 = p1[1] - i1, p2[1] - i2 
     y = min(d1 + d2, (1-d1) + (1-d2)) 
     return abs(p1[0] - p2[0]) + y 

    # simple case, return the Manhattan distance 
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1]) 


print(minimum_distance([0.4, 1], [0.9, 3])) 
# 2.7 

Answer 2

Es ist nicht die Mischung aus int und float, wahrscheinlich haben Sie einen Gleitkommafehler. floats sind nicht genau, sie sind ungefähre Angaben und können daher um kleine Beträge "aus" sein.

Sie könnten Decimal Objekte verwenden, die vom Modul decimal bereitgestellt werden, um mit Gleitkommawerten genau zu arbeiten. Hier ein Beispiel:

>>> 1.1 + 2.2  # will produce small error 
3.3000000000000003 
>>> from decimal import Decimal 
>>> Decimal('1.1') + Decimal('2.2') 
Decimal('3.3') 

Das Endergebnis wird noch „off“, aber Decimal mit helfen kumulative Rundungsfehler zu vermeiden:

>>> 3.3 - (1.1 + 2.2) 
-4.440892098500626e-16 
>>> Decimal(3.3) - (Decimal(1.1) + Decimal(2.2)) 
Decimal('-4.440892098500250464677810669E-16') 
>>> Decimal('3.3') - (Decimal('1.1') + Decimal('2.2')) 
Decimal('0.0') 

Answer 3

Von jedem Haus ein Taxi zu einer Ecke mit kurzer Reichweite nehmen. Sie haben zwei Möglichkeiten, dies zu tun. Dann - nehmen Sie ein Langstrecken-Taxi zwischen den resultierenden Ecken. Es gibt 2x2 = 4 Möglichkeiten, abhängig von den gefahrenen Ecken. Nehmen Sie die min:

from math import ceil,floor 

#as a helper function, vanilla taxicab: 

def t(p,q): 
    x,y = p 
    z,w = q 
    return abs(x-z)+abs(y-w) 

#find the two corners closest to a point: 

def corners(p): 
    x,y = p 
    if isinstance(x,float): 
     return [(floor(x),y),(ceil(x),y)] 
    else: 
     return [(x,floor(y)), (x,ceil(y))] 

#combine these: 

def dist(p,q): 
    return min(t(p,c) + t(c,d) + t(d,q) for c in corners(p) for d in corners(q)) 

Zum Beispiel

>>> dist((.4,1),(.9,3)) 
2.7