intersection_objects_d.h

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

// Copyright (c) 2002  Utrecht University (The Netherlands),
// ETH Zurich (Switzerland), Freie Universitaet Berlin (Germany),
// INRIA Sophia-Antipolis (France), Martin-Luther-University Halle-Wittenberg
// (Germany), Max-Planck-Institute Saarbruecken (Germany), RISC Linz (Austria),
// and Tel-Aviv University (Israel).  All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public License as
// published by the Free Software Foundation; version 2.1 of the License.
// See the file LICENSE.LGPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.3-branch/Kernel_d/include/CGAL/Kernel_d/intersection_objects_d.h $
// $Id: intersection_objects_d.h 36185 2007-02-11 22:27:17Z spion $
// 
//
// Author(s)     : ?

#ifndef CGAL_INTERSECTION_OBJECTS_D_H
#define CGAL_INTERSECTION_OBJECTS_D_H

CGAL_BEGIN_NAMESPACE

template <class R>
class Line_d_Line_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::FT FT;
protected:
  Line_d _l1, _l2;
  bool _known;
  Intersection_result _result;
  Point_d _ip;
public:
  Line_d_Line_d_pair() : _known(false) {}
  Line_d_Line_d_pair(const Line_d& l1, const Line_d& l2) 
    : _l1(l1), _l2(l2), _known(false) {}
  Intersection_result intersection_type();
  bool intersection(Point_d& result);
  bool intersection(Line_d& result);
};

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

  //CGAL_assertion(!_l1.is_degenerate()&&!_l2.is_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(_l1.point(0),_l1.point(1),
              _l2.point(0),_l2.point(1),
              _ip,l1,l2);

  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_Line_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_Line_d_pair<R>::intersection(Line_d& l)
{ if (!_known) intersection_type();
  if (_result != LINE) return false;
  l = _l1; return true;
}

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

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

  //CGAL_assertion(!_l.is_degenerate()&&!_r.is_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(_l.point(0),_l.point(1),
              _r.point(0),_r.point(1),
              _ip,l1,l2);

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

template <class R>
bool Line_d_Ray_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_Ray_d_pair<R>::intersection(Ray_d& r)
{ if (!_known) intersection_type();
  if (_result != RAY) return false;
  r = _r; return true;
}

template <class R>
class Line_d_Segment_d_pair {
public:
  enum Intersection_result {NO_INTERSECTION, POINT, SEGMENT};
  typedef typename R::Point_d Point_d;
  typedef typename R::Segment_d Segment_d;
  typedef typename R::Line_d  Line_d;
  typedef typename R::FT FT;
protected:
  Line_d _l; Segment_d _s;
  bool _known;
  Intersection_result _result;
  Point_d _ip; 
public:
  Line_d_Segment_d_pair() : _known(false) {}
  Line_d_Segment_d_pair(const Line_d& l, const Segment_d& s) 
    : _l(l), _s(s), _known(false) {}
  Intersection_result intersection_type();
  bool intersection(Point_d& result);
  bool intersection(Segment_d& result);
};

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

  //CGAL_assertion(!_l.is_degenerate());
  if ( _s.is_degenerate() ) {
    if ( _l.has_on(_s.point(0)) ) {
      _ip = _s.point(0);
      return _result = POINT;
    }
    return _result = NO_INTERSECTION; 
  }
  // _s 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(_l.point(0),_l.point(1),
              _s.point(0),_s.point(1),
              _ip,l1,l2);

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

template <class R>
bool Line_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 Line_d_Segment_d_pair<R>::intersection(Segment_d& s)
{ if (!_known) intersection_type();
  if (_result != SEGMENT) return false;
  s = _s; return true;
}


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

protected:
  Ray_d _r1, _r2;
  bool _known;
  Intersection_result _result;
  Point_d _ip; Segment_d _is; Ray_d _ir;
public:
  Ray_d_Ray_d_pair() : _known(false) {}
  Ray_d_Ray_d_pair(const Ray_d& r1, const Ray_d& r2)
    : _r1(r1), _r2(r2), _known(false) {}
  Intersection_result intersection_type();
  bool intersection(Point_d& result);
  bool intersection(Segment_d& result);
  bool intersection(Ray_d& result);
};

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

  //CGAL_assertion((!_r1.is_degenerate()&&!_r2.is_degenerate());
  // none of the lines should be trivial

  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(_r1.point(0),_r1.point(1),
              _r2.point(0),_r2.point(1),_ip,l1,l2);

  if (res == Int_obj_type::LINE)   
  {
    if ( _r1.direction() == _r2.direction() ) {
      if ( _r1.has_on(_r2.source()) ) _ir = _r2;
      else _ir = _r1; 
      return _result = RAY;
    }
    // now oppositely directed:
    if ( _r1.has_on(_r2.source()) ) {
      if ( _r1.source() != _r2.source() ) 
      { _is = Segment_d(_r1.source(),_r2.source()); 
        return _result = SEGMENT; }
      else
      { _ip = _r1.source(); return _result = POINT; }
    }
    return _result = NO_INTERSECTION;
  }


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

template <class R>
bool
Ray_d_Ray_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_Ray_d_pair<R>::intersection(Segment_d& s)
{ if (!_known) intersection_type();
  if (_result != SEGMENT) return false;
  s = _is; return true;
}

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

template <class R>
class Ray_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;
  typedef typename R::Ray_d Ray_d;

protected:
  Ray_d _r; Segment_d _s;
  bool _known;
  Intersection_result _result;
  Point_d _ip; Segment_d _is;  
public:
  Ray_d_Segment_d_pair() : _known(false) {}
  Ray_d_Segment_d_pair(const Ray_d& r, const Segment_d& s)
    : _r(r), _s(s), _known(false) {}
  Intersection_result intersection_type();
  bool intersection(Point_d& result);
  bool intersection(Segment_d& result);
};

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

  //CGAL_assertion(!_r.is_degenerate());
  if ( _s.is_degenerate() ) {
    if ( _r.has_on(_s.point(0)) ) 
    { _ip = _s.point(0); return _result = POINT; }
    return _result = NO_INTERSECTION; 
  }