pm_traits_wrap_2.h

来自「CGAL is a collaborative effort of severa」· C头文件 代码 · 共 633 行 · 第 1/2 页

// Copyright (c) 1997  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.
//
// $Source: /CVSROOT/CGAL/Packages/Planar_map/include/CGAL/Planar_map_2/Pm_traits_wrap_2.h,v $
// $Revision: 1.7 $ $Date: 2004/05/09 14:17:42 $
// $Name:  $
//
// Author(s)     : Iddo Hanniel         <[e-mail]>
//                 Eyal Flato           <[e-mail]>
//                 Oren Nechushtan      <[e-mail]>
//                 Efi Fogel            <[e-mail]>
//                 Ron Wein             <[e-mail]>

#ifndef CGAL_PM_TRAITS_WRAP_H
#define CGAL_PM_TRAITS_WRAP_H

#include <CGAL/config.h>
#include <CGAL/tags.h>
#include <iostream>

CGAL_BEGIN_NAMESPACE

//--------------------------------------------------------------------------
// Pm_traits_wrap_2 - 
//     Geometric Look Up Table. This class extends the user supplied 
// interface to include various less "shallow" operations that are
// impelemented through the interface.
//--------------------------------------------------------------------------

template <class PlanarMapTraits_2>
class Pm_traits_wrap_2 : public PlanarMapTraits_2
{
public:
//  typedef  typename I::Info_vertex     Info_vertex;
//  typedef  typename I::Info_edge       Info_edge;
//  typedef  typename I::Info_face       Info_face;
  
  typedef PlanarMapTraits_2                     Base;
  typedef typename Base::X_monotone_curve_2     X_monotone_curve_2;
  typedef typename Base::Point_2                Point_2;

  typedef typename Base::Has_left_category      Has_left_category;      
  typedef typename Base::Has_reflect_category   Has_reflect_category;    
    
  // Creators:
  // ---------
  Pm_traits_wrap_2() : Base() {}
  Pm_traits_wrap_2(const Base & i) : Base(i) {}

  // Predicates:
  // -----------
  bool point_is_left(const Point_2 & p1, const Point_2 & p2) const
  { return (compare_x(p1, p2) == SMALLER); }
  
  bool point_is_right(const Point_2 & p1, const Point_2 & p2) const
  { return (compare_x(p1, p2) == LARGER); }
    
  bool point_equal_x(const Point_2 & p1, const Point_2 & p2) const
  { return (compare_x(p1, p2) == EQUAL); }
  
  bool point_is_left_low(const Point_2 & p1, const Point_2 & p2) const
  { return (compare_xy(p1, p2) == SMALLER); }
    
  bool point_is_right_top(const Point_2 & p1, const Point_2 & p2) const
  { return point_is_left_low(p2,p1); }
    
  const Point_2 & point_leftmost(const Point_2 & p1, const Point_2 & p2) const
  { return (point_is_left(p1, p2) ? p1 : p2); }
    
  const Point_2 & point_rightmost(const Point_2 & p1, const Point_2 & p2) const
  { return (point_is_right(p1, p2) ? p1 : p2); }
    
  const Point_2 & point_leftlow_most (const Point_2 & p1, 
				      const Point_2 & p2) const
  { return (point_is_left_low(p1, p2) ? p1 : p2); }
    
  const Point_2 & point_righttop_most (const Point_2 & p1, 
				       const Point_2 & p2) const
  { return (point_is_right_top(p1, p2) ? p1 : p2); }
    
  Point_2 curve_leftmost(const X_monotone_curve_2 & cv) const 
  { return point_leftmost(curve_source(cv), curve_target(cv)); }
    
  Point_2 curve_rightmost(const X_monotone_curve_2 & cv) const
  { return point_rightmost(curve_source(cv), curve_target(cv)); }
      
  Point_2 curve_leftlow_most(const X_monotone_curve_2 & cv) const 
  {
    if (!curve_is_vertical(cv)) 
      return curve_leftmost(cv);
    else
      return point_leftlow_most(curve_source(cv), curve_target(cv));
  }
    
  Point_2 curve_righttop_most(const X_monotone_curve_2 & cv) const
  {
    if (!curve_is_vertical(cv)) 
      return curve_rightmost(cv);
    else
      return point_righttop_most(curve_source(cv), curve_target(cv));
  }

  /*!
   * The function restuns whether two sub-curves can be merged to create
   * the input curve.
   * \param whole The input curve (the merge result).
   * \param part1 The first sub-curve.
   * \param part2 The second sub-curve.
   * \return (true) if whole == part1 + part2.
   */
  bool curve_merge_condition(const X_monotone_curve_2 & whole,
			     const X_monotone_curve_2 & part1,
			     const X_monotone_curve_2 & part2) const
  {
    // The function simply checks whether it is possible to merge
    // the curves part1 and part2 such that whole is the result.
    if (point_equal(curve_source(whole), curve_source(part1)))
      if (point_equal(curve_target(part1), curve_source(part2)))
	if (point_equal(curve_target(part2), curve_target(whole)))
	  return (true);
	else
	  return (false);
      else
	if (point_equal(curve_target(part1), curve_target(part2)))
	  if (point_equal(curve_source(part2), curve_target(whole)))
	    return(true);
	  else
	    return (false);
	else
	  return (false);
    else
      if (point_equal(curve_source(whole), curve_target(part1)))
	if (point_equal(curve_source(part1), curve_source(part2)))
	  if (point_equal(curve_target(part2), curve_target(whole)))
	    return (true);
	  else
	    return (false);
	else
	  if (point_equal(curve_source(part1), curve_target(part2)))
	    if (point_equal(curve_source(part2), curve_target(whole)))
	      return (true);
	    else
	      return (false);
	  else
	    return (false);
      else
	if (point_equal(curve_source(whole), curve_source(part2)) ||
	    point_equal(curve_source(whole), curve_target(part2)))
	  return (curve_merge_condition (whole, part2, part1));
	else
	  return (false);
  }
  
  /*!
   * Check whether the curve is degenerate.
   * \param cv The input curve.
   * \return (true) iff the curve source and target are the same.
   */
  inline bool curve_is_degenerate(const X_monotone_curve_2 & cv) const
  { 
    return point_equal(curve_source(cv),curve_target(cv));
  }
    
  /*! 
   * Check if the given query curve is encountered when rotating the first
   * curve in a clockwise direction around a given point until reaching the
   * second curve.
   * \param cv The query curve.
   * \param cv1 The first curve.
   * \param cv2 The second curve.
   * \param p The point around which we rotate cv1.
   * \pre p is an end-point of all three curves.
   * \return (true) if cv is between cv1 and cv2. If cv overlaps cv1 or cv2
   * the result is always (false). If cv1 and cv2 overlap, the result is
   * (true), unless cv1 also overlaps them.
   */
  bool curve_is_between_cw(const X_monotone_curve_2& cv, 
                           const X_monotone_curve_2& cv1, 
                           const X_monotone_curve_2& cv2, 
                           const Point_2& p) const
  {
    // Find the direction of each segment.
    Curve_dir_at_point     dir = _curve_direction_at_point (cv, p);
    Curve_dir_at_point     dir1 = _curve_direction_at_point (cv1, p);
    Curve_dir_at_point     dir2 = _curve_direction_at_point (cv2, p);

    // Special treatment for the cases where cv1 or cv2 are vertical segments:
    if (dir1 == DIR_UP || dir1 == DIR_DOWN)
    {
      if (dir2 == DIR_UP || dir2 == DIR_DOWN)
      {
	// Both cv1 and cv2 are vertical:
	if (dir1 == DIR_UP && dir2 == DIR_DOWN)
	  return (dir == DIR_RIGHT);
	else if (dir1 == DIR_DOWN && dir2 == DIR_UP)
	  return (dir == DIR_LEFT);
	else
	  return (dir != dir1);
      }

      // Only cv1 is vertical:
      if (dir1 == DIR_UP)
      {
	if (dir2 == DIR_LEFT)
	  return (dir == DIR_RIGHT ||
		  dir == DIR_DOWN ||
                  (dir == DIR_LEFT &&
                   curves_compare_y_at_x_left (cv2, cv, p) == LARGER));
	else
	  return (dir == DIR_RIGHT &&
		  curves_compare_y_at_x_right (cv2, cv, p) == SMALLER);
      }
      else
      {
	if (dir2 == DIR_LEFT)
	  return (dir == DIR_LEFT &&
		  curves_compare_y_at_x_left (cv2, cv, p) == LARGER);
	else
	  return (dir == DIR_LEFT ||
		  dir == DIR_UP ||
                  (dir == DIR_RIGHT &&
                   curves_compare_y_at_x_right (cv2, cv, p) == SMALLER));
      }
    }

    if (dir2 == DIR_UP || dir2 == DIR_DOWN)
    {
      // Only cv2 is vertical:
      if (dir2 == DIR_UP)
      {
	if (dir1 == DIR_LEFT)
	  return (dir == DIR_LEFT &&
		  curves_compare_y_at_x_left (cv1, cv, p) == SMALLER);
	else
	  return (dir == DIR_LEFT || 
		  dir == DIR_DOWN ||
                  (dir == DIR_RIGHT &&
                   curves_compare_y_at_x_right (cv1, cv, p) == LARGER));
      }
      else
      {
	if (dir1 == DIR_LEFT)
	  return (dir == DIR_RIGHT ||
		  dir == DIR_UP ||
                  (dir == DIR_LEFT &&
                   curves_compare_y_at_x_left (cv1, cv, p) == SMALLER));
	else
	  return (dir == DIR_RIGHT &&
		  curves_compare_y_at_x_right (cv1, cv, p) == LARGER);
      }
    }

    // Take care of the general 4 cases:
    if (dir1 == DIR_LEFT && dir2 == DIR_LEFT)
    {
      // Case 1: Both cv1 and cv2 are defined to the left of p.
      Comparison_result l_res = curves_compare_y_at_x_left (cv1, cv2, p);
      
      if (l_res == LARGER)
      {
	// Case 1(a) : cv1 is above cv2.
	return (dir != DIR_LEFT ||
		curves_compare_y_at_x_left (cv1, cv, p) == SMALLER ||
                curves_compare_y_at_x_left (cv2, cv, p) == LARGER);
      }
      else if (l_res == SMALLER)
      {
	// Case 1(b): cv1 is below cv2.
	return (dir == DIR_LEFT &&
		curves_compare_y_at_x_left (cv1, cv, p) == SMALLER &&
		curves_compare_y_at_x_left (cv2, cv, p) == LARGER);
      }
      else
      {
        // Overlapping segments.
        return (dir != DIR_LEFT ||
                curves_compare_y_at_x_left (cv1, cv, p) != EQUAL);
      }
    }
    else if (dir1 == DIR_RIGHT && dir2 == DIR_RIGHT)
    {
      // Case 2: Both cv1 and cv2 are defined to the right of p.
      Comparison_result r_res = curves_compare_y_at_x_right (cv1, cv2, p);

      if (r_res == LARGER)
      {
	// Case 2(a) : cv1 is above cv2.
	return (dir == DIR_RIGHT &&
		curves_compare_y_at_x_right (cv1, cv, p) == LARGER &&
		curves_compare_y_at_x_right (cv2, cv, p) == SMALLER);
      }
      else if (r_res == SMALLER)
      {
	// Case 2(b): cv1 is below cv2.
	return (dir != DIR_RIGHT ||
		curves_compare_y_at_x_right (cv1, cv, p) == LARGER ||
                curves_compare_y_at_x_right (cv2, cv, p) == SMALLER);
      }
      else
      {
        // Overlapping segments.
        return (dir != DIR_RIGHT ||
                curves_compare_y_at_x_right (cv1, cv, p) != EQUAL);
      }
    }
    else if (dir1 == DIR_LEFT && dir2 == DIR_RIGHT)
    {