infimaximal_box.h

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

    return CGAL_NTS abs(p.hy()) == RT(0,p.hw()[0]);
  }

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

  static Point_3 create_extended_point(NT x, NT y, NT z) {
    return Point_3(RT(0,x), RT(0,y), RT(0,z), RT(1));
  }

  static Plane_3 create_extended_plane(NT a, NT b, NT c, NT d) {
    return Plane_3(a,b,c,RT(0,d));
  }

  static Point_3 create_extended_point(NT a0,NT a1,NT b0,NT b1,NT c0,NT c1,NT d) {
    return Point_3(RT(a0,a1),RT(b0,b1),RT(c0,c1),RT(d));
  }

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

  template <typename SNC_structure>
  static bool is_beyond_Infibox(typename SNC_structure::SFace_handle sf, 
				SNC_structure& snc) {
    typename SNC_structure::SNC_decorator D(snc);
    return (D.volume(sf) == snc.volumes_begin());
  }

  template <typename SNC_constructor, typename Mark>
  static std::list<typename SNC_constructor::Vertex_handle> 
    create_vertices_on_infibox(SNC_constructor& C, 
			       const Plane_3& h, const std::list<Point_3>& points, 
			       const Mark& bnd, const Mark& inside, const Mark& outside) {
    return C.create_vertices_on_infibox(h,points,bnd,inside,outside);
  }

  template <typename SNC_constructor>
  static void create_vertices_of_box_with_plane(SNC_constructor& C, const Plane_3& h, bool b) {
    C.create_vertices_of_box_with_plane(h, b);
  }

  static void compute_min_max(const Plane_3& h, NT orth_coords[3], int& min, int& max) {
    Vector_3 orth = h.orthogonal_vector();
    
    orth_coords[0] = CGAL_NTS abs(orth.hx()[0]);
    orth_coords[1] = CGAL_NTS abs(orth.hy()[0]);
    orth_coords[2] = CGAL_NTS abs(orth.hz()[0]);
    
    max = 0;
    if(orth_coords[1] > orth_coords[0])
      max = 1;
    if(orth_coords[2] > orth_coords[max])
      max = 2;   
    
    min = 0;
    if(orth_coords[1] < orth_coords[0])
      min = 1;
    if(orth_coords[2] < orth_coords[min])
      min = 2;
  }

  template<typename SNC_structure>
  static NT compute_evaluation_constant_for_halfedge_pairup(const SNC_structure& snc) {
    NT eval = 0;
    typename SNC_structure::Vertex_const_iterator v;
    CGAL_forall_vertices(v, snc) {
      Point_3 p(v->point());
      if(p.hx()[0] > eval) eval = p.hx()[0];
      if(p.hy()[0] > eval) eval = p.hy()[0];
      if(p.hz()[0] > eval) eval = p.hz()[0];
    }
    eval *= 4;
    if(eval == 0) return 1;
    return eval;
  }

  static Point_3 scale_infibox_vertex(const Point_3 pin, const Aff_transformation_3& aff) {
    RT lx(pin.hx()[0]);
    RT ly(pin.hy()[0]);
    RT lz(pin.hz()[0]);
    RT hx(pin.hx()-lx);
    RT hy(pin.hy()-ly);
    RT hz(pin.hz()-lz);
    RT hw(pin.hw());
    Point_3 p(Point_3(lx,ly,lz,hw).transform(aff));
    return Point_3(hx+p.hx(),hy+p.hy(),hz+p.hz(),hw);    
  }

  static Point_3 normalize_transformed_vertex(const Point_3& p) {
    int i=0;
    if(CGAL_NTS abs(p.hx()) < CGAL_NTS abs(p.hy()))
      if(CGAL_NTS abs(p.hy()) < CGAL_NTS abs(p.hz()))
	i = 2;
      else
	i = 1;
    else if(CGAL_NTS abs(p.hx()) < CGAL_NTS abs(p.hz()))
      i = 2;

    switch(i) {
    case 0:
      CGAL_assertion(p.hx().degree() == 1);
      if(p.hx()[1] > 0)
	return Point_3(RT(0,p.hx()[1]*p.hw()[0]),
		       RT(p.hy()[0]*p.hx()[1]-p.hx()[0]*p.hy()(1),p.hy()(1)*p.hw()[0]),
		       RT(p.hz()[0]*p.hx()[1]-p.hx()[0]*p.hz()(1),p.hz()(1)*p.hw()[0]),
		       RT(p.hw()[0]*p.hx()[1]));
      else
	return Point_3(RT(0,-p.hx()[1]*p.hw()[0]),
		       RT(p.hy()[0]*p.hx()[1]-p.hx()[0]*p.hy()(1),-p.hy()(1)*p.hw()[0]),
		       RT(p.hz()[0]*p.hx()[1]-p.hx()[0]*p.hz()(1),-p.hz()(1)*p.hw()[0]),
		       RT(p.hw()[0]*p.hx()[1]));
    case 1:
      CGAL_assertion(p.hy().degree() == 1);
      if(p.hy()[1] > 0)
	return Point_3(RT(p.hx()[0]*p.hy()[1]-p.hy()[0]*p.hx()(1),p.hx()(1)*p.hw()[0]),
		       RT(0,p.hy()[1]*p.hw()[0]),
		       RT(p.hz()[0]*p.hy()[1]-p.hy()[0]*p.hz()(1),p.hz()(1)*p.hw()[0]),
		       RT(p.hw()[0]*p.hy()[1]));
      else
	return Point_3(RT(p.hx()[0]*p.hy()[1]-p.hy()[0]*p.hx()(1),-p.hx()(1)*p.hw()[0]),
		       RT(0,-p.hy()[1]*p.hw()[0]),
		       RT(p.hz()[0]*p.hy()[1]-p.hy()[0]*p.hz()(1),-p.hz()(1)*p.hw()[0]),
		       RT(p.hw()[0]*p.hy()[1]));
    case 2:
      CGAL_assertion(p.hz().degree() == 1);
      if(p.hz()[1] > 0)
	return Point_3(RT(p.hx()[0]*p.hz()[1]-p.hz()[0]*p.hx()(1),p.hx()(1)*p.hw()[0]),
		       RT(p.hy()[0]*p.hz()[1]-p.hz()[0]*p.hy()(1),p.hy()(1)*p.hw()[0]),
		       RT(0,p.hz()[1]*p.hw()[0]),
		       RT(p.hw()[0]*p.hz()[1]));
      else
	return Point_3(RT(p.hx()[0]*p.hz()[1]-p.hz()[0]*p.hx()(1),-p.hx()(1)*p.hw()[0]),
		       RT(p.hy()[0]*p.hz()[1]-p.hz()[0]*p.hy()(1),-p.hy()(1)*p.hw()[0]),
		       RT(0,-p.hz()[1]*p.hw()[0]),
		       RT(p.hw()[0]*p.hz()[1]));
    default: CGAL_assertion_msg(false, "wrong value");
    }
    return Point_3();
  }

  static typename std::list<Point_3>::const_iterator segment_on_side(int side_of_point, 
								     const std::list<Point_3>& segs) {  

    typename std::list<Point_3>::const_iterator s1,t1;
    for(s1 = segs.begin(); s1 != segs.end(); ++s1) {
      t1 = s1;
      ++t1;
      if(t1 == segs.end()) t1 = segs.begin();
      switch(side_of_point) {
      case  1: 
	if( s1->hx()(1) != s1->hw()) continue; 
	if( t1->hx()(1) != t1->hw()) continue;
	return s1;
      case -1: 
	if(-s1->hx()(1) != s1->hw()) continue;
	if(-t1->hx()(1) != t1->hw()) continue; 
	return s1;
      case  2: 
	if( s1->hy()(1) != s1->hw()) continue;
	if( t1->hy()(1) != t1->hw()) continue;
	return s1;	break;
      case -2: 
	if(-s1->hy()(1) != s1->hw()) continue; 
	if(-t1->hy()(1) != t1->hw()) continue; 
	return s1;
      case  3: 
	if( s1->hz()(1) != s1->hw()) continue; 
	if( t1->hz()(1) != t1->hw()) continue; 
	return s1;
      case -3: 
	if(-s1->hz()(1) != s1->hw()) continue; 
	if(-t1->hz()(1) != t1->hw()) continue; 
	return s1;
      default: CGAL_assertion_msg(false, "wrong value");
      }
    }
    CGAL_assertion_msg(false, "this line of shall not be reached");
    return s1;
  }

  template <typename SNC_constructor>
  static void initialize_infibox_vertices(SNC_constructor& C, bool space) {
    C.create_extended_box_corner( 1, 1, 1, space );
    C.create_extended_box_corner(-1, 1, 1, space );
    C.create_extended_box_corner( 1,-1, 1, space );
    C.create_extended_box_corner(-1,-1, 1, space );
    C.create_extended_box_corner( 1, 1,-1, space );
    C.create_extended_box_corner(-1, 1,-1, space );
    C.create_extended_box_corner( 1,-1,-1, space );
    C.create_extended_box_corner(-1,-1,-1, space ); 
  }

  /*
  template <typename SHalfedge_handle>
  static bool is_edge_on_infibox(SHalfedge_handle e) {

    Point_3 p  = e->center_vertex()->point();
    if(is_standard(p)) return false;

    Vector_3 v(e->vector());
    CGAL_assertion(p.hw().degree() == 0);
    FT Outer(RT(0,1));

    if(CGAL_NTS abs(p.x()) == Outer && 
       ((p.x() > 0 && v.x() > 0)||(p.x() < 0 && v.x() < 0))) return false;
    if(CGAL_NTS abs(p.y()) == Outer && 
       ((p.y() > 0 && v.y() > 0)||(p.y() < 0 && v.y() < 0))) return false;
    if(CGAL_NTS abs(p.z()) == Outer && 
       ((p.z() > 0 && v.z() > 0)||(p.z() < 0 && v.z() < 0))) return false;

    if(CGAL_NTS abs(p.x()) == Outer && v.x() == 0) return true;
    if(CGAL_NTS abs(p.y()) == Outer && v.y() == 0) return true;
    if(CGAL_NTS abs(p.z()) == Outer && v.z() == 0) return true;

    return false; 
  }
  */

  template <typename SHalfedge_handle>
  static bool is_edge_on_infibox(SHalfedge_handle e) {

    Point_3 p  = e->center_vertex()->point();
    if(is_standard(p)) return false;

    Vector_3 v(e->vector());
    CGAL_assertion(p.hw().degree() == 0);
    RT Outer(0,CGAL_NTS abs(p.hw()[0]));

    if(CGAL_NTS abs(p.hx()) == Outer && 
       ((p.hx() > 0 && v.hx() > 0)||(p.hx() < 0 && v.hx() < 0))) return false;
    if(CGAL_NTS abs(p.hy()) == Outer && 
       ((p.hy() > 0 && v.hy() > 0)||(p.hy() < 0 && v.hy() < 0))) return false;
    if(CGAL_NTS abs(p.hz()) == Outer && 
       ((p.hz() > 0 && v.hz() > 0)||(p.hz() < 0 && v.hz() < 0))) return false;

    if(CGAL_NTS abs(p.hx()) == Outer && v.hx() == 0) return true;
    if(CGAL_NTS abs(p.hy()) == Outer && v.hy() == 0) return true;
    if(CGAL_NTS abs(p.hz()) == Outer && v.hz() == 0) return true;

    return false; 
  }

  template <typename SHalfedge_handle>
  static bool is_sedge_on_infibox(SHalfedge_handle sh) {

    Point_3 p = sh->source()->center_vertex()->point();
    CGAL_NEF_TRACEN("Point " << p);
    if(is_standard(p)) return false;

    CGAL_NEF_TRACEN("Circle " << sh->circle() << 
	   " has signum " << sign_of(sh->circle()));
    CGAL_assertion(p.hw().degree() == 0);
    RT R(0,CGAL_NTS abs(p.hw()[0]));

    if((sh->circle().a() == 0 && sh->circle().b() == 0 
	&& CGAL_NTS abs(p.hz())== R) || 
       (sh->circle().a() == 0 && sh->circle().c() == 0 
	&& CGAL_NTS abs(p.hy())== R) ||
       (sh->circle().b() == 0 && sh->circle().c() == 0 
	&& CGAL_NTS abs(p.hx())== R))
      if(is_edge_on_infibox(sh->source()) && 
	 is_edge_on_infibox(sh->twin()->source()))
	return true;

    return false;
  }
  
  template <typename Sphere_map>
  static bool is_complex_facet_infibox_intersection(const Sphere_map& sm) {
    
    typename Sphere_map::SHalfedge_const_iterator sei;
    bool found = false;
    CGAL_forall_sedges(sei, sm) {
      if(!is_sedge_on_infibox(sei)) {
	if(found)
	  return true;
	else
	  found = true;
      }
    }
    return false;
  }

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

  template <typename Halfedge_handle>
  static bool is_type4(Halfedge_handle e) {

    Point_3 p(e->center_vertex()->point());
    Direction_3 d(e->vector());

    if((CGAL_NTS abs(p.hx()) == CGAL_NTS abs(p.hw()) || 
	d == Direction_3(1,0,0) ||
	d == Direction_3(-1,0,0)) &&
       (CGAL_NTS abs(p.hy()) == CGAL_NTS abs(p.hw()) || 
	d == Direction_3(0,1,0) ||
	d == Direction_3(0,-1,0)) &&
       (CGAL_NTS abs(p.hz()) == CGAL_NTS abs(p.hw()) || 
	d == Direction_3(0,0,1) ||
	d == Direction_3(0,0,-1)))
      return true;
    return false;
  }

  template <typename Halfedge_handle>
  static bool is_type3(Halfedge_handle e) {

    Point_3 p(e->center_vertex()->point());
    Direction_3 d(e->vector());
    
    if(d == Direction_3(1,0,0) || d == Direction_3(-1,0,0)) {
      if(CGAL_NTS abs(p.hy()) == CGAL_NTS abs(p.hw()))
	return true;
      return false;
    }
    if(d == Direction_3(0,1,0) || d == Direction_3(0,-1,0)) {
      if(CGAL_NTS abs(p.hx()) == CGAL_NTS abs(p.hw()))
	return true;
      return false;
    }
    if(d == Direction_3(0,0,1) || d == Direction_3(0,0,-1)) {
      if(CGAL_NTS abs(p.hy()) == CGAL_NTS abs(p.hw()))
	return true;
      return false;
    }

    return false;
  }

};

CGAL_END_NAMESPACE
#endif // CGAL_INFIMAXIMAL_BOX_H