Tìm tọa độ điểm từ ma trận khoảng cách

Question

Tôi có một tập hợp các điểm (có tọa độ không xác định) và ma trận khoảng cách. Tôi cần phải tìm tọa độ của các điểm này để vẽ chúng và hiển thị giải pháp của thuật toán của tôi.

Tôi có thể đặt một trong các điểm này trong tọa độ (0,0) để mô phỏng và tìm các điểm khác. Bất cứ ai có thể cho tôi biết nếu nó có thể tìm thấy các tọa độ của các điểm khác, và nếu có, làm thế nào?

Cảm ơn trước!

EDIT Quên để nói rằng tôi cần các tọa độ trên x-y chỉ

Answer 1

Bước 1, tùy tiện gán một P1 điểm như (0,0).

Bước 2, tự ý chỉ định một điểm P2 dọc theo trục x dương. (0, Dp1p2)

Bước 3, hãy tìm một điểm P3 mà

Dp1p2 ~= Dp1p3+Dp2p3 
Dp1p3 ~= Dp1p2+Dp2p3 
Dp2p3 ~= Dp1p3+Dp1p2 

và thiết lập thời điểm đó trong "tích cực" y miền (nếu nó đáp ứng bất kỳ các tiêu chí này, điểm nên được đặt trên trục P1P2).
Sử dụng các luật cosin để xác định khoảng cách:

cos (A) = (Dp1p2^2 + Dp1p3^2 - Dp2p3^2)/(2*Dp1p2* Dp1p3) 
P3 = (Dp1p3 * cos (A), Dp1p3 * sin(A)) 

Bây giờ bạn đã xây dựng thành công một không gian trực giao và đặt ba điểm trong không gian đó.

Bước 4: Để xác định tất cả các điểm khác, lặp lại bước 3, để cho bạn một tọa độ y dự kiến. (Xn, Yn).
So sánh khoảng cách {(Xn, Yn), (X3, Y3)} với Dp3pn trong ma trận của bạn. Nếu nó giống hệt nhau, bạn đã xác định thành công tọa độ cho điểm n. Nếu không, điểm n là tại (Xn, -Yn).

Lưu ý có một thay thế cho bước 4, nhưng nó là quá nhiều toán cho một chiều thứ bảy

Answer 2

Nếu cho điểm p, q, và r bạn có pq, qr, và rp trong ma trận của bạn, bạn có Tam giác.

Bất cứ nơi nào bạn có tam giác trong ma trận, bạn có thể tính toán một trong hai giải pháp cho tam giác đó (độc lập với biến đổi euclide của hình tam giác trên mặt phẳng). Tức là, đối với mỗi tam giác bạn tính toán, đó là hình ảnh phản chiếu cũng là một hình tam giác đáp ứng các giới hạn khoảng cách trên p, q và r. Thực tế là có hai giải pháp ngay cả đối với tam giác dẫn đến vấn đề chirality: Bạn phải chọn chirality (định hướng) của mỗi tam giác, và không phải tất cả các lựa chọn đều có thể dẫn đến một giải pháp khả thi cho vấn đề.

Tuy nhiên, tôi có một số gợi ý. Nếu các mục nhập số nhỏ, hãy cân nhắc sử dụng simulated annealing. Bạn có thể kết hợp chirality vào bước ủ. Điều này sẽ chậm cho các hệ thống lớn, và nó có thể không hội tụ đến một giải pháp hoàn hảo, nhưng đối với một số vấn đề đó là tốt nhất bạn và làm.

Đề xuất thứ hai sẽ không cung cấp cho bạn giải pháp hoàn hảo, nhưng nó sẽ phân phối lỗi: method of least squares. Trong trường hợp của bạn, hàm mục tiêu sẽ là lỗi giữa khoảng cách trong ma trận của bạn và khoảng cách thực tế giữa các điểm của bạn.

Answer 3

Các câu trả lời dựa trên các góc đều cồng kềnh để triển khai và không thể dễ dàng khái quát hóa với dữ liệu ở các thứ nguyên cao hơn.Một cách tiếp cận tốt hơn là đề cập đến trong tôi và WimC của câu trả lời here: cho ma trận khoảng cách D(i, j), xác định

M(i, j) = 0.5*(D(1, j)^2 + D(i, 1)^2 - D(i, j)^2) 

mà phải là một ma trận bán xác định dương với cấp bậc tương đương với kích thước Euclide tối thiểu k trong đó các điểm có thể được nhúng. Sau đó, các tọa độ của các điểm có thể được lấy từ các số riêng k các số riêng v(i) của M tương ứng với các giá trị không khác: đặt các vectơ sqrt(q(i))*v(i) làm các cột trong một ma trận n x kX; sau đó mỗi hàng của X là một điểm. Nói cách khác, sqrt(q(i))*v(i) cung cấp cho thành phần thứ i của tất cả các điểm.

Các vectơ riêng của một ma trận có thể thu được một cách dễ dàng ở hầu hết các ngôn ngữ lập trình (ví dụ, sử dụng GSL trong C/C++, sử dụng được xây dựng trong chức năng eig trong Matlab, sử dụng NumPy bằng Python, vv)

Lưu ý rằng phương pháp đặc biệt này luôn đặt điểm đầu tiên tại điểm gốc, nhưng bất kỳ phép quay, phản xạ hoặc dịch nào của các điểm cũng sẽ thỏa mãn ma trận khoảng cách ban đầu.

Answer 4

Đây là vấn đề về toán học. Để lấy được ma trận tọa độ X chỉ được đưa ra bởi ma trận khoảng cách của nó.

Tuy nhiên, có một giải pháp hiệu quả cho điều này - Đa chiều Scaling, mà làm một số đại số tuyến tính. Đơn giản chỉ cần đặt, nó đòi hỏi một ma trận khoảng cách Euclide cặp đôi D, và đầu ra là tọa độ Y ước tính (có thể xoay), đó là một xấp xỉ với X. Vì lý do lập trình, chỉ cần sử dụng SciKit.manifold.MDS trong Python.