Convex Hull

/*
 * Name: Convex Hull
 * Author: Vikram R. Bhat
 * Description: This program solves the geometric problem,
 *    called the Convex Hull problem. Given a set of points,
 *    the objective is to find a region such that the line joining
 *    any two points lies within that region. Informally, it is
 *    the polygon of largest area that can be formed out of the
 *    given points.( Imagine a number of pins in a plane. The
 *    convex hull is the region you get when you stretch a rubber
 *    band and allow it to snap ) I've used the TurboC++ graphics
 *    library.
*/

	  // Include files
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
#include <graphics.h>
#include <stdarg.h>
#include <stdlib.h>
#include <dos.h>

		 // Macros and function declarations
#define BGI_PATH ""
#define LEFT_CLICK 1
#define RIGHT_CLICK 2
#define NO_CLICK 0

int Max_X, Max_Y;    // Maximum x and y coordinates for the graphics mode.
					 // Set by InitGraph( )

void InitGraphSystem( const char *bgi_path );
void gprintf( int x_pos, int y_pos, char *fmt, ... );
void StatusLine( char *msg );

int InitMouse( void );
int ShowMouse( void );
int HideMouse( void );
int GetMouseStatus( int *x_pos,int *y_pos,int *btn );
void SetMousePos( int x_pos, int y_pos );
int RestrictMouse( int x1, int y1, int x2, int y2 );

	 // Checks if 'a' is within given range
inline int IsBetween( int a, int low, int high )
{
	return (  a >=low && a <=high );
}

	/************ Class definitions *************/

	  // The point class
class POINT
{
	  int x_pos, y_pos;

  public:

	  POINT( ) { x_pos = y_pos = 0; }
	  POINT( int x, int y ) { x_pos = x, y_pos = y; }

	  void Set( int x, int y ) { x_pos = x, y_pos = y; }
	  void Mark( void );
	  void DrawLine( POINT p );

	  int IsOnScreen( ) { return ( IsBetween( x_pos, 0, Max_X ) && IsBetween( y_pos, 0, Max_Y )); }
	  int Get_x( ) { return x_pos; }
	  int Get_y( ) { return y_pos; }
	  int operator!=( POINT p ) { return ( x_pos != p.x_pos) || ( y_pos != p.y_pos); }
	  int operator==( POINT p ) { return ( x_pos == p.x_pos) && ( y_pos == p.y_pos); }
};

	  // The line class : a line of the from ax + by = c
class LINE
{
	  long int a,b,c;

   public:

		  LINE( ) { a = b = c = 0; }
		  LINE( POINT p, POINT q ) { Make( p,q ); }

		  void Make( POINT p, POINT q );
		  int Evaluate( POINT p );
};

  	 /************ Function definitions ***********/
  		  
  		  // Show a point on screen
void POINT::Mark( void )
{
	if( IsOnScreen( ))
		fillellipse( x_pos, y_pos, 2,2 );
}

		// Draws a line on screen
void POINT::DrawLine( POINT p )
{
	if( IsOnScreen( ) && p.IsOnScreen(  ))
		line( x_pos, y_pos, p.x_pos, p.y_pos );
}

		// Creates the line from two given points
void LINE::Make( POINT p, POINT q )
{
	 a = q.Get_y( ) - p.Get_y( );
	 b = - (q.Get_x( ) - p.Get_x( ));

	 c = ( (long)p.Get_x( ) * ( q.Get_y( ) - p.Get_y( ) )) - (long)p.Get_y( ) * ( q.Get_x( ) - p.Get_x( ));
}


 /* Evaluates the equation of the line at the given point and returns
				1 if aX + bY > c
				0 if aX + bY = c
				-1 if aX+bY < c
*/
int LINE::Evaluate( POINT p )
{
	 long int val = a*p.Get_x( ) + b*p.Get_y( );

	 if( val > c )
	     return 1;
	 else if( val == c )
	      return 0;
	 else
	     return -1;
}

		 // Initialize the graphics system and set the maximum x any coordinates
void InitGraphSystem( const char *bgi_path )
{
	int graphDriver = DETECT, graphMode, result;

	initgraph( &graphDriver, &graphMode,bgi_path );
	result = graphresult( );

	if( result != grOk )
	{
		cout<<"Failed to initialize graphics system.\nError: "
		    <<grapherrormsg( result )
			<<"\nAborting...";
		getch( );
		exit(1);
	}

	Max_X = getmaxx( );
	Max_Y = getmaxy( );
}

	// A printf-like function to send output in graphics mode
void gprintf( int xloc, int yloc, char *fmt, ... )
{
  va_list  argptr;
  char str[140];

  va_start( argptr, fmt );

  vsprintf( str, fmt, argptr );
  outtextxy( xloc, yloc, str );

  va_end( argptr );
}

		  // Prints a message on status line
void StatusLine( char *msg )
{
	 setfillstyle( SOLID_FILL, LIGHTGRAY );
	 setcolor( BLACK );
	 bar( 0, Max_Y - 10, Max_X, Max_Y );
	 gprintf( 10, Max_Y - 7, msg );
	 setfillstyle( SOLID_FILL, WHITE );
	 setcolor( BLACK );
}

		  /*********** Main  ***********/
int main( )
{
	int x,y,btn = 0, n = 0, i, prev = 0, min_y = -1, j, side, prev_side;
	POINT points[50], p, init_point, q;
	LINE l;

	InitGraphSystem( BGI_PATH );
	
	if( ! InitMouse( ))
	{
		cout<<"\nFatal Error: Cannot init mouse.\nAborting...";
		getch( );
		closegraph( );
		return 1;
	}
	
	ShowMouse( );
	RestrictMouse( 2, 2, Max_Y - 10, Max_X - 2 );

	StatusLine( "Left-click to add points. Right-click when done." );
	
	while( btn != RIGHT_CLICK )
	{
		GetMouseStatus( &x, &y, &btn );

		if( btn == LEFT_CLICK )
		{
			if( prev == 1 )
				continue;
			points[n].Set( x, y );

			if( min_y == -1 )
			{
				min_y = y;
				init_point = points[n];
			}
			else
			{
				if( y < min_y )
				{
					min_y = y;
					init_point = points[n];
				}
			}

			HideMouse( );
			points[n].Mark( );
			n++;
			ShowMouse( );
			prev = btn;
		}
		else
		       prev = btn;
	}

	p = q = init_point;
	setcolor( CYAN );
	setfillstyle( SOLID_FILL, CYAN );
	
	              // This is the main loop
	do
	{
			// Form all possible lines
		for( i = 0; i < n ; i++ )
		{
			 if( points[i] == p || points[i] == q )
			     continue;

			 l.Make( p, points[i] );

			 prev_side = 0;
				   // Check if all the points are on the same side of the line
			 for( j = 0; j < n ; j++ )
			 {
				 if( points[j] == points[i] || points[j] == p )
					continue;
				 side = l.Evaluate( points[j] );
				 if( prev_side == 0 )
				      prev_side = side;
				 else if( ( prev_side == 1 && side == -1 )
					|| ( prev_side == -1 && side == 1 )) // Found two points on
									     // opposite sides
							  break;
			 }

			 if( j == n && side == prev_side )           // Loop terminated normally
			 {
				 p.DrawLine( points[i] );
				 p.Mark( );
				 points[i].Mark( );
				 q = p;
				 p = points[i];          // The new point becomes the starting point
				 break;
			 }
		}
	}while( p != init_point );

	StatusLine( "Done... press any key to exit" );
	getch( );
	closegraph( );
	return 0;

}

	/****** Mouse-handling functions *******/

		// Initialize mouse driver
int InitMouse( void )
{
	union REGS in, out;
	in.x.ax = 0;
	int86( 0x33, &in, &out );
	return out.x.ax;
}

		// Show mouse pointer
int ShowMouse( void )
{
	union REGS in, out;
	in.x.ax = 1;
	int86( 0x33, &in, &out );
	return out.x.ax;
}

int HideMouse( void )
{
	union REGS in, out;
	in.x.ax = 2;
	int86( 0x33, &in, &out );
	return out.x.ax;
}

	// Get mouse position and button-click
int GetMouseStatus( int *x_pos, int *y_pos, int *btn )
{
	union REGS in, out;
	in.x.ax = 3;
	int86( 0x33, &in, &out );
	*x_pos = out.x.cx;
	*y_pos = out.x.dx;
	*btn = out.x.bx;

	return out.x.ax;
}

	// Restrict mouse between given points
int RestrictMouse( int x1, int y1, int x2, int y2 )
{
	union REGS in, out;
	in.x.ax = 7;
	in.x.cx = x1;
	in.x.dx = x2;
	int86( 0x33, &in, &out );

	in.x.ax = 8;
	in.x.cx = y1;
	in.x.dx = y2;
	int86( 0x33, &in, &out );

	return out.x.ax;
}