Izgarada 2 nokta arasındaki mesafeyi bulun

Question

departure = [x,y] ve destination = [x,y] verilen iki nokta arasındaki mesafeyi buluyorum. X veya y ile, her zaman bir kayan nokta ve diğeri int, bu yüzden her zaman bir satırda. Hedef noktaya ulaşmak için kılavuz çizgileri üzerinde kalmanız gerekir ve hiçbir ek artış yoktur. Ben burada inters ve floats karışımı ile ilgilenen bir ızgara üzerinde mesafe bulma konusunda herhangi bir mesaj görmedim.

Bu

benim kodudur:

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

bir örnek departure = [0.4, 1] ve destination = [0.9, 3] olacağını, bu 2.7 eşit olmalıdır, ama ben 2.5

Örneğin, [1, 3][0.9, 3] ila [1, 1] için [0.4, 1] gitmek olsun Toplam 2.7 fark için. Manhattan mesafesini hesaplamak gibidir, ancak kafes noktalarından başlamak ve bitirmek yerine, bir bloğun yarısına kadar başlayıp/veya sona erdirebilirsiniz.

Answer 1

, bu gibi görünüyor Naif Manhattan mesafesi, yolunuz "C" şeklini aldığında (örnekte verildiği gibi) hariç çalışacaktır. Bu, iki şamandıra noktanızın hem x koordinatları hem de y koordinatları ve aynı tamsayı parçasına sahip olması durumunda gerçekleşecektir. Her Evden

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

int ve float karışımı değil, muhtemelen kayan nokta hatasıyla karşılaşıyorsunuz. floats kesin değildir, yaklaşık değerlerdir ve bu nedenle küçük miktarlarda "kapalı" olabilirler.

decimal modülünün sağladığı Decimal nesnelerini, kayan nokta değerleriyle doğru şekilde çalışmak için kullanabilirsiniz. İşte bir örnek:

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

nihai sonuç yine "kapalı" olacak, ama Decimal kullanılarak kümülatif yuvarlama hatalarını önlemek için yardımcı olacaktır: Farklı kombinasyonlar baktığınızda

>>> 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

bir köşeye kısa menzilli taksiyi almak:

girişimi gibi görünebilir. Bunu yapmanın iki yolu var. Ardından, ortaya çıkan köşeler arasında uzun menzilli bir taksiler kullanın. Gezinilen köşelere bağlı olarak 2x2 = 4 olasılık vardır. min atın:

Örneğin

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)) 

,

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