_segment.c

数据类型和算法库LEDA 数据类型和算法库LEDA

/*******************************************************************************
+
+  LEDA  3.0
+
+
+  _segment.c
+
+
+  Copyright (c) 1992  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 6600 Saarbruecken, FRG     
+  All rights reserved.
+ 
*******************************************************************************/



#include <LEDA/line.h>
#include <math.h>
#include <ctype.h>

static const double eps = 1e-10;


//------------------------------------------------------------------------------
// segments 
//------------------------------------------------------------------------------

segment_rep::segment_rep()  { count = 1; }

segment_rep::segment_rep(point p, point q) 
{ start = p;
  end   = q;
  count = 1; 
}

segment::segment()                 { PTR = new segment_rep; }
segment::segment(point x, point y) { PTR = new segment_rep(x,y); }
segment::segment(double x1, double y1, double x2, double y2) 
                          { PTR = new segment_rep(point(x1,y1), point(x2,y2)); }

segment::segment(point p, double alpha, double length)
{ point q = p.translate(alpha,length);
  PTR  = new segment_rep(p,q); 
 }
  

segment segment::translate(double alpha, double d)
{ point p = ptr()->start.translate(alpha,d);
  point q = ptr()->end.translate(alpha,d);
  return segment(p,q);
 }

segment segment::translate(const vector& v)
{ point p = ptr()->start.translate(v);
  point q = ptr()->end.translate(v);
  return segment(p,q);
 }


ostream& operator<<(ostream& out, const segment& s) 
{ out << "[" << s.start() << "===" << s.end() << "]"; 
  return out;
 } 

/*
istream& operator>>(istream& in, segment& s) 
{ double x1,x2,y1,y2; 
  in >> x1 >> y1 >> x2 >> y2; 
  s = segment(x1,y1,x2,y2); 
  return in; 
 } 
*/

istream& operator>>(istream& in, segment& s) 
{ // syntax: {[} p {===} q {]}

  point p,q; 
  char c;

  do in.get(c); while (isspace(c));
  if (c != '[') in.putback(c);

  in >> p;

  do in.get(c); while (isspace(c));
  while (c== '=') in.get(c);
  while (isspace(c)) in.get(c);
  in.putback(c);

  in >> q; 

  do in.get(c); while (c == ' ');
  if (c != ']') in.putback(c);

  s = segment(p,q); 
  return in; 

 } 



bool  segment::vertical()            
{ return ptr()->start.ptr()->x == ptr()->end.ptr()->x; }

bool  segment::horizontal()            
{ return ptr()->start.ptr()->y == ptr()->end.ptr()->y; }
 
double  segment::length()            
{ return ptr()->start.distance(ptr()->end); }

double segment::angle()
{  return -angle(segment(0,0,1,0)); }


double segment::angle(segment s)
{
  double cosfi,fi,norm;
  
  double dx  = ptr()->end.ptr()->x - ptr()->start.ptr()->x; 
  double dy  = ptr()->end.ptr()->y - ptr()->start.ptr()->y; 

  double dxs = s.ptr()->end.ptr()->x - s.ptr()->start.ptr()->x; 
  double dys = s.ptr()->end.ptr()->y - s.ptr()->start.ptr()->y; 
  
  cosfi=dx*dxs+dy*dys;
  
  norm=(dx*dx+dy*dy)*(dxs*dxs+dys*dys);

  cosfi /= sqrt( norm );

  if (cosfi >=  1.0 ) return 0;
  if (cosfi <= -1.0 ) return M_PI;
  
  fi=acos(cosfi);

  if (dx*dys-dy*dxs>0) return fi;

  return -fi;
}
  
double segment::distance(segment s)
{ if (angle(s)!=0) return 0;
  return distance(s.ptr()->start);
 }

double  segment::distance()          
{ return distance(point(0,0)); }

double segment::distance(point p)
{ segment s(ptr()->start,p);
  double l = s.length();
  if (l==0) return 0;
  else return l*sin(angle(s));
 }

double  segment::slope()  
{ double dx = (ptr()->end.ptr()->x - ptr()->start.ptr()->x); 
  if (dx==0) 
  { cout << *this << "\n";
    cout.flush();
    error_handler(1,"segment::slope() : vertical segment");
   }
  return   (ptr()->end.ptr()->y - ptr()->start.ptr()->y)/dx; 
}

double  segment::y_proj(double x) 
{ return  ptr()->start.ptr()->y - ((ptr()->start.ptr()->x - x)*slope()); }

double  segment::x_proj(double y) 
{ if (vertical())  return  ptr()->start.ptr()->x;
  return  ptr()->start.ptr()->x - ((ptr()->start.ptr()->y - y)/slope()); }


double  segment::y_abs()  { return y_proj(0); }


bool segment::intersection(segment s, point& inter)
{ line l(s);
  if (l.intersection(*this,inter))
  { double d1  = inter.distance(s.ptr()->start);
    double d2  = inter.distance(s.ptr()->end);
    double l   = s.length()+eps;
    if ( d1 < l && d2 < l) return true;
   }
   return false;
}

segment segment::rotate(double alpha)
{  double  l = length();
   point p = start();
   double beta = alpha + angle();
   return segment(p,beta,l);
}

segment segment::rotate(point origin, double alpha)
{  point p = start().rotate(origin,alpha);
   point q = end().rotate(origin,alpha);
   return segment(p,q);
}