Skip to content

Instantly share code, notes, and snippets.

@superwills
Last active September 7, 2019 15:15
Show Gist options
  • Save superwills/5808630 to your computer and use it in GitHub Desktop.
Save superwills/5808630 to your computer and use it in GitHub Desktop.
Pt In Poly simple algorithm. Works for convex & concave polygons.
#include <stdlib.h> // MUST BE BEFORE GLUT ON WINDOWS
#ifdef _WIN32
#include <gl/glut.h>
#else
#include <GLUT/glut.h>
#include <OpenGL/gl.h>
#include <OpenGL/glu.h>
#endif
#include <vector>
using namespace std;
inline float& clamp( float& x, float minVal, float maxVal ) {
if( x < minVal ) x = minVal ;
else if( x > maxVal ) x = maxVal ;
return x ;
}
struct Vector2f
{
float x,y;
Vector2f():x(0.f),y(0.f){}
Vector2f( float ix, float iy ):x(ix),y(iy){}
//Vector2f( const CGPoint& o ):x( o. { }
Vector2f( float iv ):x(iv),y(iv){}
} ;
union Vector4f
{
struct{ float x,y,z,w ; } ;
struct{ float r,g,b,a ; } ;
float elts[4];
Vector4f():x(0.f),y(0.f),z(0.f),w(1.f){}
Vector4f( float ix, float iy, float iz ):x(ix),y(iy),z(iz),w(1.f){}
Vector4f( float ix, float iy, float iz, float iw ):x(ix),y(iy),z(iz),w(iw){}
Vector4f( float iv ):x(iv),y(iv),z(iv),w(iv){}
} ;
Vector4f Red( 1,0,0,1 ), DarkRed( 0.35,0,0,1 ),
Green( 0,1,0,1 ), DarkGreen( 0,0.35,0,1 ),
Blue( 0,0,1,1 ), DarkBlue( 0,0,0.35,1 ),
White(1,1,1,1), Gray(0.5,0.5,0.65,1), DarkGray(0.21,0.21,0.21,1), Black(0,0,0,1),
Magenta(1,0,1,1), Teal(0,1,1,1), Yellow(1,1,0,1),
TWhite(1,1,1,0), TBlack(0,0,0,0)
;
inline bool GL_OK()
{
GLenum err = glGetError() ;
if( err != GL_NO_ERROR )
printf( "GLERROR %d\n", err ) ;
return err == GL_NO_ERROR ;
}
static float w=512.f,h=512.f,ptSize=1.f ;
static Vector2f mousePos ;
struct Poly
{
vector<Vector2f> pts ;
vector<Vector4f> colors ;
void setColor( const Vector4f& color )
{
for( int i = 0 ; i < colors.size() ; i++ )
colors[i] = color ;
}
void draw()
{
if( colors.size() != pts.size() ) {
printf( "ERROR colors.size( %d ) != pts.size( %d )\n", colors.size(), pts.size() ) ;
colors.resize( pts.size() ) ; // shouldn't happen, but could.
}
//if( !pts.size() ) {
// puts( "ERROR NO PTS INSIDE POLYGON" ) ;
// return ;
//}
else if( pts.size() == 1 )
glBegin( GL_POINTS ) ;
else if( pts.size() == 2 )
glBegin( GL_LINES ) ;
else
glBegin( GL_POLYGON ) ;
for( int i = 0 ; i < pts.size() ; i++ )
{
glColor4fv( &colors[i].x ) ;
glVertex2fv( &pts[i].x ) ;
}
glEnd() ;
}
void addPt( const Vector2f &pt, const Vector4f &color )
{
pts.push_back( pt ) ;
colors.push_back( color ) ;
}
int pnpoly( const Vector2f& test )
{
int i, j, c = 0;
for (i = 0, j = pts.size()-1; i < pts.size(); j = i++) {
if ( ((pts[i].y>test.y) != (pts[j].y>test.y)) &&
(test.x < (pts[j].x-pts[i].x) * (test.y-pts[i].y) / (pts[j].y-pts[i].y) + pts[i].x) )
c = !c;
}
return c;
}
} ;
vector<Poly*> polys;
static Poly* cp = 0;
void addPt( const Vector2f& pt )
{
cp->addPt( pt, White ) ;
}
void draw()
{
glEnable( GL_DEPTH_TEST ) ;
glClear( GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT ) ;
glViewport( 0, 0, w, h ) ;
glMatrixMode( GL_PROJECTION ) ;
glLoadIdentity();
glOrtho( 0, w, 0, h, 10, -10 ) ;
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
for( Poly * p : polys ) p->draw() ;
glBegin( GL_POINTS ) ;
glColor4f( 1,1,0,1 ) ;
glVertex2fv( &mousePos.x ) ;
glEnd() ;
//TEXT
glDisable( GL_DEPTH_TEST ) ;
glColor4f(1.0f, 1.0f, 1.0f, 1.0f);
glRasterPos2f( 20, h-20 ) ;
char buf[300];
if( !polys.size() )
sprintf( buf, "Left click: add pt." ) ;
else
sprintf( buf, "Move mouse to poly test. Keys: new (p)oly, (c)lear all polys." ) ;
const char * p = buf ;
do glutBitmapCharacter( GLUT_BITMAP_HELVETICA_18, *p ); while( *(++p) ) ;
glutSwapBuffers();
}
// Called every time a window is resized to resize the projection matrix
void resize( int newWidth, int newHeight )
{
w = newWidth ;
h = newHeight ;
}
void newPoly()
{
polys.push_back( new Poly() ) ;
cp = polys.back() ;
}
void mouse( int button, int up, int x, int y )
{
if( !cp ) newPoly() ;
y = h-y;
if( !up )
addPt( Vector2f( x, y ) ) ;
}
void mouseMotion( int x, int y )
{
Vector2f pt( x, h-y ) ;
mousePos = pt ;
for( int i = 0 ; i < polys.size() ; i++ )
{
if( polys[i]->pnpoly( pt ) )
{
polys[i]->setColor( Red ) ;
}
else
{
polys[i]->setColor( White ) ;
}
}
}
void keyboard( unsigned char key, int x, int y )
{
static float lineWidth = 1.f ;
switch( key )
{
case '2':
{
int pMode[2];
glGetIntegerv( GL_POLYGON_MODE, pMode ) ;
if( pMode[0] == GL_FILL ) glPolygonMode( GL_FRONT_AND_BACK, GL_LINE ) ;
else glPolygonMode( GL_FRONT_AND_BACK, GL_FILL ) ;
}
break ;
case '-':
lineWidth--;
::clamp( lineWidth, 1.f, 16.f ) ;
glLineWidth( lineWidth ) ;
break;
case '+':
case '=':
lineWidth++;
::clamp( lineWidth, 1.f, 16.f ) ;
glLineWidth( lineWidth ) ;
break;
case 'c':
puts( "Clear" ) ;
for( Poly * p : polys ) delete p ;
cp=0;
polys.clear() ;
break ;
case 'p':
newPoly() ;
break ;
case 27:
exit(0);
break;
default:
break;
}
}
void init()
{
glClearColor( 0.1, 0.1, 0.1, 0.1 ) ;
glEnable( GL_COLOR_MATERIAL ) ;
ptSize=4.f;
glPointSize( ptSize ) ;
glLineWidth( 2.f ) ;
glPolygonMode( GL_FRONT_AND_BACK, GL_LINE ) ;
glEnable( GL_BLEND ) ;
glBlendFunc( GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA ) ;
}
int main( int argc, char **argv )
{
glutInit( &argc, argv ) ; // Initializes glut
glutInitDisplayMode( GLUT_DOUBLE | GLUT_DEPTH | GLUT_RGBA ) ;
glutInitWindowSize( w, h ) ;
glutInitWindowPosition( 0, 0 ) ;
glutCreateWindow( "Point in poly" ) ;
glutReshapeFunc( resize ) ;
glutDisplayFunc( draw ) ;
glutIdleFunc( draw ) ;
glutMouseFunc( mouse ) ;
glutPassiveMotionFunc( mouseMotion ) ;
glutKeyboardFunc( keyboard ) ;
init();
glutMainLoop();
return 0;
}
@superwills
Copy link
Author

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment