trapezoidal_decomposition_2.h

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

                   tt_right->is_right_unbounded());
    CGAL_assertion(**tt_left->get_node()==*tt_left);
#endif
    
    tt_right->remove(&tt_left);
    // mark root as deleted
    tt->remove();
  }
  
  /* Description:
     splits the trapezoid that corresponds to the root of the
     trapezoidal tree with an input edge cv*/
  /* Precondition:
     The root trapezoid is active
     cv is non degenerate
     The root trapezoid is devided by cv or
     is equal to it and is vertical.
  */
  Data_structure&
  split_trapezoid_by_curve(Data_structure& tt,
                           pointer& prev,
                           pointer& prev_bottom,
                           pointer& prev_top,
                           const X_curve& cv)
  {
    
#ifndef CGAL_TD_DEBUG
    
    CGAL_warning(traits);
    
#else
    
    CGAL_assertion(traits);
    
#endif
    
    reference currt=*tt;
    //Point p[2];
    //int i= CGAL_POINT_IS_LEFT_LOW(
    //  p[0]=traits->curve_source(cv),
    //  p[1]=traits->curve_target(cv)
    //  ) ? 0 : 1;
    //
    //// sets left and right accoring to curves source's and target's positions
    //// sets bottom and top to X_curve itself
    //X_trapezoid sep(p[i],p[1-i],cv,cv);

    //IDIT: change this according to the new traits, we already know which 
    //point is left and which is right
    X_trapezoid sep(traits->construct_min_vertex_2_object()(cv), 
                    traits->construct_max_vertex_2_object()(cv),
                    cv,
                    cv);

    /*
      creates a one-way path for all the X_curve-degenerate
      trapezoids that represent the X_curve.
      right_bottom_neighbour() is used to retrieve the
      next on path information
    */
    Data_structure
      topBT = Data_structure(X_trapezoid(currt.left(), currt.right(), cv,
                                         currt.top(),
                                         currt.boundedness() &
					   (CGAL_TRAPEZOIDAL_DECOMPOSITION_2_LEFT_UNBOUNDED |
					    CGAL_TRAPEZOIDAL_DECOMPOSITION_2_RIGHT_UNBOUNDED|
					    CGAL_TRAPEZOIDAL_DECOMPOSITION_2_TOP_UNBOUNDED))),
      bottomBT = Data_structure(X_trapezoid(currt.left(),currt.right(),
                                            currt.bottom(), cv,
                                            currt.boundedness() &
					    (CGAL_TRAPEZOIDAL_DECOMPOSITION_2_LEFT_UNBOUNDED|
                         CGAL_TRAPEZOIDAL_DECOMPOSITION_2_RIGHT_UNBOUNDED|
                         CGAL_TRAPEZOIDAL_DECOMPOSITION_2_BOTTOM_UNBOUNDED)));
    reference bottom=*bottomBT;
    reference top=*topBT;
    top.init_neighbours(prev_top, currt.left_top_neighbour(), 0,
                        currt.right_top_neighbour());
    bottom.init_neighbours(currt.left_bottom_neighbour(),
                           prev_bottom,currt.right_bottom_neighbour(),0);
    if (prev_bottom) prev_bottom->set_rt(&bottom);
    if (prev_top) prev_top->set_rb(&top);
    if (currt.left_bottom_neighbour())
      currt.left_bottom_neighbour()->set_rb(&bottom);
    if (currt.left_top_neighbour())
      currt.left_top_neighbour()->set_rt(&top);
    if (currt.right_bottom_neighbour())
      currt.right_bottom_neighbour()->set_lb(&bottom);
    if (currt.right_top_neighbour()) currt.right_top_neighbour()->set_lt(&top);
    tt.replace(sep,bottomBT,topBT);
    const Data_structure
      *bottomPtr=&tt.left(),
      *topPtr=&tt.right();
    (*bottomPtr)->set_node((Data_structure*)bottomPtr);
    (*topPtr)->set_node((Data_structure*)topPtr);
    if (prev) prev->set_rb(tt.operator->());
    prev_bottom=(*bottomPtr).operator->();
    prev_top=(*topPtr).operator->();
    prev=tt.operator->();
    return tt;
  }
  
  /* replace X_curve-point adjacency in the data structure with
     a new one
     precondition:
     the X_curve represented by t is top-right
     relative to the point represented by sep
     if and only if top=true
  */
  void replace_curve_at_point_using_geometry(reference t, reference sep,
					     bool cv_top_right=true)
  {
    Point p(sep.left());
    X_curve cv(t.top());
    Around_point_circulator circ(traits,p,cv_top_right ?
                                 sep.right_top_neighbour() :
                                 sep.left_bottom_neighbour());
    if (circ.operator->())
    {
      if (cv_top_right)
        while(traits->compare_cw_around_point_2_object ()
              (circ->top(), CGAL_CURVE_IS_TO_RIGHT(circ->top(),p),
               cv, CGAL_CURVE_IS_TO_RIGHT(cv,p), p) != EQUAL)
          circ++;
      else
        while(traits->compare_cw_around_point_2_object()
              (circ->bottom(), CGAL_CURVE_IS_TO_RIGHT(circ->bottom(),p),
               cv, CGAL_CURVE_IS_TO_RIGHT(cv,p), p, false) != EQUAL)
          circ++;
      circ.replace(t);
    }
  }

  void insert_curve_at_point_using_geometry(reference sep, reference end_point)
  {
    
#ifndef CGAL_TD_DEBUG
    
    CGAL_warning(traits);
    CGAL_warning(traits->is_degenerate_point(end_point));
    CGAL_warning(traits->is_degenerate_curve(sep));
    CGAL_warning(traits->equal_2_object()(end_point.left(),sep.right()) ||
                 traits->equal_2_object()(end_point.left(),sep.left()));
    
#else
    
    CGAL_assertion(traits);
    CGAL_precondition(traits->is_degenerate_point(end_point));
    CGAL_precondition(traits->is_degenerate_curve(sep));
    CGAL_precondition(traits->equal_2_object()(end_point.left(),sep.right()) ||
                      traits->equal_2_object()(end_point.left(),sep.left()));
    
#endif
    
    /* update (in this order)
       end_point.left_bottom_neighbour()
       if no curves adjacent to the point eminating toward up
       or right exist returns null, otherwise return
       the first X_curve sweeped using a counter clockwise sweep
       starting from up direction not including.
       end_point.right_top_neighbour()
       if no curves adjacent to the point eminating toward bottom
       or left exist returns null, otherwise return
       the first X_curve sweeped using a counter clockwise sweep
       starting from bottom direction not including.
       sep.right_top_neighbour()
       next clockwise degenerate_curve around rightmost end_point (possibly
       himself)
       sep.left_bottom_neighbour()
       next clockwise degenerate_curve around leftmost end_point (possibly
       himself)
    */
    const X_curve& cv=sep.top();
    const Point& p=end_point.left();
    pointer rt = end_point.right_top_neighbour(),
      lb = end_point.left_bottom_neighbour();
    if(!traits->equal_2_object()(end_point.left(),sep.right()))
    {
      if (!rt && !lb)
        // empty circulator
	  {
	    end_point.set_rt(&sep);
	    sep.set_lb(&sep);
	  }
      else
	  {
	    /* set circ[0] to first X_curve on a counter clockwise 
	       sweep starting at cv */
	    Around_point_circulator circ(traits,p,rt ? rt : lb),stopper=circ;
	    // if !rt set circ to lb
	    // otherwise advance as required
#ifdef CGAL_TD_DEBUG
        
	    Around_point_circulator first_circ(circ);
        
#endif
        
	    while (traits->compare_cw_around_point_2_object ()
               (circ->top(), CGAL_CURVE_IS_TO_RIGHT(circ->top(),p),
                cv, CGAL_CURVE_IS_TO_RIGHT(cv,p), p) == SMALLER)
        {
          circ++;
          if (circ==stopper)
            break;
          
#ifdef CGAL_TD_DEBUG
          
          CGAL_assertion(first_circ!=circ);
          CGAL_assertion(circ->is_active());
          
#endif
          
        }
        
#ifdef CGAL_TD_DEBUG
        
	    CGAL_assertion(traits->compare_cw_around_point_2_object()
                       (circ->top(), CGAL_CURVE_IS_TO_RIGHT(circ->top(),p),
                        cv, CGAL_CURVE_IS_TO_RIGHT(cv,p), p) != EQUAL);
#endif
        
	    circ.insert(sep);
	    // set end_point.left_bottom_neighbour()
	    // set end_point.right_top_neighbour();
	    if (lb)
        {
          Around_point_circulator lb_circ(traits,p,lb);
          if (!rt) end_point.set_rt(lb);
          if (lb_circ.operator->()==&sep) end_point.set_lb(&sep);
        }
	    else
        {
          if (traits->compare_cw_around_point_2_object()
              (rt->top(), CGAL_CURVE_IS_TO_RIGHT(rt->top(),p),
               cv, CGAL_CURVE_IS_TO_RIGHT(cv,p),
               p, false) == SMALLER)
            end_point.set_rt(&sep);
        }
	  }
    }
    else
    {
      if (!rt && !lb)
	  // empty circulator
	  {
	    end_point.set_lb(&sep);
	    sep.set_rt(&sep);
	  }
      else
	  {
	    /* set circ[0] to first X_curve on a counter clockwise 
	       sweep starting at cv */
	    Around_point_circulator circ(traits,p,lb ? lb : rt),stopper=circ;
	    // if !lb set circ to rt
	    // otherwise advance as required
	    while (traits->compare_cw_around_point_2_object()
               (circ->top(), CGAL_CURVE_IS_TO_RIGHT(circ->top(),p),
                cv, CGAL_CURVE_IS_TO_RIGHT(cv,p), p, false) == SMALLER)
        {
          circ++;
          if (circ==stopper)
            break;
        }
        
#ifdef CGAL_TD_DEBUG
        
	    CGAL_assertion(traits->compare_cw_around_point_2_object()
                       (circ->top(), CGAL_CURVE_IS_TO_RIGHT(circ->top(),p),
                        cv, CGAL_CURVE_IS_TO_RIGHT(cv,p), p, false) != EQUAL);
#endif
        
	    circ.insert(sep);
	    if (rt)
	      // set end_point.left_bottom_neighbour()
        {
          Around_point_circulator rt_circ(traits,p,rt);
          if (!lb) end_point.set_lb(rt);
          if (rt_circ.operator->()==&sep) end_point.set_rt(&sep);
        }
	    else
        {
          // set end_point.right_top_neighbour();
          if(traits->compare_cw_around_point_2_object()
             (lb->top(), CGAL_CURVE_IS_TO_RIGHT(lb->top(),p),
              cv, CGAL_CURVE_IS_TO_RIGHT(cv,p), p) ==SMALLER)
            end_point.set_lb(&sep);
        }
	  }
    }
  }
  /*
    description:
    Update top(),bottom() for trapezoid
    Update rt,lb
    remarks:
    The point degenerate trapezoid representing a point p holds as its top and
    bottom curves
    the output for a vertical ray shoot quiries immidiately below the point
    toward up and
    immediately above the point toward down respectively.
    optimization:
    Each degenerate X_curve trapezoid eminating from the point p holds a pointer
    to the next
    trapezoid in a clockwise sweep around p(possibly to itself).
    This pointer is stored in rt or lb depending on the trapezoid is top right
    or bottom left of p.
    For the trapezoid representing p rt and lb hold the previous X_curve
    degenerate trapezoid
    in a clockwise sweep to the first top right and bottom left respectively.
  */
  
  void remove_curve_at_point_using_geometry(const_ref sep,reference end_point)
  {
    
#ifndef CGAL_TD_DEBUG
    
    CGAL_warning(traits);
    CGAL_warning(traits->is_degenerate_point(end_point));
    CGAL_warning(traits->is_degenerate_curve(sep));
    CGAL_warning(traits->equal_2_object()(end_point.left(),sep.right()) ||
                 traits->equal_2_object()(end_point.left(),sep.left()));
    CGAL_warning(end_point.is_active());
    CGAL_warning(sep.is_active());
    
#else
    
    CGAL_assertion(traits);
    CGAL_precondition(traits->is_degenerate_point(end_point));
    CGAL_precondition(traits->is_degenerate_curve(sep));
    CGAL_precondition(traits->equal_2_object()(end_point.left(),sep.right()) ||
                      traits->equal_2_object()(end_point.left(),sep.left()));
    CGAL_precondition(end_point.is_active());
    CGAL_precondition(sep.is_active());
    
#endif
    
    /* update (in this order)
       end_point.left_bottom_neighbour()
       if no curves adjacent to the point eminating toward up
       or right exist returns null, otherwise return
       the first X_curve sweeped using a counter clockwise sweep
       starting from up direction not including.
       end_point.right_top_neighbour()
       if no curves adjacent to the point eminating toward bottom
       or left exist returns null, otherwise return
       the first X_curve sweeped using a counter clockwise sweep
       starting from bottom direction not including.
       sep.right_top_neighbour()
       next clockwise degenerate_curve around rightmost end_point (possibly
       himself)
       sep.left_bottom_neighbour()
       next clockwise degenerate_curve around leftmost end_point (possibly
       himself)
    */
    const X_curve& cv=sep.top();
    const Point& p=end_point.left();
    Around_point_circulator
      prev_top(traits,p,end_point.right_top_neighbour()),
      prev_bottom(traits,p,end_point.left_bottom_neighbour());
    
    // update bottom
    if(traits->equal_2_object()(cv,end_point.bottom()))
    {
      Around_point_circulator bottom=(!!prev_bottom) ? prev_bottom : prev_top;
      bottom++;
      
#ifdef CGAL_TD_DEBUG
      
      CGAL_assertion(!!bottom);
      
#endif
      
      if (!bottom->is_bottom_unbounded())
        end_point.set_bottom(bottom->bottom());
      else
        end_point.set_bottom_unbounded();
    }
    // update top
    if(traits->equal_2_object()(cv,end_point.top()))
    {
      Around_point_circulator top=(!!prev_top) ? prev_top : prev_bottom;
      top++;
      
#ifdef CGAL_TD_DEBUG
      
      CGAL_assertion(!!top);
      
#endif
      
      if (!top->is_top_unbounded())
        end_point.set_top(top->top());
      else
        end_point.set_top_unbounded();
    }
    
    //update right top neighbour and left bottom neighbour
    bool b=CGAL_POINT_IS_LEFT_LOW(p,sep.right());
    Around_point_circulator circ(traits,p,b ? end_point.right_top_neighbour() :
                                 end_point.left_bottom_neighbour());
    
#ifdef CGAL_TD_DEBUG
    
    CGAL_precondition(!!circ);
    
#endif
    
    while(*circ!=sep)circ++;
    pointer removed=circ.operator->();
    circ.remove();
    if(!!circ)
    {
      pointer effective_curr=circ[0];
      if (end_point.right_top_neighbour()==removed)
        end_point.set_rt(effective_curr);
      if (end_point.left_bottom_neighbour()==removed)
        end_point.set_lb(effective_curr);
      Around_point_circulator rt_circ(traits, p,
                                      end_point.right_top_neighbour());
      if (!!rt_circ)
	  {
	    rt_circ++;
	    if (rt_circ.is_right_rotation())
	      end_point.set_rt(0);
	  }
      Around_point_circulator lb_circ(traits, p,
                                      end_point.left_bottom_neighbour());
      if (!!lb_circ)
	  {
	    lb_circ++;