Znajdowanie współrzędnych punktów z macierzy odległości

Question

Mam zestaw punktów (z nieznanymi współrzędnymi) i macierz odległości. Muszę znaleźć współrzędne tych punktów, aby je narysować i pokazać rozwiązanie mojego algorytmu.

Mogę ustawić jeden z tych punktów we współrzędnych (0,0), aby je uprościć i znaleźć pozostałe. Czy ktoś może mi powiedzieć, czy możliwe jest znalezienie współrzędnych innych punktów, a jeśli tak, to w jaki sposób?

Z góry dziękuję!

EDIT Zapomniałem że trzeba współrzędnych w x, y tylko

Answer 1

Etap 1 dowolnie przydzielić jeden punkt P1 jako (0,0).

Krok 2, arbitralnie przypisz jeden punkt P2 wzdłuż dodatniej osi X. (0, Dp1p2)

Etap 3, znaleźć punkt P3 tak, że

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

i ustawiony, że punkt w „pozytywnej” domeny Y (jeśli spełnia którykolwiek z tych kryteriów, temperatura powinna być umieszczona na osi P1P2).
Użyj prawo cosinus aby określić odległość:

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

Z powodzeniem zbudował przestrzeń ortonormalną i umieszczone trzy punkty w tej przestrzeni.

Krok 4: Aby ustalić wszystkie pozostałe punkty, powtórz krok 3, aby uzyskać wstępną współrzędną y. (Xn, Yn).
Porównaj odległość {(Xn, Yn), (X3, Y3)} do Dp3pn w macierzy. Jeśli jest identyczny, udało ci się zidentyfikować współrzędne dla punktu n. W przeciwnym razie punkt n ma wartość (Xn, -Yn).

Uwaga istnieje alternatywa do kroku 4, ale to jest zbyt dużo matematyki na sobotnie popołudnie

Answer 2

Jeśli punkty P, Q i R masz PQ, QR, i rp w macierzy, trzeba trójkąt.

Wszędzie tam, gdzie macie trójkąt w macierzy, możecie obliczyć jedno z dwóch rozwiązań dla tego trójkąta (niezależnie od transformacji euklidesowej trójkąta na płaszczyźnie). Oznacza to, że dla każdego trójkąta, który obliczysz, jego odbicie lustrzane jest również trójkątem, który spełnia ograniczenia odległości dla p, q i r. Fakt, że istnieją dwa rozwiązania nawet dla trójkąta, prowadzi do problemu chiralności: Musisz wybrać chiralność (orientację) każdego trójkąta, a nie wszystkie wybory mogą prowadzić do możliwego rozwiązania problemu.

Niemniej jednak, mam kilka sugestii. Jeśli liczba wpisów jest mała, należy rozważyć użycie numeru simulated annealing. Możesz włączyć chiralność do etapu wyżarzania. Będzie to powolne w przypadku dużych systemów i może nie dojść do perfekcyjnego rozwiązania, ale w przypadku niektórych problemów jest to najlepsze rozwiązanie.

Druga sugestia nie zapewni Ci idealnego rozwiązania, ale spowoduje dystrybucję błędu: method of least squares. W twoim przypadku funkcją celu będzie błąd między odległościami w twojej macierzy, a rzeczywistymi odległościami między twoimi punktami.

Answer 3

Odpowiedzi oparte na kątach są uciążliwe w implementacji i nie można ich łatwo uogólnić na dane w wyższych wymiarach.Lepszym rozwiązaniem jest to, że wymienione w moje i WimC-tych odpowiedziach here: podany macierz odległości D(i, j) zdefiniować

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

które powinny być pozytywnym pół określony matryca z rankingu równa minimalnej euklidesowej wymiaru k w której punkty mogą być osadzonym. Współrzędne punktów można następnie uzyskać z k wektorów własnych v(i) z M odpowiadających niezerowej wartości własnej q(i): umieścić wektory sqrt(q(i))*v(i) jako kolumny w macierzy ; następnie każdy wiersz X jest punktem. Innymi słowy, sqrt(q(i))*v(i) daje komponent wszystkich punktów.

Te wartości i wektory własne macierzy można łatwo otrzymać w wielu językach programowania (na przykład za pomocą GSL C/C++ za pomocą wbudowanej funkcji eig Matlab, stosując Numpy Python etc.)

Należy zauważyć, że ta konkretna metoda zawsze umieszcza pierwszy punkt w punkcie początkowym, ale wszelkie obracanie, odbicie lub przekształcenie punktów będzie również spełniać oryginalną macierz odległości.

Answer 4

To jest problem matematyczny. Wyprowadzanie macierzy współrzędnych X tylko przez jej macierz odległości.

Istnieje jednak skuteczne rozwiązanie tego problemu - wielowymiarowe skalowanie, które wykonuje pewną algebrę liniową. Mówiąc najprościej, wymaga to macierzy odległości D na poziomie euklidesowym, a wynikiem jest szacowana współrzędna Y (być może obrócona), która jest zbliżeniem do X. Z powodów programowania, po prostu użyj SciKit.manifold.MDS w Pythonie.