Rozłóż obiekty w sześcianie, aby miały między sobą maksymalną odległość

Próbuję użyć kolorowej kamery do śledzenia wielu obiektów w przestrzeni. Każdy obiekt będzie miał inny kolor i aby móc dobrze rozróżnić poszczególne obiekty, staram się upewnić, że każdy kolor przypisany do obiektu jest tak różny od dowolnego koloru na jakimkolwiek innym obiekcie, jak to możliwe.

W przestrzeni RGB mamy trzy płaszczyzny, wszystkie o wartościach od 0 do 255. W tej kostce chciałbym rozmieścić kolorów, aby było tyle odległość między sobą a innymi, jak to możliwe. Dodatkowym ograniczeniem jest to, że i (lub jak najbliżej nich, jak to możliwe) powinny być uwzględnione w $(0,0,0) / (255,255,255)$ $n$ $(0, 0, 0)$ $(255, 255, 255)$ $n$ kolory, ponieważ chcę się upewnić, że żaden z moich obiektów nie przyjmuje żadnego koloru, ponieważ tło prawdopodobnie będzie jednym z tych kolorów. $(n-2)$

Prawdopodobnie (w tym czarny i while) nie będzie więcej niż około 14. $n$

Z góry dziękuję za wszelkie wskazówki, jak uzyskać te kolory.

algorithms optimization computational-geometry

— Matt
źródło

Myślę, że powinieneś wziąć pod uwagę tylko przestrzeń dwuwymiarową, ponieważ twój aparat prawdopodobnie nie będzie w stanie odróżnić obiektów, które mają ten sam kolor, ale różne natężenia. Problem jest jednak interesujący.

— Stéphane Gimenez,

Trzy wymiary pochodzą z trzech płaszczyzn kolorów: czerwonego, zielonego i niebieskiego, z których każdy może niezależnie przyjmować wartości od 0-255. W przestrzeni RGB nie sądzę, żeby była tam intensywność. Istnieją inne przestrzenie kolorów, które mogą być bardziej odpowiednie do tego, ponieważ mogą być tylko 2D, chociaż niewiele o nich wiem.

— Matt

Jeśli potrafisz precyzyjnie kontrolować ilość światła padającego na obiekty, to OK. W przestrzeni RGB (100, 100, 100) i (200, 200, 200) są to, co nazwałem tym samym kolorem (szarym) z różnymi intensywnościami.

— Stéphane Gimenez,

@Matt, Stephane wydaje się sugerować, aby używać kostki HSL lub HSV zamiast kostki RGB. Kolory są mapowane mniej więcej, ale wtedy możesz zignorować komponent S dla mapy 2D. Chciałbym pójść dalej, aby zasugerować skalę 1D na samym H przy wybranym SV lub SL, która utrzymałaby twoje kolory w podobnym „tonie” estetycznym. Algorytm równej dystrybucji w porównaniu z 1D jest również prostszy!

— Jason Kleban

Tak, maksymalna odległość parami. @ uosɐſ HSV wydawał się zwracać lepsze wyniki niż RGB. Nawet używając wszystkich trzech płaszczyzn HSV mogłem lepiej wybrać poszczególne kolory w oparciu o odległość do każdego idealnego koloru.

— Matt

Wszystkie kolory będą na powierzchni kostki RGB, chyba że się mylę, z tego samego powodu, dla którego cały ładunek elektryczny pojawia się na powierzchni przewodów elektrycznych. Sugeruje to następującą metodę określania kolorów:

interpretować przestrzeń kolorów RGB jako przestrzeń kartezjańską XYZ;
interpretować kolory kandydujące jako naładowane cząstki, np. elektrony;
znaleźć stan niskiego zużycia energii przez system, np. przez symulowane wyżarzanie;

$n \sim 15$

Kiedy cząstki się zbiegną, masz układ kolorów, interpretując punkty jako kolory. Początkowo cząstki mogą być rozmieszczane losowo na powierzchni sześcianu, z niewielkimi odstępami (pomaga to w kwestiach zbieżności i stabilności). Umieszczanie małych grup na powierzchniach sześcianu powinno działać.

Aby uniknąć utknięcia w lokalnym (a nie globalnym) minimum, możesz „pulsować” jakieś małe przypadkowe pole elektryczne po konwergencji i zobaczyć, czy system powraca do tej samej konfiguracji, czy innej. Jest mało prawdopodobne, aby losowo rozmieszczone cząstki zrobiły to w tym scenariuszu, ale jest to możliwe.

EDYTOWAĆ:

Jak wskazano w komentarzach, założenie, że optymalne rozwiązania powinny leżeć tylko na powierzchni, prawdopodobnie nie dotyczy wszystkich geometrii w przypadku dyskretnym.

Na szczęście ma to niewielki wpływ na resztę opisanej powyżej techniki. Cząstki można początkowo umieścić w dowolnym miejscu; po prostu zostaw trochę miejsca między parami cząstek dla stabilności i pokrycia, a następnie iteruj system do zbieżności, a następnie pulsuj kilka razy (być może ze wzrostem intensywności), aby sprawdzić, czy możesz doprowadzić system do konwergencji do jakiejś innej (być może lepszej) konfiguracji .

Zauważ też, że uważam, że ta metoda zmaksymalizuje coś w rodzaju „(harmonicznej?) Średniej odległości między parami cząstek”. Jeśli chcesz zmaksymalizować minimalną odległość między parami cząstek lub inną średnią (geometryczną?) Między parami cząstek, może to nie dać najlepszego rozwiązania.

W każdym razie uważam, że ta technika da ci łatwy sposób wymyślenia dobrych, w przybliżeniu optymalnych zestawów kolorów ... uzyskanie rzeczywistych „optymalnych” rozwiązań prawdopodobnie nie jest wymagane w twoim przypadku użycia. Oczywiście, jeśli pożądane jest dokładne i możliwe do udowodnienia optymalne rozwiązanie, symulacja numeryczna prawdopodobnie nie jest najlepszym rozwiązaniem.

— Patrick87
źródło

n = 9

$n=9$

@SaeedAmiri Ciekawe spostrzeżenie ... problem może dotyczyć dyskretnej natury tego problemu, w porównaniu do zwykłej fizycznej dyskusji na temat gęstości ładunku. Warto jednak zauważyć, że nie ma powodu, dla którego symulacja numeryczna z wyżarzaniem fizycznym nie znalazłaby rozwiązania, które opisujesz; edytuj odpowiedź, aby ponownie zaznaczyć swój komentarz i ten wgląd.

— Patrick87

Zobaczę, czy uda mi się dowiedzieć, jak to zrobić w programie Matlab (z simulannealbnd). Wyobrażam sobie trudność w przełożeniu problemu na funkcję matematyczną, którą Matlab może spróbować zminimalizować.

— Matt

ps początkowo myślałem o użyciu wierzchołków wielościanu (dwudziestościanu), ponieważ myślałem również, że rozwiązanie prawdopodobnie będzie miało je na powierzchni, ale wtedy nie byłem pewien, czy to prawda.

— Matt

W Matlabie napisałem funkcję, która biorąc pod uwagę zbiór punktów (x, y, z), oblicza sumę par odległości euklidesowych między każdą parą punktów w zbiorze. Następnie dzielę jeden przez wynik i matlab powinien znaleźć minimum tej funkcji. Ale Matlab nie robi tego poprawnie, na przykład dla 4 punktów 3D zwraca następujące punkty x1, x2, x3, x4; y1, y2 .... punkty (zakres 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. Niemniej jednak uważam, że jest to problem Matlaba, więc zaakceptuję to.

— Mat.