// ------------------------------------------------------------------------
  // 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: ShamosHoey.cpp
  // 
  // Description: Detect whether a set of line segments intersect or not
  // Implement in a STL fashion a simple but optimal algorithm 
  // to detect whether there exists an intersection point among a set of n segments in O(n log n) time
  //
  // Michael I. Shamos and Dan Hoey. 
  // "Geometric intersection problems" (FOCS 1976)
  // In 17th Annual Symposium on Foundations of Computer Science
  // pages 208-215, Houston, Texas, 25-27 October 1976. IEEE. 
  // ------------------------------------------------------------------------
  
  include <stdafx.h>
  
  include <vector>
  include <algorithm>
  include <windows.h>
  include <GL/gl.h>
  include <GL/glut.h>
  
  define W 900
  define H 900
  
  using namespace std;
  
  enum type {LEFT, RIGHT};
  
  class point {
  public:
  double x,y;
  int n;
  type endpoint;
  
  // Lexicographic order on the x-coordinate
  bool operator <  ( const point & rhs)
  {return (x<rhs.x);}
  
  bool operator >  (const point & rhs)
  {return (x>rhs.x);}
  };
  
  class segment {
  public:
  point A,B;
  };
  
  class Yline {
  public:
  static double x;
  
  double a,b; // equation of nonvertical line y=ax+b
  int n;
  
  void setX(double xx) {x=xx;}
  
  bool operator <  ( const Yline &  rhs)
  {
  //        cout <<"\t\tGeneric dictionary (inferior): "<<x<<endl;
          return (a*x+b<rhs.a*x+rhs.b);
  }
  
  bool operator >  ( const Yline &  rhs)
  {
  //        cout <<"\t\tGeneric dictionary (inferior): "<<x<<endl;
          return (a*x+b>rhs.a*x+rhs.b);
  }
  
  bool operator ==  ( const Yline &  rhs)
  {
  //        cout <<"\t\tGeneric dictionary (inferior): "<<x<<endl;
          return (a*x+b == rhs.a*x+rhs.b);}
  
  };
  
  double Yline::x;
  
  bool intersection=false;
  
  // Orientation test: 2x2 determinant sign
  define ERR 1.0e-6
  define CCW 1
  define ON 0
  define CW -1
  
  int Orient2D( const point& p, const point& q, const point& 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;
    }
  
    bool SegmentIntersect(segment s1, segment s2)
                  {
  
                  if (Orient2D(s1.A,s1.B,s2.A)==Orient2D(s1.A,s1.B,s2.B)) return false;
                  if (Orient2D(s2.A,s2.B,s1.A)==Orient2D(s2.A,s2.B,s1.B)) return false;
                  intersection=true;
                  return true;
                  }
  
  // Return a random number in [0,1]
  inline double randd()
          {
                  return (double)rand()/(double)RAND_MAX;
          }
  
  // Line equation + segment number
  void SegmentToYevent(segment S, int nn, Yline& eventp)
  {
          eventp.n=nn;
          eventp.a=(S.B.y-S.A.y)/(S.B.x-S.A.x); //slope
          eventp.b=S.A.y-eventp.a*S.A.x; // y=ax+b
  }
  
  int Intersect()
  {
  cout << "Some pair of segments intersect"<<endl;
  return 1;
  }