[QGHG-it-dev-list] Zadatak 15 - Pachner-ov potez 1-u-(D+1) (kompleks proizvoljne dim)

[Marko Vojinovic]

Implementirati f-ju koja ce da realizuje Pachner-ov potez 1-u-(D+1) za proizvoljno D.

    KSimplex* Pachner_move_1_to_D_plus_one( KSimplex *simp, SimpComp *G );

    Input: D-simpleks simp nad kojim se vrsi potez, kompleks G.
    Output: Verteks (k=0) koji se kreira potezom.

Ovo je (verovatno) jedini Pachner-ov potez koji cemo implementirati za prozivoljnu dimenziju D. Intuitivno, on "radi" tako sto dati D-simpleks (simp) u kompleksu G "isece" na D+1 novih. Najlaksi nacin da se ovo uradi je da se privremeno nad simp-om sazida (D+1)-simpleks (vece dimenzije od D!!), pa da se zatim obrisu njegova "unutrasnjost" i simp nad kojim je sazidan. To ce u kompleksu ostaviti tacno D+1 D-simpleksa koji su "omotac" obrisanog (D+1)-simpleksa, i to zakacenih tacno na mesto gde je bio obrisani simp --- time je realizovan potez. Pritom, novi D-simpleksi se susrecu u jednom novom zajednickom verteksu (koji uvek kreira f-ja za zidanje iz zadatka 12). Njega treba odrediti i vratiti kao output.

Algoritam ide otprilike ovako:

(1) Proveriti da simp pripada u G i da ima dimenziju D. Ako ne, prijaviti error u log i vratiti nullptr.

(2) Pozvati nad simp-om f-ju build_simplex_one_level_up() iz zadatka 12, da sazida (D+1)-simpleks. Obratiti paznju da ce f-ja privremeno da podigne dimenziju celog kompleksa sa D na D+1.

(3) Izabrati bilo koji od D-suseda novokreiranog (D+1)-simpleksa koji nije simp. Uporediti spisak 0-suseda (verteksa) tog D-suseda sa spiskom 0-suseda od simp. Imace zajednicke sve vertekse osim po jednog --- simp ce da ima jedan dodatni verteks koji D-sused nema, i slicno D-sused ce da ima jedan verteks koji nije sused za simp. Zapamtiti taj verteks, njega treba da vratimo kao output.

(4) Proveriti da li neki od "starih" tj. "ostalih" (D-1)-simpleksa u kompleksu ima Boundary boju. Ako ima, obojiti sve (D-1)-susede novog (D+1)-simpleksa Boundary bojom, i za svaki od njih je setovati na "false".

(5) Proci kroz sve susede (svih nivoa) novog (D+1)-simpleksa, i obrisati ga sa spiskova suseda svakog od njih. Drugim recima, "razvezati" (D+1)-simpleks od svih njegovih pod-suseda.

(6) Deinstancirati (D+1)-simpleks (koji je "unutrasnjost"). Zatim obrisati i simp.

(7) Smanjiti dimenziju kompleksa sa vrednosti D+1 na originalnu vrednost D, i deinstancirati poslednji element iz G->elements. Ovime se kompleks vraca u konzistentno stanje sa D dimenzija. Prijaviti warning u log da smo ovo uradili --- taj warning treba da bude parnjak odgovarajucem warning-u kojim je prethodno podignuta dimenzija kompleksa, tako da korisnik moze da pregleda log i proveri da je svako podizanje dimenzije bilo praceno odgovarajucim spustanjem dimenzije.

(8) Vratiti pointer na verteks iz koraka (4) kao output. Ako je nesto krenulo naopako, prijaviti error (ili panic) u log i vratiti nullptr.

Ideja i koraci algoritma mogu da se isprate na papiru za slucaj D=2, kada je simp trougao: nad 2-dim kompleksom u kome se nalazi dati trougao, u "ekstra dimenziji" sazidati tetraedar. Vrh tetraedra je nov verteks koji f-ja vraca. Tri nove strane tetraedra su novi trouglovi u kompleksu. Zatim obrisemo unutrasnjost tetraedra i pocetni trougao, sto nam ostavlja tri nova trougla u kompleksu koji je ponovo skroz 2-dim. Time smo pocetni trougao "isekli" na tri nova trougla (koji se susrecu u novom verteksu). Postupak na slican nacin radi za prozivoljno D.

I ova f-ja se najlakse testira bojenjem kompleksa sa UniqueID, ispisivanjem sa print_compact() i crtanjem rezultata na papiru.

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