Foro de elhacker.net

Hola.
Necesito ayuda para ordenar los vértices de un polígono convexo.
Tengo los siguientes vértices (x,y).
-9.75, 1.12.
-5.5, -0.5
-9.75, -1.12
-8, 1
-7.75, -1.4

Pues bien, lo que quiero es organizar dichos vértices para formar un polígono convexo.

Muchas gracias de antemano.

algo que le digo a todoslos nuevos practicamente...

1- escribe lo que quieres (ya lo hiciste)
2- muestra lo que tienes (coloca tu codigo, procura usar las etiquetas GeSHi de la edicion de textos del foro)
3- di donde te trancaste o que te causa problemas

estamos aqui para ayudarnos... no para hacer trabajos o tareas

Tengo el siguiente código escrito, pero me falla el punto pivote, que cambia de valor en la funcion angleCmp. Los datos que se toman en Vect p, son los indicados arriba.

#include "OrdenGraham.h"
#include <iostream>
 
using namespace std;
 
angulo::angulo()
{
 
};
angulo::~angulo()
{
 
};
 
float distsqr(const point &a, const point &b)
{
	return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
};
 
float dist(const point &a, const point &b)
{
	return sqrt(distsqr(a, b));
};
 
float cross(const point &a, const point &b, const point &c){
	float d = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
	if(fabs(d) < 1e-9) return 0.0;
	return d;
};
 
bool angleCmp(const point &self, const point &that)
{
    //angulo a;
	float t = cross(an.pivote, that, self);
	if(t < 0.0) return true;
	if(t == 0)
	{
		return (distsqr(an.pivote, self) < distsqr(an.pivote, that));
	}
	return false;
};
 
 
Vect graham(Vect p)
{
     angulo an;
     for(int i = 1; i < p.size(); ++i)
	 {
		if(p[i].y < p[0].y || (p[i].y == p[0].y && p[i].x < p[0].x ))
			swap(p[0], p[i]);
	 }
 
     an.pivote = p[0];
 
	 cout <<"orden"<<endl;
	 for(int i = 0; i < p.size(); ++i)
	 {
             cout << p[i].x << "  " << p[i].y << endl;
     }
     return p;
};
 

#ifndef ORDEN_GRAHAM
#define ORDEN_GRAHAM
 
#include <cmath>
#include <iostream>
#include <vector>
 
struct point
{
	float x, y;
	point() {}
	point(float X, float Y): x(X), y(Y) {}
};
 
typedef std::vector<point> Vect;
float distsqr(const point &a, const point &b);
float dist(const point &a, const point &b);
float cross(const point &a, const point &b, const point &c); 
bool angleCmp(const point &self, const point &that);
Vect graham(Vect p);
 
 
class angulo
{
      public:
             angulo();
             ~angulo();
             point pivote;
};
 
#endif

Gracias

Si es un polígono convexo se entiende que debería tener un centro de gravedad (CG)... es decir, un punto central que esté equidistante de todos sus vértices.

Con todo, para que sea convexo, se entiende que si la secuencia de vértices es V1, V2, V3, ..., entonces el ángulo CG^V1 es menor que CG^V2 y este a su vez menor que CG^V3... y así

Es como un reloj, el CG será el eje de las manecillas, si suponemos V0 las 12, V1 la 1, V2 las 2, etc...
CG^V0 = 0
CG^V1 = 360/12 = 30
CG^V2 = 360/6 = 60
CG^V3 = 90
...

Solo habría que ordenar esos ángulos y ya tendrías el orden de los vértices.

Bueno, técnicamente CG^V0 es un vector, lo que tienes que hacer es coger un primer vector como referencia y después calcular el ángulo del resto de vectores con respecto al de referencia.