Pod razlicitim rotacijama sam podrazumevao sledece:
vec pomenuti trougao za rotaciju od 0 stepeni daje sliku
1000
1100
1110
1111
dok za rotaciju od 90 stepeni daje sliku
0001
0011
0111
1111
za rotaciju od recimo 1 stepen daje sliku (cini mi se, radim na pamet)
11000
11100
11110
11111
To je slika i za 2 i josh par manjih stepeni rotacije
ako ti je jednostavnije, posmatraj to ovako
1|1000
1|1100
1|1110
1|1111
-------
Linije predstavljaju koordinate, mada kada se radi ovako sa matricama, mozemo posmatrati sve matrice tako
da su translirane u 0,0
Mozda ce ti pomoci u shvatanju ako pogledas neki algoritam i opis rasterizacije trouglova, gde pikseli predstavljaju
celije grida.
Sam algoritam za pokrivanje grid-a, odnosno za odabir koja je celija 0 a koja 1 je u sustini jednostavan (pod uslovom
da je jedinicna duzina celije manja od najmanje stranice bilo kog posmatranog poligona, ovo ujedno moze biti i uslov
za gornji nivo granulacije, dok se donji odredjuje od strane korisnika a u zavisnosti od potrebne finoce resenja)
Ako i jedan od coskova celije pada unutar poligona onda je celija vrednosti 1, u suprotnom je 0
(ovo vazi samo za poligone koji se lepe na osnovni, osnovni treba smanjiti u tom smislu da uzimas samo
celije koje u potpunosti leze unutar poligona, odnosno sva cetiri coska su unutar poligona)
Sam algoritam za ispitivanje da li tacka lezi unutar poligona je jednostavan. Radi se o parnosti preseka
duzi koja spaja tu tacku i tacku koja je sigurno van poligona sa stranicama poligona. Paran broj preska, tacka je izvan,
neparan broj preseka, tacka je unutar poligona.
Posto u startu zelish sve kombinacije rotacija (mada ovo dosta uvecava prostor pretrage), potrebno je da nadjes sve
razlicite slike koje poligon formira svojom rotacijom. Ovo moze da se uradi na par nacina, sto odokativno (krenes stepen
po stepen pa odbacis slike koje se ponavljaju) ili mozda nekom binearnom subdivizijom ugla rotacije (dok U1 i U2 daju razlicite
slike proveri za U1 i (U1+(U2-U1)/2) i za (U1+(U2-U1)/2) i U2 sve dok ne dodjes do Ux i Uy koji daju istu sliku) ili tako nesto.
Ovim si rotaciju i translaciju za necele vrednosti izbacio iz igre (pod necelim vrednostima se podrazumeva one vrednosti koje nisu
poravnate sa gridom, odnosno samo celobrojni umnosci jedinicne duzine celije grid-a).
Dalje ostaje da se odigra tetris sa matricama :D odnosno da ispitas kombinacije slaganja i da li se poklapaju sa grid-om velikog poligona.
E tu dalje opet ostaje mesta za razmisljanje kako implementirati.
Uvek moze bruteforce (sve zive kombinacije, sa eliminacijom cim dodje do nekog nepoklapanja ili do prekoracenja nekog kriterijuma - dimenzije
preostalog prostora ili nesto slicno).
Ili mozda dinamicki pristup, uparivanje pojedinacnih matrica u vece matrice sa najvecim brojem susednih celija grida koje se dodiruju a minimizovanjem
nekih drugih parametara kao sto je velicina bounding box-a (mada je ovo diskutabilno kada su u pitanju konkavni poligoni).
Stvar sa ovim pristupom je da pojednostavljuje detekciju kolizije (preklapanja) i eliminise potrebu za analitickim rotiranjem i transliranjem.
I dalje ostaje problem pakovanja.
Ako vam ponestane ideja, mozete cak mozda probati i geneticki algoritam, posto je u pitanju pretraga. Mada je pitanje kako formirati dobru fitness
funkciju.
