[QGHG-it-dev-list] Zadatak 38 - konstrukcija Cayley-Menger matrice za dati k-simpleks

[Marko Vojinovic]

Implementirati staticku funkciju

    vector<vector<double>> cayley_menger_matrix ( KSimplex *simp )

koja kao input dobija pointer na neki k-simpleks, i kao output vraca realnu kvadratnu matricu, koja se zove Cayley-Menger matrica. Proveriti da li je pointer na simpleks dobro definisan, i da li su svi njegovi susedni edge-evi (podsimpleksi tipa k=1) obojeni bojom VolumeSquaredColor. Ako je pointer nullptr, prijaviti gresku log_report funkcijom (vidi triangulator/library/include/input_and_output.hpp), i vratiti nula-matricu dimenzije 1x1. Ako pointer jeste dobro definisan ali bar jedan njegov edge nije obojen kako treba, prijaviti gresku log_report funkcijom i vratiti nula-matricu dimenzije (k+2)x(k+2) za dati k-simpleks.

Ako je sve dobro zadato, Cayley-Menger matrica se konstruise po formuli napisanoj u [1] (tamo je zadata determinanta, a nama treba odgovarajuca matrica). Za simpleks nivoa k matrica ima dimenziju (k+2)x(k+2), a velicine d^2_{ij} u clanku na Wikipediji odgovaraju vrednosti VolumeSquaredColor boje (double vsq) za edge koji je zajednicki za i-ti i j-ti verteks u tabeli suseda naseg k-simpleksa. Drugim recima, za sve vrednosti i,j (koje idu od 0 do k+1 inkluzivno) treba odrediti pointere na vertekse iz tabele suseda ( simp->neighbors->elements[0][i] i slicno za j), pa zatim u tabeli suseda pronaci jedan edge (simp->neighbors->elements[1][??]) koji sadrzi oba ona verteksa kao svoje podsusede (edge->neighbors->elements[0][0] i edge->neighbors->elements[0][1]). Kad nadjemo taj edge (mora da postoji tacno jedan), procitati njegovu vsq boju --- tada je d^2_{ij} = vsq, i to je broj koji treba staviti na odgovarajuce mesto u Cayley-Menger matrici.

Kada se odredjuje edge koji sadrzi dva verteksa, obratiti paznju na to da verteksi-susedi datog edge-a mogu da se uparuju sa zadatim verteksima na dva moguca nacina --- prvi sa prvim i drugi sa drugim, odnosno prvi sa drugim i drugi sa prvim. Bilo koji od ta dva redosleda moze da bude realizovan, pa treba proveriti oba.

Oblik Cayley-Menger matrice zavisi od redosleda kojim su numerisani verteksi, ali je dovoljno dobro da se izabere redosled verteksa koji je vec zadat tabelom suseda k-simpleksa, tj. pointer na i-ti verteks je simp->neighbors->elements[0][i], gde i uzima vrednosti 0,...,k+1.

Funkciju cayley-menger-matrix() staviti u source fajl biblioteke, math_functions.cpp odnosno u include fajl math_functions.hpp.

Unutar triangulator/test/ putanje zatim dodati nov fajl cayleymengertest.cpp, i na osnovu fajla volume-squared-color-test.cpp konstruisati i odstampati na stdout Cayley-Menger matricu za prvi simpleks svakog nivoa k za 2-sferu, tj. za sve k-simplekse g->elements[k][0], gde k uzima vrednosti 0,1,2. Po zelji menjati VolumeSquaredColor boje svih edge-eva u 2-sferi, da rezultujuce matrice izgledaju raznovrsnije.

Ukoliko imate bilo kakva pitanja ili sugestije vezane za ovaj zadatak, slobodno se javite.

:-)
Marko

[1] https://en.wikipedia.org/wiki/Distance_geometry#Cayley%E2%80%93Menger_determinants



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