Khoảng cách ngắn nhất giữa hai điểm Python

Trong bài này mình sẽ nói chi tiết hơn về ví dụ tìm khoảng cách ngắn nhất từ ​​một điểm đến một đoạn thẳng. Tôi sẽ đi từng bước một cho đến khi nhận được kết quả như trong hình 1

Cách tính khoảng cách giữa hai điểm

Tôi bắt đầu hướng dẫn này bằng một câu hỏi, làm cách nào để tìm khoảng cách giữa hai điểm? . Khoảng cách Euclide được sử dụng phổ biến nhất để tính toán đường thẳng giữa hai điểm trên hệ tọa độ Descartes. Khoảng cách Euclide có thể được tính bằng phương trình bên dưới. \[d=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2} \]

Trong triển khai Tìm kiếm Phần Vàng, việc tính toán khoảng cách sẽ được thực hiện trong mỗi lần lặp cho từng điểm bên trong $x_1$ và $x_2$. Đó là lý do tại sao trong hình 1, chúng ta có thể thấy hai đường màu đỏ từ một điểm xác định màu xanh bên ngoài đường thẳng đến mỗi điểm bên trong. Quá trình lặp sẽ tiếp tục và dừng khi đạt đến giá trị lỗi ngưỡng. Giá trị ngưỡng thực sự nhỏ như 0. 05 để đảm bảo sự khác biệt giữa hai khoảng cách thực sự nhỏ ở độ chính xác dài hoặc thậm chí giống nhau ở độ chính xác ngắn hơn

Triển khai Giải pháp bằng Python

Bây giờ hãy làm điều đó trong Python. Đầu tiên chúng ta cần nhập một số thư viện cần thiết, chẳng hạn như. numpy, matplotlib, thời gian và IPython

#IMPORTING REQUIRED LIBRARIES
%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
from IPython.display import clear_output
import time

Vì chúng ta đang làm việc với một dòng, chúng ta cần xác định hàm của dòng. Một chức năng cho một dòng có thể được thể hiện như. $f(x)=mx+b$. Trong đó $x$ là biến đầu vào, $m$ là hệ số góc và $b$ là hằng số

Độ dốc có thể được tính theo phương trình sau. \[m=\frac{y_2-y_1}{x_2-x_1} \] Sau đó, $b$ có thể được tìm thấy bằng cách thay giá trị của $y_1$ và $x_1$ hoặc $y_1$ và $x_1$ thành $f(

Dưới đây là hàm tính hệ số góc $m$ và $b$ với 4 biến đầu vào $x_1$,$y_1$ và $x_2$,$y_2$ là tọa độ đầu và cuối của một đoạn thẳng

def line_func(x1,x2,y1,y2):
    m=(y2-y1)/(x2-x1)
    b=y1-(m*x1)
    return m,b

Sau khi nhận được $m$ và $b$, sau đó chúng tôi sử dụng nó để tính toán $f(x)$ hoặc $y$. Đối với điều này, chúng tôi tạo ra một chức năng để tính toán nó

def func_fx(m,b,x):
    fx=m*x+b
    return fx

Tiếp theo, chúng ta tạo một hàm để tính khoảng cách giữa hai điểm bằng phương trình trên

def distance(x1,y1,x2,y2):
    d=np.sqrt((x1-x2)**2+(y1-y2)**2)
    return d

Để chọn đúng điểm tối ưu ta phải biết vị trí của các điểm trong với nhau. Đối với điều này, chúng tôi tạo một chức năng được gọi là check_pos. Nếu $x_1$ lớn hơn $x_2$, điều đó có nghĩa là $x_1$ ở bên phải của $x_2$. Vì điều đó, chúng tôi đưa ra nhãn 'đúng'

def check_pos(x1,x2):
    if x2<x1:
        label='right'
    else:
        label=''
    return label

Sau đó, chúng tôi tạo một chức năng được gọi là update_interior. Hàm này được sử dụng để cập nhật các giá trị bên trong $x_1$ và $x_2$ dựa trên điểm biên $x_u$ và $x_l$

def update_interior(xl,xu):
    d=((np.sqrt(5)-1)/2)*(xu-xl)
    x1=xl+d
    x2=xu-d
    return x1,x2

Mục tiêu của trường hợp này là tìm chênh lệch nhỏ nhất giữa hai khoảng cách từ một điểm đã biết đến từng điểm bên trong $x_1$ và $x_2$. Do đó, chúng tôi sử dụng hàm find_min. Trong hàm, chúng tôi tính toán từng khoảng cách như trong dòng 4 và 5 trong đoạn mã sau. Từ dòng 6, chúng tôi thực hiện so sánh khoảng cách. Dựa trên tiêu chí quy tắc, các giá trị ranh giới và  bên trong được cập nhật

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def find_min(xl,xu,x1,x2,label):
    y1=func_fx(m,b,x1)
    y2=func_fx(m,b,x2)
    fx1=distance(x_point,y_point,x1,y1)
    fx2=distance(x_point,y_point,x2,y2)
    if fx2>fx1 and label=='right':
        xl=x2
        xu=xu
        new_x=update_interior(xl,xu)
        x1=new_x[0]
        x2=new_x[1]
        xopt=x1
    else:
        xl=xl
        xu=x1
        new_x=update_interior(xl,xu)
        x1=new_x[0]
        x2=new_x[1]
        xopt=x2
    return xl,xu,xopt,fx1,fx2

Cuối cùng, chúng tôi tạo chức năng tìm kiếm vàng với bốn biến đầu vào cụ thể là. ranh giới trên($x_u$), ranh giới dưới($x_l$), chế độ (là 'tối thiểu' vì chúng tôi chỉ tìm kiếm giá trị nhỏ nhất) và ngưỡng lỗi($et$). Trong hàm còn có lệnh vẽ đồ thị tại dòng 28-34 cho ra đồ thị như hình 1. Phần còn lại của chức năng này là in ra một số kết quả như số lần lặp, giá trị lỗi, khoảng cách và khoảng cách trung bình

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

def golden_search(xl,xu,mode,et):
    it=0
    e=1
    while e>=et:
        new_x=update_interior(xl,xu)
        x1=new_x[0]
        x2=new_x[1]
        fx1=func_fx(m,b,x1)
        fx2=func_fx(m,b,x2)
        label=check_pos(x1,x2)
        
        #SELECTING AND UPDATING BOUNDARY-INTERIOR POINTS
        if mode=='max':
            new_boundary=find_max(xl,xu,x1,x2,label)
        elif mode=='min':
            new_boundary=find_min(xl,xu,x1,x2,label)
        else:
            print('Please define min/max mode')
            break #exit if mode not min or max
        xl=new_boundary[0]
        xu=new_boundary[1]
        xopt=new_boundary[2]
        distance_1=new_boundary[3]
        distance_2=new_boundary[4]
        mean_distance=(distance_1+distance_2)/2
        
        #PLOTTING
        clear_output(wait=True)
        plt.plot([x_point,x1],[y_point,fx1],'r')
        plt.plot([x_point,x2],[y_point,fx2],'r')
        plt.plot(x,y)
        plt.plot(x_point,y_point,'bo')
        plt.axis('equal')
        plt.show()

        it+=1
        print ('Iteration: ',it)
        r=(np.sqrt(5)-1)/2 #GOLDEN RATIO
        e=((1-r)*(abs((xu-xl)/xopt)))*100 #Error
        print('Error:',e)
        print ('distance 1=',distance_1)
        print ('distance 2=',distance_2)
        print('mean distance=',round(mean_distance,3))
        time.sleep(1)

Chúng tôi đã tạo tất cả các chức năng cần thiết cho ứng dụng này. Bây giờ hãy chạy nó với đoạn mã sau

Làm cách nào để tìm khoảng cách ngắn nhất giữa hai điểm trong Python?

Thuật toán cho khoảng cách giữa hai điểm trong Python là gì?

Con đường ngắn nhất giữa hai điểm là gì?

Khoảng cách Euclide ngắn nhất giữa hai điểm là gì?