snc_k3_tree_traits.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_k3_tree_traits.h $
// $Id: SNC_k3_tree_traits.h 38429 2007-04-24 15:09:03Z hachenb $
// 
//
// Author(s)     : Miguel Granados <[e-mail]>

#ifndef CGAL_NEF_SNC_K3_TREE_TRAITS_H
#define CGAL_NEF_SNC_K3_TREE_TRAITS_H

#include <CGAL/Nef_3/Bounding_box_3.h>
#include <CGAL/Lazy_kernel.h>
#include <list>

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

CGAL_BEGIN_NAMESPACE


template <typename Kernel, typename Coordinate>
class ComparePoints {

  typedef typename Kernel::Point_3  Point_3;
 public:
  ComparePoints(Coordinate c) : coord(c) {
    CGAL_assertion( c >= 0 && c <=2);
  }
  CGAL::Comparison_result operator()(const Point_3 p1, const Point_3& p2) {
    switch(coord) {
    case 0: 
      CGAL_NEF_TRACEN("compare_x " << p1 << ", " << p2 << "=" << (int) CGAL::compare_x(p1, p2));
      return CGAL::compare_x(p1, p2);
    case 1: 
      CGAL_NEF_TRACEN("compare_y " << p1 << ", " << p2 << "=" << (int) CGAL::compare_y(p1, p2));
      return CGAL::compare_y(p1, p2);
    case 2: 
      CGAL_NEF_TRACEN("compare_z " << p1 << ", " << p2 << "=" << (int) CGAL::compare_z(p1, p2));
      return CGAL::compare_z(p1, p2);
    default: CGAL_assertion(false);
    }
    return CGAL::EQUAL;
  }
private:
  Coordinate coord;
};


template <typename Coordinate, typename EK>
class ComparePoints<CGAL::Lazy_kernel<EK>, Coordinate> {

  typedef CGAL::Lazy_kernel<EK>     Kernel;
  typedef typename Kernel::Point_3  Point_3;
 public:
  ComparePoints(Coordinate c) : coord(c) {
    CGAL_assertion( c >= 0 && c <=2);
  }
  CGAL::Comparison_result operator()( const Point_3 p1, const Point_3 p2) {
    switch(coord) {
    case 0: 
      if(CGAL::to_interval(p1.x()).second <
	 CGAL::to_interval(p2.x()).first)
	return CGAL::SMALLER;
      else if(CGAL::to_interval(p2.x()).second <
	      CGAL::to_interval(p1.x()).first)
	return CGAL::LARGER;
      return CGAL::EQUAL;
    case 1:  
      if(CGAL::to_interval(p1.y()).second <
	 CGAL::to_interval(p2.y()).first)
	return CGAL::SMALLER;
      else if(CGAL::to_interval(p2.y()).second <
	      CGAL::to_interval(p1.y()).first)
	return CGAL::LARGER;
      return CGAL::EQUAL;
    case 2: 
      if(CGAL::to_interval(p1.z()).second <
	 CGAL::to_interval(p2.z()).first)
	return CGAL::SMALLER;
      else if(CGAL::to_interval(p2.z()).second <
	      CGAL::to_interval(p1.z()).first)
	return CGAL::LARGER;
      return CGAL::EQUAL;
    default: CGAL_assertion(false);
    }
    return CGAL::EQUAL;
  }
private:
  Coordinate coord;
};

template <class SNC_decorator>
class Side_of_plane {
public:
  typedef typename SNC_decorator::SNC_structure SNC_structure;	
  typedef typename SNC_decorator::Decorator_traits Decorator_traits;

  typedef typename Decorator_traits::Vertex_handle Vertex_handle;
  typedef typename Decorator_traits::Halfedge_handle Halfedge_handle;
  typedef typename Decorator_traits::Halffacet_handle Halffacet_handle;

#ifdef CGAL_NEF3_TRIANGULATE_FACETS
  typedef typename SNC_structure::Halffacet_triangle_handle 
                                  Halffacet_triangle_handle;
#endif
#ifdef CGAL_NEF3_FACET_WITH_BOX
  typedef typename SNC_structure::Partial_facet Partial_facet;
#endif
  typedef typename SNC_structure::Object_handle Object_handle;

  typedef typename Decorator_traits::Halffacet_cycle_iterator
    Halffacet_cycle_iterator;
  typedef typename Decorator_traits::SHalfedge_around_facet_circulator 
    SHalfedge_around_facet_circulator;
  typedef typename Decorator_traits::SHalfedge_handle SHalfedge_handle;
  
  typedef typename SNC_decorator::Kernel Kernel;
  typedef typename Kernel::Point_3 Point_3;
  typedef typename Kernel::Segment_3 Segment_3;
  typedef typename Kernel::Plane_3 Plane_3;
  typedef typename Kernel::Triangle_3 Triangle_3;
  typedef typename Kernel::Vector_3 Vector_3;  
  typedef typename Kernel::RT  RT;

  typedef ComparePoints<Kernel, int> ComparePoints_;
  
#ifdef CGAL_NEF_EXPLOIT_REFERENCE_COUNTING
  Side_of_plane(bool rc = false) : reference_counted(rc) {}
#else    
    Side_of_plane() {}
#endif


  template<typename Depth> Oriented_side operator()
    ( const Point_3& pop, Object_handle o, Depth depth);
  template<typename Depth> Oriented_side operator()
    ( const Point_3& pop, Vertex_handle v, Depth depth);
  template<typename Depth> Oriented_side operator()
    ( const Point_3& pop, Halfedge_handle e, Depth depth);
  template<typename Depth> Oriented_side operator()
    ( const Point_3& pop, Halffacet_handle f, Depth depth);
#ifdef CGAL_NEF3_TRIANGULATE_FACETS
  template<typename Depth> Oriented_side operator()
    ( const Point_3& pop, Halffacet_triangle_handle f, Depth depth);
#endif
#ifdef CGAL_NEF3_FACET_WITH_BOX
  template<typename Depth> Oriented_side operator()
    ( const Point_3& pop, Partial_facet& f, Depth depth);
#endif
#ifdef CGAL_NEF_EXPLOIT_REFERENCE_COUNTING
  bool reference_counted;
#endif
  SNC_decorator D;
  Unique_hash_map<Vertex_handle, Oriented_side> OnSideMap;
  Unique_hash_map<const RT*, Oriented_side> OnSideMapRC;
};

template <class SNC_decorator>
class Objects_bbox {
public:
  typedef typename SNC_decorator::SNC_structure SNC_structure;	
  typedef typename SNC_decorator::Decorator_traits Decorator_traits;

  typedef typename Decorator_traits::Vertex_handle Vertex_handle;
  typedef typename Decorator_traits::Halfedge_handle Halfedge_handle;
  typedef typename Decorator_traits::Halffacet_handle Halffacet_handle;

  typedef typename SNC_structure::Halffacet_triangle_handle Halffacet_triangle_handle;
  typedef typename SNC_structure::Object_handle Object_handle;
  typedef std::vector<Object_handle> Object_list;

  typedef typename Decorator_traits::Halffacet_cycle_iterator
    Halffacet_cycle_iterator;
  typedef typename Decorator_traits::SHalfedge_around_facet_circulator 
    SHalfedge_around_facet_circulator;
  typedef typename Decorator_traits::SHalfedge_handle SHalfedge_handle;

  typedef typename SNC_decorator::Kernel Kernel;
  typedef typename Kernel::Plane_3 Plane_3;
  typedef typename Kernel::Segment_3 Segment_3;
  typedef typename Kernel::Point_3 Point_3;
  typedef typename Kernel::Triangle_3 Triangle_3;

  typedef typename Kernel::RT RT;
  typedef typename Kernel::FT FT;
  typedef typename Kernel::Kernel_tag Kernel_tag;
  typedef CGAL::Bounding_box_3<Tag_true, Kernel> 
    Bounding_box_3;
  //  typedef CGAL::Bounding_box_3
  //    <typename Is_extended_kernel<Kernel>::value_type, Kernel> 
  //    Bounding_box_3;
  
  Bounding_box_3 operator()( const Object_list& O) const {
    Bounding_box_3 b;
    typename Object_list::const_iterator o = O.begin();
    Vertex_handle v;
    while(o != O.end() && !CGAL::assign(v, *o)) ++o;
    if(o != O.end()) {
      FT q[3];
      q[0] = v->point().x();
      q[1] = v->point().y();
      q[2] = v->point().z();
      Bounding_box_3 b(q);
      for(++o; o != O.end(); ++o) {
	if( CGAL::assign( v, *o)) {
	  b.extend(v->point());
	}
      }
      return b;
    }
    FT q[3];
    q[0] = q[1] = q[2] = 0;
    return Bounding_box_3(q);
  }

  /*
  Bounding_box_3 operator()(Object_handle o) const {
    Vertex_handle v;
    Halfedge_handle e;
    Halffacet_handle f;
    if( CGAL::assign( v, o))
      return operator()(v);
    else if( CGAL::assign( e, o))
      return operator()(e);
    else if( CGAL::assign( f, o))
      return operator()(f);
    else {
      Halffacet_triangle_handle t;
      if( CGAL::assign( t, o))
	return operator()(t);
      else
	CGAL_assertion_msg( 0, "wrong handle");
    }
    return Bounding_box_3(); // never reached
  }

  Bounding_box_3 operator()(Vertex_handle v) const {    
    Bounding_box_3 b;
    b.extend(v->point());
    return b;
  }

  Bounding_box_3 operator()(Halfedge_handle e) const {
    Bounding_box_3 b;
    b.extend(e->source()->point());
    b.extend(e->twin()->source()->point());
    return b;
  }

  Bounding_box_3 operator()(Halffacet_triangle_handle t) const {
    Bounding_box_3 bbox;
    Triangle_3 tr(t.get_triangle());
    for( int i = 0; i < 3; ++i)
      bbox.extend(tr[i]);
    return bbox;
  }

  Bounding_box_3 operator()(Halffacet_handle f) const {
    CGAL_assertion( f->facet_cycles_begin() != 
		    Halffacet_cycle_iterator());
    Halffacet_cycle_iterator fc(f->facet_cycles_begin());
    SHalfedge_handle e;
    CGAL_assertion(fc.is_shalfedge());
    e = SHalfedge_handle(fc);
    SHalfedge_around_facet_circulator sc(e), send(sc);
    CGAL_assertion( !is_empty_range( sc, send));
    Bounding_box_3 b;
    CGAL_For_all( sc, send)
      b.extend(sc->source()->source()->point());
    return b;
  }
  */
};

template <class Decorator>
class SNC_k3_tree_traits {

public:
  typedef Decorator SNC_decorator;
  typedef typename SNC_decorator::SNC_structure SNC_structure;
  typedef typename SNC_structure::Kernel Kernel;

  typedef typename SNC_structure::Infi_box Infimaximal_box;
  typedef typename SNC_decorator::Decorator_traits Decorator_traits;
  typedef typename Decorator_traits::Vertex_handle Vertex_handle;
  typedef typename Decorator_traits::Halfedge_handle Halfedge_handle;
  typedef typename Decorator_traits::Halffacet_handle Halffacet_handle;
#ifdef CGAL_NEF3_TRIANGULATE_FACETS
  typedef typename SNC_structure::Halffacet_triangle_handle 
                                  Halffacet_triangle_handle;
#endif
#ifdef CGAL_NEF3_FACET_WITH_BOX
  typedef typename SNC_structure::Partial_facet Partial_facet;
#endif

  typedef typename SNC_structure::Object_handle Object_handle;
  typedef std::vector<Object_handle> Object_list;

  typedef typename Kernel::Point_3 Point_3;
  typedef typename Kernel::Segment_3 Segment_3;
  typedef typename Kernel::Ray_3 Ray_3;
  typedef typename Kernel::Vector_3 Vector_3;
  typedef typename Kernel::Plane_3 Plane_3;
  typedef typename Kernel::Triangle_3 Triangle_3;
  typedef typename Kernel::Aff_transformation_3 Aff_transformation_3;