snc_point_locator.h

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

  virtual void intersect_with_edges_and_facets( Halfedge_handle e0,
	const typename SNC_point_locator::Intersection_call_back& call_back) const {

    CGAL_NEF_TIMER(it_t.start());
    CGAL_assertion( initialized);
    _CGAL_NEF_TRACEN( "intersecting edge: "<<&*e0<<' '<<Segment_3(e0->source()->point(),
                                                         e0->twin()->source()->point()));

#ifdef CGAL_NEF3_TRIANGULATE_FACETS
    Unique_hash_map< Halffacet_triangle_handle, bool> f_mark(false);
#endif // CGAL_NEF3_TRIANGULATE_FACETS

    Segment_3 s(Segment_3(e0->source()->point(),e0->twin()->source()->point()));
    Vertex_handle v;
    Halfedge_handle e;
    Halffacet_handle f;
#ifdef CGAL_NEF3_TRIANGULATE_FACETS
    Halffacet_triangle_handle t;
#endif
#ifdef CGAL_NEF3_FACET_WITH_BOX
    Partial_facet pf;
#endif
    Object_list_iterator o;
    Object_list objects = candidate_provider->objects_around_segment(s);
    CGAL_for_each( o, objects) {
      if( CGAL::assign( v, *o)) {
        /* do nothing */
      }
      else if( CGAL::assign( e, *o)) {

#ifdef CGAL_NEF3_DUMP_STATISTICS
      ++number_of_intersection_candidates;
#endif

        Point_3 q;
        if( is.does_intersect_internally( s, Segment_3(e->source()->point(),
	                                               e->twin()->source()->point()), q)) {
          q = normalized(q);
          call_back( e0, Object_handle(Halfedge_handle(e)), q);
          _CGAL_NEF_TRACEN("edge intersects edge "<<' '<<&*e<< Segment_3(e->source()->point(),
                                                                e->twin()->source()->point())<<" on "<<q);
        }
      }
      else if( CGAL::assign( f, *o)) {
#ifdef CGAL_NEF3_DUMP_STATISTICS
      ++number_of_intersection_candidates;
#endif

        Point_3 q;
        if( is.does_intersect_internally( s, f, q) ) {
          q = normalized(q);
          call_back( e0, Object_handle(Halffacet_handle(f)), q);
          _CGAL_NEF_TRACEN("edge intersects facet on plane "<<f->plane()<<" on "<<q);
        }
      }
#ifdef CGAL_NEF3_FACET_WITH_BOX
	else if( CGAL::assign(pf, *o)) {
	  CGAL_assertion_msg(false, "not implemented yet");
	}
#endif
#ifdef CGAL_NEF3_TRIANGULATE_FACETS
      else if( CGAL::assign( t, *o)) {
        Point_3 q;
        Triangle_3 tr = t.get_triangle();

	if( f_mark[t])
	  continue;
	_CGAL_NEF_TRACEN("trying with triangle "<<tr);
        if( is.does_intersect( s, tr, q) &&
            !is.does_contain_on_boundary( t, q)) {
          q = normalized(q);
          call_back( e0, Object_handle(Halffacet_handle(t)), q);
          _CGAL_NEF_TRACEN("edge intersects facet triangle on plane "<<t->plane()<<" on "<<q);
	  f_mark[t] = true;
        }
      }
#endif // CGAL_NEF3_TRIANGULATE_FACETS
      else
        CGAL_assertion_msg( 0, "wrong handle");
    }
    CGAL_NEF_TIMER(it_t.stop());
  }

  virtual void intersect_with_edges( Halfedge_handle e0,
    const typename SNC_point_locator::Intersection_call_back& call_back) const {
    CGAL_NEF_TIMER(it_t.start());
    CGAL_assertion( initialized);
    _CGAL_NEF_TRACEN( "intersecting edge: "<<&*e0<<' '<<Segment_3(e0->source()->point(),
                                                         e0->twin()->source()->point()));
    Segment_3 s(Segment_3(e0->source()->point(),e0->twin()->source()->point()));
    Vertex_handle v;
    Halfedge_handle e;
    Halffacet_handle f;
#ifdef CGAL_NEF3_TRIANGULATE_FACETS
    Halffacet_triangle_handle t;
#endif
#ifdef CGAL_NEF3_FACET_WITH_BOX
    Partial_facet pf;
#endif
    Object_list_iterator o;
    Object_list objects = candidate_provider->objects_around_segment(s);
    CGAL_for_each( o, objects) {
      if( CGAL::assign( v, *o)) {
        /* do nothing */
      }
      else if( CGAL::assign( e, *o)) {

#ifdef CGAL_NEF3_DUMP_STATISTICS
      ++number_of_intersection_candidates;
#endif

        Point_3 q;
        if( is.does_intersect_internally( s, Segment_3(e->source()->point(),
	                                               e->twin()->source()->point()), q)) {
          q = normalized(q);
          call_back( e0, Object_handle(Halfedge_handle(e)), q);
          _CGAL_NEF_TRACEN("edge intersects edge "<<' '<<&*e<< Segment_3(e->source()->point(),
                                                                e->twin()->source()->point())<<" on "<<q);
        }
      }
      else if( CGAL::assign( f, *o)) {
        /* do nothing */
      }
#ifdef CGAL_NEF3_FACET_WITH_BOX
	else if( CGAL::assign(pf, *o)) {
	  CGAL_assertion_msg(false, "not implemented yet");
	}
#endif
#ifdef CGAL_NEF3_TRIANGULATE_FACETS
      else if( CGAL::assign( t, *o)) {
        /* do nothing */
      }
#endif
      else
        CGAL_assertion_msg( 0, "wrong handle");
    }
    CGAL_NEF_TIMER(it_t.stop());
  }

  virtual void intersect_with_facets( Halfedge_handle e0, 
    const typename SNC_point_locator::Intersection_call_back& call_back) const {
    CGAL_NEF_TIMER(it_t.start());
    CGAL_assertion( initialized);
    _CGAL_NEF_TRACEN( "intersecting edge: "<< Segment_3(e0->source()->point(),
                                               e0->twin()->source()->point()));
#ifdef CGAL_NEF3_TRIANGULATE_FACETS
    Unique_hash_map< Halffacet_triangle_handle, bool> f_mark(false);
#endif // CGAL_NEF3_TRIANGULATE_FACETS
    Segment_3 s(Segment_3(e0->source()->point(),e0->twin()->source()->point()));
    Vertex_handle v;
    Halfedge_handle e;
    Halffacet_handle f;
#ifdef CGAL_NEF3_FACET_WITH_BOX
    Partial_facet pf;
#endif
#ifdef CGAL_NEF3_TRIANGULATE_FACETS
    Halffacet_triangle_handle t;
#endif
    Object_list_iterator o;
    Object_list objects = candidate_provider->objects_around_segment(s);
    CGAL_for_each( o, objects) {
      if( CGAL::assign( v, *o)) {
        /* do nothing */
      }
      else if( CGAL::assign( e, *o)) {
        /* do nothing */
      }
      else if( CGAL::assign( f, *o)) {

#ifdef CGAL_NEF3_DUMP_STATISTICS
      ++number_of_intersection_candidates;
#endif

        Point_3 q;
        if( is.does_intersect_internally( s, f, q) ) {
          q = normalized(q);
          call_back( e0, Object_handle(Halffacet_handle(f)), q);
          _CGAL_NEF_TRACEN("edge intersects facet on plane "<<f->plane()<<" on "<<q);
        }
      }
#ifdef CGAL_NEF3_FACET_WITH_BOX
      else if( CGAL::assign(pf, *o)) {
	CGAL_assertion_msg(false, "not implemented yet");
      }
#endif
#ifdef CGAL_NEF3_TRIANGULATE_FACETS
      else if( CGAL::assign( t, *o)) {
        Point_3 q;
        Triangle_3 tr = t.get_triangle();
	if( f_mark[t])
	  continue;
	_CGAL_NEF_TRACEN("trying with triangle "<<tr);
        if( is.does_intersect( s, tr, q) &&
            !is.does_contain_on_boundary( t, q)) {
          q = normalized(q);
          call_back( e0, Object_handle(Halffacet_handle(t)), q);
          _CGAL_NEF_TRACEN("edge intersects facet triangle on plane "<<t->plane()<<" on "<<q);
	  f_mark[t] = true;
        }
      }
#endif // CGAL_NEF3_TRIANGULATE_FACETS
      else
        CGAL_assertion_msg( 0, "wrong handle");
    }
    CGAL_NEF_TIMER(it_t.stop());
  }

private:
  Volume_handle determine_volume( const Ray_3& ray) const {
    Halffacet_handle f_below;
    Object_handle o = shoot(ray);
    Vertex_handle v;
    Halfedge_handle e;
    Halffacet_handle f;
    if( CGAL::assign( v, o)) {
      _CGAL_NEF_TRACEN("vertex hit, obtaining volume...");
      f_below = get_visible_facet( v, ray);
      if( f_below != Halffacet_handle())
        return f_below->incident_volume();
      SM_decorator SD(&*v); // now, the vertex has no incident facets
      CGAL_assertion( SD.number_of_sfaces() == 1);
      return SD.sfaces_begin()->volume();
    }
    else if( CGAL::assign( e, o)) {
      _CGAL_NEF_TRACEN("edge hit, obtaining volume...");
      f_below = get_visible_facet( e, ray);
      if( f_below != Halffacet_handle())
        return f_below->incident_volume();
      CGAL_assertion_code(SM_decorator SD(&*e->source())); // now, the edge has no incident facets
      CGAL_assertion(SD.is_isolated(e));
      return e->incident_sface()->volume();
    }
    else if( CGAL::assign( f, o)) {
      _CGAL_NEF_TRACEN("facet hit, obtaining volume...");
      f_below = get_visible_facet(f, ray);
      CGAL_assertion( f_below != Halffacet_handle());
      return f_below->incident_volume();
    }
    return Base(*this).volumes_begin(); // TODO: Comment this hack!
  }

public:
  void add_facet(Halffacet_handle f) {
    candidate_provider->add_facet(f);
  }

  void add_edge(Halfedge_handle e) {
    candidate_provider->add_edge(e);	
  }

  void add_vertex(Vertex_handle v) {
    candidate_provider->add_vertex(v);
  }

private:
  bool initialized;
  SNC_candidate_provider* candidate_provider;
  SNC_intersection is;
#ifdef CGAL_NEF3_TRIANGULATE_FACETS
  std::list<Halffacet_triangle_handle> triangulation;
#endif
};

#ifdef CGAL_NEF3_POINT_LOCATOR_NAIVE
template <typename SNC_decorator>
class SNC_point_locator_naive : 
  public SNC_ray_shooter<SNC_decorator>, 
  public SNC_point_locator<SNC_decorator>
{
  typedef typename SNC_decorator::SNC_structure SNC_structure;
  typedef SNC_ray_shooter<SNC_decorator> Base;
  typedef SNC_point_locator_naive<SNC_decorator> Self;
  typedef SNC_point_locator<SNC_decorator> SNC_point_locator;
  typedef CGAL::SNC_intersection<SNC_structure> SNC_intersection;
  typedef typename SNC_decorator::Decorator_traits Decorator_traits;
  typedef typename Decorator_traits::SM_decorator SM_decorator;

public:
  typedef typename SNC_decorator::Object_handle Object_handle;
  typedef typename SNC_decorator::Point_3 Point_3;
  typedef typename SNC_decorator::Segment_3 Segment_3;
  typedef typename SNC_decorator::Ray_3 Ray_3;
  typedef typename SNC_structure::Aff_transformation_3 
                                  Aff_transformation_3;

  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 Decorator_traits::Volume_handle Volume_handle;
  typedef typename Decorator_traits::Vertex_iterator Vertex_iterator;
  typedef typename Decorator_traits::Halfedge_iterator Halfedge_iterator;
  typedef typename Decorator_traits::Halffacet_iterator Halffacet_iterator;

public:
  SNC_point_locator_naive() : initialized(false) {}
  virtual void initialize(SNC_structure* W) { 
    CGAL_NEF_TIMER(ct_t.start());
    strcpy(this->version_, "Naive Point Locator (tm)");
    CGAL_NEF_CLOG(version());
    CGAL_assertion( W != NULL);
    Base::initialize(W); 
    initialized = true;
    CGAL_NEF_TIMER(ct_t.stop());
  }

  virtual Self* clone() const { 
    return new Self; 
  }

  virtual bool update( Unique_hash_map<Vertex_handle, bool>& V, 
                       Unique_hash_map<Halfedge_handle, bool>& E, 
                       Unique_hash_map<Halffacet_handle, bool>& F) {
    CGAL_NEF_TIMER(ct_t.start());
    CGAL_assertion( initialized);
    CGAL_NEF_TIMER(ct_t.stop());
    return false;
  }

  virtual ~SNC_point_locator_naive() {}

  virtual Object_handle locate(const Point_3& p) const {
    CGAL_NEF_TIMER(pl_t.start());
    CGAL_assertion( initialized);
    CGAL_NEF_TIMER(pl_t.stop());
    return Base::locate(p);
  }

  virtual Object_handle shoot(const Ray_3& r, int mask=0) const {
    CGAL_NEF_TIMER(rs_t.start());
    CGAL_assertion( initialized);
    CGAL_NEF_TIMER(rs_t.stop());
    return Base::shoot(r);
  }

  virtual void transform(const Aff_transformation_3& aff) {}

  virtual void intersect_with_edges_and_facets(Halfedge_handle e0,
    const typename SNC_point_locator::Intersection_call_back& call_back) const {
	intersect_with_edges(e0,call_back);
	intersect_with_facets(e0,call_back);
  }

  virtual void intersect_with_edges( Halfedge_handle e0, 
    const typename SNC_point_locator::Intersection_call_back& call_back) const {
    CGAL_NEF_TIMER(it_t.start());
    CGAL_assertion( initialized);
    CGAL_NEF_TRACEN( "intersecting edge: "<< Segment_3(e0->source()->point(),
                                              e0->twin()->source()->point()));
    SNC_intersection is(*this->sncp());
    Segment_3 s(Segment_3(e0->source()->point(),e0->twin()->source()->point()));
    Halfedge_iterator e;
    CGAL_forall_edges( e, *this->sncp()) {

#ifdef CGAL_NEF3_DUMP_STATISTICS
      ++number_of_intersection_candidates;
#endif

      Point_3 q;
      if( is.does_intersect_internally( s, Segment_3(e->source()->point(),
                                                     e->twin()->source()->point()), q)) {
        q = normalized(q);
        CGAL_NEF_TRACEN("edge intersects edge "<< Segment_3(e->source()->point(),
                                                   e->twin()->source()->point()) <<" on "<<q);
        call_back( e0, Object_handle(e), q);
      }
    }
    CGAL_NEF_TIMER(it_t.stop());
  }

  virtual void intersect_with_facets( Halfedge_handle e0, 
    const typename SNC_point_locator::Intersection_call_back& call_back) const {
    CGAL_NEF_TIMER(it_t.start());
    CGAL_assertion( initialized);
    CGAL_NEF_TRACEN( "intersecting edge: "<< Segment_3(e0->source()->point(),
                                              e0->twin()->source()->point()));
    SNC_intersection is(*this->sncp());
    Segment_3 s(Segment_3(e0->source()->point(),
                          e0->twin()->source()->point()));
    Halffacet_iterator f;
    CGAL_forall_facets( f, *this->sncp()) {

#ifdef CGAL_NEF3_DUMP_STATISTICS
      ++number_of_intersection_candidates;
#endif

      Point_3 q;
      if( is.does_intersect_internally( s, f, q) ) {
        q = normalized(q);
        CGAL_NEF_TRACEN("edge intersects facet on plane "<<f->plane()<<" on "<<q);
        call_back( e0, Object_handle(f), q);
      }
    }
    CGAL_NEF_TIMER(it_t.stop());
  }

private:
  bool initialized;
};
#endif

CGAL_END_NAMESPACE
#endif // CGAL_NEF_SNC_POINT_LOCATOR_H