envelope_element_visitor_3.h

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

// Copyright (c) 2005  Tel-Aviv University (Israel).
// 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/Envelope_3/include/CGAL/Envelope_3/Envelope_element_visitor_3.h $
// $Id: Envelope_element_visitor_3.h 37990 2007-04-07 09:23:14Z efif $
//
// Author(s)     : Michal Meyerovitch     <[e-mail]>
//                 Baruch Zukerman        <[e-mail]>

#ifndef CGAL_ENVELOPE_ELEMENT_VISITOR_3_H
#define CGAL_ENVELOPE_ELEMENT_VISITOR_3_H

#include <CGAL/Object.h>
#include <CGAL/enum.h>
#include <CGAL/Unique_hash_map.h>
#include <CGAL/Arr_observer.h>
#include <CGAL/Arr_accessor.h>
#include <CGAL/Arr_walk_along_line_point_location.h>
#include <CGAL/Arr_naive_point_location.h>
#include <CGAL/Arrangement_2/Arr_inc_insertion_zone_visitor.h>
#include <CGAL/Envelope_3/Arrangement_2_incremental_insert.h>
#include <CGAL/utility.h>
#include <CGAL/functions_on_enums.h> 
#include <CGAL/Arrangement_2/Arr_traits_adaptor_2.h>

#include <vector>
#include <algorithm>
#include <iostream>
#include <deque>

CGAL_BEGIN_NAMESPACE

// this class does the resolving of edge and face in the divide & conquer algorithm
// it should handle all faces (it supports holes in the face)

template <class EnvelopeTraits_3, class MinimizationDiagram_2>
class Envelope_element_visitor_3
{
public:
  typedef EnvelopeTraits_3                             Traits;
  typedef typename Traits::Multiplicity                Multiplicity;
  typedef typename Traits::Surface_3                   Surface_3;
  typedef typename Traits::Xy_monotone_surface_3       Xy_monotone_surface_3;
  typedef typename Traits::Equal_2                     Equal_2;

  typedef MinimizationDiagram_2                        Minimization_diagram_2;
  typedef typename Traits::Point_2                     Point_2;
  typedef typename Traits::X_monotone_curve_2          X_monotone_curve_2;
  typedef typename Traits::Has_boundary_category       Has_boundary_category;

protected:

  typedef Envelope_element_visitor_3<Traits, Minimization_diagram_2> Self;
  typedef typename Minimization_diagram_2::Halfedge_const_iterator  Halfedge_const_iterator;
  typedef typename Minimization_diagram_2::Halfedge_handle          Halfedge_handle;
  typedef typename Minimization_diagram_2::Halfedge_iterator        Halfedge_iterator;
  typedef typename Minimization_diagram_2::Face_handle              Face_handle;
  typedef typename Minimization_diagram_2::Face_iterator            Face_iterator;
  typedef typename Minimization_diagram_2::Vertex_handle            Vertex_handle;
  typedef typename Minimization_diagram_2::Vertex_iterator          Vertex_iterator;
  typedef typename Minimization_diagram_2::Ccb_halfedge_circulator  Ccb_halfedge_circulator;
  typedef typename Minimization_diagram_2::Hole_iterator            Hole_iterator;
  typedef typename Minimization_diagram_2::Isolated_vertex_iterator Isolated_vertex_iterator;
  typedef typename Minimization_diagram_2::Dcel                     Dcel;
  typedef typename Minimization_diagram_2::Dcel::Dcel_data_iterator Envelope_data_iterator;

  typedef Arr_observer<Minimization_diagram_2>                      Md_observer;
  typedef Arr_accessor<Minimization_diagram_2>                      Md_accessor;
  
  typedef Arr_walk_along_line_point_location<Minimization_diagram_2>
                                                                    Md_point_location;

  typedef Arr_inc_insertion_zone_visitor<Minimization_diagram_2>    Md_insert_zone_visitor;
  
  typedef std::list<Halfedge_handle>                                Halfedges_list;
  typedef typename std::list<Halfedge_handle>::iterator             Halfedges_list_iterator;

  typedef std::pair<Halfedge_handle, Multiplicity>             Halfedge_w_type;
  typedef std::list<Halfedge_w_type>                                Halfedges_w_type_list;

  typedef std::list<Vertex_handle>                                  Vertices_list;
  typedef typename std::list<Vertex_handle>::iterator               Vertices_list_iterator;

  typedef std::list<Face_handle>                                    Faces_list;
  typedef typename std::list<Face_handle>::iterator                 Faces_list_iterator;

  typedef Unique_hash_map<Vertex_handle, bool>                      Vertices_hash;
  typedef Unique_hash_map<Halfedge_handle, bool>                    Halfedges_hash;
  typedef Unique_hash_map<Halfedge_handle, Multiplicity>            Halfedges_hash_w_type;
  typedef Unique_hash_map<Face_handle, bool>                        Faces_hash;

  typedef Unique_hash_map<Vertex_handle, Vertex_handle>             Vertices_map;
  typedef Unique_hash_map<Halfedge_handle, Halfedge_handle>         Halfedges_map;
  typedef Unique_hash_map<Face_handle, Face_handle>                 Faces_map;

  typedef Unique_hash_map<Vertex_handle, Halfedge_handle>           Vertices_to_edges_map;
  
  typedef std::pair<X_monotone_curve_2, Multiplicity>          Intersection_curve;
  typedef std::list<Object>                                         Intersections_list;

  // this is used in the resolve edge process
  typedef Triple<Point_2, bool, bool>                               Point_2_with_info;
  struct Points_compare
  {
    protected:
      Traits* p_traits;
    public:
      Points_compare(Traits& tr) : p_traits(&tr)
      {}

      bool operator() (const Point_2_with_info& p1,
                       const Point_2_with_info& p2) const
      {
        Comparison_result res =
          p_traits->compare_xy_2_object()(p1.first, p2.first);
        if (res == SMALLER)
          return true;
        if (res == LARGER)
          return false;
        CGAL_assertion(false);
        return (p1.second == true || p2.third == true);
      }
  };
  
public:
  // c'tor
  Envelope_element_visitor_3(Envelope_type t = LOWER)
  {
    // Allocate the traits.
    traits = new Traits;
    own_traits = true;
    type  = t;
  }

  Envelope_element_visitor_3(Traits* tr, Envelope_type t = LOWER)
  {
    // Set the traits.
    traits = tr;
    own_traits = false;
    type  = t;
  }

  // virtual destructor.
  virtual ~Envelope_element_visitor_3()
  {
    // Free the traits object, if necessary.
    if (own_traits)
      delete traits;
  }

  // get a face with 2 surfaces defined over it, and compute the arrangement of the
  // envelope of these surfaces over the face
  void resolve(Face_handle face, Minimization_diagram_2& result)
  {
    CGAL_assertion(face->get_aux_is_set(0));
    CGAL_assertion(face->get_aux_is_set(1));
    
    // we are interested with the envelope's shape over the current face,
    // so we only need to check the first surface from each group, since
    // all the surfaces in a group overlap over the current face.
    const Xy_monotone_surface_3& surf1 = get_aux_surface(face, 0);
    const Xy_monotone_surface_3& surf2 = get_aux_surface(face, 1);

    // find the projected intersections of the surfaces. if none - we have a simple case:
    // need only resolve non-intersecting and return
    std::list<Object> inter_objs;
    get_projected_intersections(surf1, surf2, std::back_inserter(inter_objs));

    if (inter_objs.size() == 0)
    {
      // here for resolve we can compare the surfaces over the edges only (no need for left/right versions)
      Comparison_result cur_res = resolve_minimal_face(face);
      copy_data_by_comparison_result(face, face, cur_res);
      // check face boundary for "data from face" features
      #ifdef CGAL_ENVELOPE_SAVE_COMPARISONS
        copy_data_to_face_boundary(face);
      #endif
      return;
    }
    
    // we insert all projected intersections into a temporary arrangement,
    // with only the current face's curves, to find the arrangement of the lower envelope
    // of the 2 surfaces over the current face
    Minimization_diagram_2 copied_face_arr(traits);

    // here we maintain a mapping between edges in the copied arrangement and
    // their original generating edge from result
    Halfedges_map map_copied_to_orig_halfedges;
    // here we maintain a mapping between vertices in the copied arrangement and
    // their original generating vertex from result
    Vertices_map  map_copied_to_orig_vertices;
    // here we maintain a mapping between faces in the copied arrangement and
    // their corresponding face from result
    Faces_map     map_copied_to_orig_faces;

    // now, insert the face's boundary into the temporary minimization diagram
    // the face is assumed to have outer boundary, and may also have holes,
    // and isolated vertices
    // we need to keep track of the original halfedges in the inserted halfedges
    // we also need to have the face handle of the copied face in copied_face_arr
    Face_handle copied_face = copy_face(face, result, copied_face_arr,
                                        map_copied_to_orig_halfedges,
                                        map_copied_to_orig_vertices);
    CGAL_assertion(is_valid(copied_face_arr));
    map_copied_to_orig_faces[copied_face] = face;
    
    
    // insert the projected intersections into the temporary minimization diagram
    Point_2 point;
    Intersection_curve curve;
    Object cur_obj;
    
    // we use our zone visitor, which only inserts into the arrangement the
    // points and curves which are inside the copied face
    // it updates the result arrangement at the same time (action after action
    // using observer to the copied arrangement and accessor to result)
    // the visitor is responsible for updating:
    // 1. the collection of special edges. (these are (parts of) edges of the

    //    original face's boundary that overlap with projected intersections
    Halfedges_list result_special_edges;
    // 2. the collection of newly added edges, each with the type of the
    //    projected intersection that created it.
    Halfedges_w_type_list result_new_edges;
    // 3. the collection of faces that form the face before any insertion
    Faces_list     result_face_parts;
    // 4. the collection of special vertices, which contains:
    //    - new vertices that were created inside the original face
    //      (both isolated and not isolated)
    //    - new vertices created by a split of a boundary edge which has
    //      the property "data from face"
    //    - original vertices of the boundary that consolidate with projected
    //      intersections, and have common aux data with the face
    //    all these vertices should have their data set as "EQUAL"
    Vertices_list  result_special_vertices;

    New_faces_observer new_faces_obs(result);    
    Copied_face_zone_visitor zone_visitor(result,
                                          copied_face_arr,
                                          face,
                                          copied_face,
                                          map_copied_to_orig_halfedges,
                                          map_copied_to_orig_vertices,
                                          map_copied_to_orig_faces,
                                          result_special_edges,
                                          result_new_edges,
                                          result_face_parts,
                                          result_special_vertices,
                                          this);

    Md_point_location pl(copied_face_arr);
    std::list<Object>::iterator inter_objs_it = inter_objs.begin();
    for(; inter_objs_it != inter_objs.end(); ++inter_objs_it)
    {
      cur_obj = *inter_objs_it;
      CGAL_assertion(!cur_obj.is_empty());
      if (assign(point, cur_obj))
      {
        // intersection can be a point when the surfaces only touch each other.
        // we are only interested in the points that are inside the face or on its
        // boundary.
        // we insert the point into the planar map as a vertex, with both surfaces
        // over it.
        // should use observer for split_edge
        // if not in a sub-face of "face", shouldn't insert it
        // the above information is available in zone_visitor
        insert_point(copied_face_arr, point, pl, zone_visitor);
      }
      else if (assign(curve, cur_obj))
      {
        zone_visitor.set_current_intersection_type(curve.second);
        insert_x_monotone_curve(copied_face_arr, curve.first, pl, zone_visitor);
      }
      else
        CGAL_assertion_msg(false, "wrong projected intersection type");
    }

    zone_visitor.finish();

    // now determine the envelope data in result over the new faces
    
    // in order to use resolve_minimal_face with intersection halfedge, we go over
    // the new edges, and set data over their faces
    typename Halfedges_w_type_list::iterator new_edge_it;
    for(new_edge_it = result_new_edges.begin();
        new_edge_it != result_new_edges.end(); ++new_edge_it)
    {
      Halfedge_handle new_he = (*new_edge_it).first;
      Halfedge_handle new_he_twin = new_he->twin();
      #ifdef CGAL_ENVELOPE_SAVE_COMPARISONS
      Multiplicity itype = (*new_edge_it).second;
      #endif
      // set sources of the new edge
      new_he->set_aux_source(0, face->get_aux_source(0));
      new_he->set_aux_source(1, face->get_aux_source(1));
      new_he_twin->set_aux_source(0, face->get_aux_source(0));
      new_he_twin->set_aux_source(1, face->get_aux_source(1));

      // set data on new edges
      new_he->set_decision(EQUAL);
      new_he_twin->set_decision(EQUAL);
      
      // set data on the faces
      // could be that the data is set for f2, and can use itype to conclude
      // to f1, not only the opposite
      Face_handle f1 = new_he->face(), f2 = new_he_twin->face();
      Comparison_result res;
      if (!f1->is_decision_set() && !f2->is_decision_set())
      {
        res = resolve_minimal_face(f1, &new_he);
        copy_data_by_comparison_result(face, f1, res);
      }

      // now at least one of the faces f1,f2 has its decision set.      

      // if the other face doesn't have its data, we resolve it using
      // the former result and the intersection type (if exists)
      if (!f2->is_decision_set())
      {
        #ifdef CGAL_ENVELOPE_SAVE_COMPARISONS
          if (itype != 0)
          {
            res = convert_decision_to_comparison_result(f1->get_decision());
            res = resolve_by_intersection_type(res, itype);
            CGAL_expensive_assertion_code(
              Comparison_result tmp_res = resolve_minimal_face(f2, &new_he_twin);