Jump to content
Sign in to follow this  
KiNgPiTo

Rectangulos numa mesa...

Recommended Posts

KiNgPiTo

Viva!

Ando aqui "às aranhas" com um problema...

Imaginem um conjunto/lista de peças, cada uma com formas rectangulares...

Agora imaginem uma mesa rectangular com dimensões x por y...

O objectivo é construir um programa que pegue nesses rectângulos todos e os coloque em cima da mesa sem haver sobreposições...

A minha ideia era ordenar por ordem decrescente de tamanho e ir colocando segundo uma ordem da esquerda para a direita, passando para baixo se nao houver espaço, validando novamente do inicio para peças mais pequenas...

O problema é o seguinte: Cada rectângulo sofre algumas restrições do tipo o rectângulo A tem de estar a direita do B (o que vai fazer com que este seja colocado 1º e com espaço a direita para o B senão falha). E para complicar mais, cada restrição também pode ter restrições, tipo A a direita de B mas B em cima de C e C à esquerda de D...

Qual a vossa ideia pessoal?

Os melhores cumprimentos...

Share this post


Link to post
Share on other sites
clera

boas, a primeira coisa que me lembrei quando li o post foi da imagem deste link: http://en.wikipedia.org/wiki/Defragmentation que descreve o processo de desfragmentação, mas quando cheguei a parte das restrições por cima e por baixo... bem de qualquer forma pode ser que  te dê alguma ideia  😳

Share this post


Link to post
Share on other sites
mogers

Em primeiro lugar, isto é um problema de algum projecto (concurso, whatever) que tenha um enunciado mais preciso?

É que precisas de explicar melhor

O problema é o seguinte: Cada rectângulo sofre algumas restrições do tipo o rectângulo A tem de estar a direita do B (o que vai fazer com que este seja colocado 1º e com espaço a direita para o B senão falha). E para complicar mais, cada restrição também pode ter restrições, tipo A a direita de B mas B em cima de C e C à esquerda de D...

Imaginando que os rectangulos são definidos por pontos (x1,y1) e (x2,y2) que correspondem ao canto superior esquerdo e inferior direito ,respectivamente, o que é que significa exactamente ter B em cima de C? Colado a B mas acima? Mesmo assim, tens liberdade total para o por em qualquer sitio desde que o y2 de B seja > y1 de C?

Um exemplo com imagens ajudava muito..


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
KiNgPiTo

Sim, é um projecto de uma cadeira...

Este é o projecto em si:

http://dl.dropbox.com/u/878621/projLI2_v3.pdf

A ultima etapa (opcional) é a parte de criar um comando RESOLVE em que os rectângulos criados mas não colocados na mesa(ou area de trabalho como chamam nos pdfs) sejam colocados onde for possível...

Em imagem, o que tenho é isto: http://dl.dropbox.com/u/878621/etapa1.pdf

Share this post


Link to post
Share on other sites
mogers

Mal vi o pdf, mas assim muito rapidamente, não tenho a certeza que tivesses uma forma muito eficiente de os colocar caso a mesa estivesse vazia. Como a mesa já pode ter rectângulos lá metidos, penso que só mesmo com backtracking.

As restrições de tar colado não há grande volta a dar, mas há formas de fazeres o tentativa-e-erro de forma inteligente.

A meu ver, o essencial é transformar o "estar a esquerda" e o "estar a direita" numa única restrição (B à esquerda de A é o mesmo que A à direita de ;). Fazer o mesmo com o cima/baixo.

Depois disso fazer uma ordenação topológica para cada uma destas restrições. Depois começas a colocar os rectângulos nessa ordem. Por exemplo, pegando nos rectângulos que devem ficar mais acima e, dentro destes, os que devem ficar mais a esquerda.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Warrior

Também podes tentar CLP, uma vez que aparenta possuir uma interface gráfica devem ser relativamente poucos rectângulos.

Share this post


Link to post
Share on other sites
KiNgPiTo

Organizei por espaços...

Comecei por ver os que estão à esquerda/direita/cima/baixo e colocar a ultima restrição possível e andando para trás, colocando o próximo na posição respectiva, ate chegar aos que não têm nenhuma restrição, ficando com os espaços livres. Resultou em 90% dos testes, já não é mau... :)

Cumprimentos

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.