Implementar Bubble short

[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);
}

}

Edited January 3, 2013 at 05:00 PM by apocsantos
geshi

[pikax]

nao estas a implementar o bubble_sort

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

[inesbras]

Pois não, o problema é , nesta situação, não sei como o fazer.

(Aí só postei o codigo relevante e que funciona).

[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;
}

Edited January 3, 2013 at 04:46 PM by pikax

[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?

Edited January 3, 2013 at 05:58 PM by inesbras

[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.

[HappyHippyHippo]

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

sim, é C e não C++