SPAR/AIModule/BWTA/vendors/CGAL/CGAL/Sweep_line_2/Sweep_line_2_utils.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/Sweep_line_2/Sweep_line_2_utils.h $
// $Id: Sweep_line_2_utils.h 50366 2009-07-05 12:56:48Z efif $
// 
//
// Author(s)     : Baruch Zukerman <baruchzu@post.tau.ac.il>
//                 Ron Wein        <wein@post.tau.ac.il>
//                 Efi Fogel       <efif@post.tau.ac.il>

#ifndef CGAL_SWEEP_LINE_2_UTILS
#define CGAL_SWEEP_LINE_2_UTILS

#include <CGAL/basic.h>

#include <CGAL/Object.h>
#include <CGAL/assertions.h>
#include <vector>
#include <algorithm>
#include <CGAL/Arr_enums.h>

CGAL_BEGIN_NAMESPACE

template <class Traits,
          class CurveInputIter,
          class XCurveOutIter,
          class PointOutIter>
void make_x_monotone (CurveInputIter begin, CurveInputIter end,
                      XCurveOutIter x_curves,
                      PointOutIter iso_points,
                      const Traits * tr)
{
  // Split the input curves into x-monotone objects.
  unsigned int         num_of_curves = std::distance(begin, end);
  std::vector<Object>  object_vec;
  CurveInputIter       iter;

  object_vec.reserve (num_of_curves);
  for (iter = begin; iter != end; ++iter)
  {
    tr->make_x_monotone_2_object()(*iter,
                                   std::back_inserter(object_vec));
  }

  // Transform each object to either a point or an x-monotone curve.
  typedef typename Traits::X_monotone_curve_2    X_monotone_curve_2;
  typedef typename Traits::Point_2               Point_2;

  const X_monotone_curve_2 *xcv;
  const Point_2            *pt;
  unsigned int              i;

  for (i = 0 ; i < object_vec.size() ; ++i)
  {
    xcv = object_cast<X_monotone_curve_2> (&(object_vec[i]));

    if (xcv != NULL)
    {
      // The object is an x-monotone curve.
      *x_curves = *xcv;
      ++x_curves;
    }
    else
    {
      // The object is an isolated point.
      pt = object_cast<Point_2> (&(object_vec[i]));
      CGAL_assertion (pt != NULL);
      
      *iso_points = *pt;
      ++iso_points;
    }
  }

  return;
}

template <class Arrangement,
          class ExTraits,
          class XCurveInputIter,
          class PointInputIter,
          class XCurveOutIter,
          class PointOutIter>
void prepare_for_sweep (Arrangement& arr,
                        XCurveInputIter xcvs_begin, XCurveInputIter xcvs_end,
                        PointInputIter pts_begin, PointInputIter pts_end,
                        XCurveOutIter x_curves,
                        PointOutIter iso_points,
                        const ExTraits * /* ex_tr */)
{
  typedef typename Arrangement::X_monotone_curve_2    X_monotone_curve_2;
  typedef typename Arrangement::Point_2               Point_2;

  typedef typename Arrangement::Vertex_iterator       Vertex_iterator;
  typedef typename Arrangement::Edge_iterator         Edge_iterator;
  typedef typename Arrangement::Vertex_handle         Vertex_handle;
  typedef typename Arrangement::Halfedge_handle       Halfedge_handle;

  typedef typename ExTraits::X_monotone_curve_2       Ex_x_monotone_curve_2;
  typedef typename ExTraits::Point_2                  Ex_point_2;
  
  // Go over the input objects and copy them to the output iterators.
  XCurveInputIter   xcv_it;
  PointInputIter    pt_it;

  for (xcv_it = xcvs_begin; xcv_it != xcvs_end; ++xcv_it)
  {
    *x_curves = Ex_x_monotone_curve_2 (*xcv_it);
    ++x_curves;
  }

  for (pt_it = pts_begin; pt_it != pts_end; ++pt_it)
  {
    *iso_points = Ex_point_2 (*pt_it);
    ++iso_points;
  }
  
  // Go over the arrangement edges and insert their associated x-monotone
  // curves into the output iterator. To each curve we attach a handle to the
  // halfedge that goes from right to left.
  Edge_iterator     eit;
  Halfedge_handle   he;
  
  for (eit = arr.edges_begin(); eit != arr.edges_end(); ++eit) 
  {
    if (eit->direction() == ARR_LEFT_TO_RIGHT)
      he = eit->twin();
    else
      he = eit;

    *x_curves = Ex_x_monotone_curve_2 (he->curve(), he);
    ++x_curves;
  }

  // Go over the isolated arrangement vertices and insert their associated
  // points into the output iterator. To each point we attach a handle to its
  // vertex.
  Vertex_iterator   vit;
  Vertex_handle     v;

   for (vit = arr.vertices_begin(); vit != arr.vertices_end(); ++vit)
   {
     v = vit;
     if (v->is_isolated())
     {
       *iso_points = Ex_point_2 (v->point(), v);
       ++iso_points;
     }
   }

   return;
}


CGAL_END_NAMESPACE

#endif