snc_external_structure.h

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

// Copyright (c) 1997-2002  Max-Planck-Institute Saarbruecken (Germany).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: $
// $Id: SNC_external_structure.h 36279 2007-02-15 10:29:45Z hachenb $
// 
//
// Author(s)     : Michael Seel       <[e-mail]> 
//                 Miguel Granados    <[e-mail]>
//                 Susan Hert         <[e-mail]>
//                 Lutz Kettner       <[e-mail]>
//                 Peter Hachenberger <[e-mail]>
#ifndef CGAL_SNC_EXTERNAL_STRUCTURE_H
#define CGAL_SNC_EXTERNAL_STRUCTURE_H

#include <CGAL/Nef_S2/Normalizing.h>
#include <CGAL/Nef_3/Pluecker_line_3.h>
#include <CGAL/Nef_3/SNC_decorator.h>
#include <CGAL/Nef_3/SNC_point_locator.h>
#include <CGAL/Nef_S2/SM_point_locator.h>
#include <CGAL/Nef_3/SNC_FM_decorator.h>
#include <CGAL/Nef_3/SNC_io_parser.h>
#include <CGAL/Nef_3/SNC_indexed_items.h>
#include <CGAL/Nef_3/SNC_simplify.h>
#include <map>
#include <list>

#undef CGAL_NEF_DEBUG
#define CGAL_NEF_DEBUG 43
#include <CGAL/Nef_2/debug.h>

CGAL_BEGIN_NAMESPACE

struct int_lt {
  bool operator()(const int& i1, const int& i2) const { return i1<i2; }
};
template <typename Edge_handle>
struct Halfedge_key_lt4 {

  bool operator()(const Edge_handle& e1, const Edge_handle& e2) const {
    if(CGAL::sign(e1->point().x()) != 0) {
      if(e1->source() != e2->source())
	return CGAL::compare_x(e1->source()->point(), e2->source()->point()) < 0; 
      else 
	return e1->point().x() < 0;
    }
    if(CGAL::sign(e1->point().y()) != 0) {
      if(e1->source() != e2->source())
	return CGAL::compare_y(e1->source()->point(), e2->source()->point()) < 0; 
      else 
	return e1->point().y() < 0;
    }
    if(e1->source() != e2->source())
      return CGAL::compare_z(e1->source()->point(), e2->source()->point()) < 0; 
    return e1->point().z() < 0;
  }
};

template <typename Edge_handle>
struct Halfedge_key_lt3 {

  bool operator()(const Edge_handle& e1, const Edge_handle& e2) const {
    if(e1->source() != e2->source())
      return CGAL::lexicographically_xyz_smaller(e1->source()->point(), e2->source()->point()); 
    if(CGAL::sign(e1->point().x()) != 0)
      return e1->point().x() < 0;
    if(CGAL::sign(e1->point().y()) != 0)
      return e1->point().y() < 0;
    return e1->point().z() < 0;
  }
};

template <typename Point, typename Edge>
struct Halfedge_key {
  typedef Halfedge_key<Point,Edge> Self;
  Point p; int i; Edge e;
  Halfedge_key(Point pi, int ii, Edge ei) : 
    p(pi), i(ii), e(ei) {}
  Halfedge_key(const Self& k) : p(k.p), i(k.i), e(k.e) {}
  Self& operator=(const Self& k) { p=k.p; i=k.i; e=k.e; return *this; }
  bool operator==(const Self& k) const { return p==k.p && i==k.i; }
  bool operator!=(const Self& k) const { return !operator==(k); }
};

template <typename Point, typename Edge, class Decorator>
struct Halfedge_key_lt {
  typedef Halfedge_key<Point,Edge> Key;
  typedef typename Point::R R;
  typedef typename R::Vector_3 Vector;
  typedef typename R::Direction_3 Direction;
  bool operator()( const Key& k1, const Key& k2) const { 
    if( k1.e->source() == k2.e->source())
      return (k1.i < k2.i);
    Direction l(k1.e->vector());
    if( k1.i < 0) l = -l;
    return (Direction( k2.p - k1.p) == l); 
  }
};

template <typename Point, typename Edge>
std::ostream& operator<<(std::ostream& os, 
                         const Halfedge_key<Point,Edge>& k )
{ os << k.p << " " << k.i; return os; }

template <typename R>
int sign_of(const CGAL::Plane_3<R>& h)
{ if ( h.c() != 0 ) return CGAL_NTS sign(h.c());
  if ( h.b() != 0 ) return CGAL_NTS sign(-h.b());
  return CGAL_NTS sign(h.a());
}

struct Plane_lt {
  template <typename R>
  bool operator()(const CGAL::Plane_3<R>& h1,
                  const CGAL::Plane_3<R>& h2) const
  { 
    typedef typename R::RT     RT;
    RT diff = h1.a()-h2.a();
    if ( (diff) != 0 ) return CGAL_NTS sign(diff) < 0;
    diff = h1.b()-h2.b();
    if ( (diff) != 0 ) return CGAL_NTS sign(diff) < 0;
    diff = h1.c()-h2.c();
    if ( (diff) != 0 ) return CGAL_NTS sign(diff) < 0;
    diff = h1.d()-h2.d(); return CGAL_NTS sign(diff) < 0;
  }
};

struct Plane_RT_lt {
  template <typename R>
  bool operator()(const CGAL::Plane_3<R>& h1,
                  const CGAL::Plane_3<R>& h2) const
  { return (&(h1.a())) < (&(h2.a())); }
};

// ----------------------------------------------------------------------------
// SNC_external_structure 
// ----------------------------------------------------------------------------

template <typename Items_, typename SNC_structure_>
class SNC_external_structure_base : public SNC_decorator<SNC_structure_>
{ 
public:
  typedef SNC_structure_ SNC_structure;

  typedef typename SNC_structure::Infi_box                   Infi_box;
  typedef typename Infi_box::Standard_kernel                 Standard_kernel;
  typedef typename Standard_kernel::Point_3                  Standard_point_3;
  typedef typename Infi_box::NT                              NT;

  typedef CGAL::SNC_decorator<SNC_structure>                 SNC_decorator;
  typedef CGAL::SNC_point_locator<SNC_decorator>             SNC_point_locator;
  typedef CGAL::SNC_FM_decorator<SNC_structure>              FM_decorator;
  typedef CGAL::SNC_simplify<Items_, SNC_structure>          SNC_simplify;

  typedef typename SNC_structure::Sphere_map                 Sphere_map;
  typedef CGAL::SM_decorator<Sphere_map>                     SM_decorator;  
  typedef CGAL::SM_const_decorator<Sphere_map>               SM_const_decorator;
  typedef CGAL::SM_point_locator<SM_const_decorator>         SM_point_locator;

  typedef typename SNC_structure::Halfedge_iterator Halfedge_iterator;
  typedef typename SNC_structure::Halffacet_iterator Halffacet_iterator;
  typedef typename SNC_structure::Volume_iterator Volume_iterator;

  typedef typename SNC_structure::Vertex_handle Vertex_handle;
  typedef typename SNC_structure::Halfedge_handle Halfedge_handle;
  typedef typename SNC_structure::Halffacet_handle Halffacet_handle;
  typedef typename SNC_structure::Volume_handle Volume_handle;

  typedef typename SNC_structure::Halffacet_const_handle Halffacet_const_handle;
  typedef typename SNC_structure::SFace_const_handle SFace_const_handle; 

  typedef typename SNC_structure::SHalfedge_iterator SHalfedge_iterator;
  typedef typename SNC_structure::SFace_iterator SFace_iterator;
  typedef typename SNC_structure::SHalfloop_iterator SHalfloop_iterator;

  typedef typename SNC_structure::SVertex_handle SVertex_handle;
  typedef typename SNC_structure::SHalfedge_handle SHalfedge_handle;
  typedef typename SNC_structure::SFace_handle SFace_handle;
  typedef typename SNC_structure::SHalfloop_handle SHalfloop_handle;

  typedef typename SNC_structure::Object_handle Object_handle;

  typedef typename SNC_structure::SHalfedge_around_facet_circulator 
    SHalfedge_around_facet_circulator;

  typedef typename SNC_structure::Point_3 Point_3;
  typedef typename SNC_structure::Direction_3 Direction_3;
  typedef typename SNC_structure::Plane_3 Plane_3;
  typedef typename SNC_structure::Ray_3 Ray_3;

  typedef typename SNC_structure::Sphere_point Sphere_point;
  typedef typename SNC_structure::Sphere_circle Sphere_circle;

  typedef typename SM_decorator::SHalfedge_around_svertex_circulator 
    SHalfedge_around_svertex_circulator;

  SNC_point_locator* pl;

  typedef CGAL::Unique_hash_map<SFace_const_handle,unsigned int>  
                                                         Sface_shell_hash;
  typedef CGAL::Unique_hash_map<Halffacet_const_handle,unsigned int>  
                                                         Face_shell_hash;
  typedef CGAL::Unique_hash_map<SFace_const_handle,bool> SFace_visited_hash;
  typedef CGAL::Unique_hash_map<SFace_const_handle,bool> Shell_closed_hash;

  struct Shell_explorer {
    const SNC_decorator& D;
    Sface_shell_hash&  ShellSf;
    Face_shell_hash&   ShellF;
    //    Shell_closed_hash& Closed;
    SFace_visited_hash& Done;
    SFace_handle sf_min;
    int n;

    Shell_explorer(const SNC_decorator& Di, Sface_shell_hash& SSf, 
                   Face_shell_hash& SF, SFace_visited_hash& Vi) 
      : D(Di), ShellSf(SSf), ShellF(SF), Done(Vi), n(0) {}

    void visit(SFace_handle h) { 
      CGAL_NEF_TRACEN("visit sf "<<h->center_vertex()->point());
      ShellSf[h]=n;
      Done[h]=true;
      if ( CGAL::lexicographically_xyz_smaller(h->center_vertex()->point(),
					       sf_min->center_vertex()->point())) 
	sf_min = h; 
    }

    void visit(Vertex_handle h) { 
      CGAL_NEF_TRACEN("visit v  "<<h->point());
    }

    void visit(Halfedge_handle h) { 
      CGAL_NEF_TRACEN("visit he "<< h->source()->point());
    }

    void visit(Halffacet_handle h) { 
      CGAL_NEF_TRACEN(h->plane()); 
      ShellF[h]=n; 
    }

    void visit(SHalfedge_handle ) {}
    void visit(SHalfloop_handle ) {}

    SFace_handle& minimal_sface() { return sf_min; }

    void increment_shell_number() { 
      CGAL_NEF_TRACEN("leaving shell "<<n);
      ++n; 
    }
  };

  SNC_external_structure_base( SNC_structure& W, SNC_point_locator* spl = NULL) 
    : SNC_decorator(W), pl(spl) {}
  /*{\Mcreate makes |\Mvar| a decorator of |W|.}*/

 public:
  //#define CGAL_NEF_NO_HALFEDGE_KEYS
#ifdef CGAL_NEF_NO_HALFEDGE_KEYS
  void pair_up_halfedges() const {
  /*{\Mop pairs all halfedge stubs to create the edges in 3-space.}*/

  //  CGAL_NEF_SETDTHREAD(43*61);
    CGAL_NEF_TRACEN(">>>>>pair_up_halfedges");
    typedef Halfedge_key_lt3<Halfedge_handle> 
      Halfedge_key_lt;
    typedef std::list<Halfedge_handle>  Halfedge_list;
    
    typedef typename Standard_kernel::Kernel_tag   Kernel_tag;
    typedef CGAL::Pluecker_line_3<Kernel_tag,Standard_kernel> Pluecker_line_3;
    typedef CGAL::Pluecker_line_lt        Pluecker_line_lt;
    typedef std::map< Pluecker_line_3, Halfedge_list, Pluecker_line_lt> 
      Pluecker_line_map;
    
    Pluecker_line_map M;
    Pluecker_line_map M2;
    Pluecker_line_map M3;
    Pluecker_line_map M4;
    
    NT eval(Infi_box::compute_evaluation_constant_for_halfedge_pairup(*this->sncp()));
    
    Halfedge_iterator e;
    CGAL_forall_halfedges(e,*this->sncp()) {
      //    progress++;
      Point_3 p = e->source()->point();
      Point_3 q = p + e->vector();
      CGAL_NEF_TRACE(" segment("<<p<<", "<<q<<")"<<
	    " direction("<<e->vector()<<")");
      Standard_point_3 sp = Infi_box::standard_point(p,eval);
      Standard_point_3 sq = Infi_box::standard_point(q,eval);
      Pluecker_line_3  l( sp, sq);
      
      int inverted;
      l = categorize( l, inverted);
      
      if(Infi_box::is_edge_on_infibox(e))
	if(Infi_box::is_type4(e))
	  M4[l].push_back(e);
	else
	  if(Infi_box::is_type3(e))
	    M3[l].push_back(e);
	  else
	    M2[l].push_back(e);
      else
	M[l].push_back(e);
      
      // the following trace crashes when compiling with optimizations (-O{n})
      //CGAL_NEF_TRACEN(Infi_box::standard_point(point(vertex(e)))+
      
      CGAL_NEF_TRACEN(" line("<<l<<")"<<" inverted="<<inverted);
    }
    
    typename Pluecker_line_map::iterator it;
    
    CGAL_forall_iterators(it,M4) {
      //    progress++;
      it->second.sort(Halfedge_key_lt());
      CGAL_NEF_TRACEN("search opposite  "<<it->first); 
      typename Halfedge_list::iterator itl;
      CGAL_forall_iterators(itl,it->second) {
	Halfedge_handle e1 = *itl;
	++itl; 
	CGAL_assertion(itl != it->second.end());
	Halfedge_handle e2 = *itl;
	while(normalized(e1->vector()) != normalized(-e2->vector())) {
	  ++itl;
	  make_twins(e1,*itl);
	  e1 = e2;
	  ++itl;
	  e2 = *itl;
	}