internal_functions_on_circular_arc_2.h

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

// Copyright (c) 2003-2006  INRIA Sophia-Antipolis (France).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL 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/Circular_kernel_2/include/CGAL/Circular_kernel_2/internal_functions_on_circular_arc_2.h $
// $Id: internal_functions_on_circular_arc_2.h 37191 2007-03-17 09:43:57Z afabri $
//
// Author(s)     : Monique Teillaud, Sylvain Pion

// Partially supported by the IST Programme of the EU as a Shared-cost
// RTD (FET Open) Project under Contract No  IST-2000-26473 
// (ECG - Effective Computational Geometry for Curves and Surfaces) 
// and a STREP (FET Open) Project under Contract No  IST-006413 
// (ACS -- Algorithms for Complex Shapes)

#ifndef CGAL_CIRCULAR_KERNEL_PREDICATES_ON_CIRCULAR_ARC_2_H
#define CGAL_CIRCULAR_KERNEL_PREDICATES_ON_CIRCULAR_ARC_2_H

#include <CGAL/Circular_kernel_2/internal_functions_on_circle_2.h>
#include <CGAL/Interval_nt.h>
#include <CGAL/Circular_kernel_2/Circular_arc_2.h>

namespace CGAL {
namespace CircularFunctors {
  

  template < class CK >
  inline
  Comparison_result 
  compare_x(const typename CK::Circular_arc_point_2 &p0,
            const typename CK::Circular_arc_point_2 &p1)
  {
    typedef typename CK::Algebraic_kernel   AK;
    if(p0.equal_ref(p1)) return static_cast<Comparison_result>(0);
    return AK().compare_x_object()(p0.coordinates(), p1.coordinates());
  }

  template < class CK >
  inline
  Comparison_result 
  compare_y(const typename CK::Circular_arc_point_2 &p0,
            const typename CK::Circular_arc_point_2 &p1)
  {
    typedef typename CK::Algebraic_kernel   AK;
    if(p0.equal_ref(p1)) return static_cast<Comparison_result>(0);
    return AK().compare_y_object()(p0.coordinates(), p1.coordinates());
  }
  
  template < class CK >
  Comparison_result 
  compare_xy(const typename CK::Circular_arc_point_2 &p0,
             const typename CK::Circular_arc_point_2 &p1)
  {
    if(p0.equal_ref(p1)){
      return EQUAL;
    }
    typedef typename CK::Algebraic_kernel   AK;
    return AK().compare_xy_object()(p0.coordinates(), p1.coordinates());
  }

  // PRE CONDITION: 
  // The coordinates of P, Q, R have to have the same 
  // delta or (beta == 0 || delta == 0)
  // We cannot code this pre condition because
  // if Root_of_2 is interval_nt "beta", "delta" mean nothing
  template < class CK >
  Orientation 
  orientation(const typename CK::Circular_arc_point_2 &p,
              const typename CK::Circular_arc_point_2 &q,
              const typename CK::Circular_arc_point_2 &r)
  {
    typedef typename CK::Root_of_2 Root_of_2;
    const Root_of_2 px = p.x();
    const Root_of_2 py = p.y();
    const Root_of_2 qx = q.x();
    const Root_of_2 qy = q.y();
    const Root_of_2 rx = r.x();
    const Root_of_2 ry = r.y();
    const Root_of_2 a00 = qx-px;
    const Root_of_2 a01 = qy-py;
    const Root_of_2 a10 = rx-px;
    const Root_of_2 a11 = ry-py;
    return enum_cast<Orientation>(CGAL_NTS compare(a00*a11, a10*a01));
  }

//   template < class CK >
//   inline
//   Comparison_result 
//   compare_x(const typename CK::Circular_arc_point_2 &p0,
//             const typename CK::Point_2 &p1)
//   {
//     return CGAL::compare(p0.x(), p1.x());
//   }

//   template < class CK >
//   inline
//   Comparison_result 
//   compare_x(const typename CK::Point_2 &p0,
//             const typename CK::Circular_arc_point_2 &p1)
//   {
//     return CGAL::compare(p0.x(), p1.x());
//   }


//   template < class CK >
//   inline
//   Comparison_result 
//   compare_y(const typename CK::Circular_arc_point_2 &p0,
//             const typename CK::Point_2 &p1)
//   {
//     return CGAL::compare(p0.y(), p1.y());
//   }

//   template < class CK >
//   inline
//   Comparison_result 
//   compare_y(const typename CK::Point_2 &p0,
//             const typename CK::Circular_arc_point_2 &p1)
//   {
//     return CGAL::compare(p0.y(), p1.y());
//   }


//   template < class CK >
//   Comparison_result 
//   compare_xy(const typename CK::Circular_arc_point_2 &p0,
//              const typename CK::Point_2 &p1)
//   {
//     Comparison_result compx = compare_x<CK>(p0, p1);
//     if (compx != 0)
//       return compx;
//     return compare_y<CK>(p0, p1);
//   }

//   template < class CK >
//   Comparison_result 
//   compare_xy(const typename CK::Point_2 &p0,
//              const typename CK::Circular_arc_point_2 &p1)
//   {
//     Comparison_result compx = compare_x<CK>(p0, p1);
//     if (compx != 0)
//       return compx;
//     return compare_y<CK>(p0, p1);
//   }

 
  template < class CK >
  bool
  point_in_x_range(const typename CK::Circular_arc_point_2 &source,
		   const typename CK::Circular_arc_point_2 &target,
		   const typename CK::Circular_arc_point_2 &p) 
  {
    // range includes endpoints here
    return ( (CircularFunctors::compare_x<CK>(p, source) != CircularFunctors::compare_x<CK>(p, target)) 
	     || (CircularFunctors::compare_x<CK>(p, source) == CGAL::EQUAL) );
  }
  
  template < class CK >
  bool
  point_in_x_range(const typename CK::Circular_arc_2 &A,
		   const typename CK::Circular_arc_point_2 &p) 
  {
    //CGAL_kernel_precondition (A.is_x_monotone());
    // range includes endpoints here
    return CircularFunctors::compare_x<CK>( p, A.source()) != CircularFunctors::compare_x<CK>(p, A.target() );
  }

  template < class CK >
  Comparison_result
  compare_y_at_x(const typename CK::Circular_arc_point_2 &p,
                 const typename CK::Circular_arc_2 &A1)
  {
    //CGAL_kernel_precondition (A1.is_x_monotone());
    //CGAL_kernel_precondition (CircularFunctors::point_in_x_range<CK>(A1, p)); 
    
    if((p.equal_ref(A1.source())) || (p.equal_ref(A1.target()))){
      return EQUAL;
    }
    
    // Compare the ordinate of p with the ordinate of the center.
    Comparison_result sgn =
      CGAL::compare(p.y(), A1.supporting_circle().center().y());
    // Is the arc on the lower or upper part of the circle ?
    // I.e. it's the comparison of the "ordinate" of the arc with the center.
    Comparison_result cmp = A1.on_upper_part() ? LARGER : SMALLER;
    if (sgn == opposite(cmp))
      return sgn;

    // If not, then we can compute if p is inside the circle or not.
    typedef typename CK::Root_of_2 Root;
    Root dx_sqr = CGAL::square(p.x() - A1.supporting_circle().center().x());
    Root dy_sqr = CGAL::square(p.y() - A1.supporting_circle().center().y());
    // NB : that one can be factorized with the above...

    // Now we want the comparison of dx_sqr + dy_sqr with squared_radius.
    // It's the same as dx_sqr - squared_radius with -dy_sqr.

    Comparison_result distance_to_center = 
      CGAL::compare(dx_sqr, A1.supporting_circle().squared_radius() - dy_sqr);

    if (cmp > 0)
      return distance_to_center;
    else
      return opposite(distance_to_center);
  }

  

  template < class CK >
  Comparison_result 
  compare_y_to_right(const typename CK::Circular_arc_2 &A1,
		     const typename CK::Circular_arc_2 &A2, 
		     const typename CK::Circular_arc_point_2 &p)
  {
    // FIXME : add preconditions to check that the 2 arcs are defined at
    // the right of the intersection.
    //CGAL_kernel_precondition (A1.is_x_monotone());
    //CGAL_kernel_precondition (A2.is_x_monotone());

    typedef std::vector<CGAL::Object> solutions_container; 
    typedef typename CK::Circular_arc_2 Circular_arc_2; 

#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
    // intersection found on the map
    solutions_container early_sols;
    if(Circular_arc_2::template find_intersection< solutions_container >
      (A1,A2,early_sols)) {
      if(A1.on_upper_part()) return LARGER;
      return SMALLER;
    }
#endif

    const typename CK::Circle_2 & C1 = A1.supporting_circle();
    const typename CK::Circle_2 & C2 = A2.supporting_circle();
    
    if (CircularFunctors::non_oriented_equal<CK>(C1,C2)) {
      // The point is either a left vertical tangent point of both,
      // or a normal point (-> EQUAL).
      bool b1 = A1.on_upper_part();
      bool b2 = A2.on_upper_part();
      if (b1 == b2)
        return EQUAL;
      if (b1 == true && b2 == false)
        return LARGER;
      CGAL_kernel_assertion (b1 == false && b2 == true);
      return SMALLER;
    }

    const typename CK::Root_of_2 b1_y = C1.center().y() - p.y();
    const typename CK::Root_of_2 b2_y = C2.center().y() - p.y();
    
    int s_b1_y = CGAL::sign(b1_y);
    int s_b2_y = CGAL::sign(b2_y);
    
    if (s_b1_y == 0) {
      // Vertical tangent for A1.
      if (s_b2_y != 0)
        return A1.on_upper_part() ? LARGER : SMALLER;
      // Vertical tangent for A2 also.
      bool b1 = A1.on_upper_part();
      bool b2 = A2.on_upper_part();
      if (b1 == b2)
        return b1 ? compare_x(C1.center(), C2.center())
                  : compare_x(C2.center(), C1.center());
      if (b1 == true && b2 == false)
        return LARGER;
      CGAL_kernel_assertion (b1 == false && b2 == true);
      return SMALLER;
    }
    
    if (s_b2_y == 0) {
      // Vertical tangent for A2.
      return A2.on_upper_part() ? SMALLER : LARGER;
    }

    // No more vertical tangent points.
    CGAL_kernel_assertion(s_b1_y != 0);
    CGAL_kernel_assertion(s_b2_y != 0);

    int s_b1_x = (int) CGAL::compare(p.x(), C1.center().x());
    int s_b2_x = (int) CGAL::compare(p.x(), C2.center().x());

    // We compute the slope of the 2 tangents, then we compare them.
    Comparison_result cmp = CGAL::compare(s_b1_y * s_b1_x,
                                          s_b2_y * s_b2_x);
    // The slopes have different signs.
    if (cmp != 0)
      return cmp;
    
    // The slopes have the same signs : we have to square.
    if (CGAL::square(squared_distance(C1.center(), C2.center())
		     - C1.squared_radius() - C2.squared_radius())
	< 4 * C1.squared_radius() * C2.squared_radius() ) 
      {
	// The two circles are not tangent.
	return static_cast<Comparison_result>
	  (CGAL::compare(C1.squared_radius() * CGAL::square(b2_y),
			 C2.squared_radius() * CGAL::square(b1_y))
	   * s_b1_y * s_b1_x );
      }

    // tangent circles
    if (s_b1_x * s_b2_x < 0)
      // Circles are on both sides, and the tangent is not horizontal
      return compare_y(C1.center(), C2.center());

    if (s_b1_x * s_b2_x > 0)
      // Circles are on the same side, and the tgt is not horizontal.
      return compare_y(C2.center(), C1.center());

    // The tangent is horizontal.
    CGAL_kernel_assertion(s_b1_x == 0 && s_b2_x == 0);
    if (s_b1_y == s_b2_y)
      // The 2 circles are both below or both above the tangent
      return compare_y(C2.center(), C1.center());
    
    return compare_y(C1.center(), C2.center());
  }

  template < class CK >
  inline
  bool
  equal(const typename CK::Circular_arc_point_2 &p0,
        const typename CK::Circular_arc_point_2 &p1)
  {
    if(p0.equal_ref(p1)) return static_cast<Comparison_result>(1);
    return CircularFunctors::compare_xy<CK>(p0, p1) == 0;
  }

  template < class CK >
  bool
  equal(const typename CK::Circular_arc_2 &A1,
        const typename CK::Circular_arc_2 &A2)
  {
    /*if ((A1.supporting_circle() != A2.supporting_circle()) && 
	(A1.supporting_circle() != A2.supporting_circle().opposite()))
      return false;*/

    if(!CircularFunctors::non_oriented_equal<CK>(
      A1.supporting_circle(), A2.supporting_circle()))
      return false;
    
    return (CircularFunctors::equal<CK>(A1.source(), A2.source()) &&
	    CircularFunctors::equal<CK>(A1.target(), A2.target()));
  }

//   template < class CK >
//   bool
//   equal(const typename CK::Circular_arc_2 &A1,
//         const typename CK::Circular_arc_2 &A2)
//   {
//     CGAL_kernel_precondition (A1.is_x_monotone());
//     CGAL_kernel_precondition (A2.is_x_monotone());

//     if ( A1.supporting_circle() != A2.supporting_circle() )
//       return false;