trapezoidal_decomposition_2.h

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

      CGAL_assertion(tr_copy);
      tr_copy->set_rt(cur->get_rt() ? 
                      htr.find(cur->get_rt())->second : NULL);
      tr_copy->set_rb(cur->get_rb() ?
                      htr.find(cur->get_rb())->second : NULL);
      tr_copy->set_lt(cur->get_lt() ? 
                      htr.find(cur->get_lt())->second : NULL);
      tr_copy->set_lb(cur->get_lb() ? 
                      htr.find(cur->get_lb())->second : NULL);
      if (cur->get_node()->is_inner_node()) {
		child=&cur->get_node()->right();
		while (child && child->is_inner_node() && 
		       !pr(*(*child))) child=&child->left();
		tr_copy->get_node()->set_right(*child);
		child=&cur->get_node()->left();
		while (child && child->is_inner_node() && 
		       !pr(*(*child))) child=&child->left();
		tr_copy->get_node()->set_left(*child);
      }
      // Third iteration: generate links in-between trapezoids 
      //  and in-between nodes .
    }
    DS=htr.find(&*(*td.DS))->second->get_node();
  }
  /*
    TODO: Should we add another constructor with non const argument that 
    rebuild the trapezoidal decomposition prior to copy construction?
  */
  virtual ~Trapezoidal_decomposition_2()
  {
    
#ifndef CGAL_TD_DEBUG
    
    CGAL_warning(DS);
    if (!DS) return;
    
#else
    
    CGAL_assertion(DS);
    
#endif
    
    delete DS;
  }
  
  /*  Input:
      X_curve
      Output:
      if X_curve or twin already inserted the latter is returned.
      otherwise the left-low most edge-degenerate trapezoid that represents
      the input X_curve is returned
      Remark:
      Given an edge-degenerate trapezoid representing a X_curve,
      all the other trapezoids representing the X_curve can be  extracted
      via moving continously to the left and right neighbours.
  */
  X_trapezoid insert(curve_const_ref cv)
  {
#ifdef CGAL_TD_DEBUG
    *cv.get_parent();
#endif
    /*
      Point tmp;
      // maintaining some bounding box for future use.
    
      if (!number_of_curves_) 
      // give initiale values to  bounding points when empty
      {
      POINT_AT_LEFT_TOP_INFINITY=POINT_AT_RIGHT_BOTTOM_INFINITY=
      traits->curve_source(cv);
      }
    
      if (!CGAL_POINT_IS_LEFT_LOW(POINT_AT_LEFT_TOP_INFINITY,tmp=
      traits->construct_min_vertex_2_object()(cv)))
      POINT_AT_LEFT_TOP_INFINITY=traits->point_to_left(tmp);
      if (!traits->point_is_right_top(POINT_AT_RIGHT_BOTTOM_INFINITY,tmp=
      traits->construct_max_vertex_2_object()(cv)))
      POINT_AT_RIGHT_BOTTOM_INFINITY=traits->point_to_right(tmp);
    */
    return insert_in_face_interior(cv);
  }
  
  /* Input:
     X_curve
     Output:
     if X_curve or twin already inserted the latter is returned.
     otherwise the left-low most edge-degenerate trapezoid that represents the
     input X_curve is returned
     Remark:
     Given an edge-degenerate trapezoid representing a X_curve,
     all the other trapezoids representing the X_curve can be  extracted
     via moving continously to the left and right neighbours.
  */
  const X_trapezoid insert_in_face_interior(curve_const_ref cv)
  {
#ifdef CGAL_TD_DEBUG
    *cv.get_parent();
#endif
#ifdef CGAL_TDBB_DEBUG
    std::cout << "\ninsert_in_face_interior(" << cv << ")" 
              << "\nBbox " << traits->get_bounding_box();
#endif

#ifdef CGAL_TD_DEBUG
    std::cout << "\nTD::insert_in_face_interior(" << cv << ") called with "
              << (is_valid(*DS) ? "valid" : "invalid") << " data structure"
              <<  std::endl;
    write(std::cout,*DS,*traits) << std::endl;
#endif

    if (needs_update_) update();
    // locate the input X_curve end points in the X_trapezoid Dag

    CGAL_assertion(traits);
    
#ifndef CGAL_TD_DEBUG

    CGAL_warning(!traits->equal_2_object()
                 (traits->construct_min_vertex_2_object()(cv),
                  traits->construct_max_vertex_2_object()(cv)));
    
#else
    
    CGAL_precondition(!traits->equal_2_object()
                      (traits->construct_min_vertex_2_object()(cv),
                       traits->construct_max_vertex_2_object()(cv)));
    
#endif
    
    //Point p[2];

    //int i= CGAL_POINT_IS_LEFT_LOW(
    //  p[0]=traits->curve_source(cv),
    //  p[1]=traits->curve_target(cv)
    //  ) ? 0 : 1;
    
    //IDIT: change this according to the new traits, we already know which 
    //point is left and which is right
    Point p[2];
    p[0] = traits->construct_min_vertex_2_object()(cv);
    p[1] = traits->construct_max_vertex_2_object()(cv);
    int i = 0;
    //

    Locate_type lt1,lt2;
    pointer tr1,tr2;

#ifndef CGAL_NO_TRAPEZOIDAL_DECOMPOSITION_2_OPTIMIZATION
    
    locate_optimization(p[i],tr1,lt1);
    
#else
	  //location of the left endpoint of the curve we're inserting
    tr1=&locate(traits->construct_min_vertex_2_object(),lt1);
    
#endif
    
    //the inserted curve should not cut any existing curve
    if (lt1==CURVE)
    {
      CGAL_precondition_msg(lt1!=CURVE,"Input is not planar as\
        one of the input point inside previously inserted X_curve.");
      return X_trapezoid();
    }
    
    //if the curve starts at vertex, we should not insert it into the DAG, 
    //but we should update all the curves incident to the vertex. 
    //else if this is a new vertex- insert a node to the DAG that will represent the new vertex. 
    //the incident curves in this case is only the curve itself, and so it is a trivial operation.
    reference t_p1=
      (lt1==POINT) ?
      insert_curve_at_point_using_geometry(cv,p[i],tr1,lt1) :
      insert_curve_at_point_using_data_structure(cv,p[i],tr1,lt1);
    
#ifndef CGAL_NO_TRAPEZOIDAL_DECOMPOSITION_2_OPTIMIZATION
    
    locate_optimization(p[1-i],tr2,lt2);
    locate_opt_empty();
    
#else
    //TODO(oren): locating the second endpoint. this is not necessary, and time consuming. 
    tr2=&locate(p[1-i],lt2);
    
#endif
    
    if (lt2==CURVE)
    {
      CGAL_precondition_msg(lt2!=CURVE,"Input is not planar as\
        one of the input point inside previously inserted X_curve.");
      return X_trapezoid();
    }
    
    reference t_p2= (lt2==POINT) ?
      insert_curve_at_point_using_geometry(cv,p[1-i],tr2,lt2) :
      insert_curve_at_point_using_data_structure(cv,p[1-i],tr2,lt2);
    
    // locate and insert end points of the input X_curve to the X_trapezoid
    // Dag if needed
    Data_structure tt_p1(*t_p1.get_node());
    Data_structure tt_p2(*t_p2.get_node());
    
    // create the X_trapezoid iterator for traveling along the Trapezoids that
    // intersect the input X_curve, using left-low to right-high order
    In_face_iterator it=follow_curve(tt_p1,cv,LARGER);
    pointer curr,prev=&t_p1,prev_bottom,prev_top;
    pointer old_output = it.operator->(), old_top = 0, old_bottom = 0;
    
#ifndef CGAL_TD_DEBUG

    CGAL_warning(!traits->is_degenerate(*old_output));

#else
    
    CGAL_assertion(!traits->is_degenerate(*old_output));
    
#endif
    
    old_output=0;
    Data_structure *tt;
    bool first_time=true;
    while(!!it) //this means as long as the iterator is valid
    {
      curr=it.operator->();
      prev_bottom=curr->left_bottom_neighbour();
      prev_top=curr->left_top_neighbour();
      // pass using it along cv
      it++; //this is the logic of the iterator. the iterator goes to the next trapezoid right-high.
      tt = curr->get_node();
      if(first_time)
      {
        
#ifndef CGAL_TD_DEBUG
        
        if(!curr->is_top_unbounded()&&traits->equal_2_object()(curr->top(),cv))
        {
          CGAL_warning(!traits->equal_2_object()(curr->top(),cv));
          return X_trapezoid();
        }
        
#else
        
        CGAL_precondition(curr->is_top_unbounded()||
                          !traits->equal_2_object()(curr->top(),cv));
        
#endif
        
      }
      split_trapezoid_by_curve(*tt,old_output, old_bottom, old_top, cv);
      
#ifdef CGAL_TD_DEBUG
      
      CGAL_assertion(traits->equal_2_object()((**tt).top(),cv));
      
#endif
      
      if(first_time)
      {
        insert_curve_at_point_using_geometry(*old_output,t_p1);
        first_time=false;
      }
      if (tt->is_inner_node())
      {
        // merge adjacent trapezoids on input X_curve's bottom side if possible
        if(merge_if_possible(prev_bottom,
                             tt->left().operator->()))
        {
          tt->set_left(*(prev_bottom->get_node()));
          old_bottom = prev_bottom;
        }
        // merge adjacent trapezoids on input X_curve's top side if possible
        if(merge_if_possible(prev_top,
                             tt->right().operator->()))
        {
          tt->set_right(*(prev_top->get_node()));
          old_top=prev_top;
        }
        
        // update trapezoid's left/right neighbouring relations
        if(!traits->is_degenerate(*prev) &&
           !traits->is_degenerate(*curr))
        {
          curr->set_lb(prev);
          curr->set_lt(prev);
          prev->set_rb(curr);
          prev->set_rt(curr);
        }
      }
      else
      {
        
#ifdef CGAL_TD_DEBUG
        
        CGAL_assertion(curr->is_valid(traits));
        
#endif
        
        break;
      }
      
#ifdef CGAL_TD_DEBUG
      
      CGAL_assertion(curr->is_valid(traits));
      
#endif
      
    }
    
#ifdef CGAL_TD_DEBUG
    
    CGAL_postcondition(traits->is_degenerate_curve(*old_output));
    CGAL_postcondition(traits->equal_2_object()
                       ((const X_curve)old_output->top(),
                        cv));
    
#endif
    
    insert_curve_at_point_using_geometry(*old_output,t_p2);
    number_of_curves_++;
    
#ifdef CGAL_TD_DEBUG
    write(std::cout,*DS,*traits) << std::endl;
    std::cout << "\nTD::insert_in_face_interior() exited with data structure" 
              << is_valid(*DS) << std::endl;
#endif
    
    return *old_output;
  }

  // removal functions

  void remove(curve_const_ref cv)
	// We assume here that the input curves are in planar position.
  {
    remove_in_face_interior(cv);
  }

  template <class curve_iterator>
  void remove(curve_iterator begin, curve_iterator end)
  {
    if(begin == end)
      return;
    
    std::random_shuffle(begin,end);
    
    curve_iterator it=begin,next=it;
    while(it!=end) {++next;remove(*it);it=next;}
  }

  void clear()
  {
    delete DS;
    init();
  }

  void remove_in_face_interior(curve_const_ref cv)
	// Assumes the map to be planar.
  {

#ifdef CGAL_TD_DEBUG
    std::cout << "\nTD::remove_in_face_interior(" << cv << ") called with "
              << (is_valid(*DS) ? "valid" : "invalid") << " data structure"
              <<  std::endl;
    write(std::cout,*DS,*traits) << std::endl;
#endif

    if (needs_update_) update();
    
#ifndef CGAL_NO_TRAPEZOIDAL_DECOMPOSITION_2_OPTIMIZATION
    locate_opt_empty();
#endif
    
#ifndef CGAL_TD_DEBUG
    CGAL_warning(traits);
#else
    CGAL_assertion(traits);
#endif
    
    // calculating leftmost and rightmost points of X_curve cv
    Point
      leftmost=traits->construct_min_vertex_2_object()(cv),
      rightmost=traits->construct_max_vertex_2_object()(cv);
    Locate_type lt1,lt2;
    reference
      t1=locate(leftmost,lt1),
      t2=locate(rightmost,lt2);
    
    CGAL_warning(lt1==POINT && lt2==POINT);
    if (!(lt1==POINT && lt2==POINT)) return;
    
#ifndef CGAL_TD_DEBUG
    
    CGAL_warning(t1.get_node());
    CGAL_warning(t2.get_node());
    
#endif
    
    Data_structure
      &tt1=*t1.get_node(),
      &tt2=*t2.get_node();

    /* calculate the immediate lower central and upper neighbourhood of
     * the curve in the data structure
     */
    In_face_iterator
      bottom_it(follow_curve(tt1,cv,SMALLER)),
      mid_it(follow_curve(tt1,cv,EQUAL)),
      top_it(follow_curve(tt1,cv,LARGER));
    
    bool bottom, old_bottom = false, end_reached;
    map_nodes new_array;
    int last_index[]={0,0};
    int sz=0;
    Point left=bottom_it->left(),right;
    pointer last_bottom,last_top,last=0,old;
    
#ifndef CGAL_TD_DEBUG
    CGAL_warning(traits->equal_2_object()(top_it->left(),left));
#else
    CGAL_precondition(traits->equal_2_object()(top_it->left(),left));
#endif
    
    // remove adjacency at left end point
    const_ref first=*mid_it;
    //X_curve const * old_cv=&first.top();
    
#ifdef CGAL_TD_DE