> 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
e-mail:    vmarko@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@ipb.ac.rs