Exame de Graham
Origem: Wikipédia, a enciclopédia livre.
O Exame de Graham, cuja a denominação vem de Ronald Graham, é uma técnica de computação usada para determinar o envoltório convexo de um dado conjunto de pontos no plano como complexidade de tempo O(n log n).
Índice |
[editar] O Algoritmo
|
Como se pode notar, A para B e B para C são no sentido horário, mas C de D não é. Este algoritmo detecta esta situação e descarta segmentos escolhidos anteriormente até que se orientem no sentido horário (B para D neste caso.) |
O primeiro passo neste algoritmo é encontrar o ponto com a menor coordenada y. Se houver um empate, o ponto com menor coordenada x deve servir como critério de desempate. Chamaremos esta ponto de P . Este passo é da ordem O (n), onde n é o número de pontos em questão.
Depois, o conjunto de pontos deve ser ordenado em ordem crescente do ângulo que ele com o ponto P formam com o eixo X. Qualquer algoritmo ordenação de uso geral é apropriado para isto, por exemplo, o heapsort (o qual é da ordem de O(n log n)). De forma a acelerar os cálculos, não é necessário calcular os ângulos que estes pontos formam com o eixo x; ao invés disto é suficiente calcular a tangente deste ângulo, que pode ser feito com simples aritmética.
O algoritmo processa considerando que cada ponto que cada ponto do array ordenado em seqüência. Para cada ponto, é determinado movendo-se de dois pontos antes para este ponto é uma "curva para esquerda" ou uma "curva para direita". Se é uma "curva para direita", isto significa que o ponto de partida não faz parte do envoltório convexo e deve ser removido da pesquisa. Este processo continua ao longo do conjunto até que o conjunto dos três últimos pontos seja uma curva para direita. Tão logo uma "curva a esquerda" é encontrada, o algoritmo salta para o próximo ponto do array ordenado. ( Se em qualquer etapa três pontos são colineares, é indiferente se o ponto do meio é removido ou não. Removendo-o obteremos um envoltório convexo mínimo, mas o mantendo isto não o inválida).
Novamente, para determinar se três pontos constituem uma "curva a esquerda" ou "curva a direita" não é necessário calcular o ângulo existente entre os dois segmentos de retas, isto pode ser obtido simplesmente por aritmética inteira. Dado três pontos (x1,y1), (x2,y2) e (x3,y3), simplesmente calculando o produto vetorial (x2 − x1)(y3 − y1) − (y2 − y1)(x3 − x1) dos dois vetores definidos definidos pelos pontos (x1,y1), (x2,y2) e (x2,y2), (x3,y3). Se o resultado for Zero, os três pontos são colineares, se for positivo, os três pontos constituem uma "curva para esquerda", caso contrario uma "curva para direita".
Este processo irá eventualmente retornar ao ponto de inicio, neste ponto o algoritmo estará concluído e o array agora contém os pontos do envoltório convexo no sentido anti-horário.
[editar] Pseudocódigo
Este algoritmo resultará no envoltório convexo mínimo. O resultado estará armazenado na Pilha.
Find pivot P;
Sort Points by angle (resolve ties in favor of point farther from P);
# Points[1] is the pivot
Stack.push(Points[1]);
Stack.push(Points[2]);
FOR i = 3 TO Points.length
o <- Cross_product(Stack.second, Stack.top, Points[i]);
IF o == 0 THEN
Stack.pop;
Stack.push(Points[i]);
ELSEIF o < 0 THEN
Stack.push(Points[i]);
ELSE
WHILE o <= 0 and Stack.length > 2
Stack.pop;
o <- Cross_product(Stack.second, Stack.top, Points[i]);
ENDWHILE
Stack.push(Points[i]);
ENDIF
NEXT i
FUNCTION Cross_product(p1, p2, p3)
RETURN (p2.x - p1.x)*(p3.y - p1.y) - (p3.x - p1.x)*(p2.y - p1.y);
ENDFUNCTION
[editar] Referencias
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Pages 949–955 of section 33.3: Finding the convex hull.
[editar] Código GLUI
/* Betina Vath Opengl GLUI sample
*/
#include "stdafx.h"
#include <cstdlib> //num randomico
#include <iostream>
#include <string.h>
#include <math.h>
#include <vector>
#include <utility>
#include <algorithm>
#include <GL/glut.h>
#include <GL/glui.h>
using namespace std;
#define PI 3.15
#define INFINITY 9999999999999
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//------------------------------------------
//ALGORITMO GRAHAM
//------------------------------------------
//------------------------------------------
class Point{
public:
double x,y;
Point(double _x,double _y){x=_x;y=_y;};
Point(){x=0.0;y=0.0;};
};
//------------------------------------------
//indice do ponto mais baixo
int get_lower_point_id(vector<Point> &in_point)
{
double min_y = in_point[0].y;
int id_min;
for(int i=0; i < in_point.size(); ++i)
if(in_point[i].y < min_y )
{
min_y = in_point[i].y ;
id_min = i;
}
//cout << "id_min= " << id_min << "\n";
return id_min;
}
//-------------------------------------------------------------
double compute_angle(double ox, double oy, double x1, double y1)
{
// + (x1,y1)
// /
// /
// /
// /
// / angle
// ------------+-----------------
// (ox,oy)
// .
// angle . .
// ------------+-----------------
// .. \
// \
// \
// \
// \
// \
// (x1,y1)
//
//
//
double angle;
x1=x1-ox;
y1=y1-oy;
if (y1 >=0)
angle = acos(x1/(sqrt(x1*x1+y1*y1)));
else
angle = 2.0*PI - acos(x1/(sqrt(x1*x1+y1*y1)));
//cout << angle << "x1= " << x1 << "y1= " << y1 << "x2= " << x2 << "y2= " << y2 << "\n";
return angle;
}
//-------------------------------------------
bool compute_is_left_curve(double v1x,double v1y,double v2x, double v2y, double v3x, double v3y)
{
//produto vetorial (v1-v2)x(v3-v2)
double prod_vetorial =(v1x-v2x)*(v3y-v2y)-(v3x-v2x)*(v1y-v2y);
if (prod_vetorial==0)
cout<<"zero \n";
if( prod_vetorial > 0)
return true;
else
return false;
};
//-------------------------------------------
typedef pair<double,int> anglepoint;
void Graham(vector<Point> &in_points,vector<Point> &fecho_points)
{
fecho_points.clear();
int min_y_point_id = get_lower_point_id(in_points);
//temos que colocar o ponto min_y_point_id na posicao zero
Point temp_front_point = in_points[0];
in_points[0] = in_points[min_y_point_id];
in_points[min_y_point_id] = temp_front_point ;
vector<anglepoint> list_ord;
for (int i=1;i<in_points.size();++i)
{
//computar o angulo entre o elemento 0 e o i-esimo elemento
double angle = compute_angle(in_points[0].x, in_points[0].y, in_points[i].x,in_points[i].y);
list_ord.push_back(anglepoint( angle , i ) );
}
//ordenado pelo angulo
sort(list_ord.begin(), list_ord.end());
//for (int i=0; i<list_ord.size(); ++i)
//cout<<"an - "<<list_ord[i].first<<"id- "<<list_ord[i].second<<"\n";
fecho_points.push_back(in_points[0]);
fecho_points.push_back(in_points[list_ord[0].second]);
fecho_points.push_back(in_points[list_ord[1].second]);
for (int i=2;i<list_ord.size();++i)
{
int id = list_ord[i].second;
fecho_points.push_back(in_points[id]);
//testar ultimos 3 elementos da lista
//else kill ate ser positivo
while (!compute_is_left_curve(fecho_points[fecho_points.size()-1].x,
fecho_points[fecho_points.size()-1].y,
fecho_points[fecho_points.size()-2].x,
fecho_points[fecho_points.size()-2].y,
fecho_points[fecho_points.size()-3].x,
fecho_points[fecho_points.size()-3].y) && fecho_points.size()>3 )
{
Point temp1 = fecho_points[fecho_points.size()-1];
fecho_points.pop_back();
fecho_points.pop_back();
fecho_points.push_back( temp1 );
}
}
}
//definicao de variaveis globais
vector<Point> vec_points; //vetor de pontos de onde saira o fecho convexo
vector<Point> fecho_points;
float xy_aspect;
int last_x, last_y;
float rotationX = 0.0, rotationY = 0.0;
/** These are the live variables passed into GLUI ***/
int wireframe = 0;
int obj_type = 1;
int segments = 8;
int segments2 = 8;
int light0_enabled = 1;
int light1_enabled = 1;
float light0_intensity = 1.0;
float light1_intensity = .4;
int main_window;
float scale = 1.0;
int show_axes = 1;
int show_text = 1;
float view_rotate[16] = { 1,0,0,0, 0,1,0,0, 0,0,1,0, 0,0,0,1 };
float obj_pos[] = { 0.0, 0.0, 0.0 };
char *string_list[] = { "GLUI -- Betina Vath", "Foo", "Testing...", "Bounding box: on" };
int curr_string = 0;
/** Pointers to the windows and some of the controls we'll create **/
GLUI *glui, *glui2;
GLUI_Checkbox *checkbox;
GLUI_Spinner *spinner, *light0_spinner, *light1_spinner;
GLUI_RadioGroup *radio;
GLUI_Panel *obj_panel;
/********** User IDs for callbacks ********/
#define LIGHT0_ENABLED_ID 200
#define LIGHT1_ENABLED_ID 201
#define LIGHT0_INTENSITY_ID 250
#define LIGHT1_INTENSITY_ID 251
#define BUTTON_01_ID 261
#define BUTTON_02_ID 262
/********** Miscellaneous global variables **********/
GLfloat light0_ambient[] = {0.1f, 0.1f, 0.3f, 1.0f};
GLfloat light0_diffuse[] = {.6f, .6f, 1.0f, 1.0f};
GLfloat light0_position[] = {.5f, .5f, 1.0f, 0.0f};
GLfloat light1_ambient[] = {0.1f, 0.1f, 0.3f, 1.0f};
GLfloat light1_diffuse[] = {.9f, .6f, 0.0f, 1.0f};
GLfloat light1_position[] = {-1.0f, -1.0f, 1.0f, 0.0f};
GLfloat lights_rotation[16] = {1,0,0,0, 0,1,0,0, 0,0,1,0, 0,0,0,1 };
/**************************************** control_cb() *******************/
/* GLUI control callback */
void control_cb( int control )
{
if ( control == LIGHT0_ENABLED_ID ) {
if ( light0_enabled ) {
glEnable( GL_LIGHT0 );
light0_spinner->enable();
}
else {
glDisable( GL_LIGHT0 );
light0_spinner->disable();
}
}
else if ( control == LIGHT1_ENABLED_ID ) {
if ( light1_enabled ) {
glEnable( GL_LIGHT1 );
light1_spinner->enable();
}
else {
glDisable( GL_LIGHT1 );
light1_spinner->disable();
}
}
else if ( control == LIGHT0_INTENSITY_ID ) {
float v[] = { light0_diffuse[0], light0_diffuse[1],
light0_diffuse[2], light0_diffuse[3] };
v[0] *= light0_intensity;
v[1] *= light0_intensity;
v[2] *= light0_intensity;
glLightfv(GL_LIGHT0, GL_DIFFUSE, v );
}
else if ( control == LIGHT1_INTENSITY_ID ) {
float v[] = { light1_diffuse[0], light1_diffuse[1],
light1_diffuse[2], light1_diffuse[3] };
v[0] *= light1_intensity;
v[1] *= light1_intensity;
v[2] *= light1_intensity;
glLightfv(GL_LIGHT1, GL_DIFFUSE, v );
}
else if ( control == BUTTON_01_ID ) {
std::cout<< "Button 01 pressed ! \n";
}
else if ( control == BUTTON_02_ID ) {
std::cout<< "Button 02 pressed ! \n";
}
}
/**************************************** myGlutKeyboard() **********/
void myGlutKeyboard(unsigned char Key, int x, int y)
{
switch(Key)
{
case 27:
case 'q':
exit(0);
break;
};
glutPostRedisplay();
}
/***************************************** myGlutMenu() ***********/
void myGlutMenu( int value )
{
myGlutKeyboard( value, 0, 0 );
}
/***************************************** myGlutIdle() ***********/
void myGlutIdle( void )
{
/* According to the GLUT specification, the current window is
undefined during an idle callback. So we need to explicitly change
it if necessary */
if ( glutGetWindow() != main_window )
glutSetWindow(main_window);
/* GLUI_Master.sync_live_all(); -- not needed - nothing to sync in this
application */
glutPostRedisplay();
}
/***************************************** myGlutMouse() **********/
void myGlutMouse(int button, int button_state, int x, int y )
{
}
/***************************************** myGlutMotion() **********/
void myGlutMotion(int x, int y )
{
glutPostRedisplay();
}
/**************************************** myGlutReshape() *************/
void myGlutReshape( int x, int y )
{
int tx, ty, tw, th;
GLUI_Master.get_viewport_area( &tx, &ty, &tw, &th );
glViewport( tx, ty, tw, th );
xy_aspect = (float)tw / (float)th;
glutPostRedisplay();
}
/************************************************** draw_axes() **********/
/* Disables lighting, then draws RGB axes */
void draw_axes( float scale )
{
glDisable( GL_LIGHTING );
glPushMatrix();
glScalef( scale, scale, scale );
glBegin( GL_LINES );
glColor3f( 1.0, 0.0, 0.0 );
glVertex3f( .8f, 0.05f, 0.0 ); glVertex3f( 1.0, 0.25f, 0.0 ); /* Letter X */
glVertex3f( 0.8f, .25f, 0.0 ); glVertex3f( 1.0, 0.05f, 0.0 );
glVertex3f( 0.0, 0.0, 0.0 ); glVertex3f( 1.0, 0.0, 0.0 ); /* X axis */
glColor3f( 0.0, 1.0, 0.0 );
glVertex3f( 0.0, 0.0, 0.0 ); glVertex3f( 0.0, 1.0, 0.0 ); /* Y axis */
glColor3f( 0.0, 0.0, 1.0 );
glVertex3f( 0.0, 0.0, 0.0 ); glVertex3f( 0.0, 0.0, 1.0 ); /* Z axis */
glEnd();
glPopMatrix();
glEnable( GL_LIGHTING );
}
/***************************************** myGlutDisplay() *****************/
void myGlutDisplay( void )
{
glClearColor( .9f, .9f, .9f, 1.0f );
glClear( GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT );
glMatrixMode( GL_PROJECTION );
glLoadIdentity();
glFrustum( -xy_aspect*.04, xy_aspect*.04, -.04, .04, .1, 15.0 );
glMatrixMode( GL_MODELVIEW );
glLoadIdentity();
glMultMatrixf( lights_rotation );
glLightfv(GL_LIGHT0, GL_POSITION, light0_position);
glLightfv(GL_LIGHT1, GL_POSITION, light1_position);
glLoadIdentity();
glTranslatef( 0.0, 0.0, -2.6f );
glTranslatef( obj_pos[0], obj_pos[1], -obj_pos[2] );
glMultMatrixf( view_rotate );
glScalef( scale, scale, scale );
/*** Now we render object, using the variables 'obj_type', 'segments', and
'wireframe'. These are _live_ variables, which are transparently
updated by GLUI ***/
glPushMatrix();
/*if ( wireframe )
glutWireTorus( .15,.3,16,segments );
else
glutSolidTorus( .15,.3,16,segments );*/
glDisable( GL_LIGHTING );
glPointSize(8.0);
glColor3d(1,0,0);
//desenha todos os pontos do vetor
glBegin(GL_POINTS);
for(int i=0; i<vec_points.size(); ++i) glVertex2d(vec_points[i].x,vec_points[i].y);
glEnd();
glPointSize(15.0);
glColor3d(1,0,1);
//desenha todos os pontos do vetor
glBegin(GL_POINTS);
for(int i=0; i<fecho_points.size(); ++i) glVertex2d(fecho_points[i].x,fecho_points[i].y);
glEnd();
glBegin(GL_LINE_STRIP);
for(int i=0; i<fecho_points.size(); ++i) glVertex2d(fecho_points[i].x,fecho_points[i].y);
glEnd();
if ( show_axes )
draw_axes(.52f);
glPopMatrix();
if ( show_text )
{
glDisable( GL_LIGHTING ); /* Disable lighting while we render text */
glMatrixMode( GL_PROJECTION );
glLoadIdentity();
gluOrtho2D( 0.0, 100.0, 0.0, 100.0 );
glMatrixMode( GL_MODELVIEW );
glLoadIdentity();
glColor3ub( 0, 0, 0 );
glRasterPos2i( 10, 10 );
/* printf( "text: %s\n", text ); */
/*** Render the live character array 'text' ***/
int i;
for( i=0; i<(int)strlen( string_list[curr_string] ); i++ )
glutBitmapCharacter( GLUT_BITMAP_HELVETICA_18, string_list[curr_string][i] );
}
glEnable( GL_LIGHTING );
glutSwapBuffers();
}
/**************************************** main() ********************/
int main(int argc, char* argv[])
{
/****************************************/
/* Fecho */
/****************************************/
for(int i=0; i<220; ++i)
{
vec_points.push_back(Point(cos((double) (i*89765)),sin((double) (i*888))));
}
Graham(vec_points, fecho_points);
//for(int i=0; i<fecho_points.size(); ++i)
//cout<<"x= "<<fecho_points[i].x<<"y= "<<fecho_points[i].y<<"\n";
/****************************************/
/* Initialize GLUT and create window */
/****************************************/
glutInitDisplayMode( GLUT_RGB | GLUT_DOUBLE | GLUT_DEPTH );
glutInitWindowPosition( 50, 50 );
glutInitWindowSize( 800, 600 );
main_window = glutCreateWindow( "GLUI -- Betina Vath" );
glutDisplayFunc( myGlutDisplay );
GLUI_Master.set_glutReshapeFunc( myGlutReshape );
GLUI_Master.set_glutKeyboardFunc( myGlutKeyboard );
GLUI_Master.set_glutSpecialFunc( NULL );
GLUI_Master.set_glutMouseFunc( myGlutMouse );
glutMotionFunc( myGlutMotion );
/****************************************/
/* Set up OpenGL lights */
/****************************************/
glEnable(GL_LIGHTING);
glEnable( GL_NORMALIZE );
glEnable(GL_LIGHT0);
glLightfv(GL_LIGHT0, GL_AMBIENT, light0_ambient);
glLightfv(GL_LIGHT0, GL_DIFFUSE, light0_diffuse);
glLightfv(GL_LIGHT0, GL_POSITION, light0_position);
glEnable(GL_LIGHT1);
glLightfv(GL_LIGHT1, GL_AMBIENT, light1_ambient);
glLightfv(GL_LIGHT1, GL_DIFFUSE, light1_diffuse);
glLightfv(GL_LIGHT1, GL_POSITION, light1_position);
/****************************************/
/* Enable z-buferring */
/****************************************/
glEnable(GL_DEPTH_TEST);
/****************************************/
/* Here's the GLUI code */
/****************************************/
printf( "GLUI version: %3.2f\n", GLUI_Master.get_version() );
/*** Create the side subwindow ***/
glui = GLUI_Master.create_glui_subwindow( main_window,
GLUI_SUBWINDOW_RIGHT );
obj_panel = glui->add_rollout( "Properties", false );
/***** Control for object params *****/
checkbox =
glui->add_checkbox_to_panel( obj_panel, "Wireframe", &wireframe, 1,
control_cb );
spinner = glui->add_spinner_to_panel( obj_panel, "Segments:",
GLUI_SPINNER_INT, &segments);
spinner->set_int_limits( 3, 60 );
spinner->set_alignment( GLUI_ALIGN_RIGHT );
GLUI_Spinner *scale_spinner =
glui->add_spinner_to_panel( obj_panel, "Scale:",
GLUI_SPINNER_FLOAT, &scale);
scale_spinner->set_float_limits( .2f, 4.0 );
scale_spinner->set_alignment( GLUI_ALIGN_RIGHT );
/******** Add some controls for lights ********/
GLUI_Rollout *roll_lights = glui->add_rollout( "Lights", false );
GLUI_Panel *light0 = glui->add_panel_to_panel( roll_lights, "Light 1" );
GLUI_Panel *light1 = glui->add_panel_to_panel( roll_lights, "Light 2" );
glui->add_checkbox_to_panel( light0, "Enabled", &light0_enabled,
LIGHT0_ENABLED_ID, control_cb );
light0_spinner =
glui->add_spinner_to_panel( light0, "Intensity:", GLUI_SPINNER_FLOAT,
&light0_intensity, LIGHT0_INTENSITY_ID,
control_cb );
light0_spinner->set_float_limits( 0.0, 1.0 );
glui->add_checkbox_to_panel( light1, "Enabled", &light1_enabled,
LIGHT1_ENABLED_ID, control_cb );
light1_spinner =
glui->add_spinner_to_panel( light1, "Intensity:", GLUI_SPINNER_FLOAT,
&light1_intensity, LIGHT1_INTENSITY_ID,
control_cb );
light1_spinner->set_float_limits( 0.0, 1.0 );
/*** Add another rollout ***/
GLUI_Rollout *options = glui->add_rollout( "Options", true );
/*** Add some buttons to the options rollout ***/
glui->add_button_to_panel( options,"MyButton01", BUTTON_01_ID,control_cb );
glui->add_button_to_panel( options,"MyButton02", BUTTON_02_ID,control_cb );
/**** Add listbox ****/
glui->add_statictext( "" );
GLUI_Listbox *list = glui->add_listbox( "Text:", &curr_string );
int i;
for( i=0; i<4; i++ )
list->add_item( i, string_list[i] );
glui->add_statictext( "" );
glui->add_statictext( "" );
/****** A 'quit' button *****/
glui->add_button( "Quit", 0,(GLUI_Update_CB)exit );
/**** Link windows to GLUI, and register idle callback ******/
glui->set_main_gfx_window( main_window );
/*** Create the bottom subwindow ***/
glui2 = GLUI_Master.create_glui_subwindow( main_window,
GLUI_SUBWINDOW_BOTTOM );
glui2->set_main_gfx_window( main_window );
GLUI_Rotation *view_rot = glui2->add_rotation( "Objects", view_rotate );
view_rot->set_spin( 1.0 );
glui2->add_column( false );
GLUI_Rotation *lights_rot = glui2->add_rotation( "Light", lights_rotation );
lights_rot->set_spin( .82 );
glui2->add_column( false );
GLUI_Translation *trans_xy =
glui2->add_translation( "Objects XY", GLUI_TRANSLATION_XY, obj_pos );
trans_xy->set_speed( .005 );
glui2->add_column( false );
GLUI_Translation *trans_x =
glui2->add_translation( "Objects X", GLUI_TRANSLATION_X, obj_pos );
trans_x->set_speed( .005 );
glui2->add_column( false );
GLUI_Translation *trans_y =
glui2->add_translation( "Objects Y", GLUI_TRANSLATION_Y, &obj_pos[1] );
trans_y->set_speed( .005 );
glui2->add_column( false );
GLUI_Translation *trans_z =
glui2->add_translation( "Objects Z", GLUI_TRANSLATION_Z, &obj_pos[2] );
trans_z->set_speed( .005 );
/**** We register the idle callback with GLUI, *not* with GLUT ****/
GLUI_Master.set_glutIdleFunc( myGlutIdle );
/**** Regular GLUT main loop ****/
glutMainLoop();
}
