sm_overlayer.h

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

  //                                       Constructor_const_parameter;
  typedef typename SM_const_decorator::SVertex_const_handle SVertex_const_handle;
  typedef typename SM_const_decorator::SHalfedge_const_handle SHalfedge_const_handle;
  typedef typename SM_const_decorator::SHalfloop_const_handle SHalfloop_const_handle;
  typedef typename SM_const_decorator::SFace_const_handle SFace_const_handle;
  typedef typename SM_const_decorator::SVertex_const_iterator SVertex_const_iterator;
  typedef typename SM_const_decorator::SHalfedge_const_iterator SHalfedge_const_iterator;
  typedef typename SM_const_decorator::SFace_const_iterator SFace_const_iterator;

  //  typedef typename Base::Constructor_parameter Constructor_parameter;
  typedef typename Base::SVertex_handle SVertex_handle;
  typedef typename Base::SHalfedge_handle SHalfedge_handle;
  typedef typename Base::SHalfloop_handle SHalfloop_handle;
  typedef typename Base::SFace_handle SFace_handle;
  typedef typename Base::SVertex_iterator SVertex_iterator;
  typedef typename Base::SHalfedge_iterator SHalfedge_iterator;
  typedef typename Base::SFace_iterator SFace_iterator;
  typedef typename Base::Object_handle Object_handle;

  typedef typename Base::SHalfedge_around_svertex_circulator 
                         SHalfedge_around_svertex_circulator;
  typedef typename Base::SHalfedge_around_sface_circulator 
                         SHalfedge_around_sface_circulator;
  typedef typename Base::SFace_cycle_iterator 
                         SFace_cycle_iterator;

  typedef std::pair<SHalfedge_handle,SHalfedge_handle> SHalfedge_pair;

  /*{\Mtypes 3}*/

  typedef typename Base::Sphere_kernel           Sphere_kernel;
  /*{\Mtypemember the geometry kernel.}*/
  typedef typename Sphere_kernel::Sphere_point   Sphere_point;
  /*{\Mtypemember the point type of the sphere geometry.}*/
  typedef typename Sphere_kernel::Sphere_segment Sphere_segment;
  /*{\Mtypemember the segment type of the sphere geometry.}*/
  typedef typename Sphere_kernel::Sphere_circle  Sphere_circle;
  /*{\Mtypemember the circle type of the sphere geometry.}*/
  typedef typename Base::Mark Mark;
  /*{\Mtypemember the mark of sphere map objects.}*/

  typedef typename Base::GenPtr GenPtr;

  /*{\Mgeneralization SM_decorator}*/

protected:
  SM_const_decorator PI[2];
  const Sphere_kernel& K;

public:

  // ---------------------------------------------------------------

  struct Seg_info { // to transport information from input to output
    Object_handle _o; int _from;

    Seg_info() : _o(), _from(-1) {}
    Seg_info(SVertex_const_handle v, int i) 
    { _o=Object_handle(v); _from=i; }
    Seg_info(SHalfedge_const_handle e, int i) 
    { _o=Object_handle(e); _from=i; }
    Seg_info(SHalfloop_const_handle l, int i) 
    { _o=Object_handle(l); _from=i; }
    Seg_info(const Seg_info& si) 
    { _o=si._o; _from=si._from; }
    Seg_info& operator=(const Seg_info& si) 
    { _o=si._o; _from=si._from; return *this; }
    LEDA_MEMORY(Seg_info)
  }; // Seg_info

  typedef std::list<Sphere_segment>            Seg_list;
  typedef typename Seg_list::iterator          Seg_iterator;
  typedef std::pair<Seg_iterator,Seg_iterator> Seg_it_pair;
  typedef std::pair<Sphere_segment,Sphere_segment> Seg_pair;
  typedef CGAL::Unique_hash_map<Seg_iterator,Seg_info> Seg_map;

  // ---------------------------------------------------------------

  struct vertex_info {
    Mark m[2];
    Object_handle o_supp[2];
    SHalfedge_handle e_below;
    vertex_info() 
    { o_supp[0]=o_supp[1]=Object_handle(); }
    LEDA_MEMORY(vertex_info)
  }; // vertex_info

  void assoc_info(SVertex_handle v) const
  { geninfo<vertex_info>::create(info(v)); }

  void discard_info(SVertex_handle v) const
  { geninfo<vertex_info>::clear(info(v)); }

  vertex_info& ginfo(SVertex_handle v) const
  { return geninfo<vertex_info>::access(info(v)); }

  Mark& mark(SVertex_handle v, int i) const
  { return ginfo(v).m[i]; }

  Object_handle& supp_object(SVertex_handle v, int i) const
  { return ginfo(v).o_supp[i]; }

  SHalfedge_handle& halfedge_below(SVertex_handle v) const
  { return ginfo(v).e_below; }

  // ---------------------------------------------------------------

  struct edge_info {
    Mark m[2];
    Mark mf[2];
    Object_handle o_supp[2];
    bool forw;
    edge_info()
    { m[0]=m[1]=mf[0]=mf[1]=Mark(); 
      o_supp[0]=o_supp[1]=Object_handle(); 
      forw=false; }
    LEDA_MEMORY(edge_info)
  };

  void assoc_info(SHalfedge_handle e)  const
  { geninfo<edge_info>::create(info(e)); 
    geninfo<edge_info>::create(info(e->twin())); }

  void discard_info(SHalfedge_handle e)  const
  { geninfo<edge_info>::clear(info(e)); 
    geninfo<edge_info>::clear(info(e->twin())); }

  edge_info& ginfo(SHalfedge_handle e)  const
  { return geninfo<edge_info>::access(info(e)); }

  Mark& mark(SHalfedge_handle e, int i)  const
    { return ginfo(e).m[i]; }

  Object_handle& supp_object(SHalfedge_handle e, int i) const
  // uedge information we store in the smaller one 
  { if (&*e < &*(e->twin())) return ginfo(e).o_supp[i]; 
    else                   return ginfo(e->twin()).o_supp[i]; }

  Mark& incident_mark(SHalfedge_handle e, int i)  const
  // biedge information we store in the edge
  { return ginfo(e).mf[i]; }

  bool& is_forward(SHalfedge_handle e) const
  // biedge information we store in the edge
  { return ginfo(e).forw; }

  // ---------------------------------------------------------------

  struct face_info {
    Mark m[2];
    face_info() { m[0]=m[1]=Mark(); }
    LEDA_MEMORY(face_info)
  };

  void assoc_info(SFace_handle f)  const
  { geninfo<face_info>::create(info(f)); }

  void discard_info(SFace_handle f)  const
  { geninfo<face_info>::clear(info(f)); }

  face_info& ginfo(SFace_handle f)  const
  { return geninfo<face_info>::access(info(f)); }

  Mark& mark(SFace_handle f, int i)  const
  { return ginfo(f).m[i]; }

  // ---------------------------------------------------------------

  template <typename Below_accessor>
  SFace_handle determine_face(SHalfedge_handle e, 
    const std::vector<SHalfedge_handle>& MinimalSHalfedge,
    const CGAL::Unique_hash_map<SHalfedge_handle,int>& SFaceCycle,
    const Below_accessor& D)
  { CGAL_NEF_TRACEN("determine_face "<<PH(e));
    int fc = SFaceCycle[e];
    SHalfedge_handle e_min = MinimalSHalfedge[fc];
    SHalfedge_handle e_below = D.halfedge_below(e_min->target());
    if(e_below == SHalfedge_handle())
      return SFace_handle();
    SFace_handle f = e_below->incident_sface();
    if ( f != SFace_handle() ) return f; // has already a face 
    // e_below also has no face
    f = determine_face(e_below, MinimalSHalfedge, SFaceCycle,D);
    if(f != SFace_handle())
      link_as_face_cycle(e_below,f);
    return f;
  }

  Sphere_segment segment(SM_const_decorator , 
                         SHalfedge_const_handle e) const
  { return K.construct_segment(e->source()->point(),
			       e->target()->point(),
			       e->circle()); }

  Sphere_segment trivial_segment(SM_const_decorator , 
                                 SVertex_const_handle v) const
  { Sphere_point p = v->point(); 
    return K.construct_segment(p,p); }

  Seg_pair two_segments(SM_const_decorator , 
                        SHalfedge_const_handle e) const
  // we know that e->source()==e->target()
  { return e->circle().split_at(e->source()->point()); }

  Seg_pair two_segments(SM_const_decorator , 
                        SHalfloop_const_handle l) const
  { return l->circle().split_at_xy_plane(); }


  // ---------------------------------------------------------------
  // INTERFACE INTERFACE INTERFACE INTERFACE INTERFACE INTERFACE 
  // ---------------------------------------------------------------

  /*{\Mcreation 6}*/

  SM_overlayer(Map* M, 
    const Sphere_kernel& G = Sphere_kernel()) : Base(M), K(G) {}
  /*{\Mcreate |\Mvar| is a decorator object manipulating the map
  of |v|.}*/

  /*{\Moperations 1.1 1}*/

  template <typename Forward_iterator>
  void create_from_segments(
    Forward_iterator start, Forward_iterator end); 
  /*{\Mop produces the sphere map which is the overlay of the
  segments from the iterator range |[start,end)|.  \precond
  |Forward_iterator| has value type |Sphere_segment|.}*/

  template <typename Forward_iterator>
  void create_from_circles(Forward_iterator start, Forward_iterator end);
  /*{\Mop produces the sphere map which is the overlay of the
  circles from the iterator range |[start,end)|.  \precond
  |Forward_iterator| has value type |Sphere_circle|.}*/

  void create(const Sphere_circle& c);
  /*{\Mop produces the sphere map which consists of one loop
  and the two halfspheres incident to it.}*/

  void subdivide(const Map* M0, const Map* M1, 
		 bool with_trivial_segments = false); 
  
  template <typename Association>
  void subdivide(const Map* M0, const Map* M1, 
		 Association& A, 
		 bool with_trivial_segments = false);
  /*{\Mop constructs the overlay of the sphere maps |M0| and |M1| in
  |M|, where all objects (vertices, halfedges, faces) of |M| are
  \emph{enriched} by the marks of the supporting objects of the two
  input structures: e.g. let |v| be a vertex supported by a node |v0| in
  |M0| and by a face |f1| in |M1| and |D0|, |D1| be decorators of
  type |SM_decorator| on |M0|,|M1|. Then |\Mvar.mark(v,0) = D0.v0->mark()|
  and |\Mvar.mark(v,1) = D1.f1->mark()|.}*/

  template <typename Selection> 
  void select(const Selection& SP) const;
  /*{\Mop sets the marks of all objects according to the selection
  predicate |SP|. |Selection| has to be a function object type with a
  function operator\\
  [[Mark operator()(Mark m0, Mark m1) const]]\\
  For each object |u| of |M| enriched by the marks of the supporting
  objects according to the previous procedure |subdivide|, after this
  operation |\Mvar.u->mark() = SP ( \Mvar.mark(u,0),\Mvar.mark(u,1)
  )|. The additional marks are invalidated afterwards.
  \precond subdivide() was called before.}*/

  void simplify();
  /*{\Mop simplifies the structure of |M| according to the marks of
  its objects. An edge |e| separating two faces |f1| and |f2| and equal
  marks |e->mark() == f1->mark() == f2->mark()| is removed and the faces are
  unified.  An isolated vertex |v| in a face |f| with |v->mark()==f->mark()|
  is removed.  A vertex |v| with outdegree two, two collinear out-edges
  |e1|,|e2| and equal marks |v->mark() == e1->mark() == e2->mark()| is removed
  and the edges are unified.}*/

  int check_sphere(const Seg_list& L, bool compute_halfsphere[3][2]) const;

  template <typename Iterator>
  void subdivide_segments(Iterator start, Iterator end) const;
  template <typename Iterator, typename T>
  void partition_to_halfsphere(Iterator start, Iterator end,
    Seg_list& L, CGAL::Unique_hash_map<Iterator,T>& M, 
    Sphere_circle xycircle, Sphere_circle yzcircle, bool include_equator) const;

  template <typename Mark_accessor>
  void merge_halfsphere_maps(SVertex_handle v1, SVertex_handle v2,
    const Mark_accessor& D);
  template <typename Mark_accessor>
  void merge_nodes(SHalfedge_handle e1, SHalfedge_handle e2,
    const Mark_accessor& D);

  template <typename Below_accessor, typename Halfsphere_geometry>
  void create_face_objects(SHalfedge_iterator e_start, SHalfedge_iterator e_end,
			   SVertex_iterator v_start, SVertex_iterator v_end,
			   const Below_accessor& D, 
			   const Halfsphere_geometry& SG);

  template <typename Below_accessor>
  void complete_face_support(SVertex_iterator v_start, SVertex_iterator v_end,
    const Below_accessor& D, std::vector<Mark>& mohs, int offset, bool both=true) const;

  void complete_sface_marks() const;

  void set_outer_face_mark(int offset, const std::vector<Mark>& mohs);

  template <typename Association>
    void transfer_data(Association& A);

  void dump(std::ostream& os = std::cerr) const
  { SM_io_parser<Base>::dump(*this,os); }

}; // SM_overlayer<SM_decorator>

template <typename Map>
template <typename Forward_iterator>
void SM_overlayer<Map>::
create_from_segments(Forward_iterator start, Forward_iterator end)
{
  CGAL_NEF_TRACEN("creating from segment iterator range");
  Seg_list L(start,end);
  Unique_hash_map<Seg_iterator,bool> From_input(false);
  Seg_iterator it;
  CGAL_forall_iterators(it,L) From_input[it]=true;
  Seg_list L_pos,L_neg;
  partition_to_halfsphere(L.begin(), L.end(), L_pos, From_input, 
			  Sphere_circle(0,0,1), Sphere_circle(1,0,0), true);
  partition_to_halfsphere(L.begin(), L.end(), L_neg, From_input, 
			  Sphere_circle(0,0,-1), Sphere_circle(1,0,0), true);
  //CGAL_NEF_TRACEN("L_pos="<<(MSDEBUG::print_elements(L_pos),""));
  //CGAL_NEF_TRACEN("L_neg="<<(MSDEBUG::print_elements(L_neg),""));

  typedef SMO_from_segs<Self,Seg_iterator> SM_output;
  typedef typename Sphere_kernel::Positive_halfsphere_geometry PH_geometry;
  typedef CGAL::Segment_overlay_traits< 
            Seg_iterator, SM_output, PH_geometry>  PHS_traits;
  typedef CGAL::generic_sweep<PHS_traits> Positive_halfsphere_sweep;

  typedef typename Sphere_kernel::Negative_halfsphere_geometry NH_geometry;
  typedef CGAL::Segment_overlay_traits< 
            Seg_iterator, SM_output, NH_geometry> NHS_traits;
  typedef CGAL::generic_sweep<NHS_traits> Negative_halfsphere_sweep;

  SVertex_iterator v;
  SHalfedge_iterator e;
  SM_output O(*this,From_input); 

  typedef typename PHS_traits::INPUT Input_range;
  Positive_halfsphere_sweep SP(
    Input_range(L_pos.begin(),L_pos.end()),O,
    PH_geometry());
  SP.sweep();
  //CGAL_NEF_TRACEN("POS SWEEP\n"<<(dump(std::cerr),""));
  v=--this->svertices_end(); e=--this->shalfedges_end();

  Negative_halfsphere_sweep SM(
    Input_range(L_neg.begin(),L_neg.end()),O,
    NH_geometry());
  SM.sweep();
  //CGAL_NEF_TRACEN("NEG SWEEP\n"<<(dump(std::cerr),""));
  ++v; ++e;
  // now two CCs of sphere graph are calculated
  // v = first vertex of CC in negative x-sphere
  // e = first edge of CC in negative x-sphere

  create_face_objects(this->shalfedges_begin(), e, this->svertices_begin(), v, O,
                      PH_geometry());
  create_face_objects(e, this->shalfedges_end(), v, this->svertices_end(), O,
                      NH_geometry());

  SHalfedge_iterator u;
  CGAL_forall_sedges(u,*this) {
    Sphere_segment s(u->source()->point(),u->target()->point());
    u->circle() = s.sphere_circle();
    u->twin()->circle() = s.sphere_circle().opposite();
  }

  merge_halfsphere_maps(this->svertices_begin(),v,O);
  this->check_integrity_and_topological_planarity();

  O.clear_temporary_vertex_info();
}