snc_fm_decorator.h

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

// Copyright (c) 1997-2000  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: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.3-branch/Nef_3/include/CGAL/Nef_3/SNC_FM_decorator.h $
// $Id: SNC_FM_decorator.h 39746 2007-08-07 20:10:09Z hachenb $
// 
//
// Author(s)     : Michael Seel <[e-mail]>

#ifndef CGAL_SNC_FM_DECORATOR_H
#define CGAL_SNC_FM_DECORATOR_H

#include <CGAL/Nef_2/geninfo.h>
#include <CGAL/Nef_2/Segment_overlay_traits.h>
#include <CGAL/Nef_3/SNC_decorator.h>
#include <CGAL/Lazy_kernel.h>
#include <list>
#undef CGAL_NEF_DEBUG
#define CGAL_NEF_DEBUG 31
#include <CGAL/Nef_2/debug.h>

CGAL_BEGIN_NAMESPACE

//--------------------------------------------------------------------------
/* We introduce a template that is a point that refers to a vertex.
   We derive from the point type and add the vertex handle */

template <typename P, typename H>
class Vertex_point : public H {
  P p_;
public:
  Vertex_point() {}
  Vertex_point(const P& p, H v) : H(v), p_(p) {}
  Vertex_point(const Vertex_point& vp) : H(vp) { p_=vp.p_; }
  Vertex_point& operator=(const Vertex_point& vp)
  { H::operator=(vp); p_=vp.p_; return *this; } 
  H vertex() const { return *this; }
  P point() const { return p_; } 
};

/*
bool operator==(const Vertex_point& vp1, const Vertex_point& vp2) {
    return vp1.vertex()==vp2.vertex();
}
*/

template <typename P, typename H>
std::ostream& operator<<(std::ostream& os, const Vertex_point<P,H>& p)
{ os << p.point(); return os; }

template <typename P, typename H>
std::ostream& operator<<(std::ostream& os, 
  const std::pair< Vertex_point<P,H>, Vertex_point<P,H> > & s)
{ os << s.first << s.second; return os; }

template <typename V, typename SE>
struct Sort_sedges {
  bool operator()(SE e1, SE e2) {
    V v1[2], v2[2];
    v1[0] = e1->source()->center_vertex();
    v1[1] = e1->next()->source()->center_vertex();
    v2[0] = e2->source()->center_vertex();
    v2[1] = e2->next()->source()->center_vertex();
    int i1(0), i2(0);
    if(CGAL::lexicographically_xyz_smaller(v1[1]->point(),v1[0]->point())) i1 = 1;
    if(CGAL::lexicographically_xyz_smaller(v2[1]->point(),v2[0]->point())) i2 = 1;
    if(v1[i1] != v2[i2]) return CGAL::lexicographically_xyz_smaller(v1[i1]->point(),v2[i2]->point());
    if(v1[1-i1] != v2[1-i2]) return CGAL::lexicographically_xyz_smaller(v1[1-i1]->point(),v2[1-i2]->point());
    return i1<i2;
  }
};

template <typename P, typename SE>
struct Sort_sedges2 {
  bool operator()(SE e1, SE e2) {
    P p1[2], p2[2];
    p1[0] = e1->source()->center_vertex()->point();
    p1[1] = e1->twin()->source()->twin()->center_vertex()->point();
    p2[0] = e2->source()->center_vertex()->point();
    p2[1] = e2->twin()->source()->twin()->center_vertex()->point();
    int i1(0), i2(0);
    if(CGAL::lexicographically_xyz_smaller(p1[1],p1[0])) i1 = 1;
    if(CGAL::lexicographically_xyz_smaller(p2[1],p2[0])) i2 = 1;
    if(p1[i1] != p2[i2]) return CGAL::lexicographically_xyz_smaller(p1[i1],p2[i2]);
    if(p1[1-i1] != p2[1-i2]) return CGAL::lexicographically_xyz_smaller(p1[1-i1],p2[1-i2]);
    return i1<i2;
  }
};


//--------------------------------------------------------------------------
/* The following type is an output model for our generic segment
   sweep module |Segment_overlay_traits|. We use that code to 
   sweep all sedges of a plane to finally associate facet cycles
   to facets. Note that we do not use the segment intersection
   functionality of the code as the sedges only touch in endpoints.
   There is room for optimization here. */
//--------------------------------------------------------------------------

template <typename P, typename V, typename E, typename I>
struct Halffacet_output {

Halffacet_output(CGAL::Unique_hash_map<I,E>& F, std::vector<E>& S) 
  : From(F), Support(S) { edge_number=0; Support[0]=E(); }

typedef P         Point;
typedef V         Vertex_handle;
typedef unsigned  Halfedge_handle;

CGAL::Unique_hash_map<I,E>& From;
std::vector<E>& Support;
unsigned edge_number;

Vertex_handle new_vertex(const Point& p) const
{ geninfo<unsigned>::create(p.vertex()->info());
  return p.vertex(); }

Halfedge_handle new_halfedge_pair_at_source(Vertex_handle v) 
{ CGAL_NEF_TRACEN("new_edge "<<&*v<<" "<<edge_number+1);
  return ++edge_number; }

void supporting_segment(Halfedge_handle e, I it)
{ if ( From[it] != E() ) Support[e] = From[it]; }

void halfedge_below(Vertex_handle v, Halfedge_handle e)
{ CGAL_NEF_TRACEN("halfedge_below point "<< v->point() <<": " << e); 
  geninfo<unsigned>::access(v->info()) = e; }

// all empty, no update necessary
void link_as_target_and_append(Vertex_handle, Halfedge_handle)
{ /* do nothing */ }

void trivial_segment(Vertex_handle, I) const {}
void starting_segment(Vertex_handle, I) const {}
void passing_segment(Vertex_handle, I) const {}
void ending_segment(Vertex_handle, I) const {}

};

//--------------------------------------------------------------------------
// the following class is the geometry kernel of the generic sweep
// module |Segment_overlay_traits|. 
//--------------------------------------------------------------------------

template <typename Point, typename Plane, typename Handle>
class Halffacet_geometry { 

 public:
  typedef Point Point_3;
  typedef Plane Plane_3;
  typedef Vertex_point<Point,Handle>  Point_2;
  typedef std::pair<Point_2,Point_2>  Segment_2;

 private:
  // the underlying plane:
  Plane_3 h;

  Point_3 above(const Point_3& p) const
  { return p + h.orthogonal_vector(); }

 public:

Halffacet_geometry(const Plane_3& hi) : h(hi) {}

Point_2 source(const Segment_2& s) const  { return s.first; }
Point_2 target(const Segment_2& s) const  { return s.second; }

bool is_degenerate(const Segment_2& s) const { 
  return source(s).vertex()==target(s).vertex();
}

Segment_2 construct_segment(const Point_2& p1, const Point_2& p2) const
{ return Segment_2(p1,p2); }

int orientation(const Point_2& p1, const Point_2& p2, const Point_2& p3) const
{ return static_cast<int>(
    CGAL::orientation(p1.point(),p2.point(),p3.point(),above(p1.point()))); }

int orientation(const Segment_2& s, const Point_2& p) const {
    if(source(s).vertex() == p.vertex() ||
       target(s).vertex() == p.vertex())
        return 0;
    return orientation(source(s),target(s),p); 
}

int compare_xy(const Point_2& p1, const Point_2& p2) const { 
    if(p1.vertex()==p2.vertex())
        return 0;
    return static_cast<int>(
        CGAL::compare_xyz(p1.point(),p2.point()));
}

Point_2 intersection(const Segment_2& s1, const Segment_2& s2) const
{ CGAL_assertion(target(s1).vertex()==target(s2).vertex()); 
  return target(s1); }

bool left_turn(const Point_3& p1, const Point_3& p2, const Point_3& p3) const
{ return CGAL::orientation(p1,p2,p3,above(p1)) == CGAL::POSITIVE; }

}; // Halffacet_geometry


template<class Kernel, typename SHalfedge_handle, typename Halffacet_geometry> 
class SmallerXYZ {
  
  typedef typename Kernel::Point_3  Point_3;
  Halffacet_geometry& G;
 public:
  SmallerXYZ(Halffacet_geometry& Gin) : G(Gin) {}

  bool operator()(SHalfedge_handle se, SHalfedge_handle min, bool /*init*/) {
    if(se->twin()->source()->twin()->source() == min->twin()->source()->twin()->source()) {
      Point_3 p1 = se->source()->source()->point(), 
	p2 = se->twin()->source()->twin()->source()->point(), 
	p3 = se->next()->twin()->source()->twin()->source()->point();      
      return !G.left_turn(p1,p2,p3);
    }
    return CGAL::lexicographically_xyz_smaller(se->twin()->source()->twin()->source()->point(), 
					       min->twin()->source()->twin()->source()->point());
  }
};

/*
template<typename SHalfedge_handle, typename EK> 
class SmallerXYZ<CGAL::Lazy_kernel<EK>, SHalfedge_handle> {

  typedef CGAL::Lazy_kernel<EK> Kernel;
  typedef typename Kernel::Point_3  Point_3;
 public:
  SmallerXYZ() {}

  bool point_in_positive_direction_3(const Point_3& p) const {
    if(p.x() < 0) return false;
    if(p.x() > 0) return true;
    if(p.y() < 0) return false;
    if(p.y() > 0) return true;
    return p.z() > 0;
  }  

  bool operator()(const SHalfedge_handle se, const Point_3 min, bool) {
    return 
      //      (point_in_positive_direction_3(se->next()->source()->point()) &&
      //	    point_in_positive_direction_3(se->next()->twin()->source()->point()) &&
      //	    (!init || 
	     CGAL::lexicographically_xyz_smaller(se->twin()->source()->twin()->source()->point(), 
						 min);
  }
};
*/

/*
template<class K2, typename EK, typename SHalfedge_handle> 
class SmallerXYZ<CGAL::Lazy_kernel<EK>, K2, SHalfedge_handle> {

  typedef typename K2::Point_3  Point_3;
 public:
  SmallerXYZ() {}

  bool point_in_positive_direction_2(const Point_3& p) const {
    if(p.y() < 0) return false;
    if(p.y() > 0) return true;
    return p.z() > 0;
  }

  bool point_in_positive_direction_3(const Point_3& p) const {
    if(p.x() < 0) return false;
    if(p.x() > 0) return true;
    if(p.y() < 0) return false;
    if(p.y() > 0) return true;
    return p.z() > 0;
  }  

  bool operator()(const SHalfedge_handle se, const Point_3 min, bool init) {
    return (point_in_positive_direction_3(se->next()->source()->point()) &&
	    point_in_positive_direction_3(se->next()->twin()->source()->point()) &&
	    (!init || 
	     CGAL::lexicographically_xyz_smaller(se->twin()->source()->twin()->source()->point(), 
						 min)));
  }
};
*/

//--------------------------------------------------------------------------
// SNC_FM_decorator
// Note that we interpret sedges as edge uses between vertices.  We
//   overwrite some operations from the base class for that semantics.
//--------------------------------------------------------------------------

template <typename S> class SNC_decorator;

template <typename SNC_structure_>
class SNC_FM_decorator : public SNC_decorator<SNC_structure_> {
public:
  typedef SNC_structure_ SNC_structure;
  typedef SNC_decorator<SNC_structure> Base;

  typedef typename SNC_structure::Vertex_iterator Vertex_iterator; 
  typedef typename SNC_structure::Vertex_handle Vertex_handle;
  typedef typename SNC_structure::Halfedge_iterator Halfedge_iterator; 
  typedef typename SNC_structure::Halfedge_handle Halfedge_handle;
  typedef typename SNC_structure::Halffacet_iterator Halffacet_iterator; 
  typedef typename SNC_structure::Halffacet_handle Halffacet_handle;
  typedef typename SNC_structure::Volume_iterator Volume_iterator;
  typedef typename SNC_structure::Volume_handle Volume_handle;
  typedef typename SNC_structure::SVertex_iterator SVertex_iterator; 
  typedef typename SNC_structure::SVertex_handle SVertex_handle;
  typedef typename SNC_structure::SHalfedge_iterator SHalfedge_iterator; 
  typedef typename SNC_structure::SHalfedge_handle SHalfedge_handle;
  typedef typename SNC_structure::SHalfloop_iterator SHalfloop_iterator; 
  typedef typename SNC_structure::SHalfloop_handle SHalfloop_handle;
  typedef typename SNC_structure::SFace_iterator SFace_iterator; 
  typedef typename SNC_structure::SFace_handle SFace_handle;
  typedef typename SNC_structure::SFace_cycle_iterator SFace_cycle_iterator;
  typedef typename SNC_structure::Halffacet_cycle_iterator Halffacet_cycle_iterator;
  typedef typename SNC_structure::Shell_entry_iterator Shell_entry_iterator;
  typedef typename SNC_structure::Object_handle Object_handle;