smallest enclosing rectangle of the shape?

smallest enclosing rectangle of the shape? 09.03.2017. u 12:11 · pre 117 meseci #1

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.

Potpis

ER

Re: smallest enclosing rectangle of the shape? 09.03.2017. u 12:26 · pre 117 meseci #2

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.

Re: smallest enclosing rectangle of the shape? 09.03.2017. u 13:14 · pre 117 meseci #3

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" ?

Potpis

ER

Re: smallest enclosing rectangle of the shape? 09.03.2017. u 16:03 · pre 117 meseci #4

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

Re: smallest enclosing rectangle of the shape? 09.03.2017. u 17:20 · pre 117 meseci #5

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

Potpis

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

Re: smallest enclosing rectangle of the shape? 09.03.2017. u 20:58 · pre 117 meseci #6

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.

Re: smallest enclosing rectangle of the shape? 11.03.2017. u 13:36 · pre 117 meseci #7

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

Potpis

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

Re: smallest enclosing rectangle of the shape? 12.03.2017. u 16:03 · pre 117 meseci #8

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.

Potpis

ER

Re: smallest enclosing rectangle of the shape? 12.03.2017. u 17:25 · pre 117 meseci #9

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

Re: smallest enclosing rectangle of the shape? 12.03.2017. u 18:32 · pre 117 meseci #10

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.

Potpis

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

Re: smallest enclosing rectangle of the shape? 13.03.2017. u 12:58 · pre 117 meseci #11

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.

Re: smallest enclosing rectangle of the shape? 13.03.2017. u 14:10 · pre 117 meseci #12

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.

Forum kao aplikacija na telefonu

Srodne teme