Tìm khoảng cách của 2 điểm khi biết tọa độ X và Y

[heyhey1994]

Chào cả nhà, em xin trình bày vấn đề của em ạ:

Em có 1 tập hợp nút xanh (A) và nút đỏ (B), có tọa độ tương ứng là X1, Y1 và X2 và Y2. Nay em muốn tìm những điểm B gần từng điểm A trong 1 khoảng cách cho trước, sau đó sẽ liệt kê ra theo phương ngang, mọi người xem thêm trong file excel ạ. Em có 2 ý tưởng:
1. Mình sẽ vẽ vòng tròn từ các điểm A, có bán kính là khoảng cách cho trước, sau đó đi tìm các điểm đỏ nào nằm trong đường tròn. Cách này em chưa biết xử lí bằng code như thế nào.
2. Sẽ tính toàn bộ khoảng cách từ tất cả điểm B đến từng điểm A, sau đó lấy so sánh với khoảng cách cho trước, giá trị nào nhỏ hơn khoảng cách cho trước thì lấy giá trị nút B tương ứng với công thức tính khoảng cách từ tọa độ là SQRT((X1-X2)^2+(Y1-Y2)^2)). Nhưng với cách này thì với bài toán thực tế của em có đến 2000 điểm A và 2000 điểm B thì nó phải chạy lặp đến 4 triệu lần.

Vậy nên em muốn nhờ mọi người giúp em một cách làm hiệu quả khi có hàng ngàn nút.
.
Nếu có chỗ nào chưa rõ ý, mong mọi người nhắn lại cho em biết, em xin cảm ơn ạ.

 

[VetMini]

1. về giở lại sách toán hình học lớp 11, tra công thức (phương trình) vòng tròn

2. 4 triệu con toán trên đối với math co-processor của các CPU hàng tỷ Hertz không thành vấn đề. Tuy nhiên, làm việc với số thực thì cần để ý độ chính xác.

 

[befaint]

0.5 giây là xong rồi này

 

[HieuCD]

Chào cả nhà, em xin trình bày vấn đề của em ạ:

Em có 1 tập hợp nút xanh (A) và nút đỏ (B), có tọa độ tương ứng là X1, Y1 và X2 và Y2. Nay em muốn tìm những điểm B gần từng điểm A trong 1 khoảng cách cho trước, sau đó sẽ liệt kê ra theo phương ngang, mọi người xem thêm trong file excel ạ. Em có 2 ý tưởng:
1. Mình sẽ vẽ vòng tròn từ các điểm A, có bán kính là khoảng cách cho trước, sau đó đi tìm các điểm đỏ nào nằm trong đường tròn. Cách này em chưa biết xử lí bằng code như thế nào.
2. Sẽ tính toàn bộ khoảng cách từ tất cả điểm B đến từng điểm A, sau đó lấy so sánh với khoảng cách cho trước, giá trị nào nhỏ hơn khoảng cách cho trước thì lấy giá trị nút B tương ứng với công thức tính khoảng cách từ tọa độ là SQRT((X1-X2)^2+(Y1-Y2)^2)). Nhưng với cách này thì với bài toán thực tế của em có đến 2000 điểm A và 2000 điểm B thì nó phải chạy lặp đến 4 triệu lần.

Vậy nên em muốn nhờ mọi người giúp em một cách làm hiệu quả khi có hàng ngàn nút.
.
Nếu có chỗ nào chưa rõ ý, mong mọi người nhắn lại cho em biết, em xin cảm ơn ạ.

View attachment 293365

Kiểm tra lại

Sub XYZ()
  Dim a(), b(), res(), KC#, fr&
  Dim srA&, srB&, i&, r&, r2&, j&, dx#
 
  KC = Range("H1").Value
  i = Range("A1000000").End(xlUp).Row
  res = Range("A2:C" & i).Value
  Range("A2:C" & i).Sort Range("B2"), 1, Header:=xlNo
  a = Range("A2:C" & i).Value
  Range("A2:C" & i).Value = res
  i = Range("D1000000").End(xlUp).Row
  res = Range("D2:F" & i).Value
  Range("D2:F" & i).Sort Range("E2"), 1, Header:=xlNo
  b = Range("D2:F" & i).Value
  Range("D2:F" & i).Value = res
 
  srA = UBound(a): srB = UBound(b)
  ReDim res(1 To srA, 1 To 10)
  fr = 1
  For i = 1 To srA
    res(i, 1) = a(i, 1)
    j = 1
    For r = fr To srB
      dx = a(i, 2) - b(r, 2)
      If dx < -KC Then Exit For
      If dx <= KC Then
        fr = r
        For r2 = fr To srB
          If a(i, 2) - b(r2, 2) < -KC Then
            Exit For
          Else
            If Sqr((a(i, 2) - b(r2, 2)) ^ 2 + (a(i, 3) - b(r2, 3)) ^ 2) <= KC Then
              j = j + 1
              If j > UBound(res, 2) Then ReDim Preserve res(1 To srA, 1 To UBound(a, 2) + 10)
              res(i, j) = b(r2, 1)
            End If
          End If
        Next r2
        Exit For
      End If
    Next r
  Next i
  Range("I2").Resize(srA, UBound(res, 2)) = res
End Sub

 

[Nhattanktnn]

Chào cả nhà, em xin trình bày vấn đề của em ạ:

Em có 1 tập hợp nút xanh (A) và nút đỏ (B), có tọa độ tương ứng là X1, Y1 và X2 và Y2. Nay em muốn tìm những điểm B gần từng điểm A trong 1 khoảng cách cho trước, sau đó sẽ liệt kê ra theo phương ngang, mọi người xem thêm trong file excel ạ. Em có 2 ý tưởng:
1. Mình sẽ vẽ vòng tròn từ các điểm A, có bán kính là khoảng cách cho trước, sau đó đi tìm các điểm đỏ nào nằm trong đường tròn. Cách này em chưa biết xử lí bằng code như thế nào.
2. Sẽ tính toàn bộ khoảng cách từ tất cả điểm B đến từng điểm A, sau đó lấy so sánh với khoảng cách cho trước, giá trị nào nhỏ hơn khoảng cách cho trước thì lấy giá trị nút B tương ứng với công thức tính khoảng cách từ tọa độ là SQRT((X1-X2)^2+(Y1-Y2)^2)). Nhưng với cách này thì với bài toán thực tế của em có đến 2000 điểm A và 2000 điểm B thì nó phải chạy lặp đến 4 triệu lần.

Vậy nên em muốn nhờ mọi người giúp em một cách làm hiệu quả khi có hàng ngàn nút.
.
Nếu có chỗ nào chưa rõ ý, mong mọi người nhắn lại cho em biết, em xin cảm ơn ạ.

View attachment 293365

Bạn sửa thêm cho phù hợp nhu cầu:

Sub abc()
Dim a(), b(), c(), i&, j&, x1#, y1#, x2#, y2#, col&, m&
Const d& = 2
a = [a2:c30].Value
b = [d2:f44].Value
ReDim c(1 To UBound(a), 1 To 20)
For i = 1 To UBound(a)
    x1 = a(i, 2): y1 = a(i, 3)
    c(i, 1) = a(i, 1)
    col = 1
    For j = 1 To UBound(b)
        x2 = b(j, 2): y2 = b(j, 3)
        If Sqr((x1 - x2) ^ 2 + (y1 - y2) ^ 2) <= d Then
            col = col + 1
            If col > m Then m = col
            If m > UBound(c) Then ReDim Preserve c(1 To UBound(a), 1 To m + 20)
            c(i, col) = b(j, 1)
        End If
    Next
Next
If m Then [P2].Resize(UBound(a), m) = c
End Sub

 

[VetMini]

0.5 giây là xong rồi này
...

Làm toán mà đi sử dụng VBA là đem Land Cruiser đi kéo máy cày.
Python thích hợp nhất trong trường hợp này:
1. con toán thuần toán giải tích.
2. cỏ dataset đồng bộ.

 

[heyhey1994]

Cảm ơn mọi nhiều ạ, em sử dụng thì thấy là thứ tự tất cả các nút A và nút B ở bài #4 của bác HieuCD bị đảo lung tung ạ. Còn bài #5 của bác Nhattanktnn thì đúng với cái em mong muốn rồi.
Tiện đây nhờ anh befaint cho em xem đầy đủ code python để em tham khảo với, vì thực tế là phần mềm em xài, nó liên kết trực tiếp được với python hoặc C# luôn, mà em cũng ko biết 2 món này nên phải xuất dữ liệu ra excel để làm.

0.5 giây là xong rồi này


View attachment 293370

 

[VetMini]

...nó liên kết trực tiếp được với python hoặc C# luôn, mà em cũng ko biết 2 món này nên phải xuất dữ liệu ra excel để làm.

Đừng có đem C# ra so sánh với Python.
C# chủ yếu cạnh tranh với PHP (nên tảng web), và Delphi (nền tảng đủ thứ). Chuyên về giao diện người dùng.
Python tuy dễ nhưng thư viện hổ trợ của nó viết bởi những tay cự phách về khoa học số. Các thư viện về trích giải dataset và về mảng nhiều chiều (n >- 2) của nó là vô song. Chính là học các thư viện này mới khó.

 

[bebo021999]

Góp vui.
Chia sẻ cho bạn cách của mình :
1) Quy tất cả về hệ quy chiếu dương. Hiểu nôm na là tịnh tiến tất cả các điểm lên 1/4 phía trên, bên phải của trục tọa độ.
2) Hàm khoangcach(x1,y1,x2,y2): Theo công thức Pitagore thì khoảng cách A-B là cạnh huyền của 1 tam giác vuông.
3) Lần lựơt so sánh 1 điểm A và các điểm B và gọi hàm khoangcach để lấy khoảng cách, cái nào thỏa điều kiện thì lấy.
4) Sắp xếp tăng dần theo từ dòng

Option Explicit
Sub test()
Dim i&, j&, lr1&, lr2&, t&, k&, xmin, ymin, maxC&
Dim rngA, rngB, dis, res()

' tim x<0 và y<0 nho nhat
With WorksheetFunction
    lr1 = Cells(Rows.Count, "A").End(xlUp).Row
    xmin = .min(Range("B2:B" & lr1))
    ymin = .min(Range("C2:C" & lr1))
    lr2 = Cells(Rows.Count, "E").End(xlUp).Row
    xmin = .min(xmin, .min(Range("E2:E" & lr2)))
    ymin = .min(ymin, .min(Range("F2:F" & lr2)))
End With
rngA = Range("A2:C" & lr1).Value
rngB = Range("D2:F" & lr2).Value

' quy dong tat ca toa do x,y ve toa do moi >0 (tinh tien A va B ve toa do goc "0,0")
For i = 1 To UBound(rngA)
    If xmin < 0 Then rngA(i, 2) = rngA(i, 2) - xmin
    If ymin < 0 Then rngA(i, 3) = rngA(i, 3) - ymin
Next
For i = 1 To UBound(rngB)
    If xmin < 0 Then rngB(i, 2) = rngB(i, 2) - xmin
    If ymin < 0 Then rngB(i, 3) = rngB(i, 3) - ymin
Next
ReDim res(1 To 100000, 1 To 3)
For i = 1 To UBound(rngA)
    For j = 1 To UBound(rngB)
        dis = khoangcach(rngA(i, 2), rngA(i, 3), rngB(j, 2), rngB(j, 3))
        If dis <= Range("H1") Then
            k = k + 1: res(k, 1) = rngA(i, 1)
            res(k, 2) = rngB(j, 1): res(k, 3) = dis
        End If
    Next
Next

'Dán ket qua vao sheet
Range("H2:Z100000").ClearContents
With Range("H2").Resize(k, 3)
    .Value = res
    .Sort key1:=Range("H1"), key2:=Range("J1")
    rngB = .Value
End With
ReDim res(1 To UBound(rngA), 1 To 150)
k = 0
For i = 1 To UBound(rngA)
    t = 1: k = k + 1: res(k, 1) = rngA(i, 1)
    For j = 1 To UBound(rngB)
        If rngA(i, 1) = rngB(j, 1) Then
            t = t + 1: If t > maxC Then maxC = t
            res(k, t) = rngB(j, 2)
        End If
    Next
Next
Range("H2:Z100000").ClearContents
Range("H2").Resize(k, 150).Value = res
End Sub
Function khoangcach(ByVal x1, y1, x2, y2) As Double
    'Khoang cach = canh huyen cua TG vuong= SQRT(tong binh phuong hai canh)
    khoangcach = Sqr(Abs(x1 - x2) ^ 2 + Abs(y1 - y2) ^ 2)
End Function

 

[VetMini]

Ở đây cả hai bài #5 và #9 đều không để ý đến chỗ tôi nhắc "sai số".
Toán số thực thì luon có sai số. Nhưng giảm chúng xuóng thế nào mới là kinh nghiệm của người lập trình. Như tôi vẫn thường nói "dân GPE chỉ biết có một kiểu, đụng đến tính số thực là khong có chút kinh nghiệm.

1. SQRT là hàm số thực. Sai số khá lớn. Khi so sánh một với với SQRT của biểu thức khác, người ta lũy thừa 2 biểu thực thứ hai.
Con toán ấy dân kinh nghiệm số thực sẽ viết là:
' code này ngoài vòng lặp thứ hai
sqrR = R*R ' bình thường thì con toán nhân nhanh hơn ^2. Trừ lũy thừa số nguyên thì phép dịch bit mọt vị trí là nhanh nhất.
' tuy nhiên, ở đây ta tính sqrR chỉ một lần cho nên tốc độ không quan trọng lắm. Chỉ cần nhớ rằng toán nhân chính xác hơn hàm SQRT.

' code bên trong vòng lặp thứ hai
dx = xA -xB
dy = yA - yB
IF (dx*dx + dy*dy) <= sqrR Then ' thỏa điều kiện
' tiết kiệm được một số thời gian, và quan trọng hơn là giảm được sai số

 

[Nhattanktnn]

Cảm ơn mọi nhiều ạ, em sử dụng thì thấy là thứ tự tất cả các nút A và nút B ở bài #4 của bác HieuCD bị đảo lung tung ạ. Còn bài #5 của bác Nhattanktnn thì đúng với cái em mong muốn rồi.
Tiện đây nhờ anh befaint cho em xem đầy đủ code python để em tham khảo với, vì thực tế là phần mềm em xài, nó liên kết trực tiếp được với python hoặc C# luôn, mà em cũng ko biết 2 món này nên phải xuất dữ liệu ra excel để làm.

Không chê anh nghèo lên xe anh đèo

import pandas as pd
from scipy import spatial
filename = 'Point Coordinates.xlsx'
df = pd.read_excel(filename, 'Sheet1', skiprows = 0, nrows=43,  usecols= 'A:F')
df.columns = [str(x) for x in list(range(1,7))]
d1 = df[['1', '2', '3']].dropna().values
d2 = df[['4', '5', '6']].dropna().values
tree = spatial.KDTree([(x, y) for _, x, y in d2])
for v in d1:
    j=[]
    data = {}
    p = tuple(v[1:])
    res = tree.query_ball_point(p, r=2)
    for k in res:
        j.append(d2[k][0])
    j.sort()
    data[v[0]] = j
    print(data)