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 around all the pins and allow it to snap )
The program uses the TurboC++ graphics library and TurboC++ functions.

``````/*
* 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;
}``````
3
Contributors
3
Replies
4
Views
11 Years
Discussion Span
Last Post by manutd
``````#include <iostream.h>
#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>``````

O-o-outdated. It's:

``````#include <iostream>
#include <cstdio>
#include <cstdarg>
#include <cstdlib>``````

...and not to forget the using namespace std; which has to be placed after the includes so that we can start using the constructs under the standard namespace without prefixing each of them with std::

And because this is C++, #defines should be made const. And he's using C style strings, not std::strings.

Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.