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

#ifndef CGAL_ARR_CONIC_TRAITS_2_H
#define CGAL_ARR_CONIC_TRAITS_2_H

#include <CGAL/tags.h>
#include <CGAL/Arr_tags.h>
#include <CGAL/Arr_geometry_traits/Conic_arc_2.h>
#include <CGAL/Arr_geometry_traits/Conic_x_monotone_arc_2.h>
#include <CGAL/Arr_geometry_traits/Conic_point_2.h>

#include <fstream>

CGAL_BEGIN_NAMESPACE

template <class Rat_kernel_, class Alg_kernel_, class Nt_traits_>
class Arr_conic_traits_2 
{
public:

  typedef Rat_kernel_                     Rat_kernel;
  typedef Alg_kernel_                     Alg_kernel;
  typedef Nt_traits_                      Nt_traits;

  typedef typename Rat_kernel::FT         Rational;
  typedef typename Rat_kernel::Point_2    Rat_point_2;
  typedef typename Rat_kernel::Segment_2  Rat_segment_2;
  typedef typename Rat_kernel::Line_2     Rat_line_2;
  typedef typename Rat_kernel::Circle_2   Rat_circle_2;

  typedef typename Alg_kernel::FT         Algebraic;

  typedef typename Nt_traits::Integer     Integer;

  typedef Arr_conic_traits_2<Rat_kernel, Alg_kernel, Nt_traits>  Self;

  // Category tags:
  typedef Tag_true                        Has_left_category;
  typedef Tag_true                        Has_merge_category;

  typedef Arr_oblivious_side_tag          Arr_left_side_tag;
  typedef Arr_oblivious_side_tag          Arr_bottom_side_tag;
  typedef Arr_oblivious_side_tag          Arr_top_side_tag;
  typedef Arr_oblivious_side_tag          Arr_right_side_tag;

  // Traits objects:
  typedef _Conic_arc_2<Rat_kernel, Alg_kernel, Nt_traits> Curve_2;
  typedef _Conic_x_monotone_arc_2<Curve_2>                X_monotone_curve_2;
  typedef _Conic_point_2<Alg_kernel>                      Point_2;
  typedef unsigned int                                    Multiplicity;

private:

  // Type definition for the intersection points mapping.
  typedef typename X_monotone_curve_2::Conic_id           Conic_id;
  typedef typename X_monotone_curve_2::Intersection_point_2
                                                          Intersection_point_2;
  typedef typename X_monotone_curve_2::Intersection_map   Intersection_map;

  mutable Intersection_map  inter_map;  // Mapping conic pairs to their
                                        // intersection points.

public:

  Arr_conic_traits_2 ()
  {}

  static unsigned int get_index () 
  {
    static unsigned int index = 0;
    return (++index);
  }



  class Compare_x_2
  {
  public:
    Comparison_result operator() (const Point_2 & p1, const Point_2 & p2) const
    {
      Alg_kernel   ker;
      return (ker.compare_x_2_object() (p1, p2));
    }
  };

  Compare_x_2 compare_x_2_object () const
  {
    return Compare_x_2();
  }

  class Compare_xy_2
  {
  public:
    Comparison_result operator() (const Point_2& p1, const Point_2& p2) const
    {
      Alg_kernel   ker;
      return (ker.compare_xy_2_object() (p1, p2));
    }
  };

  Compare_xy_2 compare_xy_2_object () const
  {
    return Compare_xy_2();
  }

  class Construct_min_vertex_2
  {
  public:
    const Point_2& operator() (const X_monotone_curve_2 & cv) const
    {
      return (cv.left());
    }
  };

  Construct_min_vertex_2 construct_min_vertex_2_object () const
  {
    return Construct_min_vertex_2();
  }

  class Construct_max_vertex_2
  {
  public:
    const Point_2& operator() (const X_monotone_curve_2 & cv) const
    {
      return (cv.right());
    }
  };

  Construct_max_vertex_2 construct_max_vertex_2_object () const
  {
    return Construct_max_vertex_2();
  }

  class Is_vertical_2
  {
  public:
    bool operator() (const X_monotone_curve_2& cv) const
    {
      return (cv.is_vertical());
    }
  };

  Is_vertical_2 is_vertical_2_object () const
  {
    return Is_vertical_2();
  }

  class Compare_y_at_x_2
  {
  public:
    Comparison_result operator() (const Point_2 & p,
                                  const X_monotone_curve_2 & cv) const
    {
      Alg_kernel   ker;

      if (cv.is_vertical())
      {
        // A special treatment for vertical segments:
        // In case p has the same x c-ordinate of the vertical segment, compare
        // it to the segment endpoints to determine its position.
        Comparison_result res1 = ker.compare_y_2_object() (p, cv.left());
        Comparison_result res2 = ker.compare_y_2_object() (p, cv.right());

        if (res1 == res2)
          return (res1);
        else
          return (EQUAL);
      }

      // Check whether the point is exactly on the curve.
      if (cv.contains_point(p))
        return (EQUAL);

      // Get a point q on the x-monotone arc with the same x coordinate as p.
      Comparison_result  x_res; 
      Point_2            q;

      if ((x_res = ker.compare_x_2_object() (p, cv.left())) == EQUAL)
      {
        q = cv.left();
      }
      else
      {
        CGAL_precondition (x_res != SMALLER);

        if ((x_res = ker.compare_x_2_object() (p, cv.right())) == EQUAL)
        {
          q = cv.right();
        }
        else
        {
          CGAL_precondition (x_res != LARGER);

          q = cv.point_at_x (p);
        }
      }

      // Compare p with the a point of the curve with the same x coordinate.
      return (ker.compare_y_2_object() (p, q));
    }
  };

  Compare_y_at_x_2 compare_y_at_x_2_object () const
  {
    return Compare_y_at_x_2();
  }

  class Compare_y_at_x_left_2
  {
  public:
    Comparison_result operator() (const X_monotone_curve_2& cv1,
                                  const X_monotone_curve_2& cv2,
                                  const Point_2& p) const
    {
      // Make sure that p lies on both curves, and that both are defined to its
      // left (so their left endpoint is lexicographically smaller than p).
      CGAL_precondition (cv1.contains_point (p) &&
                         cv2.contains_point (p));

      CGAL_precondition_code (
        Alg_kernel   ker;
      );
      CGAL_precondition (ker.compare_xy_2_object() (p, 
                                                    cv1.left()) == LARGER &&
                         ker.compare_xy_2_object() (p,
                                                    cv2.left()) == LARGER);

      // If one of the curves is vertical, it is below the other one.
      if (cv1.is_vertical())
      {
        if (cv2.is_vertical())
          // Both are vertical:
          return (EQUAL);
        else
          return (SMALLER);
      }
      else if (cv2.is_vertical())
      {
        return (LARGER);
      }

      // Compare the two curves immediately to the left of p:
      return (cv1.compare_to_left (cv2, p));
    }
  };

  Compare_y_at_x_left_2 compare_y_at_x_left_2_object () const
  {
    return Compare_y_at_x_left_2();
  }

  class Compare_y_at_x_right_2
  {
  public:
    Comparison_result operator() (const X_monotone_curve_2& cv1,
                                  const X_monotone_curve_2& cv2,
                                  const Point_2& p) const
    {
      // Make sure that p lies on both curves, and that both are defined to its
      // left (so their left endpoint is lexicographically smaller than p).
      CGAL_precondition (cv1.contains_point (p) &&
                         cv2.contains_point (p));

      CGAL_precondition_code (
        Alg_kernel   ker;
      );

      CGAL_precondition (ker.compare_xy_2_object() (p, 
                                                    cv1.right()) == SMALLER &&
                         ker.compare_xy_2_object() (p,
                                                    cv2.right()) == SMALLER);

      // If one of the curves is vertical, it is above the other one.
      if (cv1.is_vertical())
      {
        if (cv2.is_vertical())
          // Both are vertical:
          return (EQUAL);
        else
          return (LARGER);
      }
      else if (cv2.is_vertical())
      {
        return (SMALLER);
      }

      // Compare the two curves immediately to the right of p:
      return (cv1.compare_to_right (cv2, p));
    }
  };

  Compare_y_at_x_right_2 compare_y_at_x_right_2_object () const
  {
    return Compare_y_at_x_right_2();
  }

  class Equal_2
  {
  public:
    bool operator() (const X_monotone_curve_2& cv1,
                     const X_monotone_curve_2& cv2) const
    {
      if (&cv1 == &cv2)
        return (true);

      return (cv1.equals (cv2));
    }

    bool operator() (const Point_2& p1, const Point_2& p2) const
    {
      if (&p1 == &p2)
        return (true);

      Alg_kernel   ker;
      return (ker.compare_xy_2_object() (p1, p2) == EQUAL);
    }
  };

  Equal_2 equal_2_object () const
  {
    return Equal_2();
  }



  class Make_x_monotone_2
  {
    typedef Arr_conic_traits_2 <Rat_kernel_, Alg_kernel_, Nt_traits_>    Self;
  public:

    template<class OutputIterator>
    OutputIterator operator() (const Curve_2& cv, OutputIterator oi) const
    {
      // Increment the serial number of the curve cv, which will serve as its
      // unique identifier.
      unsigned int  index = Self::get_index();
      Conic_id      conic_id (index);
      
      // Find the points of vertical tangency to cv and act accordingly.
      typename Curve_2::Point_2  vtan_ps[2];
      int                        n_vtan_ps;

      n_vtan_ps = cv.vertical_tangency_points (vtan_ps);

      if (n_vtan_ps == 0)
      {    
        // In case the given curve is already x-monotone:
        *oi = make_object (X_monotone_curve_2 (cv, conic_id));
        ++oi;
        return (oi);
      }

      // Split the conic arc into x-monotone sub-curves. 
      if (cv.is_full_conic())
      {
        // Make sure we have two vertical tangency points.
        CGAL_assertion(n_vtan_ps == 2);

        // In case the curve is a full conic, split it into two x-monotone
        // arcs, one going from ps[0] to ps[1], and the other from ps[1] to
        // ps[0].
        *oi = make_object (X_monotone_curve_2 (cv, vtan_ps[0], vtan_ps[1], 
                                               conic_id));
        ++oi;
        *oi = make_object (X_monotone_curve_2 (cv, vtan_ps[1], vtan_ps[0], 
                                               conic_id));
        ++oi;
      }
      else
      {
        if (n_vtan_ps == 1)
        {
          // Split the arc into two x-monotone sub-curves: one going from the
          // arc source to ps[0], and the other from ps[0] to the target.
          *oi = make_object (X_monotone_curve_2 (cv, cv.source(), vtan_ps[0], 
                                                 conic_id));
          ++oi;
          *oi = make_object (X_monotone_curve_2 (cv, vtan_ps[0], cv.target(), 
                                                 conic_id));
          ++oi;
        }
        else
        {
          CGAL_assertion (n_vtan_ps == 2);

          // Identify the first point we encounter when going from cv's source
          // to its target, and the second point we encounter. Note that the
          // two endpoints must both be below the line connecting the two
          // tangnecy points (or both lies above it).
          int                   ind_first = 0;
          int                   ind_second = 1;
          Alg_kernel_           ker;
          typename Alg_kernel_::Line_2  line =
            ker.construct_line_2_object() (vtan_ps[0], vtan_ps[1]);
          const Comparison_result       start_pos =
            ker.compare_y_at_x_2_object() (cv.source(), line);
          const Comparison_result       order_vpts =
            ker.compare_x_2_object() (vtan_ps[0], vtan_ps[1]);

          CGAL_assertion (start_pos != EQUAL &&
                          ker.compare_y_at_x_2_object() (cv.target(),
                                                         line) == start_pos);
          CGAL_assertion (order_vpts != EQUAL);

          if ((cv.orientation() == COUNTERCLOCKWISE &&
               start_pos == order_vpts) ||
              (cv.orientation() == CLOCKWISE &&
               start_pos != order_vpts))
          {
            ind_first = 1;
            ind_second = 0;
          }

          // Split the arc into three x-monotone sub-curves.
          *oi = make_object (X_monotone_curve_2 (cv,
                                                 cv.source(), 
                                                 vtan_ps[ind_first], 
                                                 conic_id));
          ++oi;
          
          *oi = make_object (X_monotone_curve_2 (cv,
                                                 vtan_ps[ind_first], 
                                                 vtan_ps[ind_second], 
                                                 conic_id));
          ++oi;
          
          *oi = make_object (X_monotone_curve_2 (cv,
                                                 vtan_ps[ind_second],
                                                 cv.target(),
                                                 conic_id));
          ++oi;
        }
      }

      return (oi);
    }
  };

  Make_x_monotone_2 make_x_monotone_2_object () const
  {
    return Make_x_monotone_2();
  }

  class Split_2
  {
  public:
    void operator() (const X_monotone_curve_2& cv, const Point_2 & p,
                     X_monotone_curve_2& c1, X_monotone_curve_2& c2) const
    {
      cv.split (p, c1, c2);
      return;
    }
  };

  Split_2 split_2_object () const
  {
    return Split_2();
  }

  class Intersect_2
  {
  private:

    Intersection_map&  _inter_map;       // The map of intersection points.

  public:

    Intersect_2 (Intersection_map& map) :
      _inter_map (map)
    {}

    template<class OutputIterator>
    OutputIterator operator() (const X_monotone_curve_2& cv1,
                               const X_monotone_curve_2& cv2,
                               OutputIterator oi) const
    {
      return (cv1.intersect (cv2, _inter_map, oi));
    }
  };

  Intersect_2 intersect_2_object () const
  {
    return (Intersect_2 (inter_map));
  }

  class Are_mergeable_2
  {
  public:
    bool operator() (const X_monotone_curve_2& cv1,
                     const X_monotone_curve_2& cv2) const
    {
      return (cv1.can_merge_with (cv2));
    }
  };

  Are_mergeable_2 are_mergeable_2_object () const
  {
    return Are_mergeable_2();
  }

  class Merge_2
  {
  public:
    void operator() (const X_monotone_curve_2& cv1,
                     const X_monotone_curve_2& cv2,
                     X_monotone_curve_2& c) const
    {
      c = cv1;
      c.merge (cv2);

      return;
    }
  };

  Merge_2 merge_2_object () const
  {
    return Merge_2();
  }



  typedef double                          Approximate_number_type;

  class Approximate_2
  {
  public:

    Approximate_number_type operator() (const Point_2& p,
                                        int i) const
    {
      CGAL_precondition (i == 0 || i == 1);

      if (i == 0)
        return (CGAL::to_double(p.x()));
      else
        return (CGAL::to_double(p.y()));
    }
  };

  Approximate_2 approximate_2_object () const
  {
    return Approximate_2();
  }

  class Construct_x_monotone_curve_2
  {
  public:

    X_monotone_curve_2 operator() (const Point_2& p,
                                   const Point_2& q) const
    {
      return (X_monotone_curve_2 (p, q));
    }
  };

  Construct_x_monotone_curve_2 construct_x_monotone_curve_2_object () const
  {
    return Construct_x_monotone_curve_2();
  }


 
  class Compare_endpoints_xy_2
  {
  public:

    Comparison_result operator() (const X_monotone_curve_2& cv) const
    {
      if (cv.is_directed_right())
        return (SMALLER);
      else
        return (LARGER);
    }
  };

  Compare_endpoints_xy_2 compare_endpoints_xy_2_object() const
  {
    return Compare_endpoints_xy_2();
  }

  class Construct_opposite_2
  {
  public:

    X_monotone_curve_2 operator() (const X_monotone_curve_2& cv) const
    {
      return (cv.flip());
    }
  };

  Construct_opposite_2 construct_opposite_2_object() const
  {
    return Construct_opposite_2();
  }
};

CGAL_END_NAMESPACE

#endif