[es] - Problem: Postići što veću pokrivenost površi pokrivajući je drugim površima

adnankurtovic
Student

Član broj: 187571
Poruke: 7
*.bbone.utic.net.ba.

Profil

Problem: Postići što veću pokrivenost površi "pokrivajući" je drugim površima

^{15.09.2008. u 14:56 - pre 202 meseci}

Ovako, kolega i ja rješavamo problem za ispit, pa ako neko ima bilo kakvih ideja kako bi se problem mogao riješiti, bio bih zahvalan

Problem:
Dat je nekonveksan poligon P1. Dat je određeni broj manjih poligona Pi, i=2,k. Kako staviti što više tih malih poligona Pi na poligon P1 (treba napraviti aplikaciju koja će ih "slagati" korištenjem jednog, a vjerovatno i korištenjem više algoritama i metoda optimizacije). Dozvoljeno je rotirati i translatirati ove male poligone. Suma njihovih površina je uvijek veća od površine poligona P1.

Jako jednostavna postavka, ali rješenje .... Resursi svakako dobro došli

Odgovor na temu

masetrt
Marko Djurovic
Programer, Omni-Explorer
Beograd

Član broj: 3129
Poruke: 228
79.101.229.*

Sajt: www.vast.com

+2 Profil

Re: Problem: Postići što veću pokrivenost površi "pokrivajući" je drugim površima

^{15.09.2008. u 15:41 - pre 202 meseci}

Pa postavka jeste jednostavna ali resenje :) nije bas toliko. U sustini problem se svodi na:

http://en.wikipedia.org/wiki/Knapsack_problem

His majesty Grand Duke of Shumadija and Western Pomoravlje

Odgovor na temu

adnankurtovic
Student

Član broj: 187571
Poruke: 7
*.bbone.utic.net.ba.

Profil

Re: Problem: Postići što veću pokrivenost površi "pokrivajući" je drugim površima

^{15.09.2008. u 16:29 - pre 202 meseci}

Kako bi jedan moj profesor rekao: "Svaki problem moze podsjetiti na Knapsack ..." ali ne nije to to. Problem je u poziciji, mijenjanju pozicije, ja mislim da ne bi bilo lose ni definisati nacin za mjerenje kvalitete neke pozicije, pa onda poboljsavanju tj optimiziranju. Kod knapsacka manje - vise sve se svodi na uzimam ovo ili ne uzimam, ovdje je daleko vise parametara. Stvar je u tome sto je ovo NP-kompletan problem, e sad je stvar kako ga "napasti".

Odgovor na temu

masetrt
Marko Djurovic
Programer, Omni-Explorer
Beograd

Član broj: 3129
Poruke: 228
*.dynamic.sbb.rs.

Sajt: www.vast.com

+2 Profil

Re: Problem: Postići što veću pokrivenost površi "pokrivajući" je drugim površima

^{18.09.2008. u 21:34 - pre 202 meseci}

Eh ako se tema nije ubajatila :)

Citat:

Kako bi jedan moj profesor rekao: "Svaki problem moze podsjetiti na Knapsack ..."

Profesor je u pravu zato sto se resavanja problema ovog tipa na kraju i svedu na knapsack problem. Naime knapsack problem je speciajlni slucaj problema pakovanja tj . knapsack je u sustini jednodimenzioni specijalni slucaj packaging problema. To cak i pise u linku koji sam ti poslao i ako se prate linkovi doveli bi te do nekih slucajeva koji bi mogli da posluze kao ideja za resenje problema. E sad tu je druga stvar, po nekom mom iskustvu relativno sam lako dobijao rezultate koji izgledaju prihvatljivo, primenom greedy algoritma (jer su se od mene trazila neka prakticna "inzenjerska resenja"), ali nikad nisam znao da dokazem da je to pravo resenje. Jos pogotovo nekonveksan poligon, pa u njemu da spakujes puno malih nekonveksnih poligona. Prihavtljivo resenje je relativno lako dobiti, ali matematicki tacno hmmmm

His majesty Grand Duke of Shumadija and Western Pomoravlje

Odgovor na temu

AmarB
Amar Basic
student
Sarajevo

Član broj: 187988
Poruke: 5
*.bbone.utic.net.ba.

Profil

Re: Problem: Postići što veću pokrivenost površi "pokrivajući" je drugim površima

^{22.09.2008. u 13:32 - pre 201 meseci}

Meni ovo bas i ne mirise na jednostavno "uzmi ili nemoj uzeti". Ima puno vise elemenata koje treba uzeti u obzir. Prije svega treba obratiti paznju na poziciju na kojoj ce se nalaziti poligon koji se smjesta (ovdje podrazumijevam kako koordinate poligona tako i njegove eventualne rotacije - jer se moze zarotirati pa tako dobijamo prakticno potpuno novu situaciju). Dakle, trebalo bi, bar kako ja razmisljam, odrediti sto idealniju poziciju za svaki poligon (problem je kako odrediti kriterij koja je to pozicija dobra, a koja losa i koliko je dobra/losa). Stavise tu poziciju treba odrediti i u odnosu na preostale poligone koji se trebaju smjestiti. Treba imati na umu da su svi oni medjusobno razliciti. Nadam se da je sad jasnije i da ce nekome sinuti neka ideja. Mi smo uzeli da kodiramo najgluplji sistem slaganja i nadam se da cemo uskoro imati nesto, pa cemo se javiti, ali unaprijed znam da nam to rjesenje nece zadovoljiti zahtjeve :(

Odgovor na temu

mmix
Miljan Mitrović
Chief Software Architect
Financial Intelligence Software Ltd.
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6050

+4631 Profil

Re: Problem: Postići što veću pokrivenost površi "pokrivajući" je drugim površima

^{22.09.2008. u 13:46 - pre 201 meseci}

Iskreno, ja mislim da univerzalno resenje ne postoji. Zapravo verovatno postoji ali mislim nije "computable" jer uslovi zadatka nemaju nikakva ogranicenja (sto znaci da postoji postavka za koju je idealno resenje takvo da je pozicija i/ili ugao rotacije vrednost koja je van opsega preciznosti bilo kog zadatog programskog tipa podataka). Da bi ovaj zadatak bio "resiv" potrebno je da se ogranice neki parametri postavke (npr, uglovi samo u celim stepenima ili samo kao multiplikacije 45 ili 30 stepeni, npr, itd). Ovako kako stoji ne vidim resenje.

Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog
naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji
je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan,
sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv - Z.Đinđić

Odgovor na temu

vlaiv
Vladimir Vlaisavljevic
Novi Sad

Član broj: 15993
Poruke: 352
212.200.249.*

+1 Profil

Re: Problem: Postići što veću pokrivenost površi "pokrivajući" je drugim površima

^{22.09.2008. u 14:09 - pre 201 meseci}

Mozda bi trebalo poceti sa nekim pristupom kvantilizacije 2D prostora.

Znaci ne ici direktno na geometrijske oblike nego na grid odredjene finoce koji
geometrijski oblik pokriva.

za svaki geometriski oblik generisati matrice svih razlicitih rotacija (rotacija koje daju razlicitu pokrivenost na gridu) i
pokusati naci pakovanje gde se pojedine zauzete celije gridova ne poklapaju.

Znaci pravougli jednakokraki trougao (0,1;0,0;1,0) bi dao grid otprilike ovakav

1000
1100
1110
1111

Za jedinicnu granulaciju 4 (cetiri jedinice za jedinicnu duzinu) i rotaciju 0 stepeni

Doduse ovakav pristup ogranicava u smislu margine oko pojedinacnih elemenata, sto se regulise
finocom granulacije, ali nikada nije 0.

Na primer dva ovakva trougla se lepo uklapaju, jedan gore naveden i drugi isti takav zarotiran za 180 stepeni
u kvadrat 1x1 ali ako posmatramo matrice

1000
1100
1110
1111

i

1111
0111
0011
0001

one imaju koliziju po glavnoj dijagonali i mozemo ih pakovati na sledeci nacin

1111
2111
2211
2221
2222

(ovog puta 2 predstavlja 1 u drugoj matrici :D )

Sto je pokrivanje veceg prostora nego sto je potrebno 1.25x1

Kod odredjivanja samog prostora smestanja, zauzece grid-a se gleda malo drugacije i ne uzimaju
se oni kvadrati kroz koje prolazi ivica glavnog poligona nego samo njegova unutrasnjost

Mozda se na ovaj nacin moze doci do nekog prihvatljivog resenja

Odgovor na temu

AmarB
Amar Basic
student
Sarajevo

Član broj: 187988
Poruke: 5
*.bbone.utic.net.ba.

Profil

Re: Problem: Postići što veću pokrivenost površi "pokrivajući" je drugim površima

^{22.09.2008. u 14:37 - pre 201 meseci}

I ne treba nam optimalno rjesenje (ovo je NP-kompletan problem), vec trebamo napraviti neku heuristiku koja ce ici ka optimalnom rjesenju. Ova ideja kvantilizacije 2D prostora mi se svidja, ali nije mi jasno ovo oko generisnja "svih razlicitih rotacija koje daju razlicitu pokrivenost na gridu" (kako daju razlicitu pokrivenost?), ali i dalje ne daje ideju kako "slagati" poligone.

Odgovor na temu

vlaiv
Vladimir Vlaisavljevic
Novi Sad

Član broj: 15993
Poruke: 352
93.86.72.*

+1 Profil

Re: Problem: Postići što veću pokrivenost površi "pokrivajući" je drugim površima

^{22.09.2008. u 16:16 - pre 201 meseci}

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.

Odgovor na temu