[QGHG-it-dev-list] Studentska praksa - zadatak 38 (kreiranje Cayley Menger matrice) (fwd)

[Marko Vojinovic]

Pozdrav Marko,

Super, hvala za kod! Bacio sam pogled na brzinu, deluje ok, a kasnije cu da ga
pogledam
detaljnije i da ga testiram malo.

Sto se tice tvojih pitanja, evo i odgovora nize, u interspersed formatu. Takodje
prosledjujem mejl i na mejling listu, da imamo u arhivi za kasnije. :-)

On Sun, 24 May 2026, Marko Miladinović wrote:

> Poštovani,
> push-ovao sam rešenje zadatka 38. (funkcija koja kreira Cayley Menger
> matricu). Pre
> nego što pređem na neki sledeći zadatak, imam par pitanja. Pre početka
> implementacije
> tražene funkcije, odvojio sam vreme da se upoznam kako sa ostatkom koda
> biblioteke,
> tako i sa matematičkim pojmovima. Glavni izvor mi je bio Vaš rad
> "Infrastructure for
> Simulating n-Dimensional Simplicial Complexes" (link:
> https://www.etran.rs/2022/zbornik/ICETRAN-22_radovi/069-RTI3.1.pdf). Ako sam
> dobro
> razumeo, pojam "susedstva" (neighborhood) nekog k-simpleksa zapravo
> predstavlja skup
> ciji su elementi svi simpleksi koji su podskupi posmatranog k-simpleksa i svi
> simpleksi ciji je podskup posmatrani k-simpleks.

Tako je, pojam susedstva se upravo tako definise za simplekse.

> Takođe ako sam dobro razumeo, kada je
> u pitanju trijangulacija, u tom skupu postoji jedan i samo jedan simpleks čije
> su
> dimenzije iste kao i dimenzije posmatranog k-simpleksa i to je upravo taj
> k-simpleks
> (k-simpleks je podskup samom sebi). U implementaciji biblioteke je inače
> izabrano da
> se u "listi" suseda k-simpleksa ne pamti pokazivač na sam taj k-simpleks.

Pitanje da li je simpleks sused samom sebi je stvar konvencije, i u kodu smo
odlucili
da ne bude sused. S jedne strane, susedstvo kao relacija ima smisla samo za
razlicite simplekse, pojam "sam sebi sused" nije koristan ni za sta. Drugo, u
tablici suseda bi
taj pointer pokazivao natrag na isti simpleks, i pravio petljicu koja je
nezgodna
za implementaciju raznih funkcija. Bolje je kad tog pointera nema u tabeli
suseda.

> Glavno pitanje: ako želimo da odredimo Cayley Menger matricu simpleksu k=0
> (tačka),
> matematički gledano taj simpleks ima samo jednog suseda, i to je on sam (u
> implementaciji biblioteke niz na susedne k-simplekse biće prazan - u main
> funkcije
> fajla "cayleymengertest.cpp" sam bas to i stampao na cout), pa se postavlja
> pitanje
> koji je onda smisao indeksa i i j u formuli sa Wikipedije? U tom slučaju
> nećemo imati
> elemente d^2_ij, gde je i!=j, što onda znači da treba da vratimo matricu 2x2
> čija je
> prva vrsta 0,1, a druga 1,0? Da li onda uopšte proveravati da li su susedni
> edge-vi
> verteksa obojeni? Ovaj slučaj za sada u programu nisam implementirao, jer
> nisam
> siguran da li je ovo ispravno. Slučaj k>0 je implementiran.

Jeste, za k=0 treba prosto da vratis tu 2x2 matricu ((0,1),(1,0)). Ne moras za
ovaj
slucaj da proveravas da li su edge-evi obojeni, jer je ova matrica uvek dobar
rezultat
za vertekse. Implementiraj i taj slucaj.

> Takođe, primetio sam da u tekstu zadatka stoji da je numeracija verteksa:
> [0,k+1],
> odnosno da k-simpleks sadrži k+2 veretksa. Međutim, koliko sam video na
> Wikipediji
> (https://en.wikipedia.org/wiki/Simplex) taj broj zapravo treba da bude k+1,
> odnosno da
> je numeracija verteksa: [0,k]? I ovo sam takođe u main funkciji fajla
> "cayleymengertest.cpp" testirao - broj koji dobijam je zaista k+1. U tom
> slučaju, onda
> elementi zadnje kolone i zadnje vrste matrice treba da budu jednaki 1 (osim
> elementa
> [k+1][k+1] koji se nalazi na glavnoj dijagonali, pa je jednak 0)? Tako sam
> barem u
> biblioteci implementirao, ako bude potrebe, izmeniću to.

Typo u tekstu zadatka, izvini! Verteksi su [0,k], i uvek ih ima tacno k+1, za
simpleks.
Sama Cayley-Menger matrica ima dimenziju k+2, pa sam verovatno pri pisanju
zadatka
slucajno napisao pogresan domen za vertekse...

> Dalje, iz ovoga onda sledi da način ispitivanja da li su susedni edge-vi
> obojeni
> odgovarajućom bojom zavisi od toga koliko je k. Ako je k>1, onda vektor
> "simp->neighbors->elements[1]" sigurno nije prazan, pa ćemo ispitivati da li
> su svi
> elementi tog vektora obojeni odgovarajućom bojom, a ako je k=1, onda je vektor
> simp->neighbors->elements[1] prazan (opet, testirao sam i ovo u main funkciji
> fajla
> "cayleymengertest.cpp"), pa se u tom slučaju proveravanje da li su svi susedni
> edge-vi
> obojeni svodi na proveravanje da li je prosleđeni k-simpleks obojen. Tako sam
> za sada
> implementirao ovo ispitivanje.

Tako je, slucaj k=1 mora da se tretira zasebno, jer edge nije sam sebi sused, po
konvenciji odozgo. To je ok, bez obzira sto je kod u tvojoj funkciji malo
komplikovaniji. :-)

> Na kraju, dodao sam i templejtsku funkciju za štampanje vektora od vektora na
> cout i
> nju sam pozivao prilikom prikaza Cayley Menger matrice. Naziv je takav zato
> što ne
> moraju nužno svi vektori da budu istih dimenzija (kao što je npr. to slučaj sa
> atributom "elements" klase "SimpComp"). Pošto je u pitanju templejt, kod se
> nalazi u
> "math_functions.hpp".

Ok, mada bi mozda bilo bolje da napises pravu staticku funkciju koja ce to da
radi. Templejt u .hpp faju mi ne izgleda zgodno. Pravu funkciju cemo moci
kasnije da
prosirujemo po potrebi (da dodamo html output za gui, ovo, ono...).

Btw, ja nisam imao problema da koristim M_PI konstantu, bilo je dovoljno da
include-ujem <cmath>. Ali vidim na netu da je to platform-dependent, pa ima
smisla ono sto si dodao
da bude bolja kompatibilnost. :-)

Hvala jos jednom za kod, i ako imas jos pitanja slobodno pisi!

:-)
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