trapezoidal_decomposition_2.h

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

// 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.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.3-branch/Arrangement_2/include/CGAL/Arr_point_location/Trapezoidal_decomposition_2.h $
// $Id: Trapezoidal_decomposition_2.h 37681 2007-03-29 16:32:27Z efif $
// 
//
// Author(s)     : Oren Nechushtan <[e-mail]>
//                 Iddo Hanniel <[e-mail]>

#ifndef CGAL_TRAPEZOIDAL_DECOMPOSITION_2_H
#define CGAL_TRAPEZOIDAL_DECOMPOSITION_2_H

#include <CGAL/basic.h>
#include <CGAL/Arr_point_location/Td_predicates.h>
#include <CGAL/Arr_point_location/Trapezoidal_decomposition_2_misc.h>

#include <cstdlib>
#include <cstring>
#include <iostream>
#include <cmath>
#include <ctime>
#include <list>
#include <vector>
#include <map>

CGAL_BEGIN_NAMESPACE

#define CGAL_POINT_IS_LEFT_LOW(p,q) \
  (traits->compare_xy_2_object()((p),(q)) == SMALLER)
#define CGAL_POINT_IS_RIGHT_TOP(p,q) \
  (traits->compare_xy_2_object()((p),(q)) == LARGER)
#define CGAL_CURVE_IS_TO_RIGHT(cv,p) \
  (traits->equal_2_object()(traits->construct_min_vertex_2_object()((cv)), (p)))
#define CGAL_CURVE_COMPARE_Y_AT_X(p,cv) \
  (traits->compare_y_at_x_2_object()((p),(cv)))
/* //////////////////////////////////////////////////////////////////////////

class         Trapezoidal_decomposition_2
parameters    Traits,X_curve
Description   Implementation for a planar trapezoidal map also known as
trapezoidal decomposition and vertical decomposition.
  
For requirements on Traits and X_curve classes see 
Trapezoidal_decomposition_2 documentation.

////////////////////////////////////////////////////////////////////////// */

template < class Td_traits>
class Trapezoidal_decomposition_2
{
 public:
  enum Locate_type {POINT=0,CURVE,TRAPEZOID,UNBOUNDED_TRAPEZOID=8} ;
  class Base_trapezoid_iterator;
  class In_face_iterator;
  friend class In_face_iterator;
  class Around_point_circulator;
  struct Unbounded {};
  typedef Td_traits Traits;
  typedef const Traits& const_Traits_ref;
  typedef const Traits* const_Traits_ptr;
  typedef Trapezoidal_decomposition_2<Traits> Self;
  typedef const Self& const_Self_ref;
  typedef const Self* const_Self_ptr;
  typedef typename Traits::Point Point;
  typedef typename Traits::X_curve X_curve;
  typedef typename Traits::X_curve_ptr curve_pointer;
  typedef typename Traits::X_curve_ref curve_ref;
  typedef typename Traits::X_curve_const_ref curve_const_ref;
  typedef typename Traits::X_trapezoid X_trapezoid;
  typedef typename Traits::X_trapezoid_ptr pointer;
  typedef typename Traits::X_trapezoid_ref reference;
  typedef typename Traits::X_trapezoid_const_ref const_ref;
  typedef std::list<X_trapezoid> list_container;
  typedef std::vector<X_trapezoid> vector_container;
  typedef std::vector<X_curve> X_curve_container;
  typedef In_face_iterator Iterator;
  typedef class Base_trapezoid_iterator Base_trapezoid_circulator;
  // friend class Td_traits::X_trapezoid;
  
  typedef CGAL::Td_active_trapezoid<X_trapezoid> Td_active_trapezoid;
  typedef CGAL::Td_active_non_degenerate_trapezoid<X_trapezoid,Traits> 
    Td_active_non_degenerate_trapezoid;
  typedef CGAL::Td_active_right_degenerate_curve_trapezoid<X_trapezoid,Traits> 
    Td_active_right_degenerate_curve_trapezoid;
  typedef Td_dag< X_trapezoid> Data_structure;
  typedef std::map<int,Data_structure> map_nodes;
  //   typedef std::hash_map<const X_trapezoid*, X_trapezoid*> hash_map_tr_ptr;
  typedef Trapezoid_handle_less<const X_trapezoid* const> Trapezoid_ptr_less;
  typedef std::map<const X_trapezoid*, X_trapezoid*, Trapezoid_ptr_less> 
    hash_map_tr_ptr;
  
  /*
   * class Base_trapezoid_iterator
   * member of Trapezoidal_decomposition_2<Traits>
   * Description Implements a basic Trapezoid iterator
   */
  
  class Base_trapezoid_iterator
  {
  public:
    Base_trapezoid_iterator() : traits(0),curr(0) {};
    Base_trapezoid_iterator(const_Traits_ptr traits_,pointer currt=0):
      traits(traits_),curr(currt) {}
	Base_trapezoid_iterator(const Base_trapezoid_iterator &it):
	  traits(it.traits),curr(it.curr){;}
    Base_trapezoid_iterator  & operator=(const Base_trapezoid_iterator &it)
    {
      traits=it.traits;
      curr=it.curr;
      return *this;
    }
    bool operator==(const Base_trapezoid_iterator &it) const
    {
      return (curr==it.curr );
    }
    bool operator!=(const Base_trapezoid_iterator &it) const
    {
      return !operator==(it);
    }
    reference operator*() const
    {
      CGAL_precondition(curr);
      
      return *curr;
    }
    pointer operator->() const
    {
      return curr;
    }
    bool operator!() const
    {
      return curr==0;
    }
    
  protected:
    const_Traits_ptr traits;
    pointer curr;
  };

  /* *********************************************************************
     
  class In_face_iterator
  member of Trapezoidal_decomposition_2<Traits>
  Description Implements a Trapezoid iterator along a X_curve
     
  ********************************************************************* */
  
  class In_face_iterator : public Base_trapezoid_iterator
  {

#ifndef CGAL_CFG_USING_BASE_MEMBER_BUG_2
    using Base_trapezoid_iterator::curr;
    using Base_trapezoid_iterator::traits;
#endif

  protected:
    const X_curve& sep;

  public:
    In_face_iterator(const_Traits_ptr traits_,
                     const X_curve& sepc,pointer currt=0) :
      Base_trapezoid_iterator(traits_,currt),sep(sepc){}
    In_face_iterator(const In_face_iterator &it) :
      Base_trapezoid_iterator((Base_trapezoid_iterator&)it),sep(it.sep){}
	bool operator==(const In_face_iterator &it) const
	{
	  return ( Base_trapezoid_iterator::operator==(it) && 
               traits->equal_2_object()(sep,it.sep) );

	}
    
	/*
	  destription:
	  advances curr to one of the right neighbours according to the relation
	  between the seperating X_curve and the right() trapezoid point.
	  precoditions:
	  sep doesn't intersect no existing edges except possibly on common end
	  points.
	  postconditions:
	  if the rightest trapezoid was traversed curr is set to NULL.
	  remark:
	  if the seperator is vertical, using the precondition assumptions it
	  follows that
	  there is exactly one trapezoid to travel.
	*/
	In_face_iterator& operator++()
    {
      if (!curr) return *this;// end reached, do nothing!
      
#ifndef CGAL_TD_DEBUG
      
      CGAL_warning(traits);
      
#else
      
      CGAL_assertion(traits);
      
#endif
      
      Point right(curr->right());
      
#ifdef CGAL_TD_DEBUG
      
      CGAL_assertion(curr->is_active());
      CGAL_assertion(!traits->is_degenerate_point(*curr));
      
#endif
      if (!traits->is_degenerate(*curr))
      {
#ifndef NDEBUG
#ifndef CGAL_TD_DEBUG
		CGAL_warning_code(Data_structure* tt=curr->get_node();)
		  CGAL_warning(!tt->is_inner_node());
#else
		CGAL_assertion_code(Data_structure* tt=curr->get_node();)
		  CGAL_assertion(tt);
		CGAL_assertion(!tt->is_inner_node());
#endif
#endif
          
		// handle degeneracies
		if (!CGAL_POINT_IS_LEFT_LOW(curr->left(),
                              traits->construct_max_vertex_2_object()(sep)))
		  curr=0;
		else
        {
          switch(traits->compare_y_at_x_2_object()(right, sep))
          {
           case SMALLER:
			curr = curr->right_top_neighbour();
			break;
           case LARGER:
			curr = curr->right_bottom_neighbour();
			break;
           case EQUAL:
			// end reached
			curr=0;
			break;
           default:       
			curr=0;
			break;
          }
        }
      }
      else // pass along degenerate X_curve.
      {
#ifndef NDEBUG          
#ifndef CGAL_TD_DEBUG
          
		CGAL_warning_code(Data_structure* tt=curr->get_node();)
		  CGAL_warning(tt);
		CGAL_warning(tt->is_inner_node());
          
#else

		CGAL_assertion_code(Data_structure* tt=curr->get_node();)
		  CGAL_assertion(tt);
		CGAL_assertion(tt->is_inner_node());
#endif
#endif
          
		curr=curr->right_bottom_neighbour();
		if (curr)
        {
          while(traits->is_degenerate_point(*curr))
            curr=curr->get_node()->left().operator->();
              
#ifndef CGAL_TD_DEBUG
              
          CGAL_warning(traits->is_degenerate_curve(*curr));
              
#else
              
          CGAL_precondition(traits->is_degenerate_curve(*curr));
              
#endif
              
        }
      }
      return *this;
    }
    
	In_face_iterator operator++(int)
	{
	  In_face_iterator tmp = *this;
	  ++*this;
	  return tmp;
	}
	const X_curve& seperator()
    {
      return sep;
    }
  };
  
  /*
   * class Around_point_circulator
   * member of Trapezoidal_decomposition_2<Traits>
   * Description Implements a Trapezoid circulator around a point
   */
  class Around_point_circulator : public Base_trapezoid_circulator
  {

#ifndef CGAL_CFG_USING_BASE_MEMBER_BUG_2
    using Base_trapezoid_circulator::curr;
    using Base_trapezoid_circulator::traits;
#endif

  protected:
    const Point& fixed;
  public:
    
#ifndef CGAL_CFG_USING_BASE_MEMBER_BUG_2
    using Base_trapezoid_circulator::operator!;
#endif

    Around_point_circulator(const_Traits_ptr traits_, const Point & fixedp,
                            pointer currt) :
      Base_trapezoid_iterator(traits_,currt),fixed(fixedp) {};
    
    Around_point_circulator(const Around_point_circulator &it) :
      Base_trapezoid_iterator(it),fixed(it.fixed){};
    
	Around_point_circulator &operator++()
    {
      if (operator!()) return *this;
      
#ifndef CGAL_TD_DEBUG
      
      CGAL_warning((!curr->is_left_unbounded() &&
                    traits->equal_2_object()(fixed,curr->left())) ||
                   (!curr->is_right_unbounded() &&
                    traits->equal_2_object()(fixed,curr->right())));
      
#else
      
      CGAL_precondition((!curr->is_left_unbounded() &&
                         traits->equal_2_object()(fixed,curr->left())) ||
                        (!curr->is_right_unbounded() &&
                         traits->equal_2_object()(fixed,curr->right())));
      
#endif
      
      curr=operator->();
      return *this;
    }
	Around_point_circulator operator++(int)
	{
	  Around_point_circulator tmp = *this;
	  ++*this;
	  return tmp;
	}
	pointer operator[](int i) const
	{
	  Around_point_circulator c=*this;
	  while(i-->0) c++;
	  return c.curr;
	}
	/* returns reference to the next trapezoid
	   on a clockwise orientation rotation with centre
	   taken as the fixed point
	   preconditions:
	   ciruclator is not empty*/
	reference operator*() const
	{  
	  CGAL_precondition(!operator!());
	  return *operator->();
	}
	/* returns pointer to the next trapezoid
	   on a clockwise orientation rotation with centre
	   taken as the fixed point */
	pointer operator->() const
	{
	  pointer cand;
	  if (operator!()) return curr;
	  cand=is_right_rotation() ? 
	    curr->right_top_neighbour() : curr->left_bottom_neighbour();
	  if (traits->is_degenerate_curve(*cand)) return cand;
	  // cand was splited by a point
	  while(traits->is_degenerate_point(*cand))
	    cand=CGAL_POINT_IS_LEFT_LOW(cand->left(),fixed)?
	      // move right using data structure
	      cand->get_node()->right().operator->():
        // move left using data structure
        cand->get_node()->left().operator->();
	  return cand;
	}

	bool is_valid() const
	{
	  if ((!curr)||
	      (!curr->is_left_unbounded() &&
	       traits->equal_2_object()(fixed,curr->left())) ||
	      (!curr->is_right_unbounded() &&
	       traits->equal_2_object()(fixed,curr->right()))) {
	    return true;
	  }
	  else {
#ifdef CGAL_TD_DEBUG
	    std::cerr << "\nthis=";
	    write(std::cerr,*curr,*traits,false) << std::flush;
	    std::cerr << "\nfixed=" << fixed << std::flush;
	    CGAL_warning(!(curr && curr->is_left_unbounded() && curr->is_right_unbounded()));
#endif
	    return false;
	  }
	}
    
	/* description:
	   inserts the input trapezoid between the
	   current trapezoid and the next trapezoid
	   on a clockwise orientation rotation with
	   centre taken as the fixed point.
	   preconditions:
	   current trapezoid exist
	   input trapezoid is adjacent to fixed point
	*/
	void insert(reference tr)