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

Fri Feb 18 02:25:03 CET 2022

> Mada, ne znam zasto bas komplikovati sa povrsinom upisane kruznice, umesto da prosto uzmes povrsinu trougla koju uvek mozes trivijalno izracunati Heronovim obrascem

Fora sa povrsinama je sto mozes da zamislis corner case gde su ivice sa duzinama l, l, 2l-e, tako da u istovremenom limesu  l->oo, e->0 povrsina ipak konvergira ka necemu konacnom a trougao se svejedno spljosti. Jasno, to je vrlo tesko ako su opruge na ivicama, ali cak i u tom slucaju upisan krug mora da tezi nuli, iako je povrsina konacna. Tako da je taj krug teorijski bolja garancija protiv pljosnatih trouglova od same povrsine trougla.

Osim toga, za razliku od povrsine, upisani krug nekako favorizuje "buckaste" trouglove u odnosu na "siljaste", sto mislim da ce vizuelno biti lepse. A i jedno i drugo se racuna pomocu Heronove formule, tako da je jednako lako za racunanje. Ali kazem, to sa krugovima je samo jedan od mogucih predloga. :-)

> 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".

Pa obrnuto proporcionalno sam ga i napisao, ako se ne varam. :-)

> Mozda ako random varijacije budu u nekom sitnom opsegu, tako da je npr L_max = 1.5 x L_min,

Slazem se, izabracemo opseg za random generator tako da uvek budu zadovoljena pravila trougla, i da ivice ne divljaju previse. A sa druge strane da ima malo vise slobode nego da uvek tezi jednakostranicnosti. Mada nemam nista protiv ni jednakih opruga. :-)

> 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?

Da, otprilike tako. Za svaku cesticu ocenis na koju stranu je potencijal "nizbrdo" (tj. na koju stranu deluje sila), pomeris ih sve za neki korak u te respektivne strane, i onda ponavljas to u krug dok ne dodjes u situaciju da su za sve cestice svi pravci "uzbrdo". Inace, nama naravno ne treba *tacan* minimum, dovoljno je da mu pridjemo negde relativno blizu. Sto se tice mrtve petlje, mozemo da stavimo i neki hard cutoff na broj iteracija, pa gde se zaustavi, zaustavi. :-) To ne bi trebalo da bude tesko implementirati, vec sam bio napravio to u onom proof-of-concept kodu.

Znaci samo je vazno da potencijal sigurno ima minimum, i da se resimo globalnih simetrija (translacija i rotacija) --- u mom starom algoritmu ceo graf je umeo da "klizi" niz neku beskonacnu strmu ravan, recimo sve x-koordinate su rasle bez ogranicenja na istu stranu itd., ili je umeo da se vrti u krug. Tako da treba da stavimo neke spoljasnje potencijale koji ce ceo graf da drze u okolini koordinatnog pocetka, i da mu ne daju da se rotira kao celina. Znaci da stavimo sve u neku potencijalnu jamu oblika elipse sa centrom u nuli, ili da damo cesticama neko trenje ili sl.

Inace, ovo moze da se radi tokom "izgradnje" kompleksa --- necemo da cekamo da se skupi milion cestica pa da im trazimo minimume, nego cim uradimo neki Pachner-ov potez, u par koraka preracunamo nove ravnotezne polozaje, i tako malo po malo. Pachner-ovi potezi su lokalne transformacije, pa glavnina grafa "van" oblasti delovanja poteza nece mnogo da se pomera.

Tako nekako, videcemo. Ali treba da imamo jedno 5-6 razlicitih potencijala, da mozemo da ih biramo, gledamo kako se ponasaju itd.

Btw, ono sto bi bio mnogo zeznutiji problem je da npr. realizujemo uranjanje tako da se edge-evi ne presecaju medjusobno (ili da minimizujemo broj presecanja). Ali to vec spada u "teske" probleme, tj. ne znam algoritam koji bi tako nesto uradio. A backtracking naravno ne dolazi u obzir. ;-)

:-)
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 Thu, 17 Feb 2022, Igor Salom wrote:

> 
> > 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 d
> a 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 d
>       a 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 gene
>       ratorom. 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
> 
> 
> 
>  
> 
> 
> --
> Institute of Physics Belgrade
> Pregrevica 118, 11080 Belgrade, Serbia
> http://www.ipb.ac.rs/
> 
>