Temukan yang paling cocok untuk lingkaran terdekat

Di bawah ini adalah contoh gambar, jika saya memiliki titik titik putih di tengah dan saya ingin mencari lokasi terdekat yang mungkin untuk lingkaran biru (yang jelas di lokasi tempat saya meletakkannya) jika semua lingkaran merah sudah ada . Bagaimana saya bisa menemukan lokasi itu?

Kinerja bagi saya bukan masalah utama untuk aplikasi ini.

Ini bukan solusi umum, karena ada beberapa situasi jika tidak memberikan posisi lingkaran biru dengan jarak terpendek ke titik putih. Misalnya, jika Anda memiliki 100 bola merah yang dikelompokkan bersama dan titik putih jauh dari grup bola merah ini, maka tidak ada bola merah yang memiliki pengaruh pada posisi lingkaran biru yang hanya dapat dipusatkan pada titik putih. . Juga tidak akan menampilkan semua detail perhitungan. Pokoknya, untuk subset konfigurasi, di mana solusinya (lingkaran biru) bersinggungan dengan dua lingkaran merah berikut ini harus bekerja:
1) biarkan R menjadi jari-jari lingkaran biru
2) buat lingkaran di atas semua pasangan lingkaran merah, ya Saya tahu ini O (n2).
3) untuk setiap pasangan lingkaran i, j dengan pusat di (xi, yi) dan (xj, yj) dengan masing-masing jari-jari ri dan rj, hitung kuadrat jarak antara pasangan lingkaran

d_ij^2=(xi-xj)^2+(yi-yj)^2  

4) letakkan semua pasangan lingkaran itu

dij^2<R^2

ke dalam daftar.

5) melintasi daftar, menemukan 2 solusi lingkaran dengan jari-jari R bersinggungan dengan kedua lingkaran i dan j. Untuk melakukan ini gunakan persamaan ini bersama dengan gambar ini

a = R+ri  
b = R+rj  
c = dij  
α = arccos((b^2+c^2-a^2)/(2bc)  

dengan informasi di atas Anda dapat menemukan (X1ij, Y1ij) dan (X2ij, Y2ij) pusat-pusat dari 2 lingkaran bersinggungan dengan lingkaran i dan j. Untuk setiap kandidat, lingkarkan lingkaran biru di atas semua lingkaran merah lainnya dan lihat apakah tidak tumpang tindih. Jika mereka discart jika tidak memeriksa jarak ke lingkaran putih. Jika Anda menyimpan satu dengan jarak yang lebih kecil saya pikir Anda akan memiliki solusi ketika Anda selesai melintasi daftar pasangan lingkaran. Algoritma itu tampak seperti O (n3).

Penempatan terdekat ke titik akan berada di titik, atau menyentuh lingkaran.

Oleh karena itu, pertama periksa titik, kemudian gulung lingkaran baru di sekitar tepi setiap lingkaran yang ada, menghitung jarak dari titik dan jika Anda tumpang tindih saat Anda pergi dan melacak titik jarak minimum. Berhentilah saat Anda telah melintasi setiap lingkaran.

yaitu. periksa semua titik pada garis hijau, ditambah lingkaran putih. dimana garis hijau adalah lingkaran dengan jari-jari merah plus biru

Anda perlu memeriksa seluruh garis hijau, bukan hanya persimpangan sehingga Anda menutupi kasus tepi ini.

Jelas ukuran langkah traversal Anda akan menjadi penting dalam hal kinerja. Tetapi karena Anda menyatakan kinerja bukan masalah, pilih nilai yang sesuai dengan resolusi nilai output Anda. yaitu mengapung, panjang?

klarifikasi:

saran saya adalah untuk memaksa semua titik di sekitar setiap pengujian lingkaran untuk tumpang tindih dengan semua lingkaran lain di setiap titik. tidak ada kepintaran.

Jika contoh pic menunjukkan jumlah lingkaran dan resolusi, itu seharusnya tidak menjadi masalah untuk pc standar

kami memiliki 20 lingkaran radius rata-rata 200 jadi kira-kira 20 * 2 π * 200 poin * 20 tes persimpangan = 4800000 iterasi

catatan:

Pendekatan berulang seperti ini cacat karena ukuran langkah Anda, dalam hal ini resolusi output Anda, dapat sangat mempengaruhi hasilnya.

Katakanlah saya memiliki dua lingkaran merah yang terpisah 2 piksel dan satu lingkaran berwarna biru radius 1 piksel untuk memencetnya. Jelas dengan salah satu dari dua piksel sebagai pusat lingkaran biru itu akan tumpang tindih dengan yang merah. tapi jelas ada ruang untuk lingkaran jika pusatnya terletak di antara dua piksel.

Maka komentar saya bertanya tentang resolusi output. yang Anda katakan bisa apa saja.

Anda juga dapat memecahkan persamaan simultan untuk setiap pasangan lingkaran dengan jari-jari meningkat dengan jari-jari lingkaran biru.

ini akan memberi Anda poin di mana lingkaran biru akan menyentuh kedua lingkaran merah lebih akurat daripada iterasi.

Namun. ada beberapa kondisi di mana jika Anda hanya melakukan ini, Anda mendapatkan jawaban yang salah atau tidak ada. yaitu.

1 atau tanpa lingkaran

2 atau lebih lingkaran tetapi dengan titik sasaran jauh dan di luarnya.

banyak lingkaran tetapi dengan titik target dekat dengan permukaan

Plunk ini berisi kode kerja,

Konsep

Lingkaran yang diberikan adalah C1, C2 .... Cn

dan koordinat lingkaran Cn adalah Cnx, Cny dan jari-jari adalah Cr

dan jari-jari lingkaran yang diperlukan adalah R

jika lingkaran biru di X, lokasi Y dan jika tidak bertentangan dengan lingkaran lain, persamaan berikut ini benar

(C1x - X)^2 + (C1y - Y)^2 > (C1r + R)^2
(C2x - X)^2 + (C2y - Y)^2 > (C2r + R)^2
....
(Cnx - X)^2 + (Cny - Y)^2 > (Cnr + R)^2

mengubah persamaan pertama,

C1x^2 - 2C1x*X + X^2 + C1y^2 - 2C1y*Y + Y^2 > C1r^2 + 2C1r*R + R^2
X^2 + Y^2 - 2C1x*X - 2C1y*Y > C1r^2 + 2C1r*R + R^2 - C1x^2 - C1y^2

sehingga persamaan dapat ditulis ulang sebagai,

X^2 + Y^2 - 2C1x*X - 2C1y*Y > C1r^2 + 2C1r*R + R^2 - C1x^2 - C1y^2
X^2 + Y^2 - 2C2x*X - 2C2y*Y > C2r^2 + 2C2r*R + R^2 - C2x^2 - C2y^2
....
X^2 + Y^2 - 2Cnx*X - 2Cny*Y > Cnr^2 + 2Cnr*R + R^2 - Cnx^2 - Cny^2

Penerapan

mulai dari koordinat titik putih (Xw, Yw),

    var isValidLocation = function(x,y,r){
       var valid = true;
       for (var i = 0; i< circles.length; i++){
          var circle = circles[i];
          valid = valid && ((x*x + y*y - 2*circle.x*x - 2*circle.y*y) > (circle.radius*circle.radius + 2*circle.radius*r + r*r - circle.x*circle.x - circle.y*circle.y));
       }
       return valid;
      };

      var find = function(Xw,Yw,Rw){
        var radius = 0;
        while(true){
          for (var x=-1 * radius ;x <= radius; x++) {
            for (var y=-1 * radius;y <= radius; y++) {
               if (isValidLocation(Xw + x,Yw + y, Rw)){
                 drawCircle(Xw + x,Yw + y,Rw,"#0000FF");
                 return;
               }
            }   
          } 
          radius++;
        }
     }; 

koordinat pertama yang ditemukan untuk memenuhi semua persamaan adalah lokasi lingkaran biru

• O menjadi titik yang Anda coba dekatkan
• P menjadi titik yang Anda cari (pusat lingkaran biru)
• r menjadi jari-jari lingkaran biru
• C0 .. Cn menjadi pusat dari semua lingkaran yang membatasi penempatan biru

• extended circle adalah salah satu lingkaran dengan jari-jarinya diperpanjang oleh r

  Ada beberapa pekerjaan tambahan jika O tidak berada di pusat lingkaran. Jadi sekarang anggaplah O == C0

Hitung semua persimpangan dari semua lingkaran dengan C0, dengan menggunakan jari-jari masing-masing ditambah r , Ie memotong lingkaran yang diperluas dengan C0 yang diperluas. Jika tidak ada persimpangan maka titik yang Anda cari ada di mana saja di C0, jika ada persimpangan, untuk setiap persimpangan periksa apakah itu di dalam lingkaran yang diperluas lainnya (Anda dapat membatasi diri ke lingkaran yang memiliki persimpangan dengan C0). Ambil persimpangan pertama yang tidak dalam lingkaran panjang lain sebagai P, mungkin ada yang lain.

Jika tidak ada persimpangan antara lingkaran yang diperluas dan C0 yang tidak ada di dalam lingkaran yang diperluas, hitung persimpangan dari semua lingkaran yang diperluas satu sama lain. Kemudian periksa persimpangan ini dalam urutan jarak ke O, lagi apakah salah satu persimpangan terletak di dalam lingkaran yang diperluas, jika ya buang, jika tidak itu adalah hasil Anda.

Jika Anda membayangkan ini bayangkan menggambar garis di sekitar semua lingkaran yang menunjukkan lokasi yang mungkin untuk lingkaran biru Anda, mengambil penyatuan semua lingkaran yang diperluas akan menunjukkan area lingkaran biru Anda tidak bisa. Titik yang Anda cari adalah titik terdekat yang tidak ada dalam persatuan itu. Jika ada titik pada C0 yang tidak dalam serikat itu adalah solusinya, jika C0 sepenuhnya tertutup maka P harus berada di persimpangan antara dua lingkaran yang diperluas lainnya, dan itu harus berada di area yang tidak tercakup oleh kesatuan ini (Yaitu tidak dalam lingkaran yang diperluas ).

Ini adalah O (n ^ 2), ada beberapa cara untuk meningkatkan ini, kotak dapat digunakan untuk mengurangi upaya pencarian pasangan yang bijaksana, juga saya pikir menyortir lingkaran berdasarkan kedekatannya dengan O, (jarak antara dua lingkaran dikurangi oleh radio) akan membantu membatasi ruang pencarian untuk cakupan dan pencarian persimpangan

Kemungkinan mencari solusi

1. Periksa apakah titik putih adalah solusinya sendiri. Ini mencakup case dengan 0 lingkaran merah dan case sepele ketika lingkaran merah jauh dari titik putih.
2. Satu lingkaran merah.
   1. Titik putih adalah pusat lingkaran. Solusi yang mungkin adalah jumlah titik tak terbatas pada lingkaran dengan pusatnya di titik putih dan jari-jari merupakan jumlah dari jari-jari lingkaran biru dan diameter lingkaran merah. Sebut saja lingkaran hijau .
   2. Titik putih ada di tempat lain. Hanya ada satu solusi yang mungkin pada garis yang menghubungkan titik putih dan pusat lingkaran merah, yaitu jari-jari lingkaran biru menjauh dari titik di mana lingkaran merah melintasi garis menuju titik putih.
3. Dua atau lebih lingkaran merah.
   1. Mari kita mengambil lingkaran merah satu per satu dan mencari solusi yang mungkin untuk masing-masing secara individual sesuai dengan poin 2 (satu lingkaran).
   2. Untuk setiap pasangan lingkaran merah, mari kita periksa apakah Anda dapat menggambar lingkaran biru menyentuh kedua lingkaran merah. Yaitu jika jarak antara pusat mereka sama atau kurang dari jumlah jari-jarinya ditambah diameter lingkaran biru. Jika Anda bisa maka Anda memiliki dua (atau satu jika lingkaran merah persis satu diameter lingkaran biru jauhnya) solusi yang mungkin .

Pencarian solusi aktual di antara solusi yang mungkin

Sekarang Anda memiliki satu set poin yang merupakan solusi yang memungkinkan , beralih melalui mereka dan periksa masing-masing.

1. Jika intinya sebenarnya solusi. Tidak ada lingkaran merah yang memiliki pusat lebih dekat dari jari-jarinya ke titik ini.
2. Jika lebih dekat ke titik putih daripada solusi yang ditemukan sebelumnya.
3. Jika Anda memiliki lingkaran hijau (titik 2.1)
   • Jika di antara titik-titik individual tidak ada solusi yang termasuk dalam lingkaran hijau maka lingkaran hijau adalah jawabannya.
   • Jika Anda memiliki solusi individual pada lingkaran hijau dan Anda membutuhkan solusi apa pun maka ambil saja salah satunya.
   • Jika Anda memiliki solusi individual pada lingkaran hijau dan Anda membutuhkan semua solusi yang tidak terbatas maka Anda perlu memecahkan masalah lain. Anda harus memotong dari lingkaran hijau semua busur yang ditentukan oleh pasangan solusi individual dari setiap lingkaran merah.

NB: Saya tidak mengatakan bahwa implementasi algoritma harus dijelaskan dengan tepat. Anda dapat mencoba meningkatkan kinerja menggunakan pemrograman dinamis atau melewatkan solusi yang mungkin di mana jelas tidak akan berhasil.