Olá pessoal. Estou com uma dúvida mais algorítmica do que de Java, não sei se aqui seria o lugar ideal pra postar esse tipo de coisa, mas enfim, caso não seja, alertem-me e moverei o tópico para o local adequado.
O problema é o seguinte, tenho 51 cilindros de raios distintos (1, 2, 3, 4…) todos os inteiros de 1 a 51, e devo posicioná-los a fim de colocá-los em um compartimento (também cilíndrico) de menor raio possível.
Só estou procurando por idéias de algoritmos eficientes para minimizar o raio do compartimento, qualquer sugestão é bem vinda.
Caso conheçam algum fórum especializado em algoritmos (podem ser matemáticos), gostaria que também compartilhassem.
Grato.
se eu entendi bem, vc tem 51 circulos a qual seu raio corresponde a seu numero. ex: circulo 1 raio 1cm, circulo 2 raio 2cm.
vc quer criar o menor circulo de forma a englobar todos os circulos e estes devem estar lado a lado ?
se foi isso mesmo que eu entendi, usa a api JTS.
como fazer?
1- primeiro vc cria um plano cartesiano pra posicionar seus circulos.
2- se vai pegar a centroide do circulo para posicioná-lo
3- começe do maior para o menor
4- o algoritmo deve posicionar cada circulo levando em consideração:
a) menor distancia entre centroides de cada ponto
b) um circulo não deve interceccionar o outro
c) use o sentido horario para posicionar os circulos - fica mais facil o calculo
d) com excessão do primeiro e do segundo circulos, vc deve considerar as duas centroides mais proximas do ponto.
5) quanto terminar de posicionar, crie um buffer a qual o raio deva englobar todos os outros circulos
Conforme você pode ver, o método que lhe passaram (começar pelo maior e ir decrescendo os tamanhos dos círculos) não é tão ótimo assim.
EDIT - Aliás, o algoritmo que você precisa provavelmente é o citado no artigo http://en.wikipedia.org/wiki/Circle_packing_theorem