snc_io_parser.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/SNC_io_parser.h $
// $Id: SNC_io_parser.h 38348 2007-04-19 17:29:45Z hachenb $
// 
//
// Author(s)     : Michael Seel    <[e-mail]>
//                 Miguel Granados <[e-mail]>
//                 Susan Hert      <[e-mail]>
//                 Lutz Kettner    <[e-mail]>

#ifndef CGAL_SNC_IO_PARSER_H
#define CGAL_SNC_IO_PARSER_H

#include <CGAL/basic.h>
#include <CGAL/Unique_hash_map.h>
#include <CGAL/Nef_S2/SM_decorator.h>
#include <CGAL/Nef_3/SNC_structure.h>
#include <CGAL/Nef_3/SNC_decorator.h>
#include <CGAL/Nef_3/SNC_constructor.h>
#include <CGAL/Nef_2/Object_index.h>
#include <CGAL/Nef_S2/Normalizing.h>
#include <vector>
#include <CGAL/Fraction_traits.h>

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

CGAL_BEGIN_NAMESPACE

template<typename T>
class moreLeft : public T {
  
  typedef typename T::SM_decorator      SM_decorator;
  typedef typename T::SHalfedge_handle  SHalfedge_handle;
  typedef typename T::Vector_3          Vector_3;
  typedef typename T::FT                FT;
  typedef typename T::RT                RT;
 
 public:
  moreLeft(T D) : T(D) {}
  
  int operator()(SHalfedge_handle se1, SHalfedge_handle se2) {

    CGAL_assertion(se1 != SHalfedge_handle());
    if(se2 == SHalfedge_handle())
      return -1;

    SM_decorator SM(&*se1->source()->source());
    Vector_3 vec1 = se1->circle().orthogonal_vector();
    Vector_3 vec2 = se2->circle().orthogonal_vector();

    if(vec1 == vec2)
      return 0;
    
    if(vec1.x() == RT(0) && vec2.x() == RT(0)) {
      if(vec1.y() != vec2.y()) {
	if(vec1.y() < vec2.y())
	  return -1;
	else 
	  return 1;
      }
      if(vec1.z() < vec2.z())
	return -1;
      else
	return 1;
    }
    
    Vector_3 minus(-1,0,0);
    FT sk1(minus*vec1),  sk2(minus*vec2);
    if((sk1 >= FT(0) && sk2 <= FT(0)) ||
       (sk1 <= FT(0) && sk2 >= FT(0))) {
      if(sk1 > FT(0) || sk2 < FT(0))
	return -1;
      else
	return 1;
    }

    FT len1 = vec1.x()*vec1.x()+vec1.y()*vec1.y()+vec1.z()*vec1.z();
    FT len2 = vec2.x()*vec2.x()+vec2.y()*vec2.y()+vec2.z()*vec2.z();
    FT diff = len1*sk2*sk2 - len2*sk1*sk1;
    
    if(diff != FT(0)) {
      if((sk1>FT(0) && diff<FT(0)) || (sk1<FT(0) && diff>FT(0)))
	return -1;
      else 
	return 1;
    }

    return 0;
  }
};

template <typename T>
class sort_vertices : public SNC_decorator<T> {
  
  typedef T SNC_structure;
  typedef CGAL::SNC_decorator<T>          Base;
  typedef typename T::Vertex_handle Vertex_handle;
  typedef typename T::Point_3       Point_3;
  
 public:
  sort_vertices(T& D) : Base(D) {}
  
  bool operator() (Vertex_handle v1, Vertex_handle v2) const {
    return lexicographically_xyz_smaller(v1->point(), v2->point());
  }
};
  
template <typename T>
class sort_edges : public SNC_decorator<T> {
  
  typedef T SNC_structure;  
  typedef CGAL::SNC_decorator<T>            Base;
  typedef typename T::Halfedge_handle Halfedge_handle;
  
 public:
  sort_edges(T& D) : Base(D) {}
  
  bool operator() (Halfedge_handle e1, Halfedge_handle e2) const {
    sort_vertices<T> SORT(*this->sncp());
    if(e1->source() != e2->source())
      return SORT(e1->source(),e2->source());
    return SORT(e1->twin()->source(), e2->twin()->source());
  }
};

template <typename T>
class sort_facets : public SNC_decorator<T> {
  
  typedef T SNC_structure;  
  typedef SNC_decorator<T>             Base;
  typedef typename T::Halffacet_handle Halffacet_handle;
  typedef typename T::SHalfedge_handle SHalfedge_handle;
  typedef typename T::Vector_3         Vector_3;
  typedef typename T::Plane_3          Plane_3;

 public:
  sort_facets(T& D) : Base(D) {}
  
  bool operator() (Halffacet_handle f1, Halffacet_handle f2) const {
    

    Plane_3 p1(f1->plane());
    Plane_3 p2(f2->plane());
    
    if(p1.d() != p2.d())
      return p1.d() < p2.d();
    else if(p1.a() != p2.a())
      return p1.a() < p2.a();
    else if(p1.b() != p2.b())
      return p1.b() < p2.b();    
    else if(p1.c() != p2.c())
      return p1.c() < p2.c();    

    SHalfedge_handle se1 = SHalfedge_handle(f1->facet_cycles_begin());
    SHalfedge_handle se2 = SHalfedge_handle(f2->facet_cycles_begin());
    
    sort_vertices<T> SORT(*this->sncp());
    if(se1->source()->source() != se2->source()->source())
      return SORT(se1->source()->source(), se2->source()->source());

    se1 = se1->next();
    se2 = se2->next();
    CGAL_assertion(se1->source()->source() != se2->source()->source());
    return SORT(se1->source()->source(), se2->source()->source());

 
  }
};

template <typename T>
class sort_sedges : public SNC_decorator<T> {
  
  typedef T SNC_structure;  
  typedef CGAL::SNC_decorator<T>             Base;
  typedef CGAL::SM_decorator<T>          SM_decorator;
  typedef typename T::Vertex_handle    Vertex_handle;
  typedef typename T::SHalfedge_handle SHalfedge_handle;
  typedef typename T::Sphere_circle    Sphere_circle;

 public:
  sort_sedges(T& D) : Base(D) {}
  
  bool operator() (SHalfedge_handle se1, SHalfedge_handle se2) const {
    CGAL_NEF_TRACEN("sort sedges");
    if(se1 == se2) return false;
    sort_vertices<T> SORT(*this->sncp());
    CGAL_NEF_TRACEN("  center verices: " << se1->source()->source()->point() << 
		    " , " << se2->source()->source()->point());
    if(se1->source()->source() != se2->source()->source())
      return SORT(se1->source()->source(),se2->source()->source());
    if(se1 == se2->twin()) {
      if(se1->source() == se2->source()) {
	Sphere_circle vec1 = se1->circle();
	Sphere_circle vec2 = se2->circle();
	if(vec1.a() != vec2.a())
	  return vec1.a() < vec2.a();
	else if(vec1.b() != vec2.b())
	  return vec1.b() < vec2.b();
	return vec1.c() < vec2.c();     	
      }
      else
	return SORT(se1->source()->twin()->source(), se2->source()->twin()->source());
    }

    if(SORT(se1->twin()->source()->twin()->source(), 
	    se1->source()->twin()->source()))
      se1 = se1->twin();
    if(SORT(se2->twin()->source()->twin()->source(), 
	    se2->source()->twin()->source()))
      se2 = se2->twin();
    CGAL_NEF_TRACEN("  ssources " << se1->source()->twin()->source()->point() 
		    << " , " << se2->source()->twin()->source()->point());
    if(se1->source() != se2->source())
      return SORT(se1->source()->twin()->source(), se2->source()->twin()->source());
    CGAL_NEF_TRACEN("  starget " << se1->twin()->source()->twin()->source()->point() << 
		    " , " << se2->twin()->source()->twin()->source()->point());
    if(se1->twin()->source()->twin()->source() != se2->twin()->source()->twin()->source())
      return SORT(se1->twin()->source()->twin()->source(), se2->twin()->source()->twin()->source());

    CGAL_assertion(se1->circle() != se2->circle());
    Sphere_circle vec1 = se1->circle();
    Sphere_circle vec2 = se2->circle();
 
    if(vec1.a() != vec2.a())
      return vec1.a() < vec2.a();
    else if(vec1.b() != vec2.b())
      return vec1.b() < vec2.b();
    return vec1.c() < vec2.c();     
  }
};


template <typename T>
class sort_sloops : public SNC_decorator<T> {
  
  typedef T SNC_structure;  
  typedef CGAL::SNC_decorator<T>             Base;
  typedef typename T::SHalfloop_handle SHalfloop_handle;
  
 public:
  sort_sloops(T& D) : Base(D) {}
  
  bool operator() (SHalfloop_handle sl1, SHalfloop_handle sl2) const {
    if(sl1 == sl2) return false;
    sort_vertices<T> SORTV(*this->sncp());
    sort_facets<T> SORTF(*this->sncp());
    if(sl1->incident_sface()->center_vertex() != sl2->incident_sface()->center_vertex())
      return SORTV(sl1->incident_sface()->center_vertex(),sl2->incident_sface()->center_vertex());
    return SORTF(sl1->facet(), sl2->facet());
  }
};

template <typename T>
class sort_sface_cycle_entries : public SNC_decorator<T> {
  
  typedef T                             SNC_structure;  
  typedef CGAL::SNC_decorator<T>        Base;
  typedef typename T::SM_decorator      SM_decorator;
  typedef typename T::Object_handle     Object_handle;
  typedef typename T::SVertex_handle    SVertex_handle;
  typedef typename T::SHalfedge_handle  SHalfedge_handle;
  typedef typename T::SHalfloop_handle  SHalfloop_handle;
  typedef typename T::SFace_handle      SFace_handle;
  typedef typename T::Point_3           Point_3;
  typedef typename T::Vector_3          Vector_3;
  
 public:
  sort_sface_cycle_entries(T D) : Base(D) {}
  
  bool operator() (Object_handle o1, Object_handle o2) const {
    CGAL_NEF_TRACEN("sort sface cycles ");
    SVertex_handle sv1, sv2;
    SHalfedge_handle se1, se2;
    SHalfloop_handle sl1, sl2;

    if(!CGAL::assign(se1,o1) && !CGAL::assign(sl1,o1) && !CGAL::assign(sv1,o1))
      CGAL_assertion_msg(0,"wrong handle");
    
    if(!CGAL::assign(se2,o2) && !CGAL::assign(sl2,o2) && !CGAL::assign(sv2,o2))
      CGAL_assertion_msg(0,"wrong handle");    
    
    if(se1 != SHalfedge_handle() && se2 == SHalfedge_handle())
      return true;

    if(se1 == SHalfedge_handle() && se2 != SHalfedge_handle())
      return false;

    if(sl1 != SHalfloop_handle() && sv2 != SVertex_handle())
      return true;

    if(sl2 != SHalfloop_handle() && sv1 != SVertex_handle())
      return false;

    if(se1 != SHalfedge_handle() && se2 != SHalfedge_handle()) {
      CGAL_NEF_TRACEN("  sedges " << &*se1 << " , " << &*se2);
      sort_sedges<SNC_structure> SORT(*this->sncp());
      return SORT(se1,se2);
      /*
	sort_vertices<SNC_structure> SORT(*this->sncp());
      if(ssource(se1) != ssource(se2))
	return SORT(se1->source()->twin()->source(), se2->source()->twin()->source());
      else
	return SORT(se1->target(), se2->target());
      */
    }

    if(sl1 != SHalfloop_handle() && sl2 != SHalfloop_handle()) {
      Vector_3 vec1(sl1->circle().orthogonal_vector());
      Vector_3 vec2(sl2->circle().orthogonal_vector());
      //      CGAL_assertion(vec1 == vec2.antipode());
      if(vec1.x() != vec2.x())
	return vec1.x() < vec2.x();
      else if(vec1.y() != vec2.y())
	return vec1.y() < vec2.y();
      else if(vec1.z() != vec2.z())
	return vec1.z() < vec2.z();          
    }

    CGAL_assertion(sv1 != SVertex_handle() && sv2 != SVertex_handle());
    sort_vertices<SNC_structure> SORT(*this->sncp());
    return SORT(sv1->twin()->source(), sv2->twin()->source());
  }
};

template <typename T>
class sort_sfaces : public SNC_decorator<T> {
  
  typedef T SNC_structure;
  typedef CGAL::SNC_decorator<T>            Base;
  typedef typename T::SM_decorator          SM_decorator;
  typedef typename T::Point_3               Point_3;
  typedef typename T::Vector_3              Vector_3;
  typedef typename T::SVertex_handle        SVertex_handle;
  typedef typename T::SHalfedge_handle      SHalfedge_handle;
  typedef typename T::SHalfloop_handle      SHalfloop_handle;
  typedef typename T::SFace_handle          SFace_handle;
  typedef typename T::SFace_cycle_iterator  SFace_cycle_iterator;
  typedef typename T::SHalfedge_around_sface_circulator
                      SHalfedge_around_sface_circulator;
  
 public:
  sort_sfaces(T& D) : Base(D) {}

  bool operator() (SFace_handle sf1, SFace_handle sf2) const {
    CGAL_NEF_TRACEN("sort sfaces");
    if(&*sf1 == &*sf2) return false;
    
    sort_vertices<T> SORT(*this->sncp());
    
    CGAL_NEF_TRACEN("  vertices " << sf1->center_vertex()->point() << " , " << sf2->center_vertex()->point());
    if(sf1->center_vertex() != sf2->center_vertex())
      return SORT(sf1->center_vertex(), sf2->center_vertex());

    //    sort_sface_cycle_entries<Base> sort_cycles((Base) *this);
    //    return sort_cycles(*sf1->sface_cycles_begin(), *sf2->sface_cycles_begin());

    SM_decorator SD(&*sf1->center_vertex());
    moreLeft<Base> ml((Base) *this);
    Vector_3 plus(1,0,0);

    SFace_cycle_iterator fc;
  
    CGAL_NEF_TRACEN("  sface 1");

    SHalfedge_handle se1;
    SHalfloop_handle sl1;
    CGAL_forall_sface_cycles_of(fc,sf1) {
      if(fc.is_shalfedge()) {
	SHalfedge_handle se(fc);
	SHalfedge_around_sface_circulator ec(se),ee(se);
	CGAL_For_all(ec,ee) {
	  CGAL_NEF_TRACEN("     " << ec->source()->point() << 
		 " | " << ec->circle().orthogonal_vector());
	  if(ml(ec, se1) == -1)
	    se1 = ec;
	}
      }
      else if(fc.is_shalfloop())
	sl1 = SHalfloop_handle(fc);
      else
	CGAL_assertion(fc.is_svertex());