gps_utils.h

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

  --last;
  for(++curr ; curr != last; ++curr)
  {
    const X_monotone_curve_2& curr_cv = *curr;
    if (cmp_ends(curr_cv) == CGAL::SMALLER)
      curr_he = arr.insert_from_left_vertex(curr_cv, curr_he);
    else
    {
      CGAL_assertion(cmp_ends(curr_cv) == CGAL::LARGER);
      curr_he = arr.insert_from_right_vertex(curr_cv, curr_he);
    }
  }

  const X_monotone_curve_2& last_cv = *last;
  /*Halfedge_handle last_he =
    arr.insert_at_vertices(last_cv, curr_he, first_he); */
  bool new_face_created;
  Halfedge_handle last_he = 
    accessor.insert_at_vertices_ex (last_cv,
                                    curr_he,
                                    first_he,
                                    cmp_ends(last_cv),
                                    new_face_created);
  CGAL_assertion(new_face_created); 
  CGAL_assertion((last_he->face() != last_he->twin()->face()) && 
                 (last_he->face() != arr.unbounded_face()));
  
  last_he->face()->set_contained(true);
}


template <class Traits_, class Dcel_>
template<class PolygonIter >
void General_polygon_set_2<Traits_, Dcel_>::
insert(PolygonIter p_begin, PolygonIter p_end)
{
  typename std::iterator_traits<PolygonIter>::value_type pgn;
  _insert(p_begin, p_end, pgn);
}

template <class Traits_, class Dcel_>
template<class PolygonIter, class PolygonWithHolesIter>
void General_polygon_set_2<Traits_, Dcel_>::
insert(PolygonIter p_begin, PolygonIter p_end,
       PolygonWithHolesIter pwh_begin, PolygonWithHolesIter pwh_end)
{
  typedef std::list<X_monotone_curve_2>                  XCurveList;
  typedef Init_faces_visitor<Arrangement_2>              My_visitor;
  typedef Gps_bfs_scanner<Arrangement_2, My_visitor>     Arr_bfs_scanner;

  XCurveList xcurve_list;
  
  for( ; p_begin != p_end; ++p_begin)
  {
    CGAL_precondition(m_traits->is_valid_2_object()(*p_begin));
    _construct_curves(*p_begin, std::back_inserter(xcurve_list));
  }

  bool is_unbounded = false;
  for( ; pwh_begin != pwh_end; ++pwh_begin)
  {
    CGAL_precondition(m_traits->is_valid_2_object()(*pwh_begin));
    is_unbounded = (is_unbounded || pwh_begin->is_unbounded());
    _construct_curves(*pwh_begin, std::back_inserter(xcurve_list));
  }
  insert_non_intersecting_curves(*m_arr, xcurve_list.begin(), xcurve_list.end());

  if (is_unbounded)
    m_arr->unbounded_face()->set_contained(true);

  My_visitor v;
  Arr_bfs_scanner scanner(v);
  scanner.scan(*m_arr);
  _reset_faces(m_arr);
}

//insert a range of simple polygons to the arrangement
template <class Traits_, class Dcel_>
template<class PolygonIter>
void General_polygon_set_2<Traits_, Dcel_>::
_insert(PolygonIter p_begin, PolygonIter p_end, Polygon_2 & /*pgn*/)
{  
  for(PolygonIter pitr = p_begin; pitr != p_end; ++pitr)
  {
    CGAL_precondition(m_traits->is_valid_2_object()(*pitr));
    this->_insert(*pitr, *m_arr);
  }
}

template <class Traits_, class Dcel_>
template<class PolygonIter>
void General_polygon_set_2<Traits_, Dcel_>::
_insert(PolygonIter p_begin, PolygonIter p_end, Polygon_with_holes_2 & /*pgn*/)
{  
  typedef std::list<X_monotone_curve_2>                  XCurveList;
  typedef Init_faces_visitor<Arrangement_2>              My_visitor;
  typedef Gps_bfs_scanner<Arrangement_2, My_visitor>     Arr_bfs_scanner;

  XCurveList xcurve_list;
  bool is_unbounded = false;
  for( ; p_begin != p_end; ++p_begin)
  {
    CGAL_precondition(m_traits->is_valid_2_object()(*p_begin));
    is_unbounded = (is_unbounded || p_begin->is_unbounded());
    _construct_curves(*p_begin, std::back_inserter(xcurve_list));

  }
  insert_non_intersecting_curves(*m_arr, xcurve_list.begin(), xcurve_list.end());

  if (is_unbounded)
    m_arr->unbounded_face()->set_contained(true);

  My_visitor v;
  Arr_bfs_scanner scanner(v);
  scanner.scan(*m_arr);
  _reset_faces(m_arr);
}




 //insert non-sipmle poloygons with holes (non incident edges may have
// common vertex,  but they dont intersect at their interior
template <class Traits_, class Dcel_>
void General_polygon_set_2<Traits_, Dcel_>::
_insert(const Polygon_with_holes_2 & pgn, Arrangement_2 & arr)
{
  CGAL_precondition(m_traits->is_valid_2_object()(pgn));
  typedef std::list<X_monotone_curve_2>                  XCurveList;
  typedef Init_faces_visitor<Arrangement_2>              My_visitor;
  typedef Gps_bfs_scanner<Arrangement_2, My_visitor>     Arr_bfs_scanner;

  XCurveList xcurve_list;
  _construct_curves(pgn, std::back_inserter(xcurve_list));
  insert_non_intersecting_curves(arr, xcurve_list.begin(), xcurve_list.end());

  if (pgn.is_unbounded())
    arr.unbounded_face()->set_contained(true);

  My_visitor v;
  Arr_bfs_scanner scanner(v);
  scanner.scan(arr);
  _reset_faces(&arr);
}

template <class Traits_, class Dcel_>
template <class OutputIterator>
void 
General_polygon_set_2<Traits_, Dcel_>::
_construct_curves(const Polygon_2 & pgn, OutputIterator oi)
{
    std::pair<Curve_const_iterator,
              Curve_const_iterator> itr_pair =
              m_traits->construct_curves_2_object()(pgn);
    std::copy (itr_pair.first, itr_pair.second, oi);
}

template <class Traits_, class Dcel_>
template <class OutputIterator>
void 
General_polygon_set_2<Traits_, Dcel_>::
_construct_curves(const Polygon_with_holes_2 & pgn, OutputIterator oi)
{
  if (!pgn.is_unbounded())
  {
    const Polygon_2& pgn_boundary = pgn.outer_boundary();
    std::pair<Curve_const_iterator,
              Curve_const_iterator> itr_pair = 
              m_traits->construct_curves_2_object()(pgn_boundary);
    std::copy (itr_pair.first, itr_pair.second, oi);
  }

  GP_Holes_const_iterator hit;
  for (hit = pgn.holes_begin(); hit != pgn.holes_end(); ++hit)
  {
    const Polygon_2& pgn_hole = *hit;
    std::pair<Curve_const_iterator,
              Curve_const_iterator> itr_pair =
              m_traits->construct_curves_2_object()(pgn_hole);
    std::copy (itr_pair.first, itr_pair.second, oi);
  }
}

template <class Traits_, class Dcel_>
template <class OutputIterator>
OutputIterator
General_polygon_set_2<Traits_, Dcel_>::
polygons_with_holes(OutputIterator out) const
{
  typedef Arr_bfs_scanner<Arrangement_2, OutputIterator>     Arr_bfs_scanner;
  Arr_bfs_scanner scanner(this->m_traits, out);
  scanner.scan(*(this->m_arr));
  return (scanner.output_iterator());
}


template <class Traits_, class Dcel_>
typename General_polygon_set_2<Traits_, Dcel_>::Size 
General_polygon_set_2<Traits_, Dcel_>::
number_of_polygons_with_holes() const
{
  typedef Arr_bfs_scanner<Arrangement_2, Counting_output_iterator>
    Arr_bfs_scanner;
  Counting_output_iterator coi;
  Arr_bfs_scanner scanner(this->m_traits, coi);
  scanner.scan(*(this->m_arr));
  return (scanner.output_iterator().current_counter());
}

template <class Traits_, class Dcel_>
bool General_polygon_set_2<Traits_, Dcel_>::
locate(const Point_2& q, Polygon_with_holes_2& pgn) const
{
  Walk_pl pl(*m_arr);

  Object obj = pl.locate(q);
  Face_const_iterator f;
  if (CGAL::assign(f, obj))
  {
    if (!f->contained())
      return false;
  }
  else
  {
    Halfedge_const_handle he;
    if (CGAL::assign(he, obj))
    {
      if (he->face()->contained())
        f = he->face();
      else
      {
        CGAL_assertion(he->twin()->face()->contained());
        f = he->twin()->face();
      }
    }
    else
    {
      Vertex_const_handle v;
      CGAL_assertion(CGAL::assign(v, obj));
      CGAL::assign(v, obj);
      Halfedge_around_vertex_const_circulator hav = v->incident_halfedges();
      Halfedge_const_handle he = hav;
      if (he->face()->contained())
        f = he->face();
      else
      {
        CGAL_assertion(he->twin()->face()->contained());
        f = he->twin()->face();
      }
    }
  }

  typedef Oneset_iterator<Polygon_with_holes_2>    OutputItr;
  typedef Arr_bfs_scanner<Arrangement_2, OutputItr>     Arr_bfs_scanner;

  OutputItr oi (pgn);
  Arr_bfs_scanner scanner(this->m_traits, oi);
  
  
  Ccb_halfedge_const_circulator ccb_of_pgn = get_boundary_of_polygon(f);
  this->_reset_faces();
  if (ccb_of_pgn == Ccb_halfedge_const_circulator()) // the polygon has no boundary
  {
    // f is unbounded 
    scanner.scan_contained_ubf(m_arr->unbounded_face());
  }
  else
  {
    Halfedge_const_handle he_of_pgn = ccb_of_pgn;
    this->_reset_faces();
    he_of_pgn->face()->set_visited(true);
    scanner.scan_ccb(ccb_of_pgn);
  }

  this->_reset_faces();
  return true;
}

template <class Traits_, class Dcel_>
typename General_polygon_set_2<Traits_, Dcel_>::Ccb_halfedge_const_circulator
General_polygon_set_2<Traits_, Dcel_>::
get_boundary_of_polygon(Face_const_iterator f) const
{
  CGAL_assertion(!f->visited());
  f->set_visited(true);
  
  if (f->is_unbounded())
  {
    return Ccb_halfedge_const_circulator();
  }
  Ccb_halfedge_const_circulator ccb_end = f->outer_ccb();
  Ccb_halfedge_const_circulator ccb_circ = ccb_end;
  do
  { 
    //get the current halfedge on the face boundary
    Halfedge_const_iterator he  = ccb_circ;
    Face_const_iterator new_f = he->twin()->face();
    if (!new_f->visited())
    {
      if (is_hole_of_face(new_f, he) && !new_f->contained())
        return (he->twin());
      return (get_boundary_of_polygon(new_f));
    }
    ++ccb_circ;
  }
  while(ccb_circ != ccb_end);
  CGAL_assertion(false);
  return Ccb_halfedge_const_circulator();
  
}

template <class Traits_, class Dcel_>
bool General_polygon_set_2<Traits_, Dcel_>::
is_hole_of_face(Face_const_handle f, Halfedge_const_handle he) const
{
  Hole_const_iterator   holes_it;
  for (holes_it = f->holes_begin(); holes_it != f->holes_end(); ++holes_it)
  {
    Ccb_halfedge_const_circulator ccb = *holes_it;
    Ccb_halfedge_const_circulator ccb_end = ccb;
    do
    {
      Halfedge_const_handle he_inside_hole = ccb;
      he_inside_hole = he_inside_hole->twin();
      if (he == he_inside_hole)
        return true;

      ++ccb;
    }
    while(ccb != ccb_end);
  }

  return false;
}

#endif