Mendistribusikan objek dalam kubus sehingga mereka memiliki jarak maksimum antara satu sama lain

11

Saya mencoba menggunakan kamera warna untuk melacak banyak objek di ruang angkasa. Setiap objek akan memiliki warna yang berbeda dan untuk dapat membedakan dengan baik antara masing-masing objek saya mencoba memastikan bahwa setiap warna yang ditugaskan untuk suatu objek sama berbeda dari warna pada objek lain sebanyak mungkin.

Dalam ruang RGB, kami memiliki tiga pesawat, semua dengan nilai antara 0 dan 255. Dalam kubus ini , saya ingin mendistribusikan warna n sehingga ada sebanyak jarak antara diri mereka dan orang lain mungkin. Pembatasan tambahan adalah bahwa ( 0 , 0 , 0 ) dan ( 255 , 255 , 255 ) (atau sebagai dekat dengan mereka mungkin) harus dimasukkan dalam n(0,0,0)/(255,255,255)n(0,0,0)(255,255,255)nwarna, karena saya ingin memastikan bahwa tidak ada objek saya yang mengambil warna karena latar belakang mungkin akan menjadi salah satu warna ini.(n−2)

Mungkin, (termasuk hitam dan sementara) tidak akan lebih dari sekitar 14.n

Terima kasih sebelumnya untuk petunjuk tentang cara mendapatkan warna-warna ini.

algorithms optimization computational-geometry Mat
sumber
2
Saya pikir Anda hanya harus mempertimbangkan ruang dua dimensi, karena kamera Anda mungkin tidak akan dapat membedakan objek yang memiliki warna yang sama tetapi intensitas yang berbeda. Masalahnya menarik.
Stéphane Gimenez
Tiga dimensi berasal dari tiga bidang warna: merah, hijau, dan biru di mana mereka masing-masing dapat secara mandiri mengambil nilai dari 0-255. Di ruang RGB, saya tidak berpikir ada intensitas. Ada ruang warna lain yang mungkin lebih cocok untuk ini karena mereka mungkin hanya 2D, meskipun saya tidak tahu banyak tentang mereka.
Matt
Jika Anda dapat dengan tepat mengontrol jumlah cahaya yang dilemparkan pada objek maka OK. Dalam ruang RGB (100, 100, 100) dan (200, 200, 200) adalah apa yang saya sebut warna yang sama (abu-abu) dengan intensitas yang berbeda.
Stéphane Gimenez
@ Matt, Stephane tampaknya menyarankan agar Anda menggunakan HSL atau HSV cube daripada RGB cube. Warna dipetakan, lebih atau kurang, tetapi kemudian Anda dapat mengabaikan komponen S untuk peta 2D. Saya akan melangkah lebih jauh untuk menyarankan skala 1D pada H sendiri di SV atau SL yang dipilih yang akan menjaga warna Anda dalam "nada" estetika yang sama. Algoritma distribusi yang sama pada 1D juga lebih sederhana!
Jason Kleban
1
Ya, jarak berpasangan maksimum. @ uosɐſ HSV tampaknya benar-benar mengembalikan hasil yang lebih baik, daripada RGB. Bahkan dengan menggunakan ketiga pesawat HSV saya dapat memilih warna individual dengan lebih baik berdasarkan jarak ke setiap warna yang ideal.
Matt

Jawaban:

4

Semua warna akan ada di permukaan kubus RGB, kecuali saya salah, untuk alasan yang sama bahwa semua muatan listrik muncul di permukaan konduktor listrik. Ini menyarankan metode berikut untuk menentukan warna:

  • menafsirkan ruang warna RGB sebagai ruang Kartesius XYZ;
  • menafsirkan warna kandidat sebagai partikel bermuatan, misalnya elektron;
  • temukan keadaan rendah-energi sistem melalui mis. simulasi anil;

n∼15

Setelah partikel bertemu, Anda memiliki susunan warna dengan menafsirkan titik sebagai warna. Awalnya, partikel dapat diatur secara acak di permukaan kubus, dengan sedikit jarak (membantu masalah konvergensi dan stabilitas). Meletakkan kelompok kecil di permukaan kubus akan berhasil.

Untuk menghindari terjebak dalam minimum lokal (daripada global), Anda dapat "pulsa" beberapa medan listrik acak kecil setelah konvergensi dan melihat apakah sistem kembali ke konfigurasi yang sama, atau yang berbeda. Agak tidak mungkin bahwa partikel yang ditempatkan secara acak akan melakukan itu dalam skenario ini, tetapi mungkin.

EDIT:

Seperti yang ditunjukkan dalam komentar, asumsi bahwa solusi optimal hanya terletak di permukaan mungkin tidak berlaku untuk semua geometri dalam kasus diskrit.

Untungnya, ini memiliki sedikit pengaruh pada sisa teknik yang dijelaskan di atas. Partikel awalnya dapat ditempatkan di mana saja; tinggalkan saja ruang di antara pasangan partikel untuk stabilitas dan perlindungan, dan kemudian iterate sistem untuk konvergensi, kemudian pulsa beberapa kali (mungkin dengan meningkatnya intensitas) untuk melihat apakah Anda bisa mendapatkan sistem untuk konvergen ke beberapa konfigurasi yang berbeda (mungkin lebih baik) .

Juga perhatikan bahwa saya percaya metode ini akan memaksimalkan sesuatu seperti "(rata-rata?) Jarak rata-rata antara pasangan partikel". Jika Anda ingin memaksimalkan jarak minimum antara pasangan partikel, atau rata-rata lainnya (geometris?) Antara pasangan partikel, ini mungkin tidak memberi Anda solusi terbaik.

Bagaimanapun, saya merasa teknik ini akan memberi Anda cara mudah untuk menghasilkan set warna yang kurang lebih optimal ... mendapatkan solusi "optimal" yang sebenarnya mungkin tidak diperlukan untuk case-use Anda. Tentu, jika solusi tepat dan terbukti optimal diinginkan, simulasi numerik mungkin bukan cara terbaik untuk pergi.

Patrick87
sumber
3
n=9
@SaeedAmiri Pengamatan yang menarik ... masalahnya mungkin dengan sifat diskrit dari masalah ini, dibandingkan dengan diskusi fisik yang biasa tentang kepadatan muatan. Perlu dicatat, bagaimanapun, bahwa tidak ada alasan bahwa simulasi numerik dengan anil fisik tidak akan tetap menemukan solusi yang Anda gambarkan; mengedit jawaban untuk memilih kembali komentar Anda dan wawasan ini.
Patrick87
Saya akan melihat apakah saya bisa mencari tahu bagaimana melakukan ini di matlab (dengan simulannealbnd). Kesulitan yang saya bayangkan adalah dalam menerjemahkan masalah menjadi fungsi matematis yang dapat diminimalisasi oleh matlab.
Matt
ps pemikiran awal saya adalah menggunakan simpul polyhedron (icosahedron), karena saya juga berpikir bahwa solusinya mungkin akan ada di permukaan, tetapi kemudian saya tidak yakin apakah itu benar.
Matt
Dalam matlab saya menulis sebuah fungsi, yang diberikan satu set (x, y, z) poin, itu menghitung jumlah jarak euclidean berpasangan antara setiap pasangan poin dalam set. Kemudian saya membaginya dengan hasil dan matlab seharusnya menemukan minimum fungsi ini. Tetapi matlab tidak melakukannya dengan benar, misalnya, untuk 4 poin 3D ia mengembalikan x1, x2, x3, x4; poin berikut (rentang 0-1): 0,0001, 0,0031, 0,9993, 0,9920 ; 0,9970 0,0004 0,9919 0,0030; 0,0030 0,0003 0,9973 0,5756. Meskipun demikian, saya pikir ini masalah matlab jadi saya akan menerima ini.
Matt