internal_functions_on_line_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_line_arc_2.h $
// $Id: internal_functions_on_line_arc_2.h 36963 2007-03-09 08:37:01Z spion $
//
// 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_LINE_ARC_2_H
#define CGAL_CIRCULAR_KERNEL_PREDICATES_ON_LINE_ARC_2_H

#include <CGAL/Circular_kernel_2/internal_functions_on_line_2.h>
#include <CGAL/Circular_kernel_2/internal_functions_on_circular_arc_2.h>

namespace CGAL {
namespace CircularFunctors {

  template < class CK >
  bool
  point_in_x_range(const typename CK::Line_arc_2 &A,
		   const typename CK::Circular_arc_point_2 &p) 
  {
    // range includes endpoints here
    return ( (CircularFunctors::compare_x<CK>(p, A.source()) != CircularFunctors::compare_x<CK>(p, A.target())) 
	     || (CircularFunctors::compare_x<CK>(p, A.source()) == CGAL::EQUAL) );
  }
 
  template < class CK >
  bool
  equal(const typename CK::Line_arc_2 &A1,
        const typename CK::Line_arc_2 &A2)
  {
    if (!LinearFunctors::non_oriented_equal<CK>(
      A1.supporting_line(),A2.supporting_line())) 
      return false;

    return ( (equal<CK>(A1.source(), A2.source()) &&
	      equal<CK>(A1.target(), A2.target())) ||
	     (equal<CK>(A1.target(), A2.source()) &&
	      equal<CK>(A1.source(), A2.target())) );
  }

  template < class CK >
  bool
  do_overlap(const typename CK::Line_arc_2 &A1,
	     const typename CK::Line_arc_2 &A2)
  {
    if (!LinearFunctors::non_oriented_equal<CK>(
      A1.supporting_line(),A2.supporting_line())) 
      return false;

    return CircularFunctors::compare_xy<CK>(A1.right(), A2.left()) >= 0
        && CircularFunctors::compare_xy<CK>(A1.left(), A2.right()) <= 0; 
  }


  template < class CK >
  bool
  has_on(const typename CK::Line_arc_2 &a,
	 const typename CK::Circular_arc_point_2 &p,
         const bool has_on_supporting_line = false)
  {
    if(p.equal_ref(a.source()) || p.equal_ref(a.target())){
      return true;
    }

    if(!has_on_supporting_line) {
      if(!CGAL::LinearFunctors::has_on<CK>(a.supporting_line(),p))
        return false;
    }
    
    return (CircularFunctors::compare_xy<CK>(p, a.source()) != CircularFunctors::compare_xy<CK>(p, a.target()));
  }


  template< class CK>
  bool
  is_vertical(const typename CK::Line_arc_2 &l)
  {
    return l.supporting_line().is_vertical();
  }

  template< class CK>
  bool
  is_x_monotone(const typename CK::Line_arc_2 &l)
  {
    return true;
  }

  template< class CK>
  bool
  is_y_monotone(const typename CK::Line_arc_2 &l)
  {
    return true;
  }

  template < class CK >
  Comparison_result
  compare_y_at_x(const typename CK::Circular_arc_point_2 &p,
                 const typename CK::Line_arc_2 &A1)
  {
    if(p.equal_ref(A1.source()) || p.equal_ref(A1.target())){
      return EQUAL;
    }
    //CGAL_kernel_precondition (CircularFunctors::point_in_x_range<CK>(A1, p));
    //vertical case
    if (CircularFunctors::is_vertical<CK>(A1)) {
      if (p.y() <= A1.right().y()) {
	if(A1.left().y() <= p.y()) {
	  return CGAL::EQUAL;
	}
	return CGAL::SMALLER;
      }
      return CGAL::LARGER;
    }
    //general case
    typedef typename CK::Polynomial_1_2    Polynomial_1_2;
    typedef typename CK::Root_of_2         Root_of_2;
    Polynomial_1_2 equation = 
      CGAL::LinearFunctors::get_equation<CK>(A1.supporting_line());
    Root_of_2 y((-p.x()*equation.a() - equation.c())/equation.b());
    if (y == p.y())
      return CGAL::EQUAL;
    else if (y < p.y())
      return CGAL::LARGER;
    else return CGAL::SMALLER;
  }

  template < class CK >
  Comparison_result 
  compare_y_to_right(const typename CK::Line_arc_2 &A1,
		     const typename CK::Line_arc_2 &A2, 
		     const typename CK::Circular_arc_point_2 &/*p*/)
  {
    if(A1.supporting_line().is_vertical()){
      if(A2.supporting_line().is_vertical())
	return CGAL::EQUAL;
      return CGAL::LARGER;
    }
    if(A2.supporting_line().is_vertical())
      return CGAL::SMALLER;
    
    typedef typename CK::Circular_arc_point_2 Circular_arc_point_2;
    typedef typename CK::Polynomial_1_2       Polynomial_1_2;
    typedef typename CK::Root_of_2            Root_of_2;

    Polynomial_1_2 equation;
    if(A1.right().x() < A2.right().x()){
      equation = CGAL::LinearFunctors::get_equation<CK>(A2.supporting_line());
      Root_of_2 y((-A1.right().x()*equation.a() - equation.c())/equation.b());
      Root_of_2 A1_right_y = A1.right().y();
      if (y == A1_right_y)
	return CGAL::EQUAL;
      if (y < A1_right_y)
	return CGAL::LARGER;
      return CGAL::SMALLER;
    }
    else{
      equation = CGAL::LinearFunctors::get_equation<CK>(A1.supporting_line());
      Root_of_2 y((-A2.right().x()*equation.a() - equation.c())/equation.b());
      Root_of_2 A2_right_y = A2.right().y();
      if (y == A2_right_y)
	return CGAL::EQUAL;
      if (y < A2_right_y)
	return CGAL::SMALLER;
      return CGAL::LARGER;
    }
      
  }

  template < class CK >
  Comparison_result 
  compare_y_to_right(const typename CK::Line_arc_2 &A1,
		     const typename CK::Circular_arc_2 &A2, 
		     const typename CK::Circular_arc_point_2 &p)
  {
    //CGAL_kernel_precondition (A2.is_x_monotone());
    if(A1.supporting_line().is_vertical())
      return CGAL::LARGER;

    typedef typename CK::Polynomial_1_2          Polynomial_1_2;
    typedef typename CK::Root_of_2               Root_of_2;

    const typename CK::Circle_2 & C2 = A2.supporting_circle();

    Root_of_2 b2_y = C2.center().y() - p.y();

    int s_b2_y = CGAL::sign(b2_y);

    if (s_b2_y == 0) {
      // Vertical tangent for A1.
      return A2.on_upper_part() ? CGAL::SMALLER : CGAL::LARGER;
    }

    typename CK::Root_of_2 b2_x = C2.center().x() - p.x();

    Root_of_2 tangent_2_x;
    Root_of_2 tangent_2_y;
    if (b2_y < 0){
       tangent_2_x = -b2_y;
       tangent_2_y = b2_x;
    }
    else{
      tangent_2_x = b2_y;
      tangent_2_y = -b2_x;
    }

    Polynomial_1_2 equation = 
      CGAL::LinearFunctors::get_equation<CK>(A1.supporting_line());
    typedef typename CK::FT FT;
    FT tangent_1_x;
    FT tangent_1_y;
    if (equation.b() < 0){
      tangent_1_x = -equation.b();
      tangent_1_y = equation.a();
    }
    else{
      tangent_1_x = equation.b();
      tangent_1_y = -equation.a();
    }
      


    if (((tangent_1_x < 0) && (tangent_2_x > 0)) || 
	((tangent_1_x > 0) && (tangent_2_x < 0))){
      Root_of_2 prod_left = tangent_1_y * tangent_2_x;
      Root_of_2 prod_right = tangent_2_y * tangent_1_x;
      if (prod_left < prod_right){
	return CGAL::LARGER;
      }
      if (prod_left == prod_right){
	return  A2.on_upper_part() ? CGAL::LARGER : CGAL::SMALLER;
      }
      return CGAL::SMALLER;
    }
    else{
      Root_of_2 prod_left = tangent_1_y * tangent_2_x;
      Root_of_2 prod_right = tangent_2_y * tangent_1_x;
      if (prod_left < prod_right){
	return CGAL::SMALLER;
      }
      if (prod_left == prod_right){
	return A2.on_upper_part() ? CGAL::LARGER : CGAL::SMALLER;
      }
      return CGAL::LARGER;
    }
  }

  
  template < class CK >
  Comparison_result 
  compare_y_to_left(const typename CK::Line_arc_2 &A1,
		    const typename CK::Circular_arc_2 &A2, 
		    const typename CK::Circular_arc_point_2 &p)
  {
    //CGAL_kernel_precondition (A2.is_x_monotone());
    if(A1.supporting_line().is_vertical())
      return CGAL::LARGER;

    typedef typename CK::Polynomial_1_2          Polynomial_1_2;
    typedef typename CK::Root_of_2               Root_of_2;

    const typename CK::Circle_2 & C2 = A2.supporting_circle();

    Root_of_2 b2_y = C2.center().y() - p.y();

    int s_b2_y = CGAL::sign(b2_y);

    if (s_b2_y == 0) {
      return A2.on_upper_part() ? CGAL::SMALLER : CGAL::LARGER;
    }

    typename CK::Root_of_2 b2_x = C2.center().x() - p.x();

    Root_of_2 tangent_2_x;
    Root_of_2 tangent_2_y;
    if (b2_y < 0){ 
       tangent_2_x = -b2_y;
       tangent_2_y = b2_x;
    }
    else{
      tangent_2_x = b2_y;
      tangent_2_y = -b2_x;
    }

    Polynomial_1_2 equation = 
      CGAL::LinearFunctors::get_equation<CK>(A1.supporting_line());
    typedef typename CK::FT FT;
    FT tangent_1_x;
    FT tangent_1_y;
    if (equation.b() < 0){
      tangent_1_x = -equation.b();
      tangent_1_y = equation.a();
    }
    else{
      tangent_1_x = equation.b();
      tangent_1_y = -equation.a();
    }
      


    if (((tangent_1_x < 0) && (tangent_2_x > 0)) || 
	((tangent_1_x > 0) && (tangent_2_x < 0))){
      Root_of_2 prod_left = tangent_1_y * tangent_2_x;
      Root_of_2 prod_right = tangent_2_y * tangent_1_x;
      if (prod_left < prod_right){
	return CGAL::SMALLER;
      }
      if (prod_left == prod_right){
	return  A2.on_upper_part() ? CGAL::LARGER : CGAL::SMALLER;
      }
      return CGAL::LARGER;
    }
    else{
      Root_of_2 prod_left = tangent_1_y * tangent_2_x;
      Root_of_2 prod_right = tangent_2_y * tangent_1_x;
      if (prod_left < prod_right){
	return CGAL::LARGER;
      }
      if (prod_left == prod_right){
	      return A2.on_upper_part() ? CGAL::LARGER : CGAL::SMALLER;
      }
      return CGAL::SMALLER;
    }
  }

 
  template < class CK >
  Comparison_result 
  compare_y_to_right(const typename CK::Circular_arc_2 &A1,
		     const typename CK::Line_arc_2 &A2, 
		     const typename CK::Circular_arc_point_2 &p)
  {
    if (compare_y_to_right<CK>(A2, A1, p) == CGAL::LARGER)
      return CGAL::SMALLER;
    return CGAL::LARGER;
  }

   
  template < class CK >
  void
  split(const typename CK::Line_arc_2 &A,
	const typename CK::Circular_arc_point_2 &p,
	typename CK::Line_arc_2 &ca1,
	typename CK::Line_arc_2 &ca2)
  {   
    CGAL_kernel_precondition( has_on<CK>(A, p));
   
    typedef typename CK::Line_arc_2  Line_arc_2;

    ca1 = Line_arc_2( A.supporting_line(), A.source(), p);
    ca2 = Line_arc_2( A.supporting_line(), p, A.target());