Algoritmo para desenhar um gráfico "rectangular"

[Bruno Martins]

Alguém conhece um algoritmo que me permita desenhar um gráfico da seguinte maneira:

Tenho um rectangulo para preencher com N rectangulos com áreas diferentes. Gostaria de saber qual a posição, largura e altura de cada rectangulo a colocar.

Quase de certeza que existe um algoritmo que calcule isto.

Tenho alguma urgência nisto

[dllmetal]

Em que linguagem é que estás a trabalhar??

[Bruno Martins]

Estou a trabalhar em perl, mas pouco me importa a linguagem, desde que exista o algoritmo, converto-o para perl

[LiG]

Dá para explicares melhor o problema?
Não sei se percebi bem, é para preencher o rectangulo com rectangulos mais pequenos ou subdividir o rectangulo grande em rectangulos pequenos de tamanhos diferentes?

Antes de iniciar o algoritmo já sabes quantos rectangulos tens que colocar?
Existe a possibilidade de não ser possível colocar esses rectangulos dentro do maior?

Não sei se consigo ajudar, mas de qualquer forma se pudesses explicar melhor o problema talvez ajudasse.

Isto soa-me a algo saído de um problema de investigação operacional..

[Bruno Martins]

o que eu quero fazer é o seguinte

Tenho um rectangulo (R1) com a área A1 e tenho N rectangulos cujas somas das areas é igual a A1.

De cada vez que inicio a aplicação sei o numero de rectangulos que quero utilizar e sei as áreas de cada um.

Quero colocar os N rectangulos dentro de R1. Sendo que a soma das áreas dos N rectangulos é sempre igual a A1, é sempre possível colocar todos os rectangulos dentro de A1.

O que procuro é um algoritmo que, dando A1 e as áreas dos N rectangulos a colocar, me diga a altura, largura e posição de cada rectangulo a colocar dentro de R1.

O efeito final é igual ao "view FsPartView" do konqueror.

[Bruno Martins]

Não importa muito como são colocados os rectangulos no entanto, há aqui um pequeno senão, a altura e largura de cada rectangulo a colocar tem de ser de pelo menos 10 px, o que praticamente inviabiliza a solução A no caso de haver um rectangulo a colocar cuja a área seja muito menor relativamente ao rectangulo inicial.

[Bruno Martins]

Os rectangulos nunca serão mais altos ou mais largos que o inicial, vou trabalhar com valores relativos, ou seja, de início vou saber quantos rectangulos vou ter de colocar e que áreas é que cada um tem. Por exemplo

Imaginando uma possível utilização, vou ter 13 rectangulos a colocar num rectangulo com 600px de largura e 300px de altura.
A área deste rectangulo é 180000 px^2

os 13 rectangulos são:

r1. area: 28,4% - 51120 px ^2
r2. area: 19,1 % - 34380 px^2
r3. area: 6,2% - 11194 px^2
...

Uma possível solução com estes rectangulos seria isto http://leftclick.com.pt/temp/graph.gif

[Bruno Martins]

Não não pode sobrar espaço, como cada restangulo equivale a uma determinada percentagem da área total, e a soma dessas percentagens dá 100, não pode sobrar espaço

[LiG]

Estive a pensar no caso e tenho umas dúvidas..

Pelo que foi dito presumo que se sabe à partida as dimensões do rectangulo maior (R1).

caso 1:
Sabendo as dimensões de R1 sei a área dele.

Uma vez que sei o número de rectangulos pequenos, N, não posso simplesmente achar uma maneira de criar dentro de R1, N rectangulos?

As áreas desses N rectangulos somadas iriam ser iguais à área de R1.
Parece-me, à primeira vista, que isso simplificaria um pouco o problema.

caso 2:
Caso não possa ser da forma anterior, o problema consiste então em determinar os comprimentos, alturas e posições dos rectangulos mais pequenos. Para isto temos apenas como dados as suas áreas.

O que significa de temos que determinar a partir da área de cada rectangulo as suas dimensões, de acordo com os restantes rectangulos e com o rectangulo grande de forma a encaixá-los uns nos outros, por assim dizer.

Para este segundo caso a forma mais simples, e estúpida (muito), de resolver a situação seria testar todas as combinações de posicionamento de N rectangulos até encontrar uma cujas áreas de todos os rectangulos coincida com áreas pedidas.

[Bruno Martins]

Eu sei sempre a área, a altura e largura do rectangulo maior e sei as áreas dos rectangulos mais pequenos, não sei é a altura,largura e posição dos rectangulos mais pequenos, e é isso que quero saber.