Jump to content
thoga31

O Círculo de Arquimedes

Recommended Posts

thoga31

Título: O Círculo de Arquimedes

Para quem começar a ler e achar que isto é simples de mais, vejam a Nota 2 no final do desafio. Se isto fosse assim tão fácil, não era um desafio...

Descrição: Arquimedes descreveu, em termos simples e modernos, a circunferência (e o círculo) como sendo um polígono regular com uma infinidade de lados, cujo comprimento do lado tende para zero.

De modo a ser mais claro, o que Arquimedes fez foi encaixar dentro de um círculo polígonos regulares com cada vez mais lados de modo a tentar deduzir o mais fielmente possível o perímetro e a área.

Na imagem que se segue represento este conceito de uma forma simples: o círculo original e o octógono que encaixa dentro dele.

https://dl.dropbox.com/u/30172141/P@P/desafios/arquimedes.png

Como podem imaginar, à medida que encaixamos polígonos com mais lados, a área a sombreado torna-se menor, o lado do polígono também, e chegamos cada vez mais perto ao verdadeiro perímetro e à verdadeira área do círculo por aproximação.

A esta forma de desenhar o círculo e deduzir as suas propriedades podemos nomear, genericamente, por Método de Arquimedes.

Objectivo: Criar um programa que desenha uma circunferência através do Método de Arquimedes.

Exemplo de I/O: Deve-se pedir ao utilizador que introduza o raio da circunferência e quantos lados tem o polígono regular que a vai representar.

Input:

120    <-- o raio da circunferência (unidades arbitrárias, depende da ferramenta de desenho que utilizarem)
15     <-- o nº de lados do polígono regular
Output:

https://dl.dropbox.com/u/30172141/P@P/desafios/arquimedes2.png

Restrições:

  • Como é óbvio, o número mínimo de lados permitido é 3 (o triângulo equilátero);
  • O raio é, claro, positivo e não nulo;
  • O output poderá conter o círculo desenhado todo "certinho direitinho" de modo a se poder comparar o polígono obtido com o "original". Neste caso, os dois deverão estar sobrepostos.
  • Não poderão usar o método de dividir 360º pelo nº de lados e, com isso, determinar as intersecções com a circunferência e unir esses pontos com segmentos de recta.

Nota: Um polígono regular é uma figura geométrica 2D cujos lados têm todos o mesmo comprimento.

Nota 2: Não pensem na solução mais "fácil", se não isto não era um desafio. Não minto se disser que este é mais um desafio matemático do que de programação ;)


Knowledge is free!

Share this post


Link to post
Share on other sites
thoga31

Adicionado um ponto às restrições: não quero que façam intersecções com a circunferência original e unam os pontos... desenhem o polígono como se não fosse parte de uma circunferência, apesar de na sua base estarem dados de uma circunferência - é por isto que digo que o desafio é mais matemático do que de programação. Devem pegar no raio da circunferência e determinar com ele as propriedades do polígono, e usar essas propriedades para o desenhar. Quero total independência para com o círculo/circunferência, ele só é desenhado para termo de comparação.

EDIT: pronto, se quiserem usar este método, tudo bem. Mas adoraria ver soluções com outro(s) método(s).

Edited by thoga31

Knowledge is free!

Share this post


Link to post
Share on other sites
Warrior

O teu comentário no topo da página está-me a fazer duvidar de mim próprio..

Se tivermos a função "linha" preparada para receber os dois pontos e desenhar, isto não é duas linhas em qualquer linguagem?

Mas também não sei qual é a versão "fácil" em que estás a pensar.

Edited by Warrior

Share this post


Link to post
Share on other sites
thoga31

O teu comentário no topo da página está-me a fazer duvidar de mim próprio..

Se tivermos a função "linha" preparada para receber os dois pontos e desenhar, isto não é duas linhas em qualquer linguagem?

Não entendi.

Mas também não sei qual é a versão "fácil" em que estás a pensar.

Não estou a pensar em soluções fáceis ou difíceis. Em conversa com um amigo meu sobre este desafio, ele propôs-me que podíamos determinar, por intercepção, os pontos da circunferência onde o polígono iria fazer vértice, e depois unir os pontos. A determinação destes pontos era simples: dividias 360º pelo nº de lados - ângulo A -, imaginavas semi-rectas a partirem do centro da circunferência a fazerem ângulos A entre si, e determinavas as intersecções com a circunferência.

Não pretendia exactamente este método, sinceramente nem acho que seja o mais fácil, mas se assim quiserem, força.

O método que tinha em mente envolve pura matemática: sabendo o raio do círculo e o nº de lados do polígono, a matemática diz-te todas as características do polígono sem teres de recorrer à gincana geométrica que descrevi (aka intersecções). A partir daqui, o desenho do polígono torna-se simples.

Edited by thoga31

Knowledge is free!

Share this post


Link to post
Share on other sites
Warrior

Esse é o método complicado.

O que quis dizer é que tendo uma função "linha" disponível para desenhar um segmento, então consegue-se desenhar o polígono com 2 linhas de código.

Share this post


Link to post
Share on other sites
taviroquai

Em pseudo-codigo, considerando um plano cartesiano. É xato porque têm que se calcular o x e o y de todos os pontos que continuem os lados.

Tem mais um input, a resolução dos pontos que irão constituir a reta.

Serve para começar?

[b]ler[/b] raio
[b]ler[/b] lados
[b]ler[/b] resolução

[b]x_inicial[/b] = 0
[b]y_inicial[/b] = 0
[b]indice[/b] = 0

[b]enquanto[/b] indice [b]<[/b] lados
   x_final = (expr matematica para o calcular o proximo X)
   y_final = (expr matematica para o calcular o proximo Y)
   x = x_inicial
   y = y_inicial
   [b]enquanto[/b] x != x_final e y != y_final
       [b]desenhar[/b] x,y
       x = (expr matemática para calcular o proximo x da reta com base na resolução)
       y = (expr matemática para calcular o proximo y da reta com base na resolução)
   x_inicial = x_final
   y_inicial = y_final
   [b]incrementar[/b] indice +1

Share this post


Link to post
Share on other sites
HappyHippyHippo

bibliotecas usadas : m, SDL e SDL_gfx

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include <SDL/SDL.h>
#include <SDL/SDL_gfxPrimitives.h>

#define PI 3.14159265
#define SCREEN_SIZE 400
#define position(point) ((point  * ((SCREEN_SIZE - 10) / 2)) + (SCREEN_SIZE / 2))

void rotate_vector(double * dest, double * point, double matrix[4][4])
{
int i = 0, j = 0;

double aux[] = {point[0], point[1], point[2], point[3]};

for (i = 0; i < 4; i++)
{
	dest[i] = 0;
	for (j = 0; j < 4; j++)
	{
		dest[i] += matrix[i][j]*aux[j];
	}
}
}

int main(int argc, char ** argv)
{
long sides = 0;
char * pt = NULL;

SDL_Surface * window = NULL;
SDL_Event event;
int step = 0, run = 1;

double matrix[4][4];
double point[4], prev[4];

if (argc < 2 ||
    (sides = strtol(argv[1], &pt, 10)) == 0 ||
    sides < 3)
{
	printf("command : circulo <sides>\n");
	printf("\tsides : must be equal or greater than 3\n");
	exit(-1);
}

memset(matrix, 0, sizeof(double) * 16);
memset(point, 0, sizeof(double) * 4);

matrix[0][0] =  cos((360/sides)*(PI/180));
matrix[0][1] = -sin((360/sides)*(PI/180));
matrix[1][0] =  sin((360/sides)*(PI/180));
matrix[1][1] =  cos((360/sides)*(PI/180));
matrix[2][2] =  1;
matrix[3][3] =  1;

point[1] = -1;

if ((window = SDL_SetVideoMode(SCREEN_SIZE, SCREEN_SIZE, 32, 0)) == NULL)
{
	printf("Unable to create window\n");
	exit(-1);
}

for (step = 0; step < sides; step++)
{
	memcpy(prev, point, sizeof(double) * 4);
	rotate_vector(point, point, matrix);
	aalineColor(window, position(prev[0]), position(prev[1]), position(point[0]), position(point[1]), 0xffffff);
}
aacircleColor(window, (SCREEN_SIZE / 2), (SCREEN_SIZE / 2), ((SCREEN_SIZE - 10) / 2), 0xff00ff);

SDL_Flip(window);

while (run)
{
	while (SDL_PollEvent(&event))
	{
		if (event.type == SDL_QUIT)
		{
			run = 0;
		}
	}

	SDL_Delay(300);
}

SDL_Quit();
return 0;
}


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
thoga31

O que quis dizer é que tendo uma função "linha" disponível para desenhar um segmento, então consegue-se desenhar o polígono com 2 linhas de código.

Oh moço, aí não há problema. Desenha linha a linha o polígono usando essa função, quer seja em 2 ou em 200 linhas de código, por mim tudo bem. :D

Eu mesmo resolvi esta questão com um script Python de 10 linhas, em que há mais linhas para as formalidades do que para o essencial.

Apenas estou curioso em ver a maneira como o pessoal vai "desbravar" o problema.

Em pseudo-codigo, considerando um plano cartesiano. É xato porque têm que se calcular o x e o y de todos os pontos que continuem os lados.

Tem mais um input, a resolução dos pontos que irão constituir a reta.

Serve para começar?

Basicamente era essa a minha ideia, de uma forma geral.

bibliotecas usadas : m, SDL e SDL_gfx

Ok, no meio desse código... qual foi o teu algoritmo?

Edited by thoga31

Knowledge is free!

Share this post


Link to post
Share on other sites
HappyHippyHippo

Ok, no meio desse código... qual foi o teu algoritmo?

:D

é simples para quem está habituado a bibliotecas gráficas :D

se colocares o ponto na posição {x, y} (não interessa qual) do circulo do qual o centro se encontra no aposição {0, 0}, basta "rodar" a posição desse ponto em relação ao eixo dos Z o ângulo dado pela divisão : 360/n_lados.

é isso que a seguinte conta faz (fiz com 4 dimensões porque é assim que que se faz em 3D ;) )

[cos(x) -sin(x)  0  0] * [x] = [x_dest]
[sin(x)  cos(x)  0  0]   [y]   [y_dest]
[ 0        0     1  0]   [0]   [  0   ]
[ 0        0     0  1]   [0]   [  0   ]

o que o algoritmo faz não é mais do que aplicar esta multiplicação ao ponto {x, y}, n_lados + 1 vezes e obterás os vértices do polígono (acabando no inicial).

ps : e sim, tem muito código por causa da multiplicação da matrix pelo vector e de gestão do SDL para apresentação da janela, porque o algoritmo não é mais do que :

       for (step = 0; step < sides; step++)
       {
               memcpy(prev, point, sizeof(double) * 4);
               rotate_vector(point, point, matrix);
               aalineColor(window, position(prev[0]), position(prev[1]), position(point[0]), position(point[1]), 0xffffff);
       }

e agora que tive a ver até poderia melhor a utilização do vector "prev", mas prontos .. deixa estar

Edited by HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
thoga31

Ok, rendo-me xD

Como utilizei Python para resolver o exercício (o output que apresentei foi obtido já com esse script), utilizei o módulo turtle, pelo que simplesmente tive de determinar qual o comprimento do lado do polígono e qual o ângulo interno de modo a poder ir movendo a turtle até ao ponto inicial.

def circ(raio, n):
   from turtle import circle, forward, left, exitonclick
   from math import cos, radians
   circle(raio) #desenha o círculo inicial
   angulo = 360.0/n
   lado = raio * (2 - 2 * cos(radians(angulo))) ** 0.5
   left(angulo / 2)  # método left usa graus
   for i in range(n):
       forward(lado)
       left(angulo)
   exitonclick()

if __name__ == '__main__':
   circ(120, 15)  # output apresentado no tópico

Por isso é que disse que tinha usado matemática - reparem no cálculo do lado do polígono. ;)

Edited by thoga31

Knowledge is free!

Share this post


Link to post
Share on other sites
taviroquai

@Happy

Ha mas assim, é a biblioteca que calcula os pontos das retas a desenhar... não é o teu algortimo...

@thoga

Só estás a calcular os pontos das interseções (como indicaste no tópico), não estás a calcular os pontos que desenham as retas...

Julgava que era para calcular todos os pontos visiveis que compoem o "circulo" de arquimedes.

Share this post


Link to post
Share on other sites
HappyHippyHippo

@Happy

Ha mas assim, é a biblioteca que calcula os pontos das retas a desenhar... não é o teu algortimo...

não.

quem calcula os pontos (vértices) é a multiplicação, e isso não é a biblioteca.

a única coisa que a biblioteca faz é desenhas a recta entre os vértices calculados.


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
taviroquai

não.

quem calcula os pontos (vértices) é a multiplicação, e isso não é a biblioteca.

a única coisa que a biblioteca faz é desenhas a recta entre os vértices calculados.

Sim, refiro-me aos pontos que constituem a reta... mas se não for o pretendido então é mais fácil.

Share this post


Link to post
Share on other sites
HappyHippyHippo

Sim, refiro-me aos pontos que constituem a reta... mas se não for o pretendido então é mais fácil.

se o problema é esse, então posso alterar o código para calcular esses pontos e deixar a dependência do SDL_gfx ...


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
pwseo

taviroquai,

Penso que o objectivo não é obrigar a desenhar ponto-a-ponto as rectas que constituem os lados dos polígonos. Isso seria o equivalente a dizeres ao Arquimedes para, na sua altura, calcular manualmente todos os pontos de cada segmento de recta dos lados do polígono e pintá-los como pontos individuais em vez de simplesmente unir com uma régua os vértices dois a dois.

Share this post


Link to post
Share on other sites
thoga31

@thoga

Só estás a calcular os pontos das interseções (como indicaste no tópico), não estás a calcular os pontos que desenham as retas...

Julgava que era para calcular todos os pontos visiveis que compoem o "circulo" de arquimedes.

O objectivo não é saber as coordenadas dos pontos, se é a isso que te referes, @taviroquai. Arquimedes, no seu tempo, não sabia o que era um referencial cartesiano. Cada um terá a sua forma de resolver a questão, mas como eu utilizei a turtle do Python para resolver este desafio, aproveitei as suas características de se ir movendo a partir do último ponto e mudar a sua direcção segundo um ângulo.

Se querem calcular as coordenadas, isso dependerá 1) do vosso algoritmo e 2) das ferramentas que usem (que poderão exigir coordenadas). Como a minha ferramenta é a turtle, usei matemática para a guiar e ir desenhando o polígono segundo as suas características.

Por fim, não determinei as intersecções - a fórmula até pode coincidir de alguma forma com esse método, mas o meu raciocínio está far behind disso.

EDIT: aproveito para referir que o método que eu inicialmente não estava a ponderar "aceitar" é este: considerar a circunferência (e a sua fórmula matemática), considerar o centro, e dele fazer sair semi-rectas que fazem entre si ângulos de, obviamente, 360/n (este factor aparece inevitavelmente em qualquer raciocínio matemático deste exercício). Depois só tinham de determinar a intersecção entre a circunferência e as semi-rectas e unir esses pontos.

Achei que era mais interessante calcular outras propriedades do polígono sabendo o seu raio e com elas desenhá-lo, isto de forma independente do círculo. No final de contas, o círculo só está aqui presente por causa do Método de Arquimedes, porque caso contrário poderia pedir-vos apenas que desenhassem o polígono de n lados dado o seu raio.

Pensei que um contexto histórico e matemático tornaria isto mais interessante.

Edited by thoga31
  • Vote 1

Knowledge is free!

Share this post


Link to post
Share on other sites
thoga31

Para quem estiver interessado, o meu raciocínio não envolveu sequer o círculo em si (apenas tive de ter em conta o seu raio). Eu utilizei a lei dos co-senos para calcular o lado do polígono tendo apenas em minha posse 1 dado concreto, que é o raio dele.

https://dl.dropbox.com/u/30172141/P@P/desafios/arquimedes_explicacao.png

Pela lei dos co-senos tira-se que: https://dl.dropbox.com/u/30172141/P@P/desafios/arquimedes_ladopoligono.png

Quanto ao ângulo que a turtle tem de fazer para desenhar o seguinte lado, também é simples. Sabe-se que o ângulo A e B são iguais, pelo que 2A = 180 - 360/n. Tendo em conta a geometria do polígono regular, o triângulo adjacente é igual. Consideremos que os ângulo A´e B´ são os homónimos de A e B. Então a turtle deverá rodar 180-A-B' = 180-2A = 180 - 180 + 360/n = 360/n. Esta dedução poderia ser feita sem contas aplicando alguns axiomas da Geometria Euclidiana.

Como se pode constatar, apenas considerei qual era a posição do polígono relativamente ao círculo que representa - circunferência circunscrita ao polígono - para saber qual das suas propriedades / medidas tem o valor do raio. De facto, define-se como raio de um polígono regular a distância dos vértices ao centro. Em suma, r(círculo) = r(polígono).

E pronto, esta foi a dedução que fiz, totalmente independente do círculo em si. Não determinei exactamente as intersecções, apenas descobri 2 propriedades do polígono de n lados dado o seu raio. Aliás, é possível saber tudo sobre um polígono regular sabendo apenas o número de lados e o seu raio, e sabemos que este tem todos os seus vértices contidos na circunferência com o mesmo raio. Isto comprova que o exercício poderia ser feito independentemente do círculo ou do Senhor Arquimedes. ;)


Knowledge is free!

Share this post


Link to post
Share on other sites
Warrior

Não tenho aqui instalado nenhuma linguagem que permita facilmente desenhar os lados, mas seria isto que faria (em pseudo pseudo-código):

assumir que o método drawLine(x0, y0, x1, y1); desenha a recta (x0, y0) - (x1, y1).

for (int i = 0; i < NLADOS; i++)
drawLine(r*cos(i*2*pi/NLADOS), r*sin(i*2*pi/NLADOS),
     r*cos((i+1)*2*pi/NLADOS), r*sin((i+1)*2*pi/NLADOS));

Edited by Warrior
  • Vote 2

Share this post


Link to post
Share on other sites
thoga31

É uma solução legítima, também com matemática à mistura - círculo trigonométrico. ;)


Knowledge is free!

Share this post


Link to post
Share on other sites
HappyHippyHippo

Não tenho aqui instalado nenhuma linguagem que permita facilmente desenhar os lados, mas seria isto que faria (em pseudo pseudo-código):

assumir que o método drawLine(x0, y0, x1, y1); desenha a recta (x0, y0) - (x1, y1).

for (int i = 0; i < NLADOS; i++)
drawLine(r*cos(i*2*pi/NLADOS), r*sin(i*2*pi/NLADOS),
     r*cos((i+1)*2*pi/NLADOS), r*sin((i+1)*2*pi/NLADOS));

não é nada mais do que fiz, só que eu fiz com multiplicação de matriz


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
thoga31

É a magia da programação no seu melhor: para um mesmo problema, n soluções. :D


Knowledge is free!

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

×
×
  • 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.