SPAR/AIModule/BWTA/vendors/CGAL/CGAL/Triangle_3_Triangle_3_do_intersect.h

Go to the documentation of this file.

// Copyright (c) 2003  INRIA Sophia-Antipolis (France).
// 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.5-branch/Intersections_3/include/CGAL/Triangle_3_Triangle_3_do_intersect.h $
// $Id: Triangle_3_Triangle_3_do_intersect.h 45156 2008-08-26 13:40:26Z spion $
// 
//
// Author(s)     : Philippe Guigue

#ifndef CGAL_TRIANGLE_3_TRIANGLE_3_DO_INTERSECT_H
#define CGAL_TRIANGLE_3_TRIANGLE_3_DO_INTERSECT_H

#include <CGAL/Uncertain.h>

CGAL_BEGIN_NAMESPACE

namespace CGALi {

template <class K>
bool  _intersection_test_vertex(const typename K::Point_3 * p, 
                                const typename K::Point_3 * q, 
                                const typename K::Point_3 * r,
                                const typename K::Point_3 * a, 
                                const typename K::Point_3 * b, 
                                const typename K::Point_3 * c,
                                const K & k){

  CGAL_kernel_precondition( k.coplanar_orientation_3_object() (*p,*q,*r)
                            == POSITIVE);
  CGAL_kernel_precondition( k.coplanar_orientation_3_object() (*a,*b,*c)
                            == POSITIVE);
  

  // Vertex p sees vertex c

  typename K::Coplanar_orientation_3 coplanar_orientation = 
    k.coplanar_orientation_3_object();


  if (coplanar_orientation(*c,*a,*q) != NEGATIVE) {
    if (coplanar_orientation(*c,*b,*q) != POSITIVE) {
      if (coplanar_orientation(*p,*a,*q) == POSITIVE) 
        return  coplanar_orientation(*p,*b,*q) != POSITIVE;  
      
      return coplanar_orientation(*p,*a,*r) != NEGATIVE
        && coplanar_orientation(*q,*r,*a) != NEGATIVE;
    }
     
    if (coplanar_orientation(*p,*b,*q) != POSITIVE)
      return coplanar_orientation(*c,*b,*r) != POSITIVE
        && coplanar_orientation(*q,*r,*b) != NEGATIVE;
    return false;
    
  }
  
  if (coplanar_orientation(*c,*a,*r) != NEGATIVE) { //qr straddles (ac) 
    if (coplanar_orientation(*q,*r,*c) != NEGATIVE)
      return (coplanar_orientation(*p,*a,*r) != NEGATIVE);
    
    return coplanar_orientation(*q,*r,*b) != NEGATIVE
      && coplanar_orientation(*c,*r,*b) != NEGATIVE;
  }
  return false; // ca separes
  
}


template <class K>
bool  _intersection_test_edge(const typename K::Point_3 * p, 
                              const typename K::Point_3 * q, 
                              const typename K::Point_3 * r,
                              const typename K::Point_3 * a, 
                              const typename K::Point_3 * CGAL_kernel_precondition_code(b), 
                              const typename K::Point_3 * c,
                              const K & k){
  
  CGAL_kernel_precondition( k.coplanar_orientation_3_object() (*p,*q,*r)
                            == POSITIVE);
  CGAL_kernel_precondition( k.coplanar_orientation_3_object() (*a,*b,*c)
                            == POSITIVE);

  // Vertex p sees edge ca
  
  typename K::Coplanar_orientation_3 coplanar_orientation = 
    k.coplanar_orientation_3_object();



  if (coplanar_orientation(*c,*a,*q) != NEGATIVE) {  //pq straddles (ac)
    if (coplanar_orientation(*p,*a,*q) != NEGATIVE) 
      return coplanar_orientation(*p,*q,*c) != NEGATIVE ;
   
    return coplanar_orientation(*q,*r,*a) != NEGATIVE
      && coplanar_orientation(*r,*p,*a) != NEGATIVE;
  }
   
  if (coplanar_orientation(*c,*a,*r) != NEGATIVE) { 
    // pr and qr straddle line (pr)
    return coplanar_orientation(*p,*a,*r) != NEGATIVE
      && ( coplanar_orientation(*p,*r,*c) != NEGATIVE
           || coplanar_orientation(*q,*r,*c) != NEGATIVE );
  }
    
  return false; //ac separes
}


template <class K>
bool do_intersect_coplanar(const typename K::Triangle_3 &t1, 
                           const typename K::Triangle_3 &t2,
                           const K & k) 
{
    
  CGAL_kernel_precondition( ! k.is_degenerate_3_object() (t1) );
  CGAL_kernel_precondition( ! k.is_degenerate_3_object() (t2) );

  typedef typename K::Point_3 Point_3;
  
  typename K::Construct_vertex_3 vertex_on =
    k.construct_vertex_3_object();
 
  typename K::Coplanar_orientation_3 coplanar_orientation = 
    k.coplanar_orientation_3_object();

    const Point_3 & P = vertex_on(t1,0);
    const Point_3 & Q = vertex_on(t1,1);
    const Point_3 & R = vertex_on(t1,2);
    
    const Point_3 & A = vertex_on(t2,0);
    const Point_3 & B = vertex_on(t2,1);
    const Point_3 & C = vertex_on(t2,2);
    

    const Point_3 * p = &P;
    const Point_3 * q = &Q;
    const Point_3 * r = &R;
    
    const Point_3 * a = &A;
    const Point_3 * b = &B;
    const Point_3 * c = &C;

    // First we ensure that both triangles are counterclockwise
    // oriented, t1 and t2 are supposed  to be non flat.
    
    if ( coplanar_orientation(P,Q,R) == NEGATIVE ) {
      q = &R;
      r = &Q;
    }
    
    if ( coplanar_orientation(A,B,C) == NEGATIVE ) {
      b = &C;
      c = &B;
    }


    // Localization of p in the arrangement of the 
    // lines supporting abc's edges

    if ( coplanar_orientation(*a,*b,*p) != NEGATIVE ) {
      if ( coplanar_orientation(*b,*c,*p) != NEGATIVE ) {
        if ( coplanar_orientation(*c,*a,*p) != NEGATIVE )
          // p is inside triangle abc
          return true;
        // p sees ac
        return CGALi::_intersection_test_edge(p,q,r,a,b,c,k);
      }
      if ( coplanar_orientation(*c,*a,*p) != NEGATIVE )//p sees bc 
        return CGALi::_intersection_test_edge(p,q,r,c,a,b,k);
      // p sees c
      return CGALi::_intersection_test_vertex(p,q,r,a,b,c,k);
      
    }
    if ( coplanar_orientation(*b,*c,*p) != NEGATIVE ) {
      if ( coplanar_orientation(*c,*a,*p) != NEGATIVE ) //p sees ab
        return CGALi::_intersection_test_edge(p,q,r,b,c,a,k);
      // p sees a
      return CGALi::_intersection_test_vertex(p,q,r,b,c,a,k);
    } 
    // p sees b
    return CGALi::_intersection_test_vertex(p,q,r,c,a,b,k);
    
}


template <class K>
typename K::Boolean
do_intersect(const typename K::Triangle_3 &t1, 
             const typename K::Triangle_3 &t2,
             const K & k) 
{
  CGAL_kernel_precondition( ! k.is_degenerate_3_object() (t1) );
  CGAL_kernel_precondition( ! k.is_degenerate_3_object() (t2) );

  typedef typename K::Point_3 Point_3;

  typename K::Construct_vertex_3 vertex_on =
    k.construct_vertex_3_object();

  typename K::Orientation_3 orientation = 
    k.orientation_3_object();


   const Point_3 & p = vertex_on(t1,0);
   const Point_3 & q = vertex_on(t1,1);
   const Point_3 & r = vertex_on(t1,2);
   const Point_3 & a = vertex_on(t2,0);
   const Point_3 & b = vertex_on(t2,1);
   const Point_3 & c = vertex_on(t2,2);


   const Point_3  * s_min1;
   const Point_3  * t_min1;
   const Point_3  * s_max1;
   const Point_3  * t_max1;
   
   // Compute distance signs  of p, q and r to the plane of triangle(a,b,c)
   const Orientation dp = make_certain(orientation(a,b,c,p));
   const Orientation dq = make_certain(orientation(a,b,c,q));
   const Orientation dr = make_certain(orientation(a,b,c,r));
   
 
    switch ( dp ) {
    case POSITIVE:
      if ( dq == POSITIVE ) {
        if ( dr == POSITIVE) 
          // pqr lies in the open positive halfspace induced by
          // the plane of triangle(a,b,c)
          return false;
        // r is isolated on the negative side of the plane
        s_min1 = &q ; t_min1 = &r ; s_max1 = &r ; t_max1 = &p; 
        
      } else {
        if  ( dr == POSITIVE) {
          // q is isolated on the negative side of the plane
          s_min1 =  &p; t_min1 =  &q; s_max1 =  &q; t_max1 =  &r; 
        } else {
          // p is isolated on the positive side of the plane
          s_min1 =  &p; t_min1 =  &q; s_max1 =  &r; t_max1 =  &p; 
        }
      }
      break;
      
    case NEGATIVE:
      if ( dq == NEGATIVE ) {
        if ( dr == NEGATIVE ) 
          // pqr lies in the open negative halfspace induced by
          // the plane of triangle(a,b,c)
          return false; 
        // r is isolated on the positive side of the plane
        s_min1 =  &r; t_min1 =  &p; s_max1 =  &q; t_max1 =  &r; 
        
      } else {
        if ( dr == NEGATIVE ) {
          // q is isolated on the positive side of the plane
          s_min1 =  &q; t_min1 =  &r; s_max1 =  &p; t_max1 =  &q; 
        } else {
          // p is isolated on the negative side of the plane
          s_min1 =  &r; t_min1 =  &p; s_max1 =  &p; t_max1 =  &q; 
        }
      }
      break;
      
    case COPLANAR:
      switch  ( dq ) {
      case POSITIVE:
        if ( dr == POSITIVE ) {
          // p is isolated on the negative side of the plane
          s_min1 =  &r; t_min1 =  &p; s_max1 =  &p; t_max1 =  &q; 
        } else {
          // q is isolated on the positive side of the plane
          s_min1 =  &q; t_min1 =  &r; s_max1 =  &p; t_max1 =  &q; 
        }
        break;
        
      case NEGATIVE:
        if ( dr == NEGATIVE ) {
          // p is isolated on the positive side of the plane
          s_min1 =  &p; t_min1 =  &q; s_max1 =  &r; t_max1 =  &p; 
        } else {
          // q is isolated on the negative side of the plane
          s_min1 =  &p; t_min1 =  &q; s_max1 =  &q; t_max1 =  &r; 
        }
        break;
        
      case COPLANAR:
        switch ( dr ) {
        case POSITIVE:
          // r is isolated on the positive side of the plane
          s_min1 =  &r; t_min1 =  &p; s_max1 =  &q; t_max1 =  &r; 
          break;
          
        case NEGATIVE:
          // r is isolated on the negative side of the plane
          s_min1 =  &q ; t_min1 =  &r ; s_max1 =  &r ; t_max1 =  &p; 
          break;
          
        case COPLANAR:
          return do_intersect_coplanar(t1,t2,k);
        default: // should not happen.
          CGAL_kernel_assertion(false);
          return false;
          
        }
        break;
        
      default: // should not happen.
      CGAL_kernel_assertion(false);
      return false;
        
      }
      break;
      
    default: // should not happen.
      CGAL_kernel_assertion(false);
      return false;
    }

        
    
    const Point_3  * s_min2;
    const Point_3  * t_min2;
    const Point_3  * s_max2;
    const Point_3  * t_max2;
    
    // Compute distance signs  of a, b and c to the plane of triangle(p,q,r)
    const Orientation da = make_certain(orientation(p,q,r,a));
    const Orientation db = make_certain(orientation(p,q,r,b));
    const Orientation dc = make_certain(orientation(p,q,r,c));
    

    switch ( da ) {
    case POSITIVE:
      if ( db == POSITIVE ) {
        if ( dc == POSITIVE) 
          // abc lies in the open positive halfspace induced by
          // the plane of triangle(p,q,r)
          return false;
        // c is isolated on the negative side of the plane
        s_min2 =  &b ; t_min2 =  &c ; s_max2 =  &c ; t_max2 =  &a; 
        
      } else {
        if  ( dc == POSITIVE) {
          // b is isolated on the negative side of the plane
          s_min2 =  &a; t_min2 =  &b; s_max2 =  &b; t_max2 =  &c; 
        } else {
          // a is isolated on the positive side of the plane
          s_min2 =  &a; t_min2 =  &b; s_max2 =  &c; t_max2 =  &a; 
        }
      }
      break;
      
    case NEGATIVE:
      if ( db == NEGATIVE ) {
        if ( dc == NEGATIVE ) 
          // abc lies in the open negative halfspace induced by
          // the plane of triangle(p,q,r)
          return false; 
        // c is isolated on the positive side of the plane
        s_min2 =  &c ; t_min2 =  &a ; s_max2 =  &b ; t_max2 =  &c; 

      } else {
        if ( dc == NEGATIVE ) {
          // b is isolated on the positive side of the plane
          s_min2 =  &b ; t_min2 =  &c ; s_max2 =  &a ; t_max2 =  &b; 
        } else {
          // a is isolated on the negative side of the plane
          s_min2 =  &c ; t_min2 =  &a ; s_max2 =  &a ; t_max2 =  &b; 
        }
      }
      break;
      
    case COPLANAR:
      switch  ( db ) {
      case POSITIVE:
        if ( dc == POSITIVE ) {
          // a is isolated on the negative side of the plane
          s_min2 =  &c ; t_min2 =  &a ; s_max2 =  &a ; t_max2 =  &b; 
        } else {
          // b is isolated on the positive side of the plane
          s_min2 =  &b ; t_min2 =  &c ; s_max2 =  &a ; t_max2 =  &b; 
        }
        break;
        
      case NEGATIVE:
        if ( dc == NEGATIVE ) {
          // a is isolated on the positive side of the plane
          s_min2 =  &a ; t_min2 =  &b ; s_max2 =  &c ; t_max2 =  &a; 
        } else {
          // b is isolated on the negative side of the plane
          s_min2 =  &a ; t_min2 =  &b ; s_max2 =  &b ; t_max2 =  &c; 
        }
        break;
        
      case COPLANAR:
        switch ( dc ) {
        case POSITIVE:
          // c is isolated on the positive side of the plane
          s_min2 =  &c ; t_min2 =  &a ; s_max2 =  &b ; t_max2 =  &c;
          break;
          
        case NEGATIVE:
          // c is isolated on the negative side of the plane
          s_min2 =  &b ; t_min2 =  &c ; s_max2 =  &c ; t_max2 =  &a; 
          break;
          
        case COPLANAR:
          // Supposed unreachable code
          // since the triangles are assumed to be non-flat
          
          return do_intersect_coplanar(t1,t2,k);
        default: // should not happen.
          CGAL_kernel_assertion(false);
          return false;
          
        }
        break;
        
      default: // should not happen.
      CGAL_kernel_assertion(false);
      return false;
        
      }
      break;
      
    default: // should not happen.
      CGAL_kernel_assertion(false);
      return false;
    }
    
    return  orientation(*s_min1,*t_min1,*s_min2,*t_min2) != POSITIVE 
      &&  orientation(*s_max1,*t_max1,*t_max2,*s_max2) != POSITIVE;
}

} // namespace CGALi


template <class K>
inline typename K::Boolean
do_intersect(const Triangle_3<K> &t1, 
             const Triangle_3<K> &t2) 
{
  return typename K::Do_intersect_3()(t1,t2);
}
        
CGAL_END_NAMESPACE

#endif // CGAL_TRIANGLE_3_TRIANGLE_3_DO_INTERSECT_H