SPAR/AIModule/BWTA/vendors/CGAL/CGAL/Arr_point_location/Arr_lm_generator_base.h

Go to the documentation of this file.

// 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.5-branch/Arrangement_on_surface_2/include/CGAL/Arr_point_location/Arr_lm_generator_base.h $
// $Id: Arr_lm_generator_base.h 41847 2008-01-26 09:05:42Z golubevs $
// 
// Author(s)     : Idit Haran   <haranidi@post.tau.ac.il>
//                 Ron Wein     <wein@post.tau.ac.il>
#ifndef CGAL_ARR_LANDMARKS_GENERATOR_H
#define CGAL_ARR_LANDMARKS_GENERATOR_H

#include <CGAL/Arr_observer.h>
#include <CGAL/Arrangement_2/Arr_traits_adaptor_2.h>
#include <CGAL/Arr_point_location/Arr_lm_nearest_neighbor.h>
#include <CGAL/Arr_batched_point_location.h>
#include <list>
#include <algorithm>
#include <vector>

CGAL_BEGIN_NAMESPACE

template <class Arrangement_,
          class Nearest_neighbor_ =
            Arr_landmarks_nearest_neighbor <typename
                                            Arrangement_::Geometry_traits_2> >
class Arr_landmarks_generator_base
    : public Arr_observer <Arrangement_>
{
public:

  typedef Arrangement_                                Arrangement_2;
  typedef typename Arrangement_2::Geometry_traits_2   Geometry_traits_2;
  typedef Nearest_neighbor_                           Nearest_neighbor;

  typedef Arr_landmarks_generator_base<Arrangement_2,
                                       Nearest_neighbor>  Self;

  typedef typename Arrangement_2::Vertex_const_handle   Vertex_const_handle;
  typedef typename Arrangement_2::Halfedge_const_handle Halfedge_const_handle;
  typedef typename Arrangement_2::Face_const_handle     Face_const_handle;
  typedef typename Arrangement_2::Vertex_handle         Vertex_handle;
  typedef typename Arrangement_2::Halfedge_handle       Halfedge_handle;
  typedef typename Arrangement_2::Face_handle           Face_handle;
  typedef typename Arrangement_2::Vertex_const_iterator 
                                                    Vertex_const_iterator;
  typedef typename Arrangement_2::Ccb_halfedge_circulator 
                                                    Ccb_halfedge_circulator;

  typedef typename Arrangement_2::Point_2               Point_2;
  typedef typename Arrangement_2::X_monotone_curve_2    X_monotone_curve_2;

  typedef typename Nearest_neighbor::NN_Point_2         NN_Point_2;
  typedef std::list<NN_Point_2>                         NN_Points_set;

  typedef std::vector<Point_2>                          Points_set;
  typedef std::pair<Point_2,CGAL::Object>               PL_pair;
  typedef std::vector<PL_pair>                          Pairs_set;
  typedef typename std::vector<PL_pair>::iterator       Pairs_iterator;

protected:

  typedef Arr_traits_basic_adaptor_2<Geometry_traits_2> Traits_adaptor_2;

  // Data members:
  const Traits_adaptor_2  *m_traits;  // The associated traits object.
  Nearest_neighbor         nn;      // The associated nearest neighbor object.
  bool                     ignore_notifications;
  bool                     updated;
  int                      num_small_not_updated_changes;

private:

  Arr_landmarks_generator_base (const Self& );

  Self& operator= (const Self& );

public:

  Arr_landmarks_generator_base (const Arrangement_2& arr) :
    Arr_observer<Arrangement_2> (const_cast<Arrangement_2 &>(arr)),
    ignore_notifications (false),
    updated (false),
    num_small_not_updated_changes(0)
  {
    m_traits = static_cast<const Traits_adaptor_2*> (arr.geometry_traits());
    // One needs to call build_landmark_set() in the constructor of any
    // inherited class.
  }

  virtual void build_landmark_set ()
  {
    // Create the landmark points.
    NN_Points_set     nn_points; 

    _create_nn_points_set(nn_points);

    // Update the search structure.
    nn.clear();
    nn.init (nn_points.begin(), nn_points.end());

    num_small_not_updated_changes = 0;
    updated = true;
  }

  virtual void clear_landmark_set ()
  {
    nn.clear();
    num_small_not_updated_changes = 0;
    updated = false;
  }

  virtual Point_2 closest_landmark (Point_2 p, Object &obj)
  {
    CGAL_assertion(updated);
    return (nn.find_nearest_neighbor(p, obj));
  }



  virtual void before_assign (const Arrangement_2& arr)
  {
    this->clear_landmark_set();
    m_traits = static_cast<const Traits_adaptor_2*> (arr.geometry_traits());
    ignore_notifications = true;
  }

  virtual void after_assign ()
  { 
    this->build_landmark_set();
    ignore_notifications = false;
  }

  virtual void before_attach (const Arrangement_2& arr)
  {
    this->clear_landmark_set();
    m_traits = static_cast<const Traits_adaptor_2*> (arr.geometry_traits());
    ignore_notifications = true;
  }

  virtual void after_attach ()
  {
    this->build_landmark_set();
    ignore_notifications = false;
  }

  virtual void before_detach ()
  {
    this->clear_landmark_set();
  }

  virtual void after_clear ()
  { 
    this->clear_landmark_set();
    this->build_landmark_set();
  }

  virtual void before_global_change ()
  {
    this->clear_landmark_set();
    ignore_notifications = true;
  }

  virtual void after_global_change ()
  {
    this->build_landmark_set();
    ignore_notifications = false;
  }



  virtual void after_create_vertex (Vertex_handle )
  {
    this->_handle_local_change_notification();
  }

  virtual void after_create_edge (Halfedge_handle )
  {
    this->_handle_local_change_notification();
  }

  virtual void after_split_edge (Halfedge_handle ,
                                 Halfedge_handle )
  {
    this->_handle_local_change_notification();
  }

  virtual void after_split_face (Face_handle ,
                                 Face_handle ,
                                 bool )
  {
    this->_handle_local_change_notification();
  }

  virtual void after_split_outer_ccb (Face_handle ,
                                      Ccb_halfedge_circulator ,
                                      Ccb_halfedge_circulator )
  {
    this->_handle_local_change_notification();
  }

  virtual void after_split_inner_ccb (Face_handle ,
                                      Ccb_halfedge_circulator ,
                                      Ccb_halfedge_circulator )
  {
    this->_handle_local_change_notification();
  }

  virtual void after_add_outer_ccb (Ccb_halfedge_circulator )
  {
    this->_handle_local_change_notification();
  }

  virtual void after_add_inner_ccb (Ccb_halfedge_circulator )
  {
    this->_handle_local_change_notification();
  }

  virtual void after_add_isolated_vertex (Vertex_handle )
  {
    this->_handle_local_change_notification();
  }

  virtual void after_merge_edge (Halfedge_handle )
  {
    this->_handle_local_change_notification();
  }

  virtual void after_merge_face (Face_handle )
  {
    this->_handle_local_change_notification();
  }

  virtual void after_merge_outer_ccb (Face_handle ,
                                      Ccb_halfedge_circulator )
  {
    this->_handle_local_change_notification();
  }

  virtual void after_merge_inner_ccb (Face_handle ,
                                      Ccb_halfedge_circulator )
  {
    this->_handle_local_change_notification();
  }

  virtual void after_move_outer_ccb (Ccb_halfedge_circulator )
  {
    this->_handle_local_change_notification();
  }

  virtual void after_move_inner_ccb (Ccb_halfedge_circulator )
  {
    this->_handle_local_change_notification();
  }

  virtual void after_move_isolated_vertex (Vertex_handle )
  {
    this->_handle_local_change_notification();
  }

  virtual void after_remove_vertex ()
  {
    this->_handle_local_change_notification();
  }

  virtual void after_remove_edge ()
  {
    this->_handle_local_change_notification();
  }

  virtual void after_remove_outer_ccb (Face_handle )
  {
    this->_handle_local_change_notification();
  }

  virtual void after_remove_inner_ccb (Face_handle )
  {
    this->_handle_local_change_notification();
  }

protected:

  void _handle_local_change_notification ()
  {
    if (! ignore_notifications)
    {
      clear_landmark_set();
      build_landmark_set();
    }
    return;
  }

  virtual void _create_points_set (Points_set &) = 0;

  virtual void _create_nn_points_set (NN_Points_set &nn_points) 
  {
    Points_set           points;
    Pairs_set            pairs;

    // Create the set of landmark points.
    _create_points_set(points);

    // Locate the landmarks in the arrangement using batched point-location
    // global function.
    locate (*(this->arrangement()), points.begin(), points.end(),
            std::back_inserter(pairs));

    // Apply a random shuffle on the points, since the batched point-location
    // returns them sorted.
    std::random_shuffle (pairs.begin(), pairs.end());

    // Insert all landmarks (paired with their current location in the
    // arrangement) into the nearest-neighbor search structure.
    Pairs_iterator   itr;

    for (itr = pairs.begin(); itr != pairs.end(); ++itr)
    {
      NN_Point_2  np(itr->first, itr->second); 
      nn_points.push_back(np);
    }
  }
};

CGAL_END_NAMESPACE

#endif