Convex Hull

19 Years Ago vicky_dev 0 591 Views

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

Dani AI

Generated 10 Months Ago

’s program is a straightforward implementation of the gift‑wrapping (Jarvis March) approach: it walks the hull, picking the next point so every other point lies on one side of the directed line. That’s simple and very visual, but it’s O(n·h) (n = points, h = hull size) and the Turbo C++/BGI + DOS mouse bits make the code hard to reuse on modern systems.

Modernization notes (short, practical):

Replace the Turbo/BGI graphics and the INT‑33 mouse calls with either simple stdin input (for algorithm work) or a cross‑platform graphics library (SDL/SFML/GLFW) for visualization.
Use standard containers: std::vector, std::sort, std::unique. Prefer constexpr/const over #define. ’s hint about modern headers is on point; ’s note on namespaces is useful — avoid a global using namespace std; in headers, prefer explicit std:: or local using in .cpp files.

A compact, robust alternative: Andrew’s monotone‑chain (O(n log n)). Key parts below — uses 64‑bit integers for the cross product to avoid overflow and removes duplicates first.

struct P { long long x,y; };
long long cross(const P &a,const P &b,const P &c){
  return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}
// sort pts, unique them, then build lower and upper hulls with <= 0 to discard collinear interior points

Quick troubleshooting checklist:

Handle n<3 as a special case.
Remove exact duplicate points after sorting.
To include all collinear boundary points, use < 0 in the hull loop; to exclude them use <= 0.
For very large coordinates, consider using __int128 for the cross product.
For performance on large inputs prefer monotone chain (or Graham scan) over Jarvis March.

These changes keep the algorithm intact while making the code portable, safer, and faster for larger point sets.

manutd 2 Junior Poster

19 Years Ago

#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>

~s.o.s~ 2,560 Failure as a human

19 Years Ago

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

manutd 2 Junior Poster

19 Years Ago

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

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.