SPAR/AIModule/BWTA/vendors/CGAL/CGAL/Arr_segment_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_segment_traits_2.h $
// $Id: Arr_segment_traits_2.h 50374 2009-07-05 15:04:52Z efif $
// 
//
// Author(s)     : Ron Wein          <wein@post.tau.ac.il>
//                 Efi Fogel         <efif@post.tau.ac.il>

#ifndef CGAL_ARR_SEGMENT_TRAITS_2_H
#define CGAL_ARR_SEGMENT_TRAITS_2_H

#include <CGAL/tags.h>
#include <CGAL/intersections.h>
#include <CGAL/Arr_tags.h>
#include <CGAL/Arr_geometry_traits/Segment_assertions.h>
#include <fstream>

CGAL_BEGIN_NAMESPACE

template <class Kernel_> class Arr_segment_2;

template <class Kernel_>
class Arr_segment_traits_2 : public Kernel_
{
  friend class Arr_segment_2<Kernel_>;

public:

  typedef Kernel_                         Kernel;
  typedef typename Kernel::FT             FT;

  typedef typename Algebraic_structure_traits<FT>::Is_exact 
                                          Has_exact_division;

  // 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;
 
  typedef typename Kernel::Line_2         Line_2;
  typedef CGAL::Segment_assertions<Arr_segment_traits_2<Kernel> >
                                          Segment_assertions;

  class _Segment_cached_2
  {
  public:

    typedef typename Kernel::Line_2                Line_2;
    typedef typename Kernel::Segment_2             Segment_2;
    typedef typename Kernel::Point_2               Point_2;

  protected:

    Line_2    l;                // The line that supports the segment.
    Point_2   ps;               // The source point of the segment.
    Point_2   pt;               // The target point of the segment.
    bool      is_pt_max;        // Is the target (lexicographically) larger
                                // than the source.
    bool      is_vert;          // Is this a vertical segment.
    bool      is_degen;         // Is the segment degenerate (a single point).

  public:

    _Segment_cached_2 () :
      is_vert(false),
      is_degen(true)
    {}

    _Segment_cached_2 (const Segment_2& seg)
    {
      Kernel   kernel;

      typename Kernel_::Construct_vertex_2
        construct_vertex = kernel.construct_vertex_2_object();

      ps = construct_vertex(seg, 0);
      pt = construct_vertex(seg, 1);

      Comparison_result  res = kernel.compare_xy_2_object()(ps, pt);
      is_degen = (res == EQUAL);
      is_pt_max = (res == SMALLER);

      CGAL_precondition_msg (! is_degen,
                             "Cannot contruct a degenerate segment.");

      l = kernel.construct_line_2_object()(seg);
      is_vert = kernel.is_vertical_2_object()(seg);
    }

    _Segment_cached_2 (const Point_2& source, const Point_2& target) :
      ps (source),
      pt (target)
    {
      Kernel   kernel;

      Comparison_result  res = kernel.compare_xy_2_object()(ps, pt);
      is_degen = (res == EQUAL);
      is_pt_max = (res == SMALLER);

      CGAL_precondition_msg (! is_degen,
                             "Cannot contruct a degenerate segment.");

      l = kernel.construct_line_2_object()(source, target);
      is_vert = kernel.is_vertical_2_object()(l);
    }

    _Segment_cached_2 (const Line_2& supp_line,
                       const Point_2& source, const Point_2& target) :
      l (supp_line),
      ps (source),
      pt (target)
    {
      Kernel   kernel;

      CGAL_precondition(
        Segment_assertions::_assert_is_point_on(source, l,
                                                Has_exact_division()) &&
        Segment_assertions::_assert_is_point_on(target,l,
                                                Has_exact_division())
        );

      is_vert = kernel.is_vertical_2_object()(l);

      Comparison_result  res = kernel.compare_xy_2_object()(ps, pt);
      is_degen = (res == EQUAL);
      is_pt_max = (res == SMALLER);

      CGAL_precondition_msg (! is_degen,
                             "Cannot contruct a degenerate segment.");
    }

    const _Segment_cached_2& operator= (const Segment_2& seg)
    {
      Kernel   kernel;

      typename Kernel_::Construct_vertex_2
        construct_vertex = kernel.construct_vertex_2_object();

      ps = construct_vertex(seg, 0);
      pt = construct_vertex(seg, 1);

      Comparison_result  res = kernel.compare_xy_2_object()(ps, pt);
      is_degen = (res == EQUAL);
      is_pt_max = (res == SMALLER);

      CGAL_precondition_msg (! is_degen,
                             "Cannot contruct a degenerate segment.");

      l = kernel.construct_line_2_object()(seg);
      is_vert = kernel.is_vertical_2_object()(seg);

      return (*this);
    }

    const Point_2& left () const
    {
      return (is_pt_max ? ps : pt);
    }

    void set_left (const Point_2& p)
    {
      CGAL_precondition (! is_degen);
      CGAL_precondition_code (
        Kernel    kernel;
      );
      CGAL_precondition 
        (Segment_assertions::_assert_is_point_on (p, l, 
                                                  Has_exact_division()) &&
         kernel.compare_xy_2_object() (p, right()) == SMALLER);

      if (is_pt_max)
        ps = p;
      else
        pt = p;
    }

    const Point_2& right () const
    {
      return (is_pt_max ? pt : ps);
    }

    void set_right (const Point_2& p)
    {
      CGAL_precondition (! is_degen);
      CGAL_precondition_code (
        Kernel    kernel;
      );
      CGAL_precondition 
        (Segment_assertions::_assert_is_point_on (p, l, 
                                                  Has_exact_division()) &&
         kernel.compare_xy_2_object() (p, left()) == LARGER);

      if (is_pt_max)
        pt = p;
      else
        ps = p;
    }

    const Line_2& line () const
    {
      CGAL_precondition (! is_degen);
      return (l);
    }

    bool is_vertical () const
    {
      CGAL_precondition (! is_degen);
      return (is_vert);
    }

    bool is_directed_right () const
    {
      return (is_pt_max);
    }

    bool is_in_x_range (const Point_2& p) const
    {
      Kernel                          kernel;
      typename Kernel_::Compare_x_2   compare_x = kernel.compare_x_2_object();
      const Comparison_result         res1 = compare_x (p, left());

      if (res1 == SMALLER)
        return (false);
      else if (res1 == EQUAL)
        return (true);

      const Comparison_result         res2 = compare_x (p, right());

      return (res2 != LARGER);
    }

    bool is_in_y_range (const Point_2& p) const
    {
      Kernel                          kernel;
      typename Kernel_::Compare_y_2   compare_y = kernel.compare_y_2_object();
      const Comparison_result         res1 = compare_y (p, left());

      if (res1 == SMALLER)
        return (false);
      else if (res1 == EQUAL)
        return (true);

      const Comparison_result         res2 = compare_y (p, right());

      return (res2 != LARGER);
    }
  };

public:

  // Traits objects
  typedef typename Kernel::Point_2        Point_2;
  typedef Arr_segment_2<Kernel>           X_monotone_curve_2;
  typedef Arr_segment_2<Kernel>           Curve_2;
  typedef unsigned int                    Multiplicity;

public:

  Arr_segment_traits_2 ()
  {}



  class Compare_x_2
  {
  public:
    Comparison_result operator() (const Point_2& p1, const Point_2& p2) const
    {
      Kernel    kernel;

      return (kernel.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
    {
      Kernel    kernel;
      return (kernel.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
    {
      CGAL_precondition (cv.is_in_x_range (p));

      Kernel    kernel;

      if (! cv.is_vertical())
      {
        // Compare p with the segment's supporting line.
        return (kernel.compare_y_at_x_2_object()(p, cv.line()));
      }
      else
      {
        // Compare with the vertical segment's end-points.
        typename Kernel::Compare_y_2  compare_y = kernel.compare_y_2_object();
        Comparison_result res1 = compare_y (p, cv.left());
        Comparison_result res2 = compare_y (p, cv.right());

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

  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
    {
      Kernel                        kernel;

      // 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_code (
        typename Kernel::Compare_xy_2 compare_xy = 
                                                  kernel.compare_xy_2_object();
      );

      CGAL_precondition 
        (Segment_assertions::_assert_is_point_on (p, cv1, 
                                                  Has_exact_division()) &&
         Segment_assertions::_assert_is_point_on (p, cv2,
                                                  Has_exact_division()));

      CGAL_precondition (compare_xy(cv1.left(), p) == SMALLER &&
                         compare_xy(cv2.left(), p) == SMALLER);

      // Compare the slopes of the two segments to determine thir relative
      // position immediately to the left of q.
      // Notice we use the supporting lines in order to compare the slopes,
      // and that we swap the order of the curves in order to obtain the
      // correct result to the left of p.
      return (kernel.compare_slope_2_object()(cv2.line(), cv1.line()));
    }
  };

  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
    {
      Kernel                        kernel;

      // Make sure that p lies on both curves, and that both are defined to its
      // right (so their right endpoint is lexicographically larger than p).
      CGAL_precondition_code (
        typename Kernel::Compare_xy_2 compare_xy = 
                                                 kernel.compare_xy_2_object();
      );

      CGAL_precondition
        (Segment_assertions::_assert_is_point_on (p, cv1, 
                                                  Has_exact_division()) &&
         Segment_assertions::_assert_is_point_on (p, cv2,
                                                  Has_exact_division()));

      CGAL_precondition (compare_xy(cv1.right(), p) == LARGER &&
                         compare_xy(cv2.right(), p) == LARGER);

      // Compare the slopes of the two segments to determine thir relative
      // position immediately to the left of q.
      // Notice we use the supporting lines in order to compare the slopes.
      return (kernel.compare_slope_2_object()(cv1.line(), cv2.line()));
    }
  };

  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
    {
      Kernel                    kernel;
      typename Kernel::Equal_2  equal = kernel.equal_2_object();

      return (equal(cv1.left(), cv2.left()) &&
              equal(cv1.right(), cv2.right()));
    }

    bool operator() (const Point_2& p1, const Point_2& p2) const
    {
      Kernel    kernel;
      return (kernel.equal_2_object()(p1, p2));
    }
  };

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



  class Make_x_monotone_2
  {
  public:
    template<class OutputIterator>
    OutputIterator operator() (const Curve_2& cv, OutputIterator oi) const
    {
      // Wrap the segment with an object.
      *oi = make_object (cv);
      ++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
    {
      // Make sure that p lies on the interior of the curve.
      CGAL_precondition_code (
        Kernel                        kernel;
        typename Kernel::Compare_xy_2 compare_xy = 
                                                 kernel.compare_xy_2_object();
      );

      CGAL_precondition
        (Segment_assertions::_assert_is_point_on (p, cv,
                                                  Has_exact_division()) &&
         compare_xy(cv.left(), p) == SMALLER &&
         compare_xy(cv.right(), p) == LARGER);

      // Perform the split.
      c1 = cv;
      c1.set_right (p);

      c2 = cv;
      c2.set_left (p);

      return;
    }
  };

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

  class Intersect_2
  {
  public:
    template<class OutputIterator>
    OutputIterator operator() (const X_monotone_curve_2& cv1,
                               const X_monotone_curve_2& cv2,
                               OutputIterator oi) const
    {
      // Intersect the two supporting lines.
      Kernel       kernel;
      CGAL::Object obj = kernel.intersect_2_object()(cv1.line(), cv2.line());

      if (obj.is_empty())
      {
        // The supporting line are parallel lines and do not intersect:
        return (oi);
      }

      // Check if we have a single intersection point.
      const Point_2  *ip = object_cast<Point_2> (&obj);
      
      if (ip != NULL)
      {
        // Check if the intersection point ip lies on both segments.
        const bool    ip_on_cv1 = cv1.is_vertical() ? cv1.is_in_y_range(*ip) :
                                                      cv1.is_in_x_range(*ip);

        if (ip_on_cv1)
        {
          const bool  ip_on_cv2 = cv2.is_vertical() ? cv2.is_in_y_range(*ip) :
                                                      cv2.is_in_x_range(*ip);

          if (ip_on_cv2)
          {
            // Create a pair representing the point with its multiplicity,
            // which is always 1 for line segments.
            std::pair<Point_2, Multiplicity>   ip_mult (*ip, 1);
            *oi = make_object (ip_mult);
            oi++;
          }
        }
        return (oi);
      }

      // In this case, the two supporting lines overlap.
      // The overlapping segment is therefore [p_l,p_r], where p_l is the
      // rightmost of the two left endpoints and p_r is the leftmost of the
      // two right endpoints.
      typename Kernel::Compare_xy_2  compare_xy = kernel.compare_xy_2_object();
      Point_2                        p_l, p_r;

      if (compare_xy (cv1.left(), cv2.left()) == SMALLER)
        p_l = cv2.left();
      else
        p_l = cv1.left();

      if (compare_xy (cv1.right(), cv2.right()) == SMALLER)
        p_r = cv1.right();
      else
        p_r = cv2.right();

      // Examine the resulting segment.
      const Comparison_result        res = compare_xy (p_l, p_r);

      if (res == SMALLER)
      {
        // We have discovered an overlapping segment:
        if(cv1.is_directed_right() == cv2.is_directed_right())
        {
          // cv1 and cv2 have the same directions, maintain this direction
          // in the overlap segment
          if(cv1.is_directed_right())
          {
            X_monotone_curve_2  overlap_seg (cv1.line(), p_l, p_r);
            *oi = make_object (overlap_seg);
            oi++;
          }
          else
          {
            X_monotone_curve_2  overlap_seg (cv1.line(), p_r, p_l);
            *oi = make_object (overlap_seg);
            oi++;
          }
        }
        else
        {
          // cv1 and cv2 have opposite directions, the overlap segment
          // will be directed from left to right
          X_monotone_curve_2  overlap_seg (cv1.line(), p_l, p_r);
          *oi = make_object (overlap_seg);
          oi++;
        }
      }
      else if (res == EQUAL)
      {
        // The two segment have the same supporting line, but they just share
        // a common endpoint. Thus we have an intersection point, but we leave
        // the multiplicity of this point undefined.
        std::pair<Point_2, Multiplicity>   ip_mult (p_r, 0);
        *oi = make_object (ip_mult);
        oi++;
      }

      return (oi);
    }
  };

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

  class Are_mergeable_2
  {
  public:
    bool operator() (const X_monotone_curve_2& cv1,
                     const X_monotone_curve_2& cv2) const
    {
      Kernel                    kernel;
      typename Kernel::Equal_2  equal = kernel.equal_2_object();

      // Check if the two curves have the same supporting line.
      if (! equal (cv1.line(), cv2.line()) && 
          ! equal (cv1.line(), 
                   kernel.construct_opposite_line_2_object() (cv2.line())))
        return (false);

      // Check if the left endpoint of one curve is the right endpoint of the
      // other.
      return (equal (cv1.right(), cv2.left()) ||
              equal (cv2.right(), cv1.left()));
    }
  };

  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
    {
      Kernel                    kernel;
      typename Kernel::Equal_2  equal = kernel.equal_2_object();

      CGAL_precondition
        (equal (cv1.line(), cv2.line()) ||
         equal (cv1.line(),
                kernel.construct_opposite_line_2_object() (cv2.line())));

      // Check which curve extends to the right of the other.
      if (equal (cv1.right(), cv2.left()))
      {
        // cv2 extends cv1 to the right.
        c = cv1;
        c.set_right (cv2.right());
      }
      else
      {
        CGAL_precondition (equal (cv2.right(), cv1.left()));

        // cv1 extends cv2 to the right.
        c = cv2;
        c.set_right (cv1.right());
      }

      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);
      return (i == 0) ? (CGAL::to_double(p.x())) : (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
    {
      return (cv.is_directed_right()) ? (SMALLER) : (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();
  }
};

template <class Kernel_>
class Arr_segment_2 :
    public Arr_segment_traits_2<Kernel_>::_Segment_cached_2
{
  typedef Kernel_                                                  Kernel;
  typedef typename Arr_segment_traits_2<Kernel>::_Segment_cached_2 Base;
  typedef typename Kernel::Segment_2                               Segment_2;
  typedef typename Kernel::Point_2                                 Point_2;
  typedef typename Kernel::Line_2                                  Line_2;

public:

  Arr_segment_2 () :
    Base()
  {}
    
  Arr_segment_2 (const Segment_2& seg) :
    Base(seg)
  {}

  Arr_segment_2 (const Point_2& source, const Point_2& target) :
    Base(source,target)
  {}

  Arr_segment_2 (const Line_2& line,
                 const Point_2& source, const Point_2& target) :
    Base(line,source,target)
  {}

  operator Segment_2 () const
  {
    Kernel     kernel;
    Segment_2  seg = kernel.construct_segment_2_object() (this->ps, this->pt);
    return (seg);
  }

  Bbox_2 bbox() const
  {
    Kernel     kernel;
    Segment_2  seg = kernel.construct_segment_2_object() (this->ps, this->pt);
    return (kernel.construct_bbox_2_object() (seg));
  }

  const Point_2& source() const
  { 
    return (this->ps);
  }

  const Point_2& target() const
  {
    return (this->pt);
  }

  Arr_segment_2 flip () const
  {
    Arr_segment_2   opp;
    opp.l = this->l;
    opp.ps = this->pt;
    opp.pt = this->ps;
    opp.is_pt_max = !(this->is_pt_max);
    opp.is_vert = this->is_vert;
    opp.is_degen = this->is_degen;
    
    return (opp);
  }
};

template <class Kernel, class OutputStream>
OutputStream& operator<< (OutputStream& os, const Arr_segment_2<Kernel>& seg)
{
  os << static_cast<typename Kernel::Segment_2>(seg);
  return (os);
}

template <class Kernel, class InputStream>
InputStream& operator>> (InputStream& is, Arr_segment_2<Kernel>& seg)
{
  typename Kernel::Segment_2   kernel_seg;
  is >> kernel_seg;
  seg = kernel_seg;
  return (is);
}

CGAL_END_NAMESPACE

#endif