Algorytm trilateracji dla n ilości punktów

Muszę znaleźć algorytm, który może obliczyć środek ciężkości A (inaczej środek ciężkości, środek geometryczny, środek masy) na podstawie figury, w której koła T1, T2, T3, T4, T5, .., Tn przecinają ORAZ długość linii R od środka ciężkości do najdalszy róg wspomnianej figury

Podane są następujące informacje:

• T1 Szerokość = 56.999883 Długość geograficzna = 24.144473 Promień = 943
• Szerokość geograficzna T2 = 57,005352 Długość geograficzna = 24,151168 Promień = 857
• T3 Szerokość = 57.005352 Długość geograficzna = 24.163356 Promień = 714
• T4 Szerokość = 56.999042 Długość geograficzna = 24.168506 Promień = 714
• T5 Szerokość geograficzna = 56.994226 Długość geograficzna = 24.15709 Promień = 771

Wynik powinien wyglądać następująco: A Szerokość geograficzna = XX.XXXXXXX Długość geograficzna = XX.XXXXXXX Promień = XX

Jak zapewne już się zorientowałeś, pracuję nad oprogramowaniem, które może znaleźć lokalizację urządzenia za pomocą najbliższych punktów dostępu Wi-Fi lub mobilnych stacji bazowych, ponieważ liczba punktów dostępu lub stacji bazowych może ulec zmianie, potrzebuję algorytmu, który może dostosować się do niepewnej liczby punktów .

Jest kilka podobnych pytań tu i tutaj , ale żadne z nich nie odpowiada dokładnie na moje pytanie.

Pomiary promienia z pewnością są obarczone pewnym błędem. Spodziewałbym się, że wielkość błędu będzie proporcjonalna do samych promieni. Załóżmy, że pomiary są poza tym obiektywne. Rozsądnym rozwiązaniem jest zastosowanie ważonego nieliniowego dopasowania najmniejszych kwadratów , z ciężarami odwrotnie proporcjonalnymi do kwadratowych promieni.

Jest to standardowy materiał dostępny w (między innymi), Python R, Mathematica i wiele pełnych funkcjonalny pakietów statystycznych, więc będę po prostu zilustrować go. Oto niektóre dane uzyskane przez pomiar odległości, z błędem względnym 10%, do pięciu losowych punktów dostępu otaczających lokalizację urządzenia:

Mathematica potrzebuje tylko jednego wiersza kodu i żadnego mierzalnego czasu procesora, aby obliczyć dopasowanie:

fit = NonlinearModelFit[data, Norm[{x, y} - {x0, y0}], {x0, y0}, {x, y}, Weights -> 1/observations^2]

Edytować--

W przypadku dużych promieni bardziej dokładne (sferyczne lub elipsoidalne) rozwiązania można znaleźć po prostu zastępując odległość euklidesową Norm[{x, y} - {x0, y0}]funkcją obliczającą odległość sferyczną lub elipsoidalną. W Mathematica można to zrobić np. Przez

fit = NonlinearModelFit[data, GeoDistance[{x, y}, {x0, y0}], {x0, y0}, {x, y}, 
        Weights -> 1/observations^2]

- koniec edycji

Jedną z zalet stosowania takiej techniki statystycznej jest to, że może ona wytwarzać przedziały ufności dla parametrów (które są współrzędnymi urządzenia), a nawet równoczesną elipsę pewności dla lokalizacji urządzenia.

ellipsoid = fit["ParameterConfidenceRegion", ConfidenceLevel -> 0.95];
fit["ParameterConfidenceIntervalTable", ConfidenceLevel -> 0.95]

Pouczające jest wykreślenie danych i rozwiązania:

Graphics[{Opacity[0.2], EdgeForm[Opacity[0.75]], White, Disk[Most[#], Last[#]] & /@ data, 
  Opacity[1], Red, ellipsoid, 
  PointSize[0.0125], Blue, Point[source], Red, Point[solution],
  PointSize[0.0083], White, Point @ points}, 
  Background -> Black, ImageSize -> 600]

• Białe kropki to (znane) lokalizacje punktów dostępu.

• Duża niebieska kropka to prawdziwa lokalizacja urządzenia.

• Szare kółka reprezentują zmierzone promienie. Idealnie wszystkie przecinałyby się w prawdziwej lokalizacji urządzenia - ale oczywiście nie robią tego z powodu błędu pomiaru.

• Duża czerwona kropka to szacowana lokalizacja urządzenia.

• Czerwona elipsa wyznacza 95% obszar pewności dla lokalizacji urządzenia.

W tym przypadku interesujący jest kształt elipsy: niepewność lokalizacyjna jest największa wzdłuż linii NW-SE. Tutaj odległości do trzech punktów dostępowych (do NE i SW) prawie się nie zmieniają i występuje kompromis w błędach między odległościami do dwóch innych punktów dostępowych (na północ i południowy wschód).

(Bardziej dokładny obszar ufności można uzyskać w niektórych systemach jako kontur funkcji prawdopodobieństwa; ta elipsa jest tylko przybliżeniem drugiego rzędu do takiego konturu).

Gdy promienie są mierzone bezbłędnie, wszystkie koła będą miały co najmniej jeden punkt wzajemnego przecięcia i - jeśli ten punkt jest unikalny - będzie to unikalne rozwiązanie.

Ta metoda działa z dwoma lub więcej punktami dostępu. Aby uzyskać przedziały ufności, potrzebne są trzy lub więcej. Gdy dostępne są tylko dwa, znajduje jeden z punktów przecięcia (jeśli istnieją); w przeciwnym razie wybiera odpowiednią lokalizację między dwoma punktami dostępu.

W takim przypadku każde koło przecina wszystkie pozostałe koła, dzięki czemu możemy określić punkty przecięcia w ten sposób:

Najpierw określ wszystkie n * (n-1) punkty przecięcia. Nazywamy zbiór tych punktów przecięcia I . Weź listę punktów T, która zawiera najbardziej wewnętrzne punkty. Następnie dla każdego punktu P w I sprawdzić, czy p jest wewnątrz każdego okręgu. Jeśli p jest w każdym okręgu, oznacza to punkt na najbardziej wewnętrznym przecięciu. Dodaj takiego punktu A do listy T .

Teraz masz pożądane współrzędne przecięcia. Mogę wymyślić co najmniej dwa sposoby przewidywania lokalizacji:

1. Wystarczy obliczyć centroid (użyć odległości jako masy?) Wielokąta utworzonego przez T, a centroid jest pożądaną lokalizacją.
2. Oblicz minimalny okrąg, który zawiera każdy punkt T . Następnie środkiem tego koła jest pożądana lokalizacja. Po tym obliczenie R powinno być proste.

Kolejna uwaga: najpierw przekonwertuj siłę sygnału na odległość za pomocą modelu ścieżki wolnej przestrzeni (lub odmian). Uważam, że: masz dowolny zestaw danych szkoleniowych, powinieneś spróbować znaleźć wykładnik utraty ścieżki za pomocą jakiejś techniki uczenia się zamiast używać n = 2 lub n = 2.2 jako stałej wartości.