[QGHG-it-dev-list] Zadatak 10 - (Igor, Tijana) potencijal za embedding triangulacije

[Marko Vojinovic]

Jeste, ovaj potencijal sa "pravim" oprugama je verovatno isto ok. Nemam nikakav ozbiljan argument da je losiji od onog prvog, osim mozda sto neki trouglovi mogu da budu spljosteni (da im povrsina bude nula), sto sam ja hteo da izbegnem sa onim upisanim krugovima... :-)

Mozda nisam bio dovoljno jasan u zadatku --- nije neki tezak problem smisliti potencijal, nego treba da smislimo nekoliko razlicitih, pa kad dodje vreme da crtamo komplekse na ekranu da imamo vise f-ja za embedding, i da mozemo da ih isprobavamo. Svi potencijali ce u principu da rade isti posao, ali ce da proizvode razlicite slike (ravnotezni polozaji verteksa ce da budu na razlicitim mestima), pa je ideja da mozemo da biramo koji potencijal proizvodi vizuelno najlepse (tj. najpreglednije) slike. :-)

Znaci treba da smislimo npr. jos 3-4 takva potencijala, da budu sto razlicitiji jedan od drugog a da rade posao koji nam treba.

Evo upravo mi pade na pamet, tvoj potencijal moze da se uopsti i na opruge razlicitih duzina --- da const_2 ne bude konstanta, nego da se za svaki edge bira razlicito, npr. random generatorom. To ce da napravi potpuno razlicitu sliku svaki put... Znaci sto vise primera, to bolje. ;-)

:-)
Marko


Dr. Marko Vojinovic
Group for Gravitation, Particles and Fields
Institute of Physics
University of Belgrade
======================
home page: www.markovojinovic.com
e-mail:    vmarko at ipb.ac.rs



On Mon, 14 Feb 2022, Igor Salom wrote:

> 
> Ok, evo trivijalno potpitanje, da vidim sta propustam:
> 
> Elem, zar nije prirodnije/najprostije, kad si vec i sam pomenuo oprugu, da se uzme pravi potencijal opruge, tj koji je i privlacan i odbojan, tj:
> 
> V(x_i,y_i) = \sum_edge const_1 (L_edge - const_2)^2
> 
> gde const_2 ocito ima fizicki smisao ravnotezne duzine opruge? To, bar kao formula, deluje prostije (i zadrzis se na nivou edge-ova) - je li ima neki argument kako vidis da je je to
> losije resenje?
> 
> Poz!
> 
> 
> On 14.2.22. 07:25, Marko Vojinovic wrote:
>
>       Ovo je vise problem iz fizike nego iz programiranja, ali eto sad...
>
>       Metod za crtanje simplicijalnog kompleksa na ekranu bazira se na odredjivanju koordinata za vertekse u globalnom Euklidskom prostoru u koji se embed-uje dati kompleks.
>       Koordinate se odredjuju tako sto se verteksi kompleksa tretiraju kao cestice sa nekim interakcijama u nekom potencijalu, i onda algoritam iterativno aproksimira polozaje
>       cestica koje odgovaraju minimumu tog potencijala.
>
>       Drugim recima, npr. za slucaj 2D triangulacija i embed-ovanja u ravni R^2, treba osmisliti izraz za potencijalnu energiju N-cesticnog sistema V(x_i,y_i), gde i=1,...,N, koji
>       ce da stavi cestice u neki ravnotezni polozaj. Jedan predlog koji mi je pao na pamet je da stavimo dvocesticu privlacnu interakciju (oprugu) na svaki edge u kompleksu, i
>       trocesticnu odbojnu interakciju (naduvani balon) u svaki trougao, otprilike ovako:
>
>          V(x_i,y_i) = \sum_edge const_1 (L_edge)^2 + \sum_triangle const_2 / A_triangle,
>
>       gde je L_edge(x,y) duzina edge-a izmedju date dve cestice, dok je A_triangle(x,y) povrsina kruga upisanog u trougao sa date tri cestice. Prvi clan je minimalan kada je
>       rastojanje nula, tj. kada sve cestice kolapsiraju u jednu tacku. Drugi clan je minimalan kada su povrsine upisanih krugova beskonacne, pa samim tim i rastojanja izmedju
>       cestica. Kada imamo oba clana, intuicija je da potencijal ima minimum za neku konfiguraciju "izmedju" ova dva granicna slucaja (ako su obe konstante interakcija pozitivne).
>
>       Zadatak je dakle sledeci --- ispitati da li N cestica sa ovakvim interakcijama uvek imaju ravnotezno stanje, tj. da li ovaj potencijal ima globalni izolovani minimum za neke
>       vrednosti koordinata x_i,y_i, za svako N. Takodje, razmislite koji drugi mehanicki sistem bi zgodno radio ovaj posao (tako da se cestice nikad ne sudaraju), tj. osmislite i
>       predlozite jos neki, drugaciji predlog potencijala --- sve sile i interakcije su dozvoljene (gravitacija, elektrostatika, opruge, zice, lopte i baloni, ovo, ono, stagod vam
>       padne na pamet). Samo budite sigurni da postoji globalni minimum za konacne vrednosti svih koordinata. Bonus poeni ako potencijal moze lako da se uopsti sa ravni R^2 na
>       n-dim Euklidski prostor R^n, i ako ima mali broj kapling-konstanti.
>
>       Btw, ovo mozda moze da se nacrta u Mathematici za neki jednostavan izbor grafa, da vidimo kako bi izgledali polozaji tih cestica ili sl. Recimo, za 4 cestice na grafu sa dva
>       trougla spojena duz jedne ivice, ovako napamet mi se cini da ce gornji potencijal da rasporedi cestice u dva jednakostranicna trougla. Ali za komplikovaniji izbor grafa
>       nisam siguran da postoji minimum, i nisam siguran da je jednoznacan --- gornji potencijal cak ima translacionu i rotacionu invarijantnost, kojih bi takodje trebalo da se
>       otarasimo nekim globalnim spoljasnjim poljem koje ce da narusi te simetrije. Npr ako stavimo sve u neku fiksiranu potencijalnu jamu ili nesto...
>
>       Razmislite pa javite, sve ideje i predlozi su dobrodosli. ;-)
>
>       :-)
>       Marko
> 
>
>       Dr. Marko Vojinovic
>       Group for Gravitation, Particles and Fields
>       Institute of Physics
>       University of Belgrade
>       ======================
>       home page: www.markovojinovic.com
>       e-mail:    vmarko at ipb.ac.rs
> 
> 
> 
>