Pogledaj ako mozes da dodjes do knjige Real-time collisoin detection 99 stranu gde je dat algoritam za minimalnu sferu koja sadrzi date tacke.
Ako ne nadjes knjigu a i dalje ti je potreban algoritam, javni pa da ti prepricam sustinu algoritma.

Ko je autor knjige?

Real-Time Collision Detection, Christer Ericsson (Morgan Kaufmann 2004, ISBN hardcover 1558607323).

Izuzetno korisna knjiga!

Evo ga i link bas za to sto trazis (u knjizi nema algoritma bas za to, ima sa bounding sphere around n points, al zato daje ovaj link):

http://www.inf.ethz.ch/persona...exts/own_work/ballsofballs.pdf

Hvala. Mnogo sam naivno pristupio ovome, mislio sam da je stvar trivijalna. Do knjige ne mogu da dođem (nema u lokalnoj biblioteci :)).

Pokusaj sa nekom iterativnom metodom.. tj.. upotrebi minimizaciju. Moj predlog je:
1. Napravi func koja za zadato x,y,z vraca radius koji obuhvata sve sfere. Neka to bude func float MinRadius(float x, float y, float z)
2. Nadji priblizno/pocetno resenje (npr centar boundary box-a, a radius je dijagonala bboxa). Neka to bude tacka P(x,y,z)
3. Pozovi MinRadius 6 puta i to:
r1 = MinRadius(x - d, y, z);
r2 = MinRadius(x + d, y, z);
r3 = MinRadius(x, y - d, z);
r4 = MinRadius(x, y + d, z);
r5 = MinRadius(x, y, z - d);
r6 = MinRadius(x, y, z + d);
gde je d neka konstanta.

jedno od ovih resenja ce biti najmanje i to znaci da si korak blizi ka pravom resenju.
4. Promeni x, y, z u zavisnosti od izabranog resenja i ponovi korak 3

Posle odredjenog broja iteracija, doci ces do nekog minimuma. Problem je sto ova metoda nije bas numericki stabilna.. tj ako je d veliko moze se desiti da osciluje oko boljeg resenja. Mozda bi bilo pametno da u svakoj iteraciji d smanjujes pomalo (npr.. d = d * 0.9) tako da ce algoritam prilaziti resenju i nece oscilovati ali ce trebati veci broj iteracija. Pametan izbor velicine d moze smanjiti broj iteracija i eliminisati oscilacije.

yooyo

Ili pogledaj The Computational Geometry Algorithms Library.


http://www.cgal.org/Manual/doc...s_Min_sphere_of_spheres_d.html