arr_landmarks_pl_functions.h

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

    {
      Halfedge_const_handle h = out_edge; 
      return (CGAL::make_object(h));
    }
    else if (p_in_face){
      //check holes
      CGAL_PRINT_DEBUG(" p in face. go over holes" );
      Hole_const_iterator hole_it  = face->holes_begin();
      Hole_const_iterator hole_end = face->holes_end();  
      bool p_in_hole;
      while (hole_it != hole_end) 
      {
        CGAL_PRINT_DEBUG(" loop on holes");
        p_in_hole = _is_point_in_face(p, *hole_it, 
          found_edge, found_vertex, out_edge); 
        if (found_vertex)
        {
          return (CGAL::make_object(out_edge->target())); 
          //is it really the target?
        }
        else if (found_edge) 
        {
          return (CGAL::make_object(out_edge));
        }
        else if (p_in_hole) {
          h_circ = *hole_it; 
          //update the new "face " to be the hole. check its holes.      

          if ( _find_edge_to_flip (p, np, h_circ , out_edge) ) {
            out_edge = out_edge->twin();
            face = out_edge->face();
          }
          else {
            CGAL_PRINT_ERROR( "ERROR 10:  intersection not found");
            CGAL_LM_DEBUG(getchar());
            return (CGAL::make_object (p_arr->unbounded_face()));
          }

          hole_it = hole_end; //to get out of the loop
          p_in_face = false;
        } 
        else {
          ++hole_it;
        }
      }
    }
    else {
      //find edge to switch face to (face is never unbounded)
      if ( _find_edge_to_flip (p, np, face->outer_ccb() , out_edge) ) {
        out_edge = out_edge->twin();        
        face = out_edge->face();
        CGAL_PRINT_DEBUG("after find_edge_to_flip. changed to twin @ " );
        CGAL_PRINT_DEBUG("out_edge  =  "<< out_edge->source()->point() 
                  <<" -->"<< out_edge->target()->point() );
      }
      else {
        CGAL_PRINT_ERROR("ERROR 9:  intersection not found");
        CGAL_LM_DEBUG(getchar());
        //e = p_arr->halfedges_end();
        //lt = Planar_map::UNBOUNDED_FACE;
        return (CGAL::make_object (p_arr->unbounded_face()));
      }
    }
  }while (!p_in_face); 

  if (face == p_arr->unbounded_face()) 
  {
    CGAL_PRINT_DEBUG("before return from walk from face. unbounded face.");
    return (CGAL::make_object (p_arr->unbounded_face()));
  }

  CGAL_PRINT_DEBUG("before return from walk from face. ");
  return (CGAL::make_object (face));
}

//----------------------------------------------------
/*!
* Checks if p is inside the face
* 
* \param p - the input point.
* \param e - the input edge
* \param found_edge - did we found the edge p lies on
* \param new_vertex - output bool, if a closer vertex to p was found
*/

template <class Arrangement, class Arr_landmarks_generator>
bool Arr_landmarks_point_location<Arrangement, Arr_landmarks_generator>
::_is_point_in_face (const Point_2 & p,                  //input seg src 
           const Ccb_halfedge_const_circulator & face, //input face
           bool & found_edge,                  //out is p on e?
           bool & found_vertex,      //out is p equals e->target?
           Halfedge_const_handle  & out_edge) const  //output if on curve        
{
  CGAL_PRINT_DEBUG("inside is_point_in_face. face = " << (*face).source()->point()
                <<"-->" << (*face).target()->point());

  found_edge = false;
  found_vertex = false;
  int number_of_edges_above_p = 0;

  //loop on all edges in this face
  Ccb_halfedge_const_circulator curr = face;
  Ccb_halfedge_const_circulator last =  curr;

  typename Traits_adaptor_2::Equal_2 equal = traits->equal_2_object();
  typename Traits_adaptor_2::Compare_xy_2     compare_xy = 
                                       traits->compare_xy_2_object();
  typename Traits_adaptor_2::Compare_y_at_x_2     compare_y_at_x = 
                                       traits->compare_y_at_x_2_object();


  do  {
    const X_monotone_curve_2& cv = (*curr).curve();
    const Point_2&            p1 = (*curr).source()->point();
    const Point_2&            p2 = (*curr).target()->point();

    //check if p equals one of the endpoints of e
    if (equal(p, p1))   {
      found_vertex = true;
      out_edge = (*curr).twin() ;
      CGAL_PRINT_DEBUG("p is "<< p );
      CGAL_PRINT_DEBUG("out_edge is "<< out_edge->curve() );
      CGAL_PRINT_DEBUG("target is "<< out_edge->target()->point() );
      return (true); 
    }
    if (equal(p, p2))   {
      found_vertex = true;
      out_edge = curr;
      CGAL_PRINT_DEBUG("p is "<< p );
      CGAL_PRINT_DEBUG("out_edge is "<< out_edge->curve() );
      CGAL_PRINT_DEBUG("target is "<< out_edge->target()->point() );
      return (true); 
    }

    //check in_x_range lexicographically. 
    //This is if p is on different sides from p1 and p2
    if  (compare_xy(p, p1) != compare_xy(p, p2) ) 
    {
      //check cv to see it p is above, below or on cv
      Comparison_result compare_y_at_x_res = compare_y_at_x(p, cv);

      switch (compare_y_at_x_res) 
      {
      case EQUAL:
        found_edge = true;
        out_edge = curr;
        return (true); 
      case SMALLER: //p is below cv
        //count cv
        number_of_edges_above_p ++;
        break;
      case LARGER: //p is above cv
        //don't count cv. continue
        break;
      default: //should not be equal
        CGAL_assertion (false);
      }
    }

    ++curr;
  } while (curr != last);  

  //if number_of_edges_above_p is odd, then p is inside the face, 
  //else - p is outside f. 
  //to check if number_of_edges_above_p is odd/even, 
  //simply do bitwise AND operator with 1. 
  return (number_of_edges_above_p & 1) ;
}

//----------------------------------------------------
/*!
* find the edge in the face that is intersecting with the segment v - p.  
* (out_edge)
* each edge can be chosen only once, and will get into the switch_curves list 
* returns false if there is no intersection, thus no edge to flip. 
* 
* \param p - the input point.
* \param v - the input closest point.
* \param face - the input face
* \param out_edge - the output edge
*/
template <class Arrangement, class Arr_landmarks_generator>
bool Arr_landmarks_point_location<Arrangement, Arr_landmarks_generator>
::_find_edge_to_flip (const Point_2 & p,                  //input seg src 
            const Point_2 & np,           //input closest point
            const Ccb_halfedge_const_circulator & face, //input face
            Halfedge_const_handle  & out_edge) const //output edge to flip
{
  //we want to eliminate the calls to nearest. 
  //this means we will not call to find_real_intersection at all. 
  //this also means that we will take the first edge that is intersecting, 
  //and not check which is closer. 
  //what we will check is whether this edge was selected already 
  //(and flipped),  in this case we will not flip it again, 
  //but move to the next edge
  CGAL_PRINT_DEBUG("inside find_edge_to_flip.   " );

  //create a segment vp--p. 
  const Point_2&     vp = np;
  X_monotone_curve_2 seg = traits->construct_x_monotone_curve_2_object()(vp, p);

  //loop on all edges in this face
  Ccb_halfedge_const_circulator curr = face;
  Ccb_halfedge_const_circulator last =  curr;
  bool p_in_x_range, v_in_x_range, p1_in_x_range, p2_in_x_range;  

  typename Traits_adaptor_2::Is_in_x_range_2         is_in_x_range = 
                                      traits->is_in_x_range_2_object();


  do  {
    const X_monotone_curve_2& cv = (*curr).curve();
    const Point_2&            p1 = (*curr).source()->point();
    const Point_2&            p2 = (*curr).target()->point();
 
    // check if the curve was already flipped - in this case, 
    //    don't check it at all.
    Std_edge_iterator found1 = std::find (m_flipped_edges.begin(), 
      m_flipped_edges.end(), curr);
    Std_edge_iterator found2 = std::find (m_flipped_edges.begin(), 
      m_flipped_edges.end(), (*curr).twin());
    if (found1 != m_flipped_edges.end() || found2 != m_flipped_edges.end()) {
      CGAL_PRINT_DEBUG("curve "<<p1<<"-->"<<p2<<" was found in the list");
    }
    else if (m_start_edge && 
             (curr == *m_start_edge || (*curr).twin() == *m_start_edge))
    { //check that curr and (*curr).twin() is not equal to m_start_edge
      CGAL_PRINT_DEBUG("curve "<<p1<<"-->"<<p2<<" is the start edge");
    }
    else {
      CGAL_PRINT_DEBUG("curr = " << p1 << "-->" << p2 );

      //check x-range
      p_in_x_range = is_in_x_range(cv, p);
      v_in_x_range = is_in_x_range(cv, vp);
      p1_in_x_range = is_in_x_range(seg, p1);
      p2_in_x_range = is_in_x_range(seg, p2);
      CGAL_PRINT_DEBUG("p_in_x_range = " << p_in_x_range 
        << " , v_in_x_range = " << v_in_x_range);
      CGAL_PRINT_DEBUG("p1_in_x_range = " << p1_in_x_range 
        << " , p2_in_x_range = " << p2_in_x_range);

      if (p_in_x_range || v_in_x_range || p1_in_x_range || p2_in_x_range)
      {    
        bool intersect;
        bool check_res = _check_approximate_intersection (seg, cv, intersect);

        if (check_res) 
        {
          if (intersect) {
            out_edge = curr;
            m_flipped_edges.push_back(out_edge);
            return (true);
          }
        }
        else {
          CGAL_PRINT_ERROR("ERROR 12: check_approximate_intersection "\
                      <<"did not return an answer.");
        }
      }
      //else - there is not intersection.
    }  

    ++curr;
  } while (curr != last);  

  return (false);
}


//----------------------------------------------------
//check if cv intersects seg. 
// \param seg - the input seg.
// \param cv - the input curve
// \param intersect - output: if the two curves intersects odd number of times
// \returns true if the function returned a value, false if error
// if the segment intersects the curve in one of the curves endpoints: 
// if it is the curve's left endpoint => intersects. 
// the curves right endpoint => no intersection.
// if the segment intersect the curve in one of the segments end points, 
// it may because the query point is on the curve (this should not happen, 
// since we check first if the query is on an edge), or 
// beacuse the landmark is on the curve, and in this case we should not pass 
// to the edge's other side.
template <class Arrangement_2, class Arr_landmarks_generator>
bool Arr_landmarks_point_location<Arrangement_2,Arr_landmarks_generator>
::_check_approximate_intersection (const X_monotone_curve_2 & seg,  
                  const X_monotone_curve_2 & cv,
                  bool & intersect) const 
{
  typename Traits_adaptor_2::Equal_2              equal = 
                                            traits->equal_2_object();
  typename Traits_adaptor_2::Compare_xy_2          compare_xy = 
                                            traits->compare_xy_2_object();
  typename Traits_adaptor_2::Compare_y_at_x_2     compare_y_at_x = 
                                            traits->compare_y_at_x_2_object();
  CGAL_LM_DEBUG (
  typename Traits_adaptor_2::Is_in_x_range_2      is_in_x_range = 
                                            traits->is_in_x_range_2_object();
  )
  typename Traits_adaptor_2::Compare_y_at_x_right_2 compare_y_at_x_right = 
                                      traits->compare_y_at_x_right_2_object();
  typename Traits_adaptor_2::Compare_y_at_x_left_2 compare_y_at_x_left = 
                                      traits->compare_y_at_x_left_2_object();

  const Point_2& seg_right = traits->construct_max_vertex_2_object()(seg);
  const Point_2& seg_left = traits->construct_min_vertex_2_object()(seg);
  const Point_2& cv_right = traits->construct_max_vertex_2_object()(cv);
  const Point_2& cv_left = traits->construct_min_vertex_2_object()(cv);
  intersect = false;

  CGAL_PRINT_DEBUG("seg_right =  " << seg_right << " , seg_left = " << seg_left);
  CGAL_PRINT_DEBUG("cv_right = " << cv_right << " , cv_left = " << cv_left);
  
  //compare the 2 left end-points and the 2 right end-points
  Comparison_result comp_left_xy_res = compare_xy(seg_left, cv_left);
  Comparison_result comp_right_xy_res = compare_xy(seg_right, cv_right);

  // the left end-point of the segments is equal to the left end-point 
  //of the curve
  if (comp_left_xy_res == EQUAL) 
  {
    CGAL_PRINT_DEBUG("the left end-point of the segments is equal to the"\
                <<" left end-point of the curve");
    // compare to the right of the curves
    Comparison_result curves_comp = compare_y_at_x_right(seg,cv,seg_left);
  
    if (curves_comp == EQUAL) 
    {
      CGAL_PRINT_DEBUG("overlap !!!");
      //this means: 
      // 1. the query is on the curve (should have been checked). 
      // 2. the landmark is on the curve (should have been checked).
      // 3. the curve endpoint is on the segment. if it's the left endpoint - 
      //    intersect. right - no intersection.
      if (compare_y_at_x(cv_left, seg) == EQUAL)
      {
        intersect = true;
        return (true);
      }
      else if (compare_y_at_x(cv_right, seg) == EQUAL)