intersection_objects_d.h

很多二维 三维几何计算算法 C++ 类库

  // now s is not degenerate
  typedef typename R::Line_line_intersection_d Int_obj_type;
  Int_obj_type Intersect;
  FT l1,l2; 
  typename Int_obj_type::Intersection_result res = 
    Intersect(_r.point(0),_r.point(1),
              _s.point(0),_s.point(1),_ip,l1,l2);

  if (res == Int_obj_type::LINE)   
  {
    Point_d p1 = _s.point(0), p2 = _s.point(1);
    if ( _s.direction() != _r.direction() ) std::swap(p1,p2);
    // now order p2 after p1 on r underlying line 
    typename R::Position_on_line_d pos;
    pos(p1, _r.point(0),_r.point(1), l1);
    pos(p2, _r.point(0),_r.point(1), l2);
    if ( l1 < FT(0) ) p1 = _r.point(0);
    if ( l2 < FT(0) ) { return _result = NO_INTERSECTION; }
    if ( p1 == p2 ) { _ip = p1; return _result = NO_INTERSECTION; }
    _is = Segment_d(p1,p2);
    return _result = SEGMENT;
  }


  if (res == Int_obj_type::POINT && 
      FT(0) <= l1 && FT(0) <= l2 && l2 <= FT(1)) 
  { return _result = POINT; }
  return _result = NO_INTERSECTION; 
  // now not parallel
}

template <class R>
bool
Ray_d_Segment_d_pair<R>::intersection(Point_d& p)
{ if (!_known) intersection_type();
  if (_result != POINT) return false;
  p = _ip; return true;
}

template <class R>
bool
Ray_d_Segment_d_pair<R>::intersection(Segment_d& s)
{ if (!_known) intersection_type();
  if (_result != SEGMENT) return false;
  s = _is; return true;
}


template <class R>
class Segment_d_Segment_d_pair {
public:
  enum Intersection_result { NO_INTERSECTION, POINT, SEGMENT };
  typedef typename R::FT FT;
  typedef typename R::Point_d Point_d;
  typedef typename R::Segment_d Segment_d;

protected:
  Segment_d _s1,_s2;
  bool _known;
  Intersection_result _result;
  Point_d _ip; Segment_d _is;  
public:
  Segment_d_Segment_d_pair() : _known(false) {}
  Segment_d_Segment_d_pair(const Segment_d& s1, const Segment_d& s2)
    : _s1(s1), _s2(s2), _known(false) {}
  Intersection_result intersection_type();
  bool intersection(Point_d& result);
  bool intersection(Segment_d& result);
};

template <class R>
typename Segment_d_Segment_d_pair<R>::Intersection_result
Segment_d_Segment_d_pair<R>::intersection_type()
{ 
  if (_known) return _result;
  _known = true;

  if ( _s1.is_degenerate() ) {
    if ( _s2.is_degenerate() ) {
      if ( _s1.point(0) == _s2.point(0) ) 
      { _ip = _s1.point(0); return _result = POINT; }
      else { return _result = NO_INTERSECTION; }
    } else {
      if ( _s2.has_on(_s1.point(0)) ) 
      { _ip = _s1.point(0); return _result = POINT; }
      else { return _result = NO_INTERSECTION; }
    }
  }
  if ( _s2.is_degenerate() ) { 
    CGAL_assertion( !_s1.is_degenerate() );
    if ( _s1.has_on(_s2.point(0)) ) 
    { _ip = _s2.point(0); return _result = POINT; }
    else { return _result = NO_INTERSECTION; }
  }  

  // now s1,s2 not degenerate
  typedef typename R::Line_line_intersection_d Int_obj_type;
  Int_obj_type Intersect;
  FT l1,l2; 
  typename Int_obj_type::Intersection_result res = 
    Intersect(_s1.point(0),_s1.point(1),
              _s2.point(0),_s2.point(1),_ip,l1,l2);

  if (res == Int_obj_type::LINE)   
  { Point_d p1 = (_s1.min)(), p2 = (_s1.max)();
    Point_d q1 = (_s2.min)(), q2 = (_s2.max)();
    Point_d s,t;
    // now order the for points along the line
    typename R::Position_on_line_d pos;
    pos(p1, q1, q2, l1); pos(p2, q1, q2, l2);
    if ( l1 < FT(0) ) {
      if ( l2 < FT(0) ) { return _result = NO_INTERSECTION; }
      else { s = q1; }
    } else { s = p1; } // l1 >= 0
    if ( l2 > FT(1) ) {
      if ( l1 > FT(1) ) { return _result = NO_INTERSECTION; }
      else { t = q2; }
    } else { t = p2; } // l2 <= 1
    if ( s == t ) { _ip = s; return _result = POINT; }
    _is = Segment_d(s,t); return _result = SEGMENT;
  }


  if ( res == Int_obj_type::POINT && 
       FT(0) <= l1 && l1 <= FT(1) && 
       FT(0) <= l2 && l2 <= FT(1) ) 
  { return _result = POINT; }
  return _result = NO_INTERSECTION; 
}

template <class R>
bool
Segment_d_Segment_d_pair<R>::intersection(Point_d& p)
{ if (!_known) intersection_type();
  if (_result != POINT) return false;
  p = _ip; return true;
}

template <class R>
bool
Segment_d_Segment_d_pair<R>::intersection(Segment_d& s)
{ if (!_known) intersection_type();
  if (_result != SEGMENT) return false;
  s = _is; return true;
}


template <class R>
class Line_d_Hyperplane_d_pair {
public:
  enum Intersection_result {NO_INTERSECTION, POINT, LINE};
  typedef typename R::Point_d      Point_d;
  typedef typename R::Line_d       Line_d;
  typedef typename R::Hyperplane_d Hyperplane_d;
  typedef typename R::FT           FT;

protected:
  Line_d _l; Hyperplane_d _h;
  bool _known;
  Intersection_result _result;
  Point_d _ip;
public:
  Line_d_Hyperplane_d_pair() : _known(false) {}
  Line_d_Hyperplane_d_pair(const Line_d& l, const Hyperplane_d& h) 
   : _l(l), _h(h), _known(false) {}

  Intersection_result intersection_type();
  bool intersection(Point_d& result);
  bool intersection(Line_d& result);
};

template <class R>
typename Line_d_Hyperplane_d_pair<R>::Intersection_result
Line_d_Hyperplane_d_pair<R>::intersection_type()
{ if (_known) return _result;
  _known = true;

  // CGAL_assertion_msg((!_l.is_degenerate())); 
  typedef typename R::Line_hyperplane_intersection_d Int_obj_type;
  Int_obj_type Intersect;
  FT lambda; 
  typename Int_obj_type::Intersection_result res = 
    Intersect(_l.point(0),_l.point(1),_h,_ip,lambda);

  if (res == Int_obj_type::LINE)  { return _result = LINE; }
  if (res == Int_obj_type::POINT) { return _result = POINT; }
  return _result = NO_INTERSECTION; 
}

template <class R>
bool
Line_d_Hyperplane_d_pair<R>::intersection(Point_d& p)
{ if (!_known) intersection_type();
  if (_result != POINT) return false;
  p = _ip; return true;
}

template <class R>
bool
Line_d_Hyperplane_d_pair<R>::intersection(Line_d& l)
{ if (!_known) intersection_type();
  if (_result != LINE) return false;
  l = _l; return true;
}

template <class R>
class Ray_d_Hyperplane_d_pair {
public:
  enum Intersection_result {NO_INTERSECTION, POINT, RAY};
  typedef typename R::FT FT;
  typedef typename R::Point_d Point_d;
  typedef typename R::Ray_d Ray_d;
  typedef typename R::Hyperplane_d Hyperplane_d;
protected:
  Ray_d _r; Hyperplane_d _h;
  bool                    _known;
  Intersection_result     _result;
  Point_d                 _ip;  
public:
  Ray_d_Hyperplane_d_pair() : _known(false) {}
  Ray_d_Hyperplane_d_pair(const Ray_d& r, const Hyperplane_d& h) 
   : _r(r), _h(h), _known(false) {}
  Intersection_result intersection_type();
  bool intersection(Point_d& result);
  bool intersection(Ray_d& result);
};

template <class R>
typename Ray_d_Hyperplane_d_pair<R>::Intersection_result
Ray_d_Hyperplane_d_pair<R>::intersection_type()
{ 
  if (_known) return _result;
  _known = true;

  // CGAL_assertion( !_r.is_degenerate() );
  typedef typename R::Line_hyperplane_intersection_d Int_obj_type;
  Int_obj_type Intersect;
  FT lambda = 0; // initialize to stop compiler warning
  typename Int_obj_type::Intersection_result res = 
    Intersect(_r.point(0),_r.point(1),_h,_ip,lambda);

  if ( res == Int_obj_type::POINT && FT(0) <= lambda ) 
  { return _result = POINT; }
  if ( res == Int_obj_type::LINE )  
  { return _result = RAY; }
  return _result = NO_INTERSECTION; 
}

template <class R>
bool
Ray_d_Hyperplane_d_pair<R>::intersection(Point_d& p)
{ if (!_known) intersection_type();
  if (_result != POINT) return false;
  p = _ip; return true;
}

template <class R>
bool
Ray_d_Hyperplane_d_pair<R>::intersection(Ray_d& r)
{ if (!_known) intersection_type();
  if (_result != RAY) return false;
  r = _r; return true;
}

template <class R>
class Segment_d_Hyperplane_d_pair {
public:
  enum Intersection_result {NO_INTERSECTION, POINT, SEGMENT};
  typedef typename R::FT           FT;
  typedef typename R::Point_d Point_d;
  typedef typename R::Segment_d Segment_d;
  typedef typename R::Hyperplane_d Hyperplane_d;

protected:
  Segment_d    _s;
  Hyperplane_d _h;
  bool                    _known;
  Intersection_result     _result;
  Point_d                 _ip;  
public:
  /*{\Mcreation 4}*/
  Segment_d_Hyperplane_d_pair() : _known(false) {}
  Segment_d_Hyperplane_d_pair(
    const Segment_d& s, const Hyperplane_d& h) :
    _s(s), _h(h), _known(false) {}

  Intersection_result intersection_type();
  bool intersection(Point_d& result);
  bool intersection(Segment_d& result);
};

template <class R>
typename Segment_d_Hyperplane_d_pair<R>::Intersection_result
Segment_d_Hyperplane_d_pair<R>::intersection_type()
{ 
  if (_known) return _result;
  _known = true;

  if ( _s.is_degenerate() ) {
    if ( _h.has_on(_s.point(0)) ) 
    { _ip = _s.point(0); return _result = POINT; } 
    else { return _result = NO_INTERSECTION; }
  }

  typedef typename R::Line_hyperplane_intersection_d Int_obj_type;
  Int_obj_type Intersect;
  FT lambda; 
  typename Int_obj_type::Intersection_result res = 
    Intersect(_s.point(0),_s.point(1),_h,_ip,lambda);

  if ( res == Int_obj_type::LINE )
  { return _result = SEGMENT; }
  if ( res == Int_obj_type::POINT && 
       FT(0) <= lambda && lambda <= FT(1) ) 
  { return _result = POINT; }
  return _result = NO_INTERSECTION; 
}

template <class R>
bool
Segment_d_Hyperplane_d_pair<R>::intersection(Point_d& pt)
{ if (!_known) intersection_type();
  if (_result != POINT) return false;
  pt = _ip; return true;
}

template <class R>
bool
Segment_d_Hyperplane_d_pair<R>::intersection(Segment_d& s)
{ if (!_known) intersection_type();
  if (_result != SEGMENT) return false;
  s = _s; return true;
}

CGAL_END_NAMESPACE

#endif //CGAL_INTERSECTION_OBJECTS_D_H