trapezoidal_decomposition_2.h

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

	{
#ifndef CGAL_TD_DEBUG
      
	  CGAL_precondition(curr);
	  CGAL_warning((!tr.is_left_unbounded() &&
                    traits->equal_2_object()(tr.left(), fixed)) ||
                   (!tr.is_right_unbounded() &&
                    traits->equal_2_object()(tr.right(), fixed)));
      
#else
      
	  CGAL_precondition(curr);
	  CGAL_precondition((!tr.is_left_unbounded() &&
                         traits->equal_2_object()(tr.left(),fixed)) ||
                        (!tr.is_right_unbounded() &&
                         traits->equal_2_object()(tr.right(),fixed)));
      
#endif
	  if (!tr.is_left_unbounded() &&
          traits->equal_2_object()(tr.left(),fixed))
	    tr.set_lb(operator->());
	  else
	    tr.set_rt(operator->());
	  if (is_right_rotation())
	    curr->set_rt(&tr);
	  else
	    curr->set_lb(&tr);
	}
	/* precondition:
	   curr!=NULL
	*/
	void remove()
	{
      
#ifndef CGAL_TD_DEBUG
      
	  CGAL_precondition(curr);
	  CGAL_warning( ( !curr->is_left_unbounded() &&
                      traits->equal_2_object()(curr->left(), fixed) ) ||
                    ( !curr->is_right_unbounded() &&
                      traits->equal_2_object()(curr->right(), fixed) ) );
      
#else
      
	  CGAL_precondition(curr);
	  CGAL_warning( ( !curr->is_left_unbounded() &&
                      traits->equal_2_object()(curr->left(),fixed) ) ||
                    ( !curr->is_right_unbounded() &&
                      traits->equal_2_object()(curr->right(),fixed) ) );
      
#endif
      
	  Around_point_circulator old=*this;
	  old++;
	  pointer next=old.operator->();
	  // handle 1-cycle and 2-cycles seperately
	  if (curr!=next)
      {
      }
	  // 2-cycle
	  else if (*this!=old)
      {
        next=curr;
      }
	  // 1-cycle
	  else
      {
        if (is_right_rotation())
          curr->set_rt(0);
        else
          curr->set_lb(0);
        curr=0;
        return;
      }
	  if (is_right_rotation())
	    curr->set_rt(next);
	  else
	    curr->set_lb(next);
	  if (old.is_right_rotation())
	    old[0]->set_rt(0);
	  else
	    old[0]->set_lb(0);
	}
	void replace(reference tr)
	{
      
#ifndef CGAL_TD_DEBUG
      
	  CGAL_precondition(curr);
	  CGAL_warning((!curr->is_left_unbounded() &&
                    traits->equal_2_object()(curr->left(),fixed)) ||
                   (!curr->is_right_unbounded() &&
                    traits->equal_2_object()(curr->right(),fixed)));
      
#else
      
	  CGAL_precondition(curr);
	  CGAL_precondition((!curr->is_left_unbounded() &&
                         traits->equal_2_object()(curr->left(),fixed)) ||
                        (!curr->is_right_unbounded() &&
                         traits->equal_2_object()(curr->right(),fixed)));
      
#endif
      
	  Around_point_circulator old=*this;
	  old++;
	  pointer next=old.operator->();
	  // handle 1-cycle and 2-cycles seperately
	  if (curr!=next)
      {
      }
	  // 2-cycle
	  else if (*this!=old)
      {
        next=curr;
      }
	  // 1-cycle
	  else
      {
        curr=&tr;
        if (is_right_rotation())
          curr->set_rt(curr);
        else
          curr->set_lb(curr);
        return;
      }
	  if (!tr.is_right_unbounded()&&traits->equal_2_object()(tr.right(),fixed))
	    tr.set_rt(next);
	  else
	    tr.set_lb(next);
	  if (is_right_rotation())
	    curr->set_rt(&tr);
	  else
	    curr->set_lb(&tr);
	}
	bool is_right_rotation() const
	{
	  return !curr->is_right_unbounded() &&
	    traits->equal_2_object()(curr->right(),fixed);
	}
	const Point& fixed_point() const
    {
      return fixed;
    }
  };
  //////////////////////////////////////////////
  //Trapezoidal_decomposition_2 member functions:
  //////////////////////////////////////////////
  
#ifndef CGAL_TD_DEBUG
  
protected:

#else

public:

#endif

  /* input: X_curve,
     two Trapezoidal maps that corespond the the
     X_curve's source degenerate trapezoid and the
     X_curve's target degenerate trapezoid
     output: trapezoid iterator

     Description:
     the output (trapezoid iterator) is initialized with 
     the leftmost and rightmost
     (non degenerate) trapezoids in the trapezoid interval that corresponds 
     to the input from either the top side or the bottom side, 
     depending on the up flag.
     preconditions:
     There exist non degenerate trapezoids between the roots of the input DS's
  */
  In_face_iterator follow_curve(const Data_structure& left_end_point,
                                const X_curve& cv,
                                Comparison_result up) const
  {

#ifndef CGAL_TD_DEBUG

    CGAL_warning(traits);
    CGAL_warning(traits->is_degenerate_point(*left_end_point));
    if (!(traits->equal_2_object()
          (traits->construct_min_vertex_2_object()(cv),
           left_end_point->left())))
    {
      CGAL_warning(traits->equal_2_object()
                   (traits->construct_min_vertex_2_object()(cv),
                    left_end_point->left()));
    }
    
#else
    
    CGAL_assertion(traits);
    CGAL_precondition(traits->is_degenerate_point(*left_end_point));
    CGAL_precondition(traits->equal_2_object()
                      (traits->construct_min_vertex_2_object()(cv),
                       left_end_point->left()));
    
#endif
    
    const Point& p1=left_end_point->left();
    Data_structure left=left_end_point.right();
    search_using_data_structure(left,traits,p1,&cv,up);
    return In_face_iterator(traits,cv,left.operator->());
  }
  
  /*
    input:
    X_trapezoid reference
    X_trapezoid pointer
    output:
    bool
    preconditions:
    the referenced trapezoid is to the right of the pointered trapezoid
    description:
    if the two input Trapezoids can be merged they are ,
    with one copy destroyed(the right one).
    postconfition:
    The reference points to the right trapezoid
    The returned value is true iff merging took place.
  */
  bool merge_if_possible(pointer left,pointer right)
  {
    if (left && right &&
	traits->trapezoid_top_curve_equal(*left,*right) &&
	traits->trapezoid_bottom_curve_equal(*left,*right) &&
	traits->equal_2_object()(left->right(),right->left()))
    {
      left->merge_trapezoid(*right);

#ifdef CGAL_TD_DEBUG
      CGAL_assertion(left->is_right_unbounded()==right->is_right_unbounded());
#endif

      return true;
    }
    return false;
  }
  
  /* Description:
     splits the trapezoid with vertical line through p */
  /* Precondition:
     The trapezoid is active and contains p in its closure */
  
  Data_structure& split_trapezoid_by_point(Data_structure& tt,
                                           const Point& p,
                                           const X_curve& cv_bottom_ray_shoot,
                                           const X_curve& cv_top_ray_shoot)
  {
    
#ifndef CGAL_TD_DEBUG
    
    CGAL_warning(!!tt);
    if (!tt)  return tt;
    
#else
    
    CGAL_precondition(!!tt);
    
#endif
    
    reference curr=*tt;
    pointer
	lb=curr.left_bottom_neighbour(),
	lt=curr.left_top_neighbour(),
	rb=curr.right_bottom_neighbour(),
	rt=curr.right_top_neighbour();
    
#ifndef CGAL_TD_DEBUG
    CGAL_warning(curr.is_active());
    CGAL_warning(traits->is_in_closure(curr,p));
#else
    CGAL_precondition(curr.is_active());
    if (!traits->is_in_closure(curr,p))
	{
	  std::cout << "\ncurr=";
	  write(std::cout,curr,*traits) << "\tp=" << p;
	}
    CGAL_precondition(traits->is_in_closure(curr,p));
#endif
    
    // left and right are set to the point itself,
    // bottom and top are set to the ray shooting resulting curves at this
    // stage.
    X_trapezoid sep(p,p,cv_bottom_ray_shoot,cv_top_ray_shoot);
    Data_structure leftDS =
      Data_structure(X_trapezoid(curr.left(), p,
                                 curr.bottom(),
                                 curr.top(),
                                 curr.boundedness() & (CGAL_TRAPEZOIDAL_DECOMPOSITION_2_LEFT_UNBOUNDED |
                                                       CGAL_TRAPEZOIDAL_DECOMPOSITION_2_BOTTOM_UNBOUNDED |
                                                       CGAL_TRAPEZOIDAL_DECOMPOSITION_2_TOP_UNBOUNDED)
                                 ));
    Data_structure rightDS =
      Data_structure(X_trapezoid(p, curr.right(),
                                 curr.bottom(),curr.top(),
                                 curr.boundedness()&(CGAL_TRAPEZOIDAL_DECOMPOSITION_2_RIGHT_UNBOUNDED |
                                                     CGAL_TRAPEZOIDAL_DECOMPOSITION_2_BOTTOM_UNBOUNDED |
                                                     CGAL_TRAPEZOIDAL_DECOMPOSITION_2_TOP_UNBOUNDED)
                                 ));
    
    reference left = *leftDS;
    reference right = *rightDS;
    
#ifndef CGAL_TD_DEBUG
    CGAL_warning(traits->trapezoid_top_curve_equal(left,right));
    CGAL_warning(traits->trapezoid_bottom_curve_equal(left,right));
    CGAL_warning(left.is_left_unbounded()==curr.is_left_unbounded());
    CGAL_warning(right.is_right_unbounded()==curr.is_right_unbounded());
#else
    CGAL_warning(traits->trapezoid_top_curve_equal(left,right));
    CGAL_warning(traits->trapezoid_bottom_curve_equal(left,right));
    CGAL_assertion(left.is_left_unbounded()==curr.is_left_unbounded());
    CGAL_assertion(right.is_right_unbounded()==curr.is_right_unbounded());
#endif
    
    if (!traits->is_degenerate_curve(curr))
	{
	  left.init_neighbours(lb,lt,&right,&right);
	  right.init_neighbours(&left,&left,rb,rt);
	  if (lb) lb->set_rb(&left);
	  if (lt) lt->set_rt(&left);
	  if (rb) rb->set_lb(&right);
	  if (rt) rt->set_lt(&right);
	}
    else
	{
	  left.set_bottom(cv_bottom_ray_shoot);
	  left.set_top(cv_bottom_ray_shoot);
	  right.set_bottom(cv_top_ray_shoot);
	  right.set_top(cv_top_ray_shoot);
	  left.set_rt(&right);
	  left.set_lb(lb);
	  left.set_rb(0);
	  right.set_lb(&left);
	  right.set_rt(rt);
	  right.set_rb(rb);
	}
    tt.replace(sep,leftDS,rightDS);
    const Data_structure
	*leftPtr=&tt.left(),
	*rightPtr=&tt.right();
    (*leftPtr)->set_node((Data_structure*)leftPtr);
    (*rightPtr)->set_node((Data_structure*)rightPtr);
    
#ifdef CGAL_TD_DEBUG    
    CGAL_assertion(&left==leftDS.operator->());
    CGAL_assertion(&right==rightDS.operator->());
    CGAL_assertion(left==*leftDS);
    CGAL_assertion(right==*rightDS);
    CGAL_assertion(left==*tt.left());
    CGAL_assertion(right==*tt.right());
    /*
      CGAL_assertion(left.get_node()==&tt.left());
      CGAL_assertion(right.get_node()==&tt.right());
    */
    CGAL_assertion(**left.get_node()==left);
    CGAL_assertion(**right.get_node()==right);    
#endif
    
    return tt;
  }
  
  /* Description:
     the opposite operation for spliting the trapezoid with 
     vertical line through p */
  /* Precondition:
     The root trapezoid is degenerate point (p) and is active */
  
  void remove_split_trapezoid_by_point(Data_structure& tt, const Point& p)
  {
    
#ifndef CGAL_TD_DEBUG
    
    if (!tt||
        !tt->is_active()||
        !traits->is_degenerate_point(*tt)||
        !traits->equal_2_object()(tt->left(),p))
    {
      CGAL_warning(!!tt);
      CGAL_warning(tt->is_active());
      CGAL_warning(traits->is_degenerate_point(*tt));
      CGAL_warning(traits->equal_2_object()(tt->left(),p));
      return;
    }
    
#else
    
    CGAL_precondition(!!tt);
    CGAL_precondition(tt->is_active());
    CGAL_precondition(traits->is_degenerate_point(*tt));
    CGAL_precondition(traits->equal_2_object()(tt->left(),p));
    
#endif
    
    Data_structure
      tt_left=tt.left(),
      tt_right=tt.right();
    
    search_using_data_structure(tt_left,traits,p,0);
    search_using_data_structure(tt_right,traits,p,0);

#ifndef CGAL_TD_DEBUG
    merge_if_possible(&*tt_left,&*tt_right);
    
    CGAL_warning(!tt_left.is_inner_node());
    CGAL_warning(!tt_right.is_inner_node());
    CGAL_warning(tt_left->is_right_unbounded() ==
                 tt_right->is_right_unbounded());

#else
    std::cout << "\nremove_split_trapezoid_by_point(){";
    std::cout << "\ntt_left=";
    write(std::cout,*tt_left,*traits);
    std::cout << "\ntt_right=";
    write(std::cout,*tt_right,*traits) << "}" << std::endl;

    bool merge_if_poss_left_right = merge_if_possible(&*tt_left,&*tt_right);

    std::cout << "\n->";
    write(std::cout,*tt_left,*traits) << std::endl;

    CGAL_postcondition(merge_if_poss_left_right);
    CGAL_assertion(!tt_left.is_inner_node());
    CGAL_assertion(!tt_right.is_inner_node());
    CGAL_assertion(tt_left->is_right_unbounded() ==