snc_fm_decorator.h

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

  typedef typename SNC_structure::Kernel  Kernel;
  typedef typename SNC_structure::Point_3 Point_3;
  typedef typename SNC_structure::Plane_3 Plane_3;
  typedef typename SNC_structure::Mark Mark;

  typedef typename Base::SHalfedge_around_facet_circulator
    SHalfedge_around_facet_circulator;
#if 0
  typedef typename Base::SHalfedge_around_facet_const_circulator
    SHalfedge_around_facet_const_circulator;
#endif

  typedef typename std::list<Object_handle>::iterator 
    Object_list_iterator;

  typedef CGAL::Vertex_point<Point_3,Vertex_handle>  Vertex_point;
  typedef std::pair<Vertex_point,Vertex_point> Vertex_segment;
  typedef std::list<Vertex_segment>            Segment_list;
  typedef typename Segment_list::iterator      Segment_iterator;

  typedef CGAL::Halffacet_geometry<Point_3,Plane_3,Vertex_handle> 
    Halffacet_geometry;

protected:
  Halffacet_handle f_;
public:

  SNC_FM_decorator(SNC_structure& W) : Base(W), f_() {}
  SNC_FM_decorator(SNC_structure& W, Halffacet_handle f)
   : Base(W),f_(f) {}


  Halffacet_cycle_iterator facet_cycles_begin() const 
  { return f_->facet_cycles_begin(); }  
  Halffacet_cycle_iterator facet_cycles_end()   const 
  { return f_->facet_cycles_end(); }

  void create_facet_objects(const Plane_3& h,
    Object_list_iterator start, Object_list_iterator end) const;

protected:

//--------------------------------------------------------------------------
/* We provide some information on determine_facet. To understand its
   functionality please refer to the Nef_2 implementation report where
   there is similar function determine_face with more documentation.

   When we call |determine_facet|$(e,\ldots)$ we know that the
   shalfedge |e| is not linked to a face object yet and thus no
   shalfedge in its face cycle is linked. Thus we jump to the minimal
   shalfedge and look down (along the previously used sweep line in
   the plane of the facet). If we see an shalfedge we ask for its
   face. If it does not have one we recurse.  Note that the target
   vertex of the minimal halfedge actually has a view downwards as we
   examine a hole facet cycle. The method |link_as_facet_cycle| does
   the linkage between the facet object and all sedges of the facet
   cycle. Its cost is linear in the size of the facet cycle. Note also
   that we do the linking bottom up along the recursion stack for all
   visited hole (facet) cycles.  Thus we visit each hole facet cycle
   only once as afterwards each edge of the facet cycle is incident to
   a facet. */
//--------------------------------------------------------------------------

  Halffacet_handle determine_facet(SHalfedge_handle e, 
    const std::vector<SHalfedge_handle>& MinimalEdge,
    const CGAL::Unique_hash_map<SHalfedge_handle,int>& FacetCycle,
    const std::vector<SHalfedge_handle>& Edge_of) const
  { CGAL_NEF_TRACEN("  determine_facet "<<debug(e));
    int fc = FacetCycle[e];
    SHalfedge_handle e_min = MinimalEdge[fc];
    SHalfedge_handle e_below = 
      Edge_of[geninfo<unsigned>::access(info(e_min->twin()->source()->twin()->source()))];
    CGAL_assertion( e_below != SHalfedge_handle() );
    CGAL_NEF_TRACEN("  edge below " << debug(e_below));    
    Halffacet_handle f = e_below->facet();
    if ( f != Halffacet_handle() ) return f; // has already a facet 
    // e_below also has no facet
    f = determine_facet(e_below, MinimalEdge, FacetCycle, Edge_of);
    CGAL_NEF_TRACEN("  edge below " << debug(e_below));
    link_as_facet_cycle(e_below,f); 
    link_as_facet_cycle(e_below->twin(),f->twin()); 
    return f;
  }

//--------------------------------------------------------------------------
/* segment(...)
   an shalfedge |e| can be interpreted as an edge-use extending along
   the halfedge that leaves the local graph in |target(e)|. Only
   edge-uses allow us to code the non-unique character of an edge as a
   boundary object of several facets. An edge-use |e| represents the
   edge |target(e)| in the boundary structure of a facet. */
//--------------------------------------------------------------------------

  Vertex_segment segment(SHalfedge_handle e) const
  { Vertex_handle vs = e->source()->source(), 
      vt = e->twin()->source()->twin()->source(); 
    Vertex_point  ps(vs->point(),vs), pt(vt->point(),vt);
    return Vertex_segment(ps,pt); }

  Vertex_segment segment(SHalfloop_handle l) const
  { Vertex_handle v = l->incident_sface()->center_vertex(); 
    Vertex_point  p(v->point(),v);
    return Vertex_segment(p,p); }


}; // SNC_FM_decorator<SNC_structure_>



//--------------------------------------------------------------------------
/* create_facet_objects() 
   In this method we use the visibility along a sweep line in the
   facet plane to create facet objects. |SEdge_below[v]| either
   provides the sedge that is hit first by a vertical ray downwards or
   an uninitialized edge if there is none. */
//--------------------------------------------------------------------------


template <typename SNC_>
void SNC_FM_decorator<SNC_>::
create_facet_objects(const Plane_3& plane_supporting_facet,
  Object_list_iterator start, Object_list_iterator end) const
{ CGAL_NEF_TRACEN(">>>>>create_facet_objects "
		  << normalized(plane_supporting_facet));
  CGAL::Unique_hash_map<SHalfedge_handle,int> FacetCycle(-1);
  std::vector<SHalfedge_handle> MinimalEdge;
  std::list<SHalfedge_handle> SHalfedges; 
  std::list<SHalfloop_handle> SHalfloops; 

  CGAL::Unique_hash_map<Vertex_handle,SHalfedge_handle> SHalfedgeBelow;
  CGAL::Unique_hash_map<Segment_iterator,SHalfedge_handle>  From;

  Segment_list Segments;
  SHalfedge_handle e; SHalfloop_handle l;
  typename std::list<SHalfedge_handle>::iterator eit,epred;
  typename std::list<SHalfloop_handle>::iterator lit;

  // the output decorator for the facet plane sweep
  typedef CGAL::Halffacet_output<Vertex_point, Vertex_handle, 
    SHalfedge_handle, Segment_iterator> Halffacet_output;

  // the sweep traits class instantiated with the input, output and
  // geometry models
  typedef CGAL::Segment_overlay_traits
    <Segment_iterator, Halffacet_output, Halffacet_geometry>
    Halffacet_sweep_traits;
  typedef CGAL::generic_sweep<Halffacet_sweep_traits>   Halffacet_sweep;
  Halffacet_geometry G(plane_supporting_facet);

  /* We first separate sedges and sloops, and fill a list of segments
     to trigger a sweep. */

  for ( ; start != end; ++start ) {
    if ( CGAL::assign(e,*start) ) {
      SHalfedges.push_back(e); 
    } else if ( CGAL::assign(l,*start) ) {
      SHalfloops.push_back(l); 
    } else 
      CGAL_assertion_msg(0,"Damn wrong handle.");
  }

  /* We iterate all shalfedges and assign a number for each facet
     cycle.  After that iteration for an edge |e| the number of its
     facet cycle is |FacetCycle[e]| and for a facet cycle |c| we know
     |MinimalEdge[c]|. */
  int i=0; 
  //  bool xyplane = plane_supporting_facet.b() != 0 || plane_supporting_facet.c() != 0;
  SmallerXYZ<Kernel, SHalfedge_handle, Halffacet_geometry> smallerXYZ(G);
  CGAL_forall_iterators(eit,SHalfedges) { 
    e = *eit;
    if ( FacetCycle[e] >= 0 ) continue; // already assigned
    SHalfedge_around_facet_circulator hfc(e),hend(hfc);
    FacetCycle[hfc]=i;
    SHalfedge_handle e_min = e;
    bool init=false;
    CGAL_NEF_TRACEN("\n  facet cycle numbering (up) "<<i);
    CGAL_For_all(hfc,hend) {
      FacetCycle[hfc]=i; // assign face cycle number
      if(smallerXYZ(hfc, e_min, init)) {
	init = true;
	e_min = hfc;
      }
      
      CGAL_NEF_TRACEN(hfc->twin()->source()->twin()->source()->point() << " lex xyz smaller " << 
		      e_min->twin()->source()->twin()->source()->point() << "=" << 
		      CGAL::lexicographically_xyz_smaller(hfc->twin()->source()->twin()->source()->point(), 
							  e_min->twin()->source()->twin()->source()->point()));
      
    } CGAL_NEF_TRACEN("");
    MinimalEdge.push_back(e_min);
    ++i;
  }



  /* We now know the number of facet cycles |i| and we have a minimal
     edge |e| for each facet cycle. We just check the geometric
     embedding of |e| and |e->next()| to characterize the facet cycle
     (outer or hole). Note that the two edges cannot be collinear due
     to the minimality of |e| (the lexicographic minimality of the
     embedding of its target vertex). Outer facet cycles obtain facet
     objects right away. */

  for (int j=0; j<i; ++j) {
    SHalfedge_handle e = MinimalEdge[j];
    CGAL_NEF_TRACEN("  facet cycle "<<j<<" minimal halfedge "<<debug(e));
    Point_3 p1 = e->source()->source()->point(), 
      p2 = e->twin()->source()->twin()->source()->point(), 
      p3 = e->next()->twin()->source()->twin()->source()->point();
    
    //      std::cerr << "minimal shalfedge " << e->source()->source()->point() << ":"
    //                << e->source()->point() << "->" << e->twin()->source()->point() << std::endl;


    if ( G.left_turn(p1,p2,p3) ) { 
      Halffacet_handle f = this->sncp()->new_halffacet_pair(plane_supporting_facet);
      link_as_facet_cycle(e,f); link_as_facet_cycle(e->twin(),f->twin()); 
      f->mark() = f->twin()->mark() = e->mark();
      CGAL_NEF_TRACEN("  creating new facet object "<<&*f<<" bd "<<&*e);
    }
  }

  /* Now the only shalfedges not linked are those on hole facet
     cycles.  We use a recursive scheme to find the bounding cycle
     providing the facet object and finally iterate over all isolated
     vertices to link them accordingly to their containing facet
     object. Note that in that final iteration all shalfedges already
     have facet links. Thus that ensures termination. The recursive
     operation $|determine_facet|(e,\ldots)$ returns the facet
     containing the hole cycle of |e|. As a postcondition of this code
     part we have all shalfedges and isolated shalfloops linked to
     facet objects, and all facet objects know their bounding facet
     cycles. */
 
  bool do_sweep = false;
  if(SHalfloops.size() > 0)
    do_sweep = true;

  CGAL_forall_iterators(eit,SHalfedges) { 
    //    std::cerr << "fc " << FacetCycle[*eit] << std::endl;
    if ( (*eit)->facet() == Halffacet_handle() ) {
      //      std::cerr << "nicht verlinkte shalfedge " << (*eit)->source()->source()->point() << ":"
      //                << (*eit)->source()->point() << "->" << (*eit)->twin()->source()->point() << std::endl;
      do_sweep = true;
      break;
    }
  }


  //  std::cerr << std::endl;
#ifndef CGAL_NEF3_PLANE_SWEEP_OPTIMIZATION_OFF
  if(!do_sweep) return; 
#endif

#ifdef CGAL_NEF3_TIMER_PLANE_SWEEPS
  number_of_plane_sweeps++;
  timer_plane_sweeps.start();
#endif

  //  Note that we only allow those edges that are
  //  directed from lexicographically smaller to larger vertices. 
  //  Insertion of SHalfedges into Segments is shifted below in order
  //  to guarantee that there are no gaps in the overlay.


  //  SHalfedges.sort(Sort_sedges2<Point_3,SHalfedge_handle>());
  SHalfedges.sort(Sort_sedges<Vertex_handle,SHalfedge_handle>());
  for(eit = SHalfedges.begin();eit != SHalfedges.end();) {
    CGAL_NEF_TRACEN("  appending edge "<< debug(*eit));
    Segments.push_front(segment(*eit)); 
    From[Segments.begin()] = *eit;
    epred=eit;
    ++eit;
    if(eit != SHalfedges.end()) 
      CGAL_NEF_TRACEN("test " << std::endl << "  " << debug(*epred) 
	     << std::endl << "  " << debug(*eit));
    if(eit != SHalfedges.end() && 
       (*epred)->source()->source() ==(*eit)->next()->source()->source() &&  
       (*eit)->source()->source() == (*epred)->next()->source()->source())
      ++eit;
  }

  CGAL_forall_iterators(lit,SHalfloops) {
    CGAL_NEF_TRACEN("  appending loop " << (*lit)->incident_sface()->center_vertex()->point()); 
    Segments.push_back(segment(*lit));
  }

  std::vector<SHalfedge_handle> Edge_of(Segments.size()+1);
  Halffacet_output O(From,Edge_of);
  Halffacet_sweep FS(typename Halffacet_sweep::INPUT(
    Segments.begin(),Segments.end()), O, G); FS.sweep();

#ifdef CGAL_NEF3_TIMER_PLANE_SWEEPS
  timer_plane_sweeps.stop();
#endif

  CGAL_forall_iterators(eit,SHalfedges) { e=*eit;
  if ( e->facet() != Halffacet_handle() ) continue;
    CGAL_NEF_TRACEN("  linking hole "<<debug(e));
    Halffacet_handle f = determine_facet(e,MinimalEdge,FacetCycle,Edge_of);
    link_as_facet_cycle(e,f); link_as_facet_cycle(e->twin(),f->twin());
  }

  CGAL_forall_iterators(lit,SHalfloops) { l=*lit;
    SHalfedge_handle e_below = 
      Edge_of[geninfo<unsigned>::access(info(l->incident_sface()->center_vertex()))];
    
    CGAL_assertion( e_below != SHalfedge_handle() );
    CGAL_NEF_TRACEN("link sloop at vertex "<< l->incident_sface()->center_vertex()->point());
    CGAL_NEF_TRACEN("e_below "  << debug(e_below));
    CGAL_NEF_TRACEN("next    "  << debug(e_below->next()));
    CGAL_NEF_TRACEN("next    "  << debug(e_below->next()->next()));
    CGAL_NEF_TRACEN("next    "  << debug(e_below->next()->next()->next()));
    CGAL_NEF_TRACEN("next    "  << debug(e_below->next()->next()->next()->next()));
    link_as_interior_loop(l,e_below->facet());
    link_as_interior_loop(l->twin(),e_below->facet()->twin());
  }
  
  CGAL_NEF_TRACEN("exit FM");
}

CGAL_END_NAMESPACE
#endif //CGAL_SNC_FM_DECORATOR_H