// ------------------------------------------------------------------------
  // This program is complementary material for the book:
  //
  // Frank Nielsen
  //
  // Visual Computing: Geometry, Graphics, and Vision
  //
  // ISBN: 1-58450-427-7
  //
  // Charles River Media, Inc.
  //
  //
  // All programs are available at www.charlesriver.com/visualcomputing/
  //
  // You may use this program for ACADEMIC and PERSONAL purposes ONLY. 
  //
  //
  // The use of this program in a commercial product requires EXPLICITLY
  // written permission from the author. The author is NOT responsible or 
  // liable for damage or loss that may be caused by the use of this program. 
  //
  // Copyright (c) 2005. Frank Nielsen. All rights reserved.
  // ------------------------------------------------------------------------
   
  // ------------------------------------------------------------------------
  // File: segmentintersection-primitive.cpp
  // 
  // Description: Define a predicate that report whether two line segments 
  // intersect or not using Orient2D orientation predicates of triples of points.
  // ------------------------------------------------------------------------
  
  include <stdafx.h>
  include <windows.h>
  include <GL/gl.h>
  include <GL/glut.h>
  
  using namespace std;
  
  // Orientation predicate results:
  define CCW 1
  define ON 0
  define CW -1
  
  define W 800
  define H 800
  
  // Random number from 0 to 1
  inline double drand(){return rand()/(double)RAND_MAX;}
  
  class Point2D{
  public: double x,y;
  
                  friend ostream &operator<<(ostream & o, const Point2D & p)
                  {
                          o<<"("<<p.x<<"."<<p.y<<")"; return o;
                  }
  };
  
  // Orientation test: 2x2 determinant sign
  define ERR 1.0e-6
  
  double vOrient2D( const Point2D& p, const Point2D& q, const Point2D& r)
    {
            return ((q.x-p.x)*(r.y-p.y) - (r.x-p.x)*(q.y-p.y));
    }
  
  int Orient2D( const Point2D& p, const Point2D& q, const Point2D& r)
    {
            if ((q.x-p.x)*(r.y-p.y) > (r.x-p.x)*(q.y-p.y)+ERR) return CCW;
             if ((q.x-p.x)*(r.y-p.y) < (r.x-p.x)*(q.y-p.y)-ERR) return CW;
  
     return ON;
    }
  
  class Segment2D{
  public: Point2D a,b;
  
                  Segment2D::RandomDraw()
                  {
                  a.x=drand();a.y=drand();
                  b.x=drand();b.y=drand();
  
                  // swap extremities
                  if (a.x>b.x) swap(a,b);
                  }
  
                  friend ostream &operator<<(ostream & o, const Segment2D & s)
                  {
                  o<<"Segment ["<<s.a<<","<<s.b<<"]"; return o;
                  }
                  
                  bool Intersect(Segment2D s)
                  {
  
                  if (Orient2D(a,b,s.a)==Orient2D(a,b,s.b)) return false;
                  if (Orient2D(s.a,s.b,a)==Orient2D(s.a,s.b,b)) return false;
                  return true;
                  }
  
                  // Assume a.x<s.a.x
                  // Only two orientation predicate evaluations
                  bool IntersectOptimize(Segment2D s)
                  {
                  // can be separated by a vertical line
                  if (b.x<s.a.x) return false; 
  
                  if (s.b.x<b.x)
                  {
                  if (Orient2D(a,b,s.a)!=Orient2D(a,b,s.b)) return true;
                  else return false;
                  }
                  else
                  {
                  if (Orient2D(a,b,s.a)==Orient2D(s.a,s.b,b)) return true;
                  else return false;
                  }
                  }
  
                  double orient2D( const Point2D& p, const Point2D& q, const Point2D& r)
                  {return ((q.x-p.x)*(r.y-p.y) - (r.x-p.x)*(q.y-p.y));}
  
                  Point2D ReportPoint(Segment2D s)
                  {Point2D result;double lambda;
  
                  lambda=orient2D(a,s.a,s.b)/(orient2D(a,b,s.b)-orient2D(a,b,s.a));
  
                  result.x=a.x+(b.x-a.x)*lambda;
                  result.y=a.y+(b.y-a.y)*lambda;
  
                  return result;
                  }
  };
  
  Segment2D s1,s2;
  
  void disp( void ) 
  {
  char buffer[256];
  Point2D p;
  
  glClearColor(1,1,1,1);
  glClear(GL_COLOR_BUFFER_BIT);
  
  if (s1.Intersect(s2)) 
  {
          glColor3f(1,0,0); 
  p=s1.ReportPoint(s2);
  glPointSize(5.0);
  glBegin(GL_POINTS);
  glVertex2f(p.x,p.y);
  glEnd();
  cout<<p<<endl;
  }
          else
          glColor3f(0,1,0);
  
  glPushMatrix();
    glLoadIdentity();
    glOrtho (0.0, 1, 0.0, 1, -1.0, 1.0);
  glMatrixMode(GL_MODELVIEW);
    glPushMatrix();
    glLoadIdentity();
  
          glBegin(GL_LINES); 
          glVertex2f(s1.a.x,s1.a.y);
          glVertex2f(s1.b.x,s1.b.y);
          glVertex2f(s2.a.x,s2.a.y);
          glVertex2f(s2.b.x,s2.b.y);
          glEnd();
  
    glMatrixMode(GL_PROJECTION);
    glPushMatrix();
    glLoadIdentity();
    glOrtho (0.0, W, 0.0, H, -1.0, 1.0);
    glMatrixMode(GL_MODELVIEW);
    glPushMatrix();
    glLoadIdentity();
  
    glColor3f (0, 0, 0);
  
    // First segment label
    glRasterPos2f(W*s1.a.x,H*s1.a.y);
     glutBitmapCharacter(GLUT_BITMAP_TIMES_ROMAN_24, 'a');
     glutBitmapCharacter(GLUT_BITMAP_TIMES_ROMAN_24, '1');
  
    glRasterPos2f(W*s1.b.x,H*s1.b.y);
     glutBitmapCharacter(GLUT_BITMAP_TIMES_ROMAN_24, 'b');
     glutBitmapCharacter(GLUT_BITMAP_TIMES_ROMAN_24, '1');
  
     // Second segment label
     glRasterPos2f(W*s2.a.x,H*s2.a.y);
     glutBitmapCharacter(GLUT_BITMAP_TIMES_ROMAN_24, 'a');
     glutBitmapCharacter(GLUT_BITMAP_TIMES_ROMAN_24, '2');
  
     glRasterPos2f(W*s2.b.x,H*s2.b.y);
     glutBitmapCharacter(GLUT_BITMAP_TIMES_ROMAN_24, 'b');
     glutBitmapCharacter(GLUT_BITMAP_TIMES_ROMAN_24, '2');
  
     glRasterPos2f(50,30);
     sprintf(buffer,"Press any key for another point sequence sample.");
     for(int i=0;buffer[i]!=0;i++)
     glutBitmapCharacter(GLUT_BITMAP_TIMES_ROMAN_24, buffer[i]);
  
    glMatrixMode(GL_PROJECTION);
    glPopMatrix();
    glMatrixMode(GL_MODELVIEW);
    glPopMatrix();      
  
    glFlush();
  }
  
  void key(unsigned char key , int x , int y) 
  {
  s1.RandomDraw();
  s2.RandomDraw();
  if (s1.a.x>s2.a.x) swap(s1,s2);
  
  cout<<s1<<endl;
  cout<<s2<<endl;
  glutPostRedisplay(); 
  }
  
  int main(int argc , char ** argv) 
  {
  
          
  cout<<"Visual Computing: Geometry, Graphics, and Vision (ISBN:1-58450-427-7)"<<endl;
  cout<<"Demo program\n\n"<<endl;
  
          glutInit(&argc , argv);
          glutInitWindowPosition(50,50);
          glutInitWindowSize(W,H);
          glutInitDisplayMode(GLUT_SINGLE | GLUT_RGBA);
  
          glutCreateWindow("Line segment detection");
          glutDisplayFunc(disp);
  
          srand(2005);
          cout<<"Basic primitive for checking whether two segments intersect or not."<<endl;
  
          glMatrixMode(GL_PROJECTION);
          glLoadIdentity();
          glOrtho(0,1,0,1,-1,1);
          glMatrixMode(GL_MODELVIEW);
          s1.RandomDraw();
          s2.RandomDraw();
  
          glutKeyboardFunc(key);
          glutMainLoop();
  }