infimaximal_box.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: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.3-branch/Nef_3/include/CGAL/Nef_3/Infimaximal_box.h $
// $Id: Infimaximal_box.h 38161 2007-04-17 08:27:13Z hachenb $
// 
//
// Author(s)     : Peter Hachenberger    <[e-mail]>

#ifndef CGAL_INFIMAXIMAL_BOX_H
#define CGAL_INFIMAXIMAL_BOX_H

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

#include <CGAL/Extended_cartesian.h>
#include <CGAL/Extended_homogeneous.h>

#include <CGAL/Nef_3/SNC_intersection.h>

CGAL_BEGIN_NAMESPACE

template <class T, class Kernel>
class Infimaximal_box {

 public:
  typedef typename Kernel::RT               NT;
  typedef typename Kernel::RT               RT;
  typedef Kernel                            Standard_kernel;
  typedef typename Kernel::Point_3          Point_3;
  typedef typename Kernel::Vector_3         Vector_3;
  typedef typename Kernel::Plane_3          Plane_3;
  typedef typename Kernel::Ray_3            Ray_3;
  typedef typename Kernel::Aff_transformation_3   Aff_transformation_3;
  typedef Plane_3                           Standard_plane;
  typedef Vector_3                          Standard_vector;
  typedef Point_3                           Standard_point;

  static bool standard_kernel() {
    return true;
  }

  static bool extended_kernel() {
    return false;
  }

  static bool is_standard(const Point_3& ) {
    return true;
  }

  static bool is_standard(const Plane_3& ) {
    return true;
  }

  static bool check_point_on_plane(Point_3 p, Plane_3 h) {
    return (p.hx()*h.a()+p.hy()*h.b()+p.hz()*h.c()+p.hw()*h.d() == 0);
  }

  static Point_3 simplify(Point_3& p) {
    return p;
  }

  static Standard_point standard_point(Point_3 p, NT =1) {
    return p;
  }

  static Standard_plane standard_plane(Plane_3 p, NT =1) {
    return p;
  }

  static Standard_vector standard_vector(Vector_3 p) {
    return p;
  }

  static void set_size_of_infimaximal_box(const NT& ) {}

  static int degree(const RT& ) {
    return 0;
  }

  static NT get_coeff(const RT& p, unsigned int ) {
    return p;
  }

  static NT eval_at(const RT& p) {
    return p;
  }

  static bool is_infibox_corner(const Point_3& ) {
    return false;
  }

  template <typename Sphere_map>
  static bool is_complex_facet_infibox_intersection(const Sphere_map& ) {
    return false;
  }

  static int type_of_infibox_point(const Point_3& ) {
    return 0;
  }

  template <typename SNC_structure>
  static typename SNC_structure::Volume_const_handle getNirvana(SNC_structure& snc) {
    return snc.volumes_begin();
  }

  template <typename SNC_structure>
  static bool is_beyond_Infibox(typename SNC_structure::SFace_handle , 
				SNC_structure& ) {
    return false;
  }

  static bool x_on_box(const Point_3& ) {
    return false;
  }

  static bool y_on_box(const Point_3& ) {
    return false;
  }

  static bool z_on_box(const Point_3& ) {
    return false;
  }

  template<typename SNC_structure>
  static NT compute_evaluation_constant_for_halfedge_pairup(const SNC_structure& ) {
    return NT(1);
  }

  static void compute_min_max(const Plane_3& , NT orth_coords[3], int& /* min */, int& /* max */) { }

  static Point_3 scale_infibox_vertex(const Point_3& ) {
    return Point_3();
  }

  static Point_3 normalize_transformed_vertex(const Point_3& ) {
    return Point_3();
  }

  template <typename SNC_constructor, typename Mark>
  static std::list<typename SNC_constructor::Vertex_handle> 
    create_vertices_on_infibox(SNC_constructor&, 
			       const Plane_3&, const std::list<Point_3>&, 
			       const Mark&, const Mark&, const Mark&) {
    // TODO: warning oder assertion einbauen
    return std::list<typename SNC_constructor::Vertex_handle>();
  }

  template <typename SNC_constructor>
  static std::list<Point_3> find_points_of_box_with_plane(SNC_constructor&, const Plane_3&) {
    return std::list<Point_3>();
  }

  static typename std::list<Point_3>::const_iterator segment_on_side(int side_of_point, 
							      const std::list<Point_3>& segs) {  
    return segs.begin();
  }

  static Point_3 create_extended_point(NT, NT, NT) {
    std::cerr << "function should not be called" << std::endl;
    CGAL_assertion_msg(0,"function should not be called");
    return Point_3(0,0,0);
  }

  static Plane_3 create_extended_plane(NT, NT, NT, NT) {
    std::cerr << "function should not be called" << std::endl;
    return Plane_3(1,0,0,0);
  }

  template <typename SNC_decorator, typename Point>
    static Ray_3 get_ray(SNC_decorator& , Point& p) {
    //    return D.point(D.vertex(D.shells_begin(D.volumes_begin())));
    return Ray_3(p, Vector_3(-1,0,0));
  }

  template <typename SNC_constructor_>
  static void create_vertices_of_box_with_plane(SNC_constructor_&, const Plane_3&, bool) {
    std::cerr << "Constructor not available for this Kernel" << std::endl;
  }

  template <typename SNC_constructor>
  static void initialize_infibox_vertices(SNC_constructor& , bool ) {
  }

  template <typename SHalfedge_handle>
  static bool is_sedge_on_infibox(SHalfedge_handle ) {
    return false;
  }

  template <typename Halfedge_handle>
  static bool is_edge_on_infibox(Halfedge_handle ) {
    return false; 
  }

  template <typename Halfedge_handle>
  static bool is_type4(Halfedge_handle ) {return false;}

  template <typename Halfedge_handle>
  static bool is_type3(Halfedge_handle ) {return false;}
};

template <class Kernel>
class Infimaximal_box<Tag_true, Kernel> {

 public:
  typedef typename Kernel::RT                    RT;
  typedef typename Kernel::RT::NT                NT;
  typedef typename Kernel::Standard_kernel       Standard_kernel;
  typedef typename Standard_kernel::Point_3      Standard_point;
  typedef typename Standard_kernel::Plane_3      Standard_plane;
  typedef typename Standard_kernel::Vector_3     Standard_vector;
  typedef typename Kernel::Point_3               Point_3;
  typedef typename Kernel::Plane_3               Plane_3;
  typedef typename Kernel::Vector_3              Vector_3;
  typedef typename Kernel::Segment_3             Segment_3;
  typedef typename Kernel::Direction_3           Direction_3;
  typedef typename Kernel::Aff_transformation_3  Aff_transformation_3;

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

  //  typedef SM_decorator<SNC_structure>        SM_decorator;

  enum Boundary { EXCLUDED=0, INCLUDED=1 };
  
  static const int RADIUS = 10000000;

  static bool standard_kernel() {
    return false;
  }

  static bool extended_kernel() {
    return true;
  }

  static bool is_standard(const Point_3& p) {
    CGAL_assertion(p.hw().degree()==0);
    return (p.hx().degree()==0 && p.hy().degree()==0 && p.hz().degree()==0);
  }

  static bool is_standard(const Plane_3& p) {
    return (p.d().degree() == 0);
  }

  static int type_of_infibox_point(const Point_3& p) {
    int res = 0;
    RT W(NT(0),p.hw()[0]);
    if(CGAL_NTS abs(p.hx()) == W) ++res;
    if(CGAL_NTS abs(p.hy()) == W) ++res;
    if(CGAL_NTS abs(p.hz()) == W) ++res;
    return res;
  }

  static bool is_infibox_corner(const Point_3& p) {
    return type_of_infibox_point(p) == 3;
  }

  static Point_3 simplify(Point_3& p) {
    CGAL_assertion(p.hw().degree() == 0);
    int deg = p.hx().degree() > p.hy().degree() 
      ? p.hx().degree() 
      : p.hy().degree();
    deg = p.hz().degree() > deg 
      ? p.hz().degree() 
      : deg;
    return Point_3(p.hx().degree() == deg ? p.hx()[deg] : 0,
		   p.hy().degree() == deg ? p.hy()[deg] : 0,
		   p.hz().degree() == deg ? p.hz()[deg] : 0,
		   p.hw()[0]);
  }

  static int degree(const RT& p) {
    return p.degree();
  }

  static NT get_coeff(const RT& p, unsigned int i) {
    return p[i];
  }

  static NT eval_at(const RT& p, NT d=RADIUS) {
    return p.eval_at(d);
  }

  static Point_3 target_for_ray_shoot_on_minus_x_direction(Point_3 p) {
    CGAL_warning(is_standard(p));
    return Point(RT(0,-1), RT(p.hy()[0]), RT(p.hz()[0]), RT(p.hw()[0]));
  }

  static bool check_point_on_plane(Point_3 p, Plane_3 h) {
    NT x(p.hx().eval_at(100));
    NT y(p.hy().eval_at(100));
    NT z(p.hz().eval_at(100));
    NT w(p.hw().eval_at(100));
    NT a(h.a().eval_at(100));
    NT b(h.b().eval_at(100));
    NT c(h.c().eval_at(100));
    NT d(h.d().eval_at(100));
    return (x*a+y*b+z*c+w*d == 0);
  }

  static Standard_point standard_point(Point_3 p, NT d=1) {
    return Standard_point(p.hx().eval_at(d),
			  p.hy().eval_at(d),
			  p.hz().eval_at(d),
			  p.hw().eval_at(1));
  }

  static Standard_plane standard_plane(Plane_3 p, NT d=1) {
    return Standard_plane(p.a().eval_at(1),
			  p.b().eval_at(1),
			  p.c().eval_at(1),
			  p.d().eval_at(d));
  }

  static Standard_vector standard_vector(Vector_3 p) {
    return Standard_vector(p.hx().eval_at(1),
			   p.hy().eval_at(1),
			   p.hz().eval_at(1));
  }

  static void set_size_of_infimaximal_box(NT size) {
    RT::infi_maximal_value() = size;
  }

  static bool x_on_box(const Point_3& p) {
    return CGAL_NTS abs(p.hx()) == RT(0,p.hw()[0]);
  }

  static bool y_on_box(const Point_3& p) {