Ir para o conteúdo
inesbras

Implementar Bubble short

Mensagens Recomendadas

inesbras

Boa tarde.

Estou a tentar implementar em c++ o seguinte trabalho:

Dada uma lista de pontos(x,y) num ficheiro .txt, tenho que os ordenar pelo ângulo que formam com uma recta horizontal que passa pelo ponto de menor abcissa (ordenando os ângulos é possivel desenhar um poligono)

Já identifiquei o ponto com a menor abcissa (Ponto de referência). Para calcular os ângulos usei atan2. Até aqui funciona tudo bem.

Agora tenho que usar o Bubble sort para ordenar os ângulos mas nao sei como o implementar, pois quando crio o array para pôr os ângulos o atan2 deixa de funcionar. Como faço?

A lista de pontos é apresentada da seguinte forma (.txt)

169,133
550,220
169,306
474,63
305,414
305,25
474,376

//poligono.h

class Poligono
{

private:
Ponto p1, p2;

COLORREF cor;
struct No{ // estrutura do nó da lista ligada
No * proximo;
Ponto ponto;
};
No * primeiro; // apontador para o primeiro nó da lista

public:

//(etc..)


Poligono(Ponto p1, Ponto p2, HWND janId);
void ordenar();

};

//poligono.cpp
void Poligono::ordenar()
{
if (primeiro==NULL){return;}
No*aux=primeiro;
int px_ref,py_ref,x_menor; //px_ref,py_ref -> ponto de referência = ponto com menor x
p1 = aux->ponto;
px_ref = p1.obterX();
py_ref = p1.obterY();

aux=aux->proximo;

while(aux!=NULL)
{
p1=aux->ponto;
x_menor=p1.obterX();

if (px_ref<=x_menor)
aux=aux->proximo;

else
{
px_ref=p1.obterX();
py_ref=p1.obterY();
aux=aux->proximo;
}
}
Ponto p1(px_ref,py_ref);
printf("Ponto de referencia: %d,%d\n",p1.obterX(),p1.obterY()); //escreve o valor do menor x
Ponto p2(p2.obterX(),p2.obterY());

if(primeiro == NULL)
return;

No * aux2 = primeiro;

while(aux2->proximo != NULL)
{
p1=aux2 -> ponto;
aux2 = aux2 -> proximo;
p2 = aux2 -> ponto;

float yy= (p2.obterY()-py_ref);
float xx= (p2.obterX()-px_ref);
float angulo = atan2(yy,xx) * 180 / PI;

printf("angulo entre o ponto de referencia (%d,%d) e o ponto (%d,%d): %.f graus\n",px_ref,py_ref,p2.obterX(),p2.obterY(),angulo);
}

}

Editado por apocsantos
geshi

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pikax

nao estas a implementar o bubble_sort

https://en.wikipedia.org/wiki/Bubble_sort


Por muito mais que que estude só aprendo uma coisa, que ainda tenho muita coisa para aprender.

A beleza de um código está em decompor problemas complexos em pequenos blocos simples.

"learn how to do it manually first, then use the wizzy tool to save time."

"Kill the baby, don't be afraid of starting all over again. Fail soon, learn fast."

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pikax

ve se isto ajuda-te:

void bubbleSort(int x[], int n)
{
   bool trocas;
   do
   {
   trocas = false;
   for (int i=0; i<n-1; i++)
   {
	  if (x[i] > x[i+1])
	  {
	    //trocar
		 int temp = x[i];
		 x[i] = x[i+1];
		 x[i+1] = temp;
		 trocas = true;  // after exchange, must look again
	  }
   }
   } while (trocas);
}

int main()
{
   int x[10] = {6,3,7,4,1,2,9,8,0,5};
   for(int i=0;i<10;i++)
    cout<<x[i]<<endl;
   cout<<"BubbleSort"<<endl;
   bubbleSort(x,10);
   for(int i=0;i<10;i++)
    cout<<x[i]<<endl;
}

Editado por pikax

Por muito mais que que estude só aprendo uma coisa, que ainda tenho muita coisa para aprender.

A beleza de um código está em decompor problemas complexos em pequenos blocos simples.

"learn how to do it manually first, then use the wizzy tool to save time."

"Kill the baby, don't be afraid of starting all over again. Fail soon, learn fast."

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
inesbras

Obrigado, já deu uma ajuda. Mas continuo com um problema.

Não consigo pôr os angulos num array. Quanto o tento fazer, a função atan2 dá sempre erro.

Em vez de ter algo do genero

 int x[10] = {6,3,7,4,1,2,9,8,0,5};

queria ter


 float angulo = atan2(yy,xx)* 180 / PI;

 float x[10] = {atan2(yy,xx)* 180 / PI};

bubbleSort(x,nnos); // nnos -> numero de pontos

printf("angulo ponto (%d,%d): %.f graus\n",p2.obterX(),p2.obterY(),x);

Não sei se me fiz entender. Mas de qualquer forma, como faço isso?

Editado por inesbras

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pikax

mas tu nao estas a usar um array no teu codigo, tens que adaptar o bubble sort para uma lista e para suportar floats.


Por muito mais que que estude só aprendo uma coisa, que ainda tenho muita coisa para aprender.

A beleza de um código está em decompor problemas complexos em pequenos blocos simples.

"learn how to do it manually first, then use the wizzy tool to save time."

"Kill the baby, don't be afraid of starting all over again. Fail soon, learn fast."

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

float x[10] = {atan2(yy,xx)* 180 / PI}; // o primeiro elemento é o resultado e o resto é 0

sim, é C e não C++


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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.