[es] - smallest enclosing rectangle of the shape?

EmmaR
Srbija

Član broj: 269847
Poruke: 466

+172 Profil

smallest enclosing rectangle of the shape?

^{09.03.2017. u 11:11 - pre 86 meseci}

Na sta se odnosi "smallest enclosing rectangle of the shape" iz zadatka:

Citat:

Define a function enclose/1 that takes a shape an returns the smallest enclosing rectangle of the shape.

shape moze biti pravouganik, krug ili trougao.
Google translate nije od pomoci, a moj engleski nije dovoljno dobar da razumem.

Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3453

Jabber: djoka_l

+1462 Profil

Re: smallest enclosing rectangle of the shape?

^{09.03.2017. u 11:26 - pre 86 meseci}

Napravi funkciju koja vraća najmanji pravougaonik koji okružuje geometrijski lik.

Pretpostavljam da je apstraktni tip podataka "shape" definisan kao niz tačaka, ako je u pitanju poligon, odnosno kao tačka i poluprečnik kruga ako je u pitanju kružnica. Treba naći pravougaonik najmanje površine u koji se može smestiti takav geometrijski lik. Pretpostavljam da i taj pravougaonik, odnosno rezultat funkcije treba da bude tipa shape, odnosno da je rezultat funkcije shape sa tačkama koje predstavljaju temena pravougaonika.

Odgovor na temu

EmmaR
Srbija

Član broj: 269847
Poruke: 466

+172 Profil

Re: smallest enclosing rectangle of the shape?

^{09.03.2017. u 12:14 - pre 86 meseci}

Citat:

djoka_l: Napravi funkciju koja vraća najmanji pravougaonik koji okružuje geometrijski lik.

Pretpostavljam da je apstraktni tip podataka "shape" definisan kao niz tačaka, ako je u pitanju poligon, odnosno kao tačka i poluprečnik kruga ako je u pitanju kružnica. Treba naći pravougaonik najmanje površine u koji se može smestiti takav geometrijski lik. Pretpostavljam da i taj pravougaonik, odnosno rezultat funkcije treba da bude tipa shape, odnosno da je rezultat funkcije shape sa tačkama koje predstavljaju temena pravougaonika.

Hvala na brzom odgovoru. Jeste, svaki oblik ima definisane koordinate: krug - centar i poluprecnik, pravuganik - gornji levi ugao, sirina i visina, a trougao - duzine stranica. Kao rezultat vraca se samo povrsina. Inace, koordinate su visak jer nema geometrijskog prikaza, a i ne koriste se za racunanje dimenzija.

Znaci, u pitanju je "opisan pravouganik" ?

Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3453

Jabber: djoka_l

+1462 Profil

Re: smallest enclosing rectangle of the shape?

^{09.03.2017. u 15:03 - pre 86 meseci}

Jeste, u tom kontekstu, "enclosing rectangle" može da se prevede kao opisani pravougaonik.

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.ptt.rs.

+2789 Profil

Re: smallest enclosing rectangle of the shape?

^{09.03.2017. u 16:20 - pre 86 meseci}

Ma, najmanji pravogaonik sa ivicama paralelnim koordinatnim osama takav da je cela figura u njemu.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3453

Jabber: djoka_l

+1462 Profil

Re: smallest enclosing rectangle of the shape?

^{09.03.2017. u 19:58 - pre 86 meseci}

Moguće da je Nedeljkovo tumačenje ispravno.
Za pravougaonik i krug rešenje je trivijalno, za pravougaonik je, na način na koji je zadat pravougaonik, on sam sebi rešenje, za kružnicu je kvadrat čiji je gornji levi ćošak na x-r, y-r sa stranicom 2r (gde je (x,y) centar kružnice).

Za trougao, ako je samo zadat kao dužine tri stranice problematično, ako nije ovo što je rekao Nedeljko.

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.ptt.rs.

+2789 Profil

Re: smallest enclosing rectangle of the shape?

^{11.03.2017. u 12:36 - pre 86 meseci}

Ovo je po svoj prilici zadatak iz programiranja. U svakom slučaju, mora se dobro definisati ono što se traži.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

EmmaR
Srbija

Član broj: 269847
Poruke: 466

+172 Profil

Re: smallest enclosing rectangle of the shape?

^{12.03.2017. u 15:03 - pre 86 meseci}

Citat:

djoka_l: Moguće da je Nedeljkovo tumačenje ispravno.
Za pravougaonik i krug rešenje je trivijalno, za pravougaonik je, na način na koji je zadat pravougaonik, on sam sebi rešenje, za kružnicu je kvadrat čiji je gornji levi ćošak na x-r, y-r sa stranicom 2r (gde je (x,y) centar kružnice).

Za trougao, ako je samo zadat kao dužine tri stranice problematično, ako nije ovo što je rekao Nedeljko.

Koordinate su potpuno nevazne, bitna je samo povrsina.

Nesto slicno sam i mislila:
krug -> kvadrat stranice jednake 2 poluprecnika , a = 2*r
pravouganik / kvadrat -> isti taj pravouganik/kvadrat
trougao -> nije nista posebno specificirano tako da moze da se uzme u obzir i specificni slucaj, npr da je isti pravougani u kom slucaju pravouganik ima stranice koje odgovaraju katetama trougla.

Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3453

Jabber: djoka_l

+1462 Profil

Re: smallest enclosing rectangle of the shape?

^{12.03.2017. u 16:25 - pre 86 meseci}

Ako trougao ima katete (ako je pravougli). A ako nije? Pitanje je da li je uopšte i trougao (da li je zbir bilo koje dve stranice veći od treće stranice).

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.ptt.rs.

+2789 Profil

Re: smallest enclosing rectangle of the shape?

^{12.03.2017. u 17:32 - pre 86 meseci}

EmmaR

Mislim da bi najbolje bilo da napišeš odakle ti taj zadatak. Ako je iz zbirke zadataka, da navedeš ceo tekst zadatka, a ako je neki projekat, da kažeš za koje potrebe ovo treba, pa da vidimo šta je najbolje rešenje.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3453

Jabber: djoka_l

+1462 Profil

Re: smallest enclosing rectangle of the shape?

^{13.03.2017. u 11:58 - pre 86 meseci}

Mene ovo podseća na probleme tipa "collision detection" kada treba da se utvrdi da li su se dva objekta (dva sprajta ili sprajt i pozadina) sudarili. Onda se kao prva aproksimacija sprajtovi svedu na pravougaonike, pa ako se pravougaonici preklapaju, onda se ide na nivo piksela.

Odgovor na temu

dusans
Stojanov Dušan
Pančevo

Član broj: 9551
Poruke: 1343
*.dynamic.sbb.rs.

+311 Profil

Re: smallest enclosing rectangle of the shape?

^{13.03.2017. u 13:10 - pre 86 meseci}

Ako je u pitanju problem iz programiranja, postoji više algoritama kako doći do rešenja:
https://en.wikipedia.org/wiki/Minimum_bounding_rectangle

1. Izračunaš tačke konveksnog omotača (poligona) koji sadrži sve tačke shape-a (convex hull).
https://en.wikibooks.org/wiki/...try/Convex_hull/Monotone_chain
Ovo je opciono, ali će algoritam biti brži ako redukuješ broj tačaka koje dalje procesiraš.

2. Isprobaš rotaciju tačaka konveksnog omotača za sve uglove od 0 do 90 stepeni sa
željenom preciznošću da bi pronašla pravougaonik najmanje površine koji sadrži sve tačke konveksnog omotača.
Ovo se opet da optimizovati - ne moraš da provervaš svaku moguću rotaciju (ugao),
već možeš da radiš binarnu pretragu do određene dubine.

Ne znam da li postoji egzaktno rešenje, i mene interesuje da li ga ima,
pa neka napiše neko ako ga zna.

Odgovor na temu