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/Circular_arc_2.h $
// $Id: Circular_arc_2.h 36189 2007-02-11 22:37:08Z 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)
#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
#define CGAL_USEFUL_MAPS_FOR_THE_CIRCULAR_KERNEL
#endif

#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES
#define CGAL_USEFUL_MAPS_FOR_THE_CIRCULAR_KERNEL
#endif

#ifndef CGAL_CIRCULAR_KERNEL_CIRCULAR_ARC_2_H
#define CGAL_CIRCULAR_KERNEL_CIRCULAR_ARC_2_H

#include <CGAL/global_functions_on_circular_arcs_2.h>
#include <CGAL/Circular_kernel_2/internal_functions_on_circular_arc_2.h> // temporarily

#ifdef CGAL_USEFUL_MAPS_FOR_THE_CIRCULAR_KERNEL
#include <CGAL/Circular_kernel_2/intersection_line_2_circle_2_map.h>
#endif

#include <CGAL/intersections.h>

namespace CGAL {
namespace CGALi {

  template <class CK >
  class Circular_arc_2
  {
    typedef typename CK::FT                        FT;
    typedef typename CK::RT                        RT;
    typedef typename CK::Point_2                   Point_2;
    typedef typename CK::Line_2                    Line_2;
    typedef typename CK::Circle_2                  Circle_2;
    typedef typename CK::Circular_arc_point_2      Circular_arc_point_2;
    typedef typename CK::Root_of_2                 Root_of_2;
    typedef struct bit_field {
      unsigned short int is_full:2;
      unsigned short int is_x_monotonic:2;
      unsigned short int is_y_monotonic:2;
      unsigned short int two_end_points_on_upper_part:2;
      unsigned short int two_end_points_on_left_part:2;
      unsigned short int is_complementary_x_monotone:1;
      unsigned short int is_complementary_y_monotone:1;
    } bit_field;
  
#ifdef CGAL_USEFUL_MAPS_FOR_THE_CIRCULAR_KERNEL
  public:
    typedef CGALi::Intersection_line_2_circle_2_map Table;
#endif

  private:

  // set flags to 0
  // when 1 bit -> 0 = false, 1 = true
  // when 2 bits -> 0 = don_know, 1 = false
  //                              2 = true
  void reset_flags() const {
    flags.is_full = 0;
    flags.is_x_monotonic = 0;
    flags.is_y_monotonic = 0;
    flags.two_end_points_on_upper_part = 0;
    flags.two_end_points_on_left_part = 0;
    flags.is_complementary_x_monotone = 0;
    flags.is_complementary_y_monotone = 0;
  }

  public:

    Circular_arc_2() 
#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES
    : id_of_my_supporting_circle(0) 
#endif
   {
      reset_flags();           // example

#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
      _get_id_number();
#endif

    }

    Circular_arc_2(const Circle_2 &c)
      : _support(c)
#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES 
      , id_of_my_supporting_circle(0)
#endif
    {
      reset_flags();           // example

#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
      _get_id_number();
#endif

      flags.is_full = 2;       // is_full = true
      _begin = _end  = 
	CircularFunctors::x_extremal_point<CK>(supporting_circle(),true); 
    }

    Circular_arc_2(const Circle_2 &support,
                   const Line_2 &l1, bool b1,
                   const Line_2 &l2, bool b2)
    {
      Point_2 center1 (support.center().x() + l1.a()/2,
                       support.center().y() + l1.b()/2);

      FT sqr1 = support.squared_radius() + l1.c()
	        - CGAL::square(support.center().x())
	        - CGAL::square(support.center().y())
	        + CGAL::square(center1.x())
	        + CGAL::square(center1.y());

      Circle_2 c1 (center1, sqr1);
      
      Point_2 center2 (support.center().x() + l2.a()/2,
                       support.center().y() + l2.b()/2);

      FT sqr2 = support.squared_radius() + l2.c()
	        - CGAL::square(support.center().x())
	        - CGAL::square(support.center().y())
	        + CGAL::square(center2.x())
	        + CGAL::square(center2.y());

      Circle_2 c2 (center2, sqr2);
      
      *this = Circular_arc_2(support, c1, b1, c2, b2);

      CGAL_kernel_assertion(do_intersect(support, c1));
      CGAL_kernel_assertion(do_intersect(support, c2));
    }


    Circular_arc_2(const Circle_2 &c,
		   const Circle_2 &c1, const bool b_1,
		   const Circle_2 &c2, const bool b_2)
      : _support(c)
#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES 
      , id_of_my_supporting_circle(0)
#endif
    {
      reset_flags();

#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
      _get_id_number();
#endif

      if (c1 != c2) {
	_begin = CGAL::circle_intersect<CK>(c, c1, b_1);
	_end = CGAL::circle_intersect<CK>(c, c2, b_2);
      }
      else{
	typedef std::vector<CGAL::Object > solutions_container;
	
	solutions_container solutions;
	CGAL::intersect_2<CK>( c, c1, std::back_inserter(solutions) );
	typename solutions_container::iterator it = solutions.begin();

	CGAL_kernel_precondition( it != solutions.end() );
	// the circles intersect
	
	const std::pair<typename CK::Circular_arc_point_2, unsigned> *result;
	result = CGAL::object_cast<
	  std::pair<typename CK::Circular_arc_point_2, unsigned> > (&(*it));
	if ( result->second == 2 ){ // double solution
	  _begin =  result->first;
	  _end = result->first;
	}
	else{
	  if (b_1)
	    _begin = result->first;
	  if (b_2)
	    _end = result->first;
	  if (!(b_1 & b_2)) {
	    ++it;
	    result = CGAL::object_cast<
	      std::pair<typename CK::Circular_arc_point_2, unsigned> >(&(*it));
	    if (!b_1)
	      _begin = result->first;
	    if (!b_2)
	      _end = result->first;
	  }
	}
      }
    }

    // IS THIS CONSTRUCTOR USED ?
    // constructs a circular arc that is the arc included in A
    // having same (b) endpoint as A (true == _begin, false == _end)
    // but whose (!b) endpoint is the intersection of A with ccut given 
    // by b_cut
    Circular_arc_2(const Circular_arc_2 &A, const bool b,
		   const Circle_2 &ccut, const bool b_cut)
      : _support(A.supporting_circle())
#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES 
      , id_of_my_supporting_circle(0)
#endif
    {
      reset_flags();

#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
      _get_id_number();
#endif

      CGAL_kernel_precondition(A.is_x_monotone());
      CGAL_kernel_precondition(do_intersect(A.supporting_circle(), ccut));
      
      Circular_arc_point_2 new_p =
	CGAL::circle_intersect<CK>(A.supporting_circle(), ccut, b_cut);
      
      // CGAL_kernel_assertion(point_in_range(A, new_p));
      CGAL_kernel_assertion
	(A.on_upper_part() == (CGAL::compare(new_p.y(), A.center().y()) >= 0));

      if (b) {
	_begin  = A._begin;
	_end    = new_p;
      }
      else {
	_begin  = new_p;
	_end    = A._end;
      }
    }

    // Constructs an arc supported by Circle_2(begin, middle, end),
    // with _begin == begin, _end == end.
    // (middle is not necessarily on the arc)
    Circular_arc_2(const Point_2 &begin,
                   const Point_2 &middle,
                   const Point_2 &end)
      : _begin(begin), _end(end)
#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES 
      , id_of_my_supporting_circle(0)
#endif
    {
      reset_flags();

#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
      _get_id_number();
#endif

      CGAL_kernel_precondition(!CGAL::collinear(begin, middle, end));
      _support = Circle_2(begin, middle, end);
      /*
       *  Circle_2 c = Circle_2(begin, middle, end);
       * Line_2   l1 (begin, middle);
      Line_2   l2 (middle, end);
      *this = Circular_arc_2(c, 
			     l1, compare_xy(begin, middle) < 0,
			     l2, compare_xy(end,   middle) < 0);*/
	  //std::cout << source() << std::endl;
	  //std::cout << target() << std::endl;
    }

    Circular_arc_2(const Circle_2 &support,
		   const Circular_arc_point_2 &source,
		   const Circular_arc_point_2 &target)
      : _begin(source), _end(target), _support(support)
#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES 
      , id_of_my_supporting_circle(0)
#endif
    {
      reset_flags();

#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
      _get_id_number();
#endif

      // We cannot enable these preconditions for now, since the 
      // Lazy_circular_kernel_2
      // calls it on the Interval kernel without try/catch protection
      // through the Circular_kernel_converter.
      // CGAL_kernel_exactness_precondition(CK().has_on_2_object()(support, source));
      // CGAL_kernel_exactness_precondition(CK().has_on_2_object()(support, target));
    }
    
    Circular_arc_2(const Point_2 &begin,
                   const Point_2 &end,
		   const FT &bulge)
      : _begin(begin), _end(end)
#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES 
      , id_of_my_supporting_circle(0)
#endif
    {
      reset_flags();

#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
      _get_id_number();
#endif

      const FT sqr_bulge = CGAL::square(bulge);
      const FT common = (FT(1) - sqr_bulge) / (FT(4)*bulge);
      const FT x_coord = (begin.x() + end.x())/FT(2)
	                 + common*(begin.y() - end.y());
      const FT y_coord = (begin.y() + end.y())/FT(2)
                          + common*(end.x() - begin.x());
      
      const FT sqr_rad = squared_distance(begin, end) 
	                 * (FT(1)/sqr_bulge + FT(2) + sqr_bulge) / FT(16); 

      _support = Circle_2(Point_2(x_coord, y_coord), sqr_rad);
    }
    
  private:
    // The arc goes from _begin to _end in the positive order
    // If _begin == _end, then it's the full circle
    Circular_arc_point_2  _begin, _end;
    Circle_2 _support;
    mutable bit_field flags;
#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
    unsigned int my_id; // the id of the arc
    // to optimize make_x_monotone and splits
    // so we have not echec de filtre for intersection
    static Table table;
#endif

  public:

#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
    template < class T >
    static bool find_intersection(const Circular_arc_2& c1, 
      const Circular_arc_2& c2, 
      T& res) {
      return table.find<T>(c1.my_id, c2.my_id, res);
    }

    template < class T >
    static void put_intersection(const Circular_arc_2& c1, 
      const Circular_arc_2& c2,
      const T& res) {
      table.put<T>(c1.my_id, c2.my_id, res);
    }
#endif

#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES 
    static Table circle_table;
    mutable unsigned int id_of_my_supporting_circle;

    template < class T >
    static bool find_intersection_circle_circle(
      const Circular_arc_2& c1, 
      const Circular_arc_2& c2, 
      T& res) {
      if(c1.id_of_my_supporting_circle == 0) return false;
      if(c2.id_of_my_supporting_circle == 0) return false;