[QGHG-it-dev-list] Zadatak 3 - seed fja za D-simpleks

[Marko Vojinovic]

Implementirati seed f-ju za jedan D-simpleks (za proizvoljnu dimenziju D):

   SimpComp* seed_single_simplex( int D );

   Input: dimenzija D (pozitivan ceo broj).
   Output: pointer na instancirani simplicijalni kompleks koji se sastoji od jednog D-simpleksa.

Ova f-ja predstavlja opsti slucaj f-ja seed_single_edge(), seed_single_triangle() i seed_single_tetrahedron(), koje rade isti posao za D=1,2,3. Postupak i ovde ide u tri glavna koraka:

(1) Instancirati nov simplicijalni kompleks zadate dimenzije D i metodom create_ksimplex() kreirati simplekse svih nivoa od k=0 do k=D. Broj simpleksa datog nivoa k je jednak "D+1 nad k+1" (broj kombinacija k+1-vog reda od D+1 elemenata), tj. (D+1)! / ( (k+1)! (D-k)! ). Specijalno, ukupan broj verteksa (k=0) je D+1.

(2) Popuniti podklasu neighbors svakog simpleksa pointerima na njegove susede, koristeci add_neighbor(). Za slucaj proizvoljnog D-simpleksa ne mozemo da se oslonimo na sliku, vec se mora implementirati algoritam za prepoznavanje suseda (vidi nize).

(3) Simpleksima nivoa k = D-1 dodeliti boju boundary, i za svaki simpleks zadati vrednost boje na true.

Algoritam za odredjivanje da li je dati n-simpleks podsused datog k-simpleksa se realizuje na sledeci nacin:

(2.1) Prvo se za svaki k-simpleks (k>0) zadaju njegovi susedi nivoa k=0 (verteksi). Posto u celom kompleksu imamo tacno D+1 verteksa, svaki k-simpleks ima tacno "D+1 nad k+1" razlicitih verteksa, po definiciji D-simpleksa. Drugim recima, treba birati redom svaku kombinaciju k+1-ve klase od D+1 verteksa, i dodeljivati ih kao susede nivoa k=0 redom svakom k-simpleksu (jedna kombinacija u jedan k-simpleks, tako da ne postoje dva k-simpleksa sa istim skupom 0-suseda).

(2.2) Kada je korak (2.1) zavrsen, mozemo da odgovorimo na pitanje da li je dati n-simpleks podsused datog k-simpleksa (n<k), tako sto proverimo da li su svi 0-susedi n-simpleksa istovremeno i 0-susedi k-simpleksa. Ako jesu, onda je n-simpleks podsused k-simpleksa, a ako postoji makar jedan verteks koji pripada n-simpleksu a ne pripada k-simpleksu, onda nije podsused.

Koristeci kriterijum (2.2), za dati k-simpleks prodjemo kroz sve n-simplekse 0<n<k, i one koji ispune kriterijum stavimo u pod-susede k-simpleksa nivoa n, i takodje u n-simpleks stavimo k-simpleks kao nad-sused nivoa k. Ovo ponoviti za sve k-simplekse 1<k<=D.


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