SPAR/AIModule/BWTA/vendors/CGAL/CGAL/Arr_point_location/Arr_lm_nearest_neighbor.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_nearest_neighbor.h $
// $Id: Arr_lm_nearest_neighbor.h 40429 2007-09-24 15:01:00Z efif $
// 
// Author(s)     : Idit Haran   <haranidi@post.tau.ac.il>
//                 Ron Wein     <wein@post.tau.ac.il>
#ifndef CGAL_ARR_LANDMARKS_NEAREST_NEIGHBOR_H
#define CGAL_ARR_LANDMARKS_NEAREST_NEIGHBOR_H

#include <CGAL/basic.h>
#include <CGAL/Search_traits.h>
#include <CGAL/Orthogonal_k_neighbor_search.h>
#include <CGAL/Arrangement_2/Arr_traits_adaptor_2.h>

CGAL_BEGIN_NAMESPACE

template <class GeomTraits_>
class Arr_landmarks_nearest_neighbor 
{
public:
  
  typedef GeomTraits_                                   Geometry_traits_2;
  
  typedef typename Geometry_traits_2::Approximate_number_type    ANT;
  typedef typename Geometry_traits_2::Point_2                    Point_2;
  typedef Arr_landmarks_nearest_neighbor<Geometry_traits_2>      Self;

  class  NN_Point_2
  {
  public:

    Point_2    m_point;      // The point.
    Object     m_object;     // The arrangement feature containing the point.
    ANT        m_vec[2];     // Approximate x and y-coordinates of the point.

  public:

    NN_Point_2()
    { 
      m_vec[0] = m_vec[1] = 0;
    }

    NN_Point_2 (const Point_2 &p) :
      m_point (p)
    {
      // Obtain the coordinate approximations,
      Geometry_traits_2  m_traits;
      m_vec[0] = m_traits.approximate_2_object()(p, 0);
      m_vec[1] = m_traits.approximate_2_object()(p, 1);
    }

    NN_Point_2 (const Point_2& p, const Object& obj) :
      m_point (p),
      m_object (obj)
    { 
      // Obtain the coordinate approximations,
      Geometry_traits_2  m_traits;
      m_vec[0] = m_traits.approximate_2_object()(p, 0);
      m_vec[1] = m_traits.approximate_2_object()(p, 1);
    }

    /* Get the point. */
    const Point_2& point() const
    {
      return (m_point);
    }

    /* Get the object representing the location in the arrangement. */
    const Object& object() const
    {
      return (m_object);
    }

    const ANT* begin () const
    {
      return (m_vec);
    }

    const ANT* end () const
    {
      return (m_vec + 2);
    }

    bool operator== (const NN_Point_2& nnp) const
    {
      return (m_vec[0] == nnp.m_vec[0] &&
              m_vec[1] == nnp.m_vec[1]);
    }

    bool operator!= (const NN_Point_2& nnp) const 
    {
      return (m_vec[0] != nnp.m_vec[0] ||
              m_vec[1] != nnp.m_vec[1]);
    }

  };

  struct Construct_coord_iterator
  {
    const ANT* operator() (const NN_Point_2& nnp) const
    {
      return (nnp.begin());
    }

    const ANT* operator() (const NN_Point_2& nnp, int) const
    {
      return (nnp.end());
    }
  };

protected:

  typedef CGAL::Search_traits<ANT, NN_Point_2, const ANT*,
                              Construct_coord_iterator>      Search_traits;
  typedef CGAL::Orthogonal_k_neighbor_search<Search_traits>  Neighbor_search;
  typedef typename Neighbor_search::iterator                 Neighbor_iterator;
  typedef typename Neighbor_search::Tree                     Tree;

  // Data members:
  Tree            *m_tree;        // The search tree.
  bool             m_is_empty;    // Is the search tree empty.

private:

  Arr_landmarks_nearest_neighbor (const Self& );

  Self& operator= (const Self& );

public:

  Arr_landmarks_nearest_neighbor () :
    m_tree(NULL),
    m_is_empty(true)
  {}

  ~Arr_landmarks_nearest_neighbor() 
  {
    clear();
  }

  template <class InputIterator>
  void init (InputIterator begin, InputIterator end)
  {
    CGAL_precondition_msg (m_tree == NULL,
                           "The search tree is already initialized.");

    if (begin != end)
    {
      m_tree = new Tree (begin, end);
      m_is_empty = false;
    }
    else
    {
      m_tree = new Tree();
      m_is_empty = true;
    }

    return;
  }

  void clear () 
  {
    if (m_tree != NULL)
      delete m_tree;
    m_tree = NULL;
    m_is_empty = true;

    return;
  }

  Point_2 find_nearest_neighbor (const Point_2& q, Object &obj) const
  {
    CGAL_precondition_msg (m_tree != NULL && ! m_is_empty,
                           "The search tree is not initialized.");

    // Create an NN_Point_2 object from the query point and use it to
    // query the search tree to find the nearest landmark point.
    NN_Point_2         nn_query (q);
    Neighbor_search    search (*m_tree, nn_query, 1);
    const NN_Point_2&  nearest_p = search.begin()->first;

    // Return the search result.
    obj = nearest_p.object();
    return (nearest_p.point());
  }
};

CGAL_END_NAMESPACE

#endif