Algoritma Trilateration untuk n jumlah poin

27

Saya perlu menemukan algoritma yang dapat menghitung centroid A (alias pusat gravitasi, pusat geometri, pusat massa) dari gambar di mana lingkaran T1, T2, T3, T4, T5, .., Tn berpotongan DAN panjang garis R dari centroid ke sudut terjauh dari sosok yang disebutkan

Informasi berikut diberikan:

  • T1 Latitude = 56.999883 Bujur = 24.144473 Radius = 943
  • T2 Latitude = 57.005352 Longitude = 24.151168 Radius = 857
  • T3 Latitude = 57.005352 Bujur = 24.163356 Radius = 714
  • T4 Latitude = 56.999042 Bujur = 24.168506 Radius = 714
  • T5 Latitude = 56.994226 Bujur = 24.15709 Radius = 771

Hasilnya akan terlihat seperti ini: A Latitude = XX.XXXXXXX Longitude = XX.XXXXXXX Radius = XX

masukkan deskripsi gambar di sini

Seperti yang mungkin sudah Anda ketahui, saya sedang mengerjakan perangkat lunak yang dapat menemukan lokasi perangkat oleh Wifi Access Point atau Mobile Base station terdekat, karena jumlah titik akses atau stasiun basis mungkin berubah, saya memerlukan algoritma yang dapat beradaptasi dengan jumlah poin yang tidak pasti. .

Ada beberapa pertanyaan serupa di sini dan di sini , tetapi tidak ada yang menjawab pertanyaan saya.

Kārlis Baumanis
sumber
kamu bekerja di bahasa apa?
WolfOdrade
Sebagian besar PHP, sedikit JavaScript. Saya kira saya harus menyebutkan ini sebelumnya tetapi saya adalah seorang pengembang web dan untuk memahami jawaban Whuber saya harus menemukan ahli matematika.
Kārlis Baumanis
Apakah jari-jari berasal dari kekuatan sinyal relatif?
Kirk Kuykendall
Iya nih! Sebenarnya Radius dalam dBm
Kārlis Baumanis
1
@Reddox, sebagian - saya berhasil menghitungnya dengan php_exec () menggunakan mathematica di serveride.
Kārlis Baumanis

Jawaban:

29

Pengukuran radius pasti mengalami beberapa kesalahan. Saya berharap jumlah kesalahan sebanding dengan jari-jari itu sendiri. Mari kita asumsikan pengukurannya tidak bias. Solusi yang masuk akal kemudian menggunakan fitting kuadrat terkecil nonlinear , dengan bobot berbanding terbalik dengan jari-jari kuadrat.

Ini adalah hal-hal standar yang tersedia dalam (antara lain) Python R,, Mathematica , dan banyak paket statistik berfitur lengkap, jadi saya hanya akan menggambarkannya. Berikut adalah beberapa data yang diperoleh dengan mengukur jarak, dengan kesalahan relatif 10%, hingga lima titik akses acak di sekitar lokasi perangkat:

Tabel data

Mathematica hanya membutuhkan satu baris kode dan tidak ada waktu CPU yang dapat diukur untuk menghitung kecocokan:

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

Edit--

Untuk jari-jari besar, solusi yang lebih akurat (bola atau ellipsoidal) dapat ditemukan hanya dengan mengganti jarak Euclidean Norm[{x, y} - {x0, y0}]dengan fungsi untuk menghitung jarak bola atau ellipsoidal. Dalam Mathematica ini bisa dilakukan, misalnya melalui

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

--selamat diedit

Salah satu keuntungan menggunakan teknik statistik seperti ini adalah dapat menghasilkan interval kepercayaan untuk parameter (yang merupakan koordinat perangkat) dan bahkan elips kepercayaan simultan untuk lokasi perangkat.

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

Tabel interval kepercayaan

Penting untuk merencanakan data dan solusinya:

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]

Peta

  • Titik putih adalah lokasi titik akses (dikenal).

  • Titik biru besar adalah lokasi perangkat yang sebenarnya.

  • Lingkaran abu-abu mewakili jari-jari yang diukur. Idealnya, mereka semua akan berpotongan di lokasi perangkat yang sebenarnya - tetapi jelas tidak, karena kesalahan pengukuran.

  • Titik merah besar adalah perkiraan lokasi perangkat.

  • Elips merah membatasi wilayah kepercayaan 95% untuk lokasi perangkat.

Bentuk elips dalam kasus ini menarik: ketidakpastian lokasi terbesar di sepanjang garis NW-SE. Di sini, jarak ke tiga titik akses (ke NE dan SW) nyaris tidak berubah dan ada trade-off dalam kesalahan antara jarak ke dua titik akses lainnya (ke utara dan tenggara).

(Wilayah kepercayaan yang lebih akurat dapat diperoleh dalam beberapa sistem sebagai kontur fungsi kemungkinan; elips ini hanyalah perkiraan orde kedua dari kontur semacam itu.)

Ketika jari-jari diukur tanpa kesalahan, semua lingkaran akan memiliki setidaknya satu titik persimpangan satu sama lain dan - jika titik itu unik - itu akan menjadi solusi unik.

Metode ini berfungsi dengan dua atau lebih titik akses. Tiga atau lebih diperlukan untuk mendapatkan interval kepercayaan. Ketika hanya dua yang tersedia, ia menemukan salah satu titik persimpangan (jika ada); jika tidak, ia akan memilih lokasi yang sesuai antara dua titik akses.

whuber
sumber
3
Bill yang bagus!
1
@Reddox Pada prinsipnya, ya: bahasa turing-complete dapat melakukan komputasi apa pun secara harfiah. Tetapi PHP akan menurunkan daftar pilihan siapa pun sebagai bahasa target. Bahkan manual PHP mengakui sebanyak: "PHP mungkin bukan bahasa yang terbaik untuk membuat aplikasi desktop dengan antarmuka pengguna grafis, tetapi jika Anda mengenal PHP dengan sangat baik, dan ingin menggunakan beberapa fitur PHP canggih di sisi klien Anda aplikasi Anda juga dapat menggunakan PHP-GTK untuk menulis program seperti itu. "
whuber
1
@Reddox Terima kasih atas tautannya. Saya melihat bagaimana ini memberikan perhitungan geometri. Dalam keadaan ini hal-hal itu tidak benar-benar diperlukan: satu-satunya perhitungan adalah aplikasi teorema Pythagoras untuk mendapatkan jarak sebagai jumlah akar kuadrat (panggilan ke Normdalam kode saya). Semua pekerjaan terlibat dalam pemasangan kuadrat terkecil nonlinear, tapi saya tidak percaya perpustakaan GEOS menyediakan kemampuan itu. Kemungkinan GEOS bisa membantu ketika jarak ellipsoidal akurat diperlukan.
whuber
2
Jika saya membaca ini dengan benar, @BenR, tampaknya Anda menimbang data sebanding dengan jari-jari kuadrat daripada berbanding terbalik dengan mereka. Apa yang terjadi ketika Anda membaginya dengan square(data[2])alih-alih mengalikannya?
Whuber
1

Dalam hal ini, setiap lingkaran memotong semua lingkaran lain dan jadi kami dapat menentukan titik persimpangan dengan cara ini:

Pertama-tama tentukan semua titik persimpangan n * (n-1). Panggil set ini titik persimpangan saya . Ambil daftar poin T yang berisi poin paling dalam. Kemudian untuk setiap titik p dalam I , periksa apakah p ada di dalam setiap lingkaran. Jika p ada di dalam setiap lingkaran, maka ini adalah titik di persimpangan paling dalam. Menambahkan titik tersebut ke dalam daftar T .

Sekarang Anda memiliki koordinat persimpangan yang diinginkan. Saya dapat memikirkan setidaknya dua cara untuk memprediksi lokasi:

  1. Hitung saja centroid (gunakan jarak sebagai berat?) Dari poligon yang dibentuk oleh T dan centroid adalah lokasi yang diinginkan.
  2. Hitung lingkaran minimum yang berisi setiap titik T . Maka pusat dari lingkaran ini adalah lokasi yang diinginkan. Menghitung R harus langsung setelah ini.

Catatan lain: pertama-tama konversi kekuatan sinyal ke jarak menggunakan model jalur ruang bebas (atau variasi). Pandangan saya adalah: Anda memiliki set data pelatihan, Anda harus mencoba menemukan eksponen path loss menggunakan beberapa teknik pembelajaran alih-alih menggunakan n = 2 atau n = 2.2 sebagai nilai tetap.

Masum Billal
sumber
apa T ... "poin terdalam" - jika saya memiliki 5 node .. berapa banyak "poin terdalam" yang harus saya periksa?
ewizard