hyper_segment_2.h

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

// Copyright (c) 1999  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/Arrangement/include/CGAL/Arrangement_2/Hyper_segment_2.h,v $
// $Revision: 1.5 $ $Date: 2004/07/19 14:39:24 $
// $Name:  $
//
// Author(s)     : Ron Wein <[e-mail]>

#ifndef CGAL_HYPER_SEGMENT_2_H
#define CGAL_HYPER_SEGMENT_2_H

#include <CGAL/basic.h>
#include <CGAL/Cartesian.h>
#include <CGAL/Bbox_2.h>

#include <fstream>
class CGAL::Window_stream;

CGAL_BEGIN_NAMESPACE

/*!
 * Representation of a segment of a simplified canonical hyperbola, 
 * given by the equation:
 *    a*x^2 + b*y2 + c*x + d = 0
 *
 * We consider the upper part of the hyprobola (y > 0), thus the following
 * holds:
 *    y = sqrt(A*x^2 + B*x + C)
 *
 * The end-points of the hyperbolic segment are defined by x_min and x_max. 
 */
template <class Kernel_>
class Hyper_segment_2
{
protected:
  typedef Hyper_segment_2<Kernel_>      Self;
        
public:
  typedef Kernel_                       Kernel;
  typedef typename Kernel::FT           NT;
    
  typedef typename Kernel::Point_2      Point_2;

private:

  bool          _is_seg;      // Is this hyper-segment actaully a line segment.
  NT            _A;           // The coefficients of the equation of 
  NT            _B;           // the underlying canonical hyperbola:
  NT            _C;           //   y = sqrt (A*x^2 + B*x + C)

  Point_2       _source;      // The hyperbolic segment source.
  Point_2       _target;      // The hyperbolic segment target.

 public:

  /*!
   * Default constructor.
   */
  Hyper_segment_2 () :
    _is_seg(true)
  {}

  /*!
   * Construct a hyperbolic segment which lies on the canocial hyperbola:
   *    a*x^2 + b*y2 + c*x + d = 0
   * And bounded by x-min and x-max.
   * \param a The coefficient of x^2 in the equation of the hyperbola.
   * \param b The coefficient of y^2 in the equation of the hyperbola.
   * \param c The coefficient of x in the equation of the hyperbola.
   * \param d The free coefficient in the equation of the hyperbola.
   * \param x_min The x-coordinate of the leftmost end-point of the segment.
   * \param x_max The x-coordinate of the righttmost end-point of the segment.
   * \pre (a > 0) and (b < 0) -- to make sure this is indeed a hyperbola.
   *      Furthermore, x_max > x_min.
   */
  Hyper_segment_2 (const NT& a, const NT& b, const NT& c, const NT& d,
		   const NT& x_min, const NT& x_max) :
    _is_seg(false)
  {
    CGAL_precondition_code (static const NT  _zero = 0;);
    CGAL_precondition(_compare (a, _zero) == LARGER);
    CGAL_precondition(_compare (b, _zero) == SMALLER);
    CGAL_precondition(_compare (x_min, x_max) == SMALLER);

    // Set the normalized coefficients of the hyperbola.
    _A = -(a/b);
    _B = -(c/b);
    _C = -(d/b);

    // Set the end-points.
    bool  source_ok = _get_point_at_x (x_min, _source);
    bool  target_ok = _get_point_at_x (x_max, _target);

    if (! (source_ok && target_ok))
    {
      CGAL_assertion (source_ok);
      CGAL_assertion (target_ok);
    }

    // Check that both end-points lie on the same hyperbolic branch.
    /*
    CGAL_assertion_code (
      NT                xs[2];
      int               n = _solve_quadratic_equation (_A, _B, _C,
						       xs[0], xs[1]);
      Comparison_result res1;
      Comparison_result res2;
      int               i;

      CGAL_assertion (n == 2);
      for (i = 0; i < 2; i++)
      {
	res1 = _compare (x_min, xs[i]);
	res2 = _compare (x_max, xs[i]);

	CGAL_assertion (res1 == EQUAL || res2 == EQUAL || res1 == res2);
      }
    );
    */
  }

  /*!
   * Construct a degenerate hyperbolic segment defined by a line segment.
   * \param ps The source point of the segment.
   * \param pt The target point of the segment.
   * \pre The segment is not vertical -- that is, x(ps) does not equal x(pt).
   *      Furthermore, both points should lie above the x-axis.
   */
  Hyper_segment_2 (const Point_2& ps, const Point_2& pt) :
    _is_seg(true)
  {
    // Make sure that the two points do not define a vertical segment.
    Comparison_result comp_x = _compare (ps.x(), pt.x());

    CGAL_precondition(comp_x != EQUAL);

    // Make sure that both points are above the x-axis.
    CGAL_precondition_code (static const NT  _zero = 0;);
    CGAL_precondition(_compare (ps.y(), _zero) == LARGER);
    CGAL_precondition(_compare (pt.y(), _zero) == LARGER);

    // Find the line (y = a*x + b)  that connects the two points.
    const NT  denom = ps.x() - pt.x();
    const NT  a = (ps.y() - pt.y()) / denom;
    const NT  b = (ps.x()*pt.y() - pt.x()*ps.y()) / denom;

    // Set the underlying hyperbola to be the pair of lines:
    //  y^2 = (a*x + b)^2 = (a^2)*x^2 + (2ab)*x + b^2
    _A = a*a;
    _B = 2*a*b;
    _C = b*b;

    // Set the source and target point.
    if (comp_x != LARGER)
    {
      _source = ps;
      _target = pt;
    }
    else
    {
      _source = pt;
      _target = ps;
    }
  }

  /*!
   * Access the hyperblic coeffcients.
   */
  const NT& A () const {return (_A);}
  const NT& B () const {return (_B);}
  const NT& C () const {return (_C);}

  /*!
   * Get the source of the hyper-segment.
   * \return The source point.
   */
  const Point_2& source () const
  {
    return (_source);
  }

  /*!
   * Get the target of the hyper-segment.
   * \return The target point.
   */
  const Point_2& target () const
  {
    return (_target);
  }

  /*! 
   * Check whether the hyper-segment is actually a line segment.
   * \return (true) if the underlying hyperbola is actually a line segment.
   */
  bool is_linear () const
  {
    return (_is_seg);
  }

  /*!
   * Check if the two hyper-segments are equal.
   * \param seg The compares hyper-segments.
   * \return (true) if seg equals (*this) or if it is its flipped version.
   */
  bool is_equal (const Self& seg) const
  {
    if (this == &seg)
      return (true);

    // The underlying hyperbola must be the same:
    if (! _has_same_base_hyperbola(seg))
      return (false);

    // Compare the source and target.
    if (_compare (_source.x(), seg._source.x()) &&
	_compare (_target.x(), seg._target.x()))
      return (true);
    else if (_compare (_source.x(), seg._target.x()) &&
	     _compare (_target.x(), seg._source.x()))
      return (true);
    
    return (false);
  }

  /*!
   * Get a bounding box for the hyper-segment.
   * \return A bounding box.
   */
  Bbox_2 bbox () const
  {
    // Use the source and target to find the exterme coordinates.
    double  x1 = CGAL::to_double(_source.x());
    double  y1 = CGAL::to_double(_source.y());
    double  x2 = CGAL::to_double(_target.x());
    double  y2 = CGAL::to_double(_target.y());
    double  x_min, x_max;
    double  y_min, y_max;

    if (x1 < x2)
    {
      x_min = x1;
      x_max = x2;
    }
    else
    {
      x_min = x2;
      x_max = x1;
    }

    if (y1 < y2)
    {
      y_min = y1;
      y_max = y2;
    }
    else
    {
      y_min = y2;
      y_max = y1;
    }

    // Try to check if any extreme points are contained in our segment.
    if (_A != 0)
    {
      // The x-coordinate of the extreme point is given by:
      double  x_ext = CGAL::to_double(-_B / (2*_A));

      if (x_min < x_ext && x_ext < x_max)
      {
	// The y-value at the extreme point is given by:
	double   y_ext = (CGAL::to_double(_A)*x_ext + 
			  CGAL::to_double(_B))*x_ext + CGAL::to_double(_C);

	if (y_ext > 0)
	  y_ext = CGAL::sqrt(y_ext);
	else
	  y_ext = 0;

	if (y_ext < y_min)
	  y_min = y_ext;
	else if (y_ext > y_max)
	  y_max = y_ext;
      }
    }

    // Return the resulting bounding box.
    return (Bbox_2 (x_min, y_min, x_max, y_max));
  }

  /*!
   * Check if the given point is in the x-range of the hyper-segment.
   * \param q The query point.
   * \return (true) if q is in the x-range of the hyper-segment.
   */
  bool point_is_in_x_range (const Point_2& q) const
  {
    Comparison_result res1 = _compare (q.x(), _source.x());
    Comparison_result res2 = _compare (q.x(), _target.x());
    
    return ((res1 == EQUAL) || (res2 == EQUAL) || (res1 != res2));
  }

  /*!
   * Check the position of the query point with respect to the hyper-segment.
   * \param q The query point.
   * \return SMALLER if q lies under the hyper-segment;
   *         LARGER if it lies above the hyper-segment;
   *         EQUAL if q lies on the hyper-segment.
   * \pre q is in the x-range of the hyper-segment.
   */
  Comparison_result point_position (const Point_2& q) const
  {
    CGAL_precondition(point_is_in_x_range (q)); 

    // Substitute q's x-coordinate into the equation of the hyperbola and
    // compare the result.
    return (_compare (q.y(),
		      CGAL::sqrt(_A*q.x()*q.x() + _B*q.x() + _C)));
  }

  /*!
   * Return a flipped hyper-segment.
   * \return The flipped hyper-segment.
   */
  Self flip () const
  {
    Self     flipped (*this);

    flipped._source = _target;
    flipped._target = _source;

    return (flipped);
  }

  /*!
   * Compare the y-coordinates of two hyper-segments at a given x-coordinate.
   * \param seg The other segment.
   * \param q The point (a placeholder for the x-coordinate).
   * \return SMALLER if (*this) is below seg at q;
   *         LARGER if it is above seg at q;
   *         EQUAL if the two hyper-segment intersect at this x-coordinate.
   * \pre q is in the x-range of both hyper-segments.
   */
  Comparison_result compare_y_at_x (const Self& seg,
				    const Point_2& q) const
  {
    CGAL_precondition(this->point_is_in_x_range(q));
    CGAL_precondition(seg.point_is_in_x_range(q));
  
    // Compare y1 = A1*x^2 + B1*x + C1 
    //     and y2 = A2*x^2 + B2*x + C2:
    return (_compare (_A*q.x()*q.x() + _B*q.x() + _C,
		      seg._A*q.x()*q.x() + seg._B*q.x() + seg._C));
  }

  /*!