arr_landmarks_pl_functions.h

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

            (seg, (seg_orient == SMALLER),
             circ->curve(), (circ->direction() == LARGER),
             v);
          CGAL_PRINT_DEBUG("circ = "<<(*circ).curve()<<" res1= "<<res1); 
        }
      } while (res1 == LARGER && seg_orient == cv_orient 
               && circ!=circ_done);
      
      //if res1 is not larger => seg is between prev and circ,return prev
      //if seg_orient != cv_orient, then we changes side and the 
      //other side is larger than seg.
      // then also seg is between prev & circ and we have to return prev
      
      if (res1 == LARGER && seg_orient == cv_orient)  
      {//we 're only out the while because the circ end
        //in this case the seg is larger than ALL curves and all 
        //curves are to the same side 
        //we need to find the largest of all curves.
        CGAL_PRINT_DEBUG("circ == circ_done : "); 
        do {
          prev = circ;
          circ++;
          res1 =  compare_cw_around_point
            (circ->curve(), (circ->direction() == LARGER), 
             prev->curve(), (prev->direction() == LARGER),
             v);
          CGAL_PRINT_DEBUG("circ = "<<(*circ).curve()<<" res1= "<<res1); 
        } while (res1 == LARGER && circ!=circ_done);
        //if circ == circ_done, then prev is the largest
        //else if circ is not larger than prev, than prev is 
        //the largest. anyway, prev is the largest - return it
      }
      
      //out_edge = prev;
      //found_face = true;
      CGAL_PRINT_DEBUG ( "new_find_face return " << (*prev).curve() );
      return (CGAL::make_object ((*prev).face()));
    }
    else if (res1 ==SMALLER) 
    {
      //if the segment is smaller (cw) than the curve, we need to find 
      //ccw (--) the curve that seg is larger than. 
      //since we can't go --, we will go ++ few times (if necessary). 
      CGAL_PRINT_DEBUG("res1 == SMALLER : "); 
      
      //loop 1 - until reach a curve on the other side, if exists
      do {
        prev = circ; 
        circ++;
        cv_orient = circ->twin()->direction();
      } while (circ!=circ_done  && seg_orient == cv_orient); 
      
      if (seg_orient != cv_orient) 
      {
        //loop 2 - until reach the same side again 
        do {
          prev = circ; 
          circ++;
          cv_orient = circ->twin()->direction();
        }  while (seg_orient != cv_orient) ;
        
        //prev is the last edge from the other side, 
        //and curve is the first curve in this side
        res1 =  compare_cw_around_point
          (seg, (seg_orient == SMALLER),
           circ->curve(), (circ->direction() == LARGER),
           v);
        
        //loop 3 - until find curve > seg cw.
        while (res1 == LARGER && seg_orient==cv_orient) 
        {
          prev = circ; 
          circ++;
          cv_orient = circ->twin()->direction();
          if (seg_orient == cv_orient) 
          {
            res1 =  compare_cw_around_point
              (seg, (seg_orient == SMALLER),
               circ->curve(), (circ->direction() == LARGER),
               v);
            CGAL_PRINT_DEBUG("circ = "<<(*circ).curve()<<" res1= "<<res1);
          }
        }
        
        //now we can say that the output edge is prev
        //out_edge = prev;
        //found_face = true;
        CGAL_PRINT_DEBUG ( "new_find_face return " << (*prev).curve() );
        return (CGAL::make_object ((*prev).face()));
      }
      
      // else - (circ == circ_done)
      //there are no curves on the other side, 
      //find the smallest (cw) on this side
      do {
        prev = circ;
        circ++;
        res1 =  compare_cw_around_point
          (circ->curve(), (circ->direction() == LARGER),
           prev->curve(), (prev->direction() == LARGER),
           v);
        CGAL_PRINT_DEBUG("circ = "<<(*circ).curve()<<" res1= "<< res1); 
      } while (res1 == LARGER && circ!=circ_done);
      //now circ < prev ==> circ is the smallest
      
      //if seg > smallest, smallest++,
      // otherwise, out_edge  = smallest->twin();
      res1 =  compare_cw_around_point
        (seg, (seg_orient == SMALLER),
         circ->curve(), (circ->direction() == LARGER),
         v);
      
      if (res1 == SMALLER) 
      {
        //out_edge = circ->twin();
        //found_face = true;
        CGAL_PRINT_DEBUG ( "new_find_face return " << (*circ).curve() );
        return (CGAL::make_object ((*circ).twin()->face()));
      }
      
      //else: seg > smallest
      circ_done = circ; 
      do  
      {
        prev = circ;
        circ++;
        res1 =  compare_cw_around_point
          (seg, (seg_orient == SMALLER),
           circ->curve(), (circ->direction() == LARGER),
           v);
      } while (res1 == LARGER && circ!= circ_done);
      
      //out_edge = prev;
      //found_face = true;
      CGAL_PRINT_DEBUG ( "new_find_face return " << (*prev).curve() );
      return (CGAL::make_object ((*prev).face()));
    }
    else //EQUAL
    {
      //TODO: specail case - new vertex or on edge ot something
      CGAL_PRINT_DEBUG ( "specail case: seg is equal cw to circ " 
                         << (*circ).curve() );
      if (traits->equal_2_object()(p,(*circ).source()->point())) 
      {
        CGAL_PRINT_DEBUG ( "p is on a vertex ");
        //out_edge = circ;
        //out_vertex = circ->source();
        //lt = Planar_map::VERTEX;
        //found_vertex_or_edge = true;
        return (CGAL::make_object ((*circ).source()));
      }
      
      if (traits->is_in_x_range_2_object()((*circ).curve(),p) && 
          traits->compare_y_at_x_2_object()(p,(*circ).curve()) == EQUAL) 
      {
        // p lies on cv1  
        CGAL_PRINT_DEBUG ( "p is on an edge ");
        Halfedge_const_handle temp_he = circ;
        //out_edge = circ;
        //lt = Planar_map::EDGE;
        //found_vertex_or_edge = true;
        return (CGAL::make_object (temp_he)); 
      }
      
      //p does not lie on cv1 ==> 
      // the target of the equal curve is a better vertex to p 
      CGAL_PRINT_ERROR
        ("WARNING 11: found closer vertex during new_find_face");
      
      // out_vertex is the closer vertex
      //out_vertex = circ->source();
      new_vertex = true;
      CGAL_PRINT_DEBUG( "The new vertex is: "<< (*circ).source()->point() );
      // check validity (the new vertex is vetween them on a line) @@@@
      return (CGAL::make_object((*circ).source()));    
    }
  }
  
  CGAL_PRINT_ERROR("ERROR 13: new_find_face did not find the face !");
  CGAL_LM_DEBUG(getchar());
  return Object();
}    

//----------------------------------------------------
// walks from the edge to the point
// param eh - (input) halfedge that the closest point to p is located on
// param p - (input) the point to locate.
// param np - (input) the point on the edge to start the walk .
//
template <class Arrangement, class Arr_landmarks_generator>
Object Arr_landmarks_point_location<Arrangement, Arr_landmarks_generator>
::_walk_from_edge(Halfedge_const_handle eh,       
          const Point_2 & p,       
          const Point_2 & np)   const    

{ 
  CGAL_PRINT_DEBUG("inside walk_from_edge. p= "<< p << ", eh = "
    <<eh->source()->point() << "-->"  <<eh->target()->point());
  const X_monotone_curve_2& cv = eh->curve() ;
  const Point_2&            src = eh->source()->point();
  const Point_2&            trg = eh->target()->point();
  Comparison_result res;

  CGAL_LM_DEBUG( 
    if (! traits->is_in_x_range_2_object()(cv, np)) 
      std::cout<<"WARNING 5: np is not on the edge's x_range"
      <<std::endl; 
    else if (traits->compare_y_at_x_2_object()(np,cv) != EQUAL)
      std::cout<<"WARNING 6: np is not on the edge"
      <<std::endl; 
  );
  CGAL_PRINT_DEBUG("inside walk_from_edge. p= "<< p  << 
                 ", eh = "<<eh->source()->point() << "-->"  
                 <<eh->target()->point());

  // I deleted the special case: if cv is vertical: 
  // If p ON cv - o.k
  // if p not in x range - o.k.
  // if p in the same x range and is not on (meaning below or above) 
  //   then it might have been better to take the vertex and not the face. 

  //check if p equals one of the edge's end points
  if (traits->equal_2_object()(p, src))
  {
    Vertex_const_handle vh = eh->source();
    return (CGAL::make_object(vh));
  }
  if (traits->equal_2_object()(p, trg))
  {
    Vertex_const_handle vh = eh->target();
    return (CGAL::make_object(vh));
  }
  
  //save the edge we're starting from
  m_start_edge = &eh;

  //if p is in eh's x_range, then we need to check if it is above/below eh
  //and orient the halfedge eh accordingly, so that it will point to the face 
  //that is most likely containing p
  if (traits->is_in_x_range_2_object()(cv, p))
  {
    //check if p is above/below cv
    res =   traits->compare_y_at_x_2_object()(p,cv);
    CGAL_PRINT_DEBUG("curve compare y at x: p= "<< p << ", cv =  "<< cv 
          <<", res = "<<res);
    switch (res) { 
      case EQUAL://p is on cv - found !
        return (CGAL::make_object(eh));
      case LARGER:  //p is above cv
        //orient e from left to right
        if (traits->compare_x_2_object()(src,trg) == LARGER) 
          eh = eh->twin();//it is oriented from right to left
        break;
      case SMALLER: //p is below cv
        //orient e from right to left
        if (traits->compare_x_2_object()(src,trg) == SMALLER ) 
          eh = eh->twin();//it is oriented from right to left
        break;
    }  
    CGAL_PRINT_DEBUG("call from walk_from_edge to walk_from face: eh= "
                  <<eh->source()->point() << "-->"  
                  <<eh->target()->point());
    return _walk_from_face (eh->face(), p, np);
  }

  //if p is in NOT in eh's x_range,
  //we will check if p is on the left or right to eh, 
  // and take this vertex to start with.
  else 
  {
    Vertex_const_handle vh = eh->source();
    if (eh->direction() != traits->compare_xy_2_object()(p, src))
    {
      vh = eh->target();
    }
    CGAL_PRINT_DEBUG("call from walk_from_edge to walk_from_vertex: vh= "
          <<vh->point());
    return _walk_from_vertex(vh, p);
  }

}

//----------------------------------------------------
// walks from the face to the point
// \param eh - (input) halfedge that points to the face that the 
//                     closest point to p (np) is located in
// \param p - (input) the point to locate.
// \param np - (input) the point to start the walk .
//
// new algorithm: 
// 1. check if p is in face. 
//   yes: 
//     go over holes. for each hole h:
//       is p in h?
//         yes: face = h. goto 1.
//   no: 
//     call new function: 
//       find_closest_intersection_in_face( gets face, v, p) 
//                 that  returns e and intersection point (if needed). 
//       (the function go over all edges surrounding p. 
//           for each one- as done now - take out of the walk procedure) 
//             face = e->twin. goto1.
//       if intersection not found --- ? error ? 
//
template <class Arrangement, class Arr_landmarks_generator>
Object Arr_landmarks_point_location<Arrangement, Arr_landmarks_generator>
::_walk_from_face(Face_const_handle face,       
          const Point_2 & p,
          const Point_2 & np)   const   
{ 
  CGAL_PRINT_DEBUG("inside walk_from_face. p= "<< p ); 

  //inits
  //Halfedge_const_handle out_edge = eh;
  //Face_const_handle face = out_edge->face() ; //get the face that is the best potentially contains p.
  m_flipped_edges.clear();  //remove all elements from the m_flipped_edges list
  bool p_in_face = false;
  Ccb_halfedge_const_circulator h_circ;
  bool found_edge = false;
  bool found_vertex = false;
  Halfedge_const_handle out_edge;
  
  do {
    CGAL_PRINT_DEBUG(std::endl << "inside loop on face ");
    p_in_face = false;
    if (face->is_unbounded())  {
      p_in_face = true;
      CGAL_PRINT_DEBUG("unbounded face ");
    }
    else {    
      h_circ = face->outer_ccb();
      p_in_face = _is_point_in_face(p, h_circ, found_edge, 
        found_vertex, out_edge); 
      CGAL_PRINT_DEBUG("is_point_in_face returned  "<<  p_in_face );
    }
    if (found_vertex)
    {
      Vertex_const_handle v = out_edge->target(); 
      return (CGAL::make_object(v)); //is it really the target?
    }
    else if (found_edge)