[QGHG-it-dev-list] Zadatak 12 - konstrukcija (k+1)-simpleksa iz k-simpleksa

Marko Vojinovic vmarko at ipb.ac.rs
Tue Mar 1 03:49:04 CET 2022


Implementirati f-ju koja ce da sazida (k+1)-simpleks nad datim k-simpleksom:

    KSimplex * KSimplex::build_simplex_one_level_up( SimpComp *G );

    Input: pointer na simplicijalni kompleks.
    Output: pointer na novi konstruisani (k+1)-simpleks.

Jedna vazna napomena --- ova f-ja ce da bude glavni "workhorse" za vecinu narednih f-ja koje se bave kompleksima proizvoljne dimenzije D.

Nad zadatim k-simpleksom (simp) uvek moze da se sazida (k+1) simpleks, dodavanjem jos jednog verteksa koji zivi "izvan" simp i povezivanjem sa postojecom strukturom od simp. Intiuticija je sledeca --- od verteksa moze da se napravi edge dodavanjem jos jednog verteksa i njihovim spajanjem; od edge-a moze da se napravi trougao dodavanjem novog verteksa i spajanjem sa edge-om; od trougla moze da se napravi tetraedar dodavanjem novog verteksa i spajanjem sa trouglom. Ideja radi za proizvoljan nivo k.

Postupak "spajanja" novog verteksa sa k-simpleksom podrazumeva instanciranje svih dodatnih "delova" novog (k+1)-simpleksa --- treba instancirati sve edgeve, trouglove, ..., k-simplekse koji nedostaju, i naravno instancirati taj novi (k+1)-simpleks. Nakon instanciranja svih njih, treba ih povezati u celinu definisanjem sta je cemu sused.

Algoritam za ovo se oslanja na f-ju iz zadatka 11, i ide otprilike ovako:

(1) Prvo proveriti da li simp pripada kompleksu G --- ako mu ne pripada, prijaviti error pomocu log_report() i vratiti nullptr.

(2) Proveriti da li je simp->k jednako simp->D. Ako jeste, podici dimenziju D celog kompleksa G na D+1 (prosiriti G->elements za jos jedan element), i prijaviti warning pomocu log_report() da smo ovo uradili. Obratiti paznju da svi novi simpleksi koje cemo instancirati u nastavku treba da pamte staru dimenziju D (kao sto rade svi vec postojeci simpleksi u G) a ne novu dimenziju D+1 (koja je "privremena").

(3) Instancirati novi verteks "vert" u G (pomocu SimpComp::create_ksimplex()). Instancirati novi (k+1)-simpleks "novisimp" u G. Kao pod-susede nivoa 0 (pod-vertekse) za novisimp zadati sve pod-vertekse od simp, kao i nov verteks vert.

(4) Proci kroz tabelu svih pod-suseda za simp (0 <= level <= simp->k-1). Za svaki tekuci simpleks (nivoa "level"), instancirati u G nov k-simpleks nivoa za jedan vise (k = level + 1), prekopirati u njegovu tabelu suseda sve pod-vertekse od datog k-simpleksa, i jos dodati vert.

(5) Pozvati novisimp->reconstruct_neighbors_from_vertices( G ); da rekonstruise sve ostale susede u novom (k+1)-simpleksu.

(6) Ako je sve proslo kako treba, (k+1)-simpleks je sazidan, vratiti novisimp. Ako je neka od f-ja vratila false ili nullptr, prijaviti error u log i vratiti nullptr, i zatim da u log_report() f-ju uvedemo novu kategoriju LOG_PANIC i prijavimo korisniku da je struktura celog kompleksa nekonzistentna tj. opasno zeznuta, i da dize ruke od corava posla... Ili je mozda zgodnije eventualno sanirati strukturu G ako je moguce --- deinstancirati sve sto smo uspesno instancirali, vratiti dimenziju kompleksa na D, itd, unatraske.

Ovu f-ju cemo najbolje testirati kroz upotrebu u narednim f-jama --- ako ova f-ja nesto ne radi kako treba, naredne f-je ce da obavezno da daju pogresne rezultate, sto ce biti jasno uocljivo. :-)

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




More information about the QGHG-it-dev-list mailing list