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

Thu Feb 17 19:34:51 CET 2022

> osim mozda sto neki trouglovi mogu da budu spljosteni (da im povrsina bude nula) 

Djah, nije nemoguce, ali ako inicijalno svi imaju istu nerastegnutu
duzinu, zvuci da moraju bas dosta da se deformisu da bi doslo do tog
degenerisanog slucaja. Ali, zaista, nemam osecaj koliko cesto se takvi
nivoi deformisanosti mogu ocekivati u praksi. Cinjenica, ako zelis da
budes siguran da neces imati trouglove degenerisane u duzi, treba ti
neki dodatan clan. Mada, ne znam zasto bas komplikovati sa povrsinom
upisane kruznice, umesto da prosto uzmes povrsinu trougla koju uvek
mozes trivijalno izracunati Heronovim obrascem (ok, zapravo se svodi
skoro na isto...) Anyway, ako hoces da se zaista osiguras da nemas
spljostene trouglove, to mislim da ne moze da bude linearan clan, kako
si ga ti stavio, vec ti treba nesto obrnuto proporcionalno povrsini, tj
tipa const/P_trougla, sto ce da divergira kako se priblizis "spljostenju
u duz". 

> da const_2 ne bude konstanta, nego da se za svaki edge bira razlicito, npr. random generatorom. 

Pa to malo komplikuje stvari zbog nejednakosti trougla... Mozda ako
random varijacije budu u nekom sitnom opsegu, tako da je npr L_max = 1.5
x L_min, ne mnogo vise. Inace ce neki trouglovi biti suvise duguljasti
cak i u nerastegnutom stanju. 

Nego, lako cemo mi da se igramo sa variranjem potencijala - al da li je
algoritam za nalazenje tog minimuma jasan/poznat? Kako, pocnes od random
konfiguracije, i onda pomeras svaku tacku u pravcu u kojem je vuce
rezultatnta sila? Je l to nece nekad da upadne u mrtvu petlju? 

Poz! 

On 2022-02-15 15:56, Marko Vojinovic wrote:

> 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 [1]
> 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 [1]
>> e-mail:    vmarko at ipb.ac.rs

-- 
Institute of Physics Belgrade
Pregrevica 118, 11080 Belgrade, Serbia
http://www.ipb.ac.rs/ 

Links:
------
[1] http://www.markovojinovic.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.ipb.ac.rs/pipermail/qghg-it-dev-list/attachments/20220217/af2559d1/attachment-0001.htm>