isolating_interval.h

很多二维 三维几何计算算法 C++ 类库

// Copyright (c) 2005  Stanford University (USA).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public License as
// published by the Free Software Foundation; version 2.1 of the License.
// See the file LICENSE.LGPL 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.3-branch/Kinetic_data_structures/include/CGAL/Polynomial/internal/Isolating_interval.h $
// $Id: Isolating_interval.h 33379 2006-08-17 09:41:22Z afabri $
// 
//
// Author(s)     : Daniel Russel <[e-mail]>

#ifndef CGAL_POLYNOMIAL_INTERNAL_ISOLATING_INTERVAL_H
#define CGAL_POLYNOMIAL_INTERNAL_ISOLATING_INTERVAL_H
#include <CGAL/Polynomial/basic.h>
#include <CGAL/Polynomial/internal/interval_arithmetic.h>
#include <iostream>

CGAL_POLYNOMIAL_BEGIN_INTERNAL_NAMESPACE

//! necessary to support filtered_numbers which I don't like
template <class NT, class Functor>
typename Functor::result_type apply(const Functor &f,  const NT &a)
{
  return f(a);
}


//! necessary to support filtered_numbers which I don't like
template <class NT, class Functor>
typename Functor::result_type apply(const Functor &f,  const NT &a,
				    const NT &b)
{
  return f( a, b);
}


//! necessary to support filtered_numbers which I don't like
template <class NT, class Functor, class Data>
typename Functor::result_type apply(const Functor &f,  const NT &a,
				    const NT &b, const Data &da, const Data &db)
{
  return f( a, b, da, db);
}


//! Define the interface for a bounding interval By convention the intervals are closed.
/*!
  Just remember the bounds.

*/
template <class FT_t>
class Isolating_interval
{
  typedef Isolating_interval<FT_t> This;
public:
  typedef FT_t NT;
  Isolating_interval(): b_(1, -1){}
  Isolating_interval(const NT &lbi): b_(lbi, lbi) {
  }
  Isolating_interval(const NT &lbi, const NT &ubi): b_(lbi, ubi) {
    if(0) print();                        // make sure it is instantiated
    if (lb() > ub()) {
      std::cerr << "b_.first=" << lb() << " and b_.second=" << ub() << std::endl;
    }
    CGAL_Polynomial_assertion(lb() <= ub());
  }

  typedef enum Endpoint {UPPER, LOWER}
    Endpoint;

  //! Damn this is awful, but I can't think of another way for Filtered interval
  template <class Function>
  typename Function::result_type apply_to_endpoint(const Function &f, Endpoint b) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    if (b==UPPER) {
      return apply(f,ub());
    }
    else {
      return apply(f, lb());
    }
  }

  //! Damn this is awful, but I can't think of another way for Filtered interval
  template <class Function>
  typename Function::result_type apply_to_midpoint(const Function &f) {
    CGAL_Polynomial_assertion(lb() <= ub());
    return apply(f,middle());
  }

  //!
  template <class Function>
  typename Function::result_type apply_to_interval(const Function &f) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    return apply(f, lb(), ub());
  }

  //! Allow some extra data. This is kind of an evil hack.
  template <class Function, class Data>
  typename Function::result_type apply_to_interval(const Function &f,
						   const Data &d0, const Data &d1) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    return apply(f, lb(), ub(), d0, d1);
  }

  This upper_endpoint_interval() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    return This(ub());
  }

  This lower_endpoint_interval() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    return This(lb());
  }

  //! Make the interval singular on bound b.
  This endpoint_interval(Endpoint b) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    if (b==UPPER) {
      return This(ub());
    }
    else {
      return This(lb());
    }
  }

  This midpoint_interval() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    return This(middle());
  }

  //! Split in half
  This first_half() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    return This(lb(), middle());
  }
  //! Split in half
  This second_half() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    return This(middle(), ub());
  }

  //! Return both the first and second half; the midpoint is computed once
  std::pair<This,This> split() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    NT mid = middle();
    return std::pair<This,This>(This(lb(), mid), This(mid, ub()));
  }

  //! Returns the interval [(a+(a+b)/2)/2,((a+b)/2+b)/2]
  This middle_half() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    NT mid = middle();
    NT mid_left = midpoint(lb(), middle());
    NT mid_right = midpoint(middle(), ub());

    return This(mid_left, mid_right);
  }

  std::pair<This,This> split_at(const NT& x) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    CGAL_precondition( !is_singular() &&
		       lower_bound() < x && x < upper_bound() );
    return std::pair<This,This>( This(lower_bound(), x),
				 This(x, upper_bound()) );
  }

  This split_at_first_half(const NT& x) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    CGAL_precondition( !is_singular() &&
		       lower_bound() < x && x < upper_bound() );
    return This(lower_bound(), x);
  }
  This split_at_second_half(const NT& x) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    CGAL_precondition( !is_singular() &&
		       lower_bound() < x && x < upper_bound() );
    return This(x, upper_bound());
  }

  This interval_around_endpoint(Endpoint b) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    NT mid = middle();

    if ( b == LOWER ) {
      return This(lower_bound()-NT(1), mid);
    }                                     // end-if

    // b == UPPER
    return This(mid, upper_bound()+NT(1));
  }

  //! See if the interval only contains a point.
  bool is_singular() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    return lb()==ub();
  }

  const NT &to_nt() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    CGAL_Polynomial_precondition(is_singular());
    return lb();
  }

  /*bool overlaps(const This &o) const {
    if (b_.first > o.b_.first && b_.first < o.b_.second) return true;
    else if (b_.second > o.b_.first && b_.first < o.b_.second) return true;
    else if (o.b_.second > b_.first && b_.first < b_.second) return true;
    else if (o.b_.first > b_.first && b_.first < b_.second) return true;
    else if (*this==o) return true;
    else return false;
    }*/

  //! Compare this interval to another.
  Order order(const This &o) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    CGAL_Polynomial_assertion(o.lb() <= o.ub());
    if (*this < o) return STRICTLY_BELOW;
    else if (o < *this) return STRICTLY_ABOVE;
    else if (lb() <= o.lb() && ub() >= o.ub()) return CONTAINS;
    else if (o.lb() <= lb() && o.ub() >= ub()) return CONTAINED;
    else if (*this == o) return EQUAL;
    else if (lb() < o.lb()) return BELOW;
    else return ABOVE;
  }

  //! Cut this at bound b on interval o
  /*!  i.e. If bd is UPPER, then o is assumed to be below this (but
    overlaping) and the new interval goes from o.upper_bound() to
    this->upper_bound()
  */
  /*This chop(const This &o, Endpoint bd) const {
    if (bd== UPPER) {
    Polynomial_assertion(lb()== o.lb() && ub() > o.ub());
    return This(o.ub(), ub());
    } else {
    Polynomial_assertion(ub()== o.ub() && lb() < o.lb());
    return This(lb(),o.lb());
    }
    }*/

  int number_overlap_intervals(const This &o) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    CGAL_Polynomial_assertion(o.lb() <= o.ub());
    Order ord= order(o);
    switch(ord) {
    case CONTAINS:
      return 3;
    case CONTAINED:
      return 1;
    case BELOW:
    case ABOVE:
      return 2;
    case STRICTLY_ABOVE:
    case STRICTLY_BELOW:
      return 1;
    default:
      return -1;
    }
  }

  // If we have two partially overllaping intervals, then
  // *_overlap_interval  return the three possible intervals of *this:
  // the common interval and the non-common remainders of the two
  // intervals.
  This first_overlap_interval(const This &o) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    CGAL_Polynomial_assertion(o.lb() <= o.ub());
    Order ord= order(o);
    switch(ord) {
    case CONTAINS:
      return This(lb(), o.lb());
    case CONTAINED:
    case STRICTLY_ABOVE:
    case STRICTLY_BELOW:
      return *this;
    case BELOW:
      return This(lb(), o.lb());
    case ABOVE:
      return This(lb(), o.ub());