td_x_trapezoid.h

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

       and the input trapezoids
    */
    CGAL_TD_INLINE void merge_trapezoid(X_trapezoid& right)
    {
      CGAL_assertion(!is_right_unbounded());

      bool right_unbounded = right.is_right_unbounded();
      *this=X_trapezoid (!is_left_unbounded() ? &left() : 0,
			 !right_unbounded ? &right.right() : 0,
			 !is_bottom_unbounded() ? &bottom() : 0,
			 !is_top_unbounded() ? &top() : 0,
			 left_bottom_neighbour(),left_top_neighbour(),
			 right.right_bottom_neighbour(),
			 right.right_top_neighbour());

      if (right_bottom_neighbour())
	right_bottom_neighbour()->set_lb(this);
    
      if (right_top_neighbour())
	right_top_neighbour()->set_lt(this);

      CGAL_assertion(is_right_unbounded()==right.is_right_unbounded());
    }
	
#ifdef CGAL_TD_DEBUG
    bool is_valid(const Traits* traits) const
    {
      Comparison_result t;
      bool              b;

      if (is_active())
	{
	  if (get_node() && **get_node()!=*this)
	    {
	      std::cerr << "\nthis=";
	      write(std::cerr,*this,*traits,false);
	      std::cerr << "\nget_node= ";
	      write(std::cerr,**get_node(),*traits,false) << std::flush;
	      CGAL_warning(**get_node()==*this);
	      return false;
	    }
	  if (!is_left_unbounded() && !is_right_unbounded() &&
	      CGAL_POINT_IS_LEFT_LOW(right(),left()))
	    {
	      std::cerr << "\nthis=";
	      write(std::cerr,*this,*traits,false) << std::flush;
	      CGAL_warning(!CGAL_POINT_IS_LEFT_LOW(right(),left()));
	      return false;
	    }
			
	  if (!is_bottom_unbounded())
	    {
	      if (is_left_unbounded() || is_right_unbounded())
		{
		  std::cerr << "\nthis=";
		  write(std::cerr,*this,*traits,false) << std::flush;
		  CGAL_warning(!(is_left_unbounded() ||is_right_unbounded()));
		  return false;
		}

	      b = CGAL_IS_IN_X_RANGE(bottom(),left());
	      if (b) {
		t = CGAL_CURVE_COMPARE_Y_AT_X(left(), bottom());
	      }
	      if (!b || t == SMALLER)
		{
		  std::cerr << "\nthis=";
		  write(std::cerr,*this,*traits,false) << std::flush;
		  std::cerr << "\nt==" << t << std::flush;
		  CGAL_warning(b);
		  CGAL_warning(t != SMALLER);
		  return false;
		}

	      b=CGAL_IS_IN_X_RANGE(bottom(),right());
	      if (b) {
		t = CGAL_CURVE_COMPARE_Y_AT_X(right(), bottom());
	      }
	      if (!b || t == SMALLER)
		{
		  std::cerr << "\nthis=";
		  write(std::cerr,*this,*traits,false) << std::flush;
		  std::cerr << "\nt==" << t << std::flush;
		  CGAL_warning(b);
		  CGAL_warning(t != SMALLER);
		  return false;
		}
	    }
	  if (!is_top_unbounded())
	    {
	      if (is_left_unbounded() || is_right_unbounded())
		{
		  std::cerr << "\nthis=";
		  write(std::cerr,*this,*traits,false) << std::flush;
		  CGAL_warning(!(is_left_unbounded() || is_right_unbounded()));
		  return false;
		}

	      b=CGAL_IS_IN_X_RANGE(top(),left());
	      if (b) {
		t = CGAL_CURVE_COMPARE_Y_AT_X(left(), top());
	      }
	      if (!b || t == LARGER)
		{
		  std::cerr << "\nthis=";
		  write(std::cerr,*this,*traits,false) << std::flush;
		  std::cerr << "\nt==" << t << std::flush;
		  CGAL_warning(b);
		  CGAL_warning(t != LARGER);
		  return false;
		}

	      b=CGAL_IS_IN_X_RANGE(top(),right());
	      if (b) {
		t = CGAL_CURVE_COMPARE_Y_AT_X(right(), top());
	      }
	      if (!b || t == LARGER)
		{
		  std::cerr << "\nthis=";
		  write(std::cerr,*this,*traits,false) << std::flush;
		  std::cerr << "\nt==" << t << std::flush;
		  CGAL_warning(b);
		  CGAL_warning(t != LARGER);
		  return false;
		}
	    }
	  if (!traits->is_degenerate(*this))
	    {
	      if (right_top_neighbour() && 
		  (! is_top_curve_equal(*right_top_neighbour(), traits)) ||
		  left_top_neighbour() && 
		  (! is_top_curve_equal(*left_top_neighbour(), traits)) ||
		  right_bottom_neighbour() &&
		  (! is_bottom_curve_equal(*right_bottom_neighbour(), traits)) ||
		  left_bottom_neighbour() &&
		  (! is_bottom_curve_equal(*left_bottom_neighbour(), traits)) ||
		  right_top_neighbour() &&
		  traits->is_degenerate(*right_top_neighbour()) ||
		  left_top_neighbour() &&
		  traits->is_degenerate(*left_top_neighbour()) ||
		  right_bottom_neighbour() &&
		  traits->is_degenerate(*right_bottom_neighbour()) ||
		  left_bottom_neighbour() &&
		  traits->is_degenerate(*left_bottom_neighbour()))
		{
		  std::cerr << "\nthis=";
		  write(std::cerr,*this,*traits,false) << std::flush;
		  CGAL_warning(!(right_top_neighbour() &&
				 (! is_top_curve_equal(*right_top_neighbour(), traits))));
		  CGAL_warning(!(left_top_neighbour() &&
				 (! is_top_curve_equal(*left_top_neighbour(), traits))));
		  CGAL_warning(!(right_bottom_neighbour() &&
				 (! is_bottom_curve_equal(*right_bottom_neighbour(), traits))));
		  CGAL_warning(!(left_bottom_neighbour() &&
				 (! is_bottom_curve_equal(*left_bottom_neighbour(), traits))));
		  CGAL_warning(!(right_top_neighbour() &&
				 traits->is_degenerate(*right_top_neighbour())));
		  CGAL_warning(!(left_top_neighbour() &&
				 traits->is_degenerate(*left_top_neighbour())));
		  CGAL_warning(!(right_bottom_neighbour() &&
				 traits->is_degenerate(*right_bottom_neighbour())));
		  CGAL_warning(!(left_bottom_neighbour() &&
				 traits->is_degenerate(*left_bottom_neighbour())));
		  return false;
		}
	      if (right_top_neighbour()&&!right_top_neighbour()->is_active()||
		  left_top_neighbour()&&!left_top_neighbour()->is_active()||
		  right_bottom_neighbour()&&!right_bottom_neighbour()->is_active()||
		  left_bottom_neighbour()&&!left_bottom_neighbour()->is_active())
		{
		  std::cerr << "\nleft=" << left() << " right=" << right()
			    << " bottom=" << bottom() << " top=" << top()
			    << std::flush;
		  CGAL_warning(!(right_top_neighbour() &&
				 !right_top_neighbour()->is_active()));
		  CGAL_warning(!(left_top_neighbour() &&
				 !left_top_neighbour()->is_active()));
		  CGAL_warning(!(right_bottom_neighbour() &&
				 !right_bottom_neighbour()->is_active()));
		  CGAL_warning(!(left_bottom_neighbour() &&
				 !left_bottom_neighbour()->is_active()));
		  return false;
		}
	    }
	  else
	    {
	      /* if the trapezoid is degenerate, the left() and right()
		 points should be on the top() and bottom() curves.
		 In any case none of the geometric boundaries should 
		 be unbounded */
	      if (is_bottom_unbounded()||
		  is_top_unbounded()||
		  is_left_unbounded()||
		  is_right_unbounded()
		  )
		{
		  std::cerr << "\nbottom()==" << bottom() << std::flush;
		  std::cerr << "\ntop()==" << top() << std::flush;
		  std::cerr << "\nleft()==" << left() << std::flush;
		  std::cerr << "\nright()==" << right() << std::flush;
		  CGAL_warning((!is_bottom_unbounded()));
		  CGAL_warning((!is_top_unbounded()));
		  CGAL_warning((!is_left_unbounded()));
		  CGAL_warning((!is_right_unbounded()));
		  return false;
		}
	      if (!CGAL_IS_IN_X_RANGE(bottom(),left()) ||
		  CGAL_CURVE_COMPARE_Y_AT_X(left(), bottom()) != EQUAL)
		{
		  std::cerr << "\nbottom()==" << bottom() << std::flush;
		  std::cerr << "\nleft()==" << left() << std::flush;
		  CGAL_warning(CGAL_IS_IN_X_RANGE(bottom(),left()) &&
			       CGAL_CURVE_COMPARE_Y_AT_X(left(), bottom()) ==
			       EQUAL);
		  return false;
		}
	      if (!CGAL_IS_IN_X_RANGE(bottom(),right()) ||
		  CGAL_CURVE_COMPARE_Y_AT_X(right(), bottom()) != EQUAL)
		{
		  std::cerr << "\nbottom()==" << bottom() << std::flush;
		  std::cerr << "\nright()==" << right() << std::flush;
		  CGAL_warning(CGAL_IS_IN_X_RANGE(bottom(),right()) &&
			       CGAL_CURVE_COMPARE_Y_AT_X(right(), bottom()) ==
			       EQUAL);
		  return false;
		}
	      if (!CGAL_IS_IN_X_RANGE(top(),left()) ||
		  CGAL_CURVE_COMPARE_Y_AT_X(left(), top()) != EQUAL)
		{
		  std::cerr << "\ntop()==" << top() << std::flush;
		  std::cerr << "\nleft()==" << left() << std::flush;
		  CGAL_warning(!CGAL_IS_IN_X_RANGE(top(),left()) &&
			       CGAL_CURVE_COMPARE_Y_AT_X(left(), top()) == EQUAL);
		  return false;
		}
	      if (!CGAL_IS_IN_X_RANGE(top(),right()) ||
		  CGAL_CURVE_COMPARE_Y_AT_X(right(), top()) != EQUAL)
		{
		  std::cerr << "\ntop()==" << top() << std::flush;
		  std::cerr << "\nright()==" << right() << std::flush;
		  CGAL_warning(CGAL_IS_IN_X_RANGE(top(),right()) &&
			       CGAL_CURVE_COMPARE_Y_AT_X(right(), top()) == EQUAL);
		  return false;
		}
	      if (traits->is_degenerate_curve(*this))
		{
		  if (right_top_neighbour()&&!right_top_neighbour()->is_active()||
		      //!left_top_neighbour()||!left_top_neighbour()->is_active()||
		      right_bottom_neighbour() &&
		      !right_bottom_neighbour()->is_active()||
		      left_bottom_neighbour() && !left_bottom_neighbour()->is_active()
		      )
		    {
		      CGAL_warning(!right_top_neighbour() ||
				   right_top_neighbour()->is_active());
		      //CGAL_warning(!left_top_neighbour() ||
		      //left_top_neighbour()->is_active());
		      CGAL_warning(!right_bottom_neighbour() ||
				   right_bottom_neighbour()->is_active());
		      CGAL_warning(!left_bottom_neighbour() ||
				   left_bottom_neighbour()->is_active());
		      return false;
		    }
		  if (
		      /* if trapezoid is end relative to supporting X_curve, that is
			 adjacent(trapezoid's right end point,supporting X_curve right
			 end point) , right_top_neighbour() returns next such trapezoid
			 around right() point in clockwise oriented order
			 adjacent(trapezoid's left end point,supporting X_curve left end
			 point), left_bottom_neighbour() returns next such trapezoid
			 around left() point in clockwise oriented order */
		      /* right_bottom_neighbour() points to next trapezoid on
			 supporting X_curve, if such exist */
		      right_top_neighbour() &&
		      !traits->is_degenerate_curve(*right_top_neighbour())||
		      // !left_top_neighbour() ||
		      // !traits->is_degenerate_curve(*left_top_neighbour())||
		      right_bottom_neighbour() &&
		      !traits->is_degenerate_curve(*right_bottom_neighbour())||
		      left_bottom_neighbour() &&
		      !traits->is_degenerate_curve(*left_bottom_neighbour())
		      )
		    {
		      CGAL_warning(!right_top_neighbour() ||
				   traits->is_degenerate_curve(*right_top_neighbour()));
		      //CGAL_warning(!left_top_neighbour() ||
		      //!traits->is_degenerate_curve(*left_top_neighbour()));
		      CGAL_warning(!right_bottom_neighbour() ||
				   traits->
				   is_degenerate_curve(*right_bottom_neighbour()));
		      CGAL_warning(!left_bottom_neighbour() ||
				   traits->
				   is_degenerate_curve(*left_bottom_neighbour()));
		      return false;
		    }
		}
	      else if (traits->is_degenerate_point(*this))
		{
		  if (right_top_neighbour() &&
		      !traits->is_degenerate_curve(*right_top_neighbour())||
		      left_bottom_neighbour() &&
		      !traits->is_degenerate_curve(*left_bottom_neighbour())
		      )
		    {
		      CGAL_warning(!right_top_neighbour() ||
				   traits->is_degenerate_curve(*right_top_neighbour()));
		      CGAL_warning(!left_bottom_neighbour() ||
				   traits->
				   is_degenerate_curve(*left_bottom_neighbour()));
		      return false;
		    }
		  if (right_top_neighbour()&&!right_top_neighbour()->is_active()||
		      left_bottom_neighbour()&&!left_bottom_neighbour()->is_active()
		      )
		    {
		      CGAL_warning(!right_top_neighbour() ||
				   right_top_neighbour()->is_active());
		      CGAL_warning(!left_bottom_neighbour() ||
				   left_bottom_neighbour()->is_active());
		      return false;
		    }
		  if (!traits->equal_2_object()(left(),right()))
		    {
		      std::cerr << "\nleft()==" << left() << std::flush;
		      std::cerr << "\nright()==" << right() << std::flush;
		      CGAL_warning(traits->equal_2_object()(left(),right()));
		      return false;
		    }
		}
	    }
	}
      return true;
    }

    CGAL_TD_INLINE void debug() const // instantiate ptr functions.
    {
      ptr();
      bottom();
      top();
      left();
      right();
    }
#endif

};

CGAL_END_NAMESPACE

#endif