text: /*
   * $Revision: 1.6 $
   *
   * last checkin:
   *   $Author: wong $
   *   $Date: 2009-05-19 01:16:40 +1000 (Tue, 19 May 2009) $
   ***************************************************************/
  
  /** \file
   * \brief Declaration of classes DPoint, DPolyline, DLine, DRect, DScaler.
   *
   * \author Joachim Kupke
   *
   * \par License:
   * This file is part of the Open Graph Drawing Framework (OGDF).
   * Copyright (C) 2005-2007
   *
   * \par
   * This program is free software; you can redistribute it and/or
   * modify it under the terms of the GNU General Public License
   * Version 2 or 3 as published by the Free Software Foundation
   * and appearing in the files LICENSE_GPL_v2.txt and
   * LICENSE_GPL_v3.txt included in the packaging of this file.
   *
   * \par
   * In addition, as a special exception, you have permission to link
   * this software with the libraries of the COIN-OR Osi project
   * (http://www.coin-or.org/projects/Osi.xml), all libraries required
   * by Osi, and all LP-solver libraries directly supported by the
   * COIN-OR Osi project, and distribute executables, as long as
   * you follow the requirements of the GNU General Public License
   * in regard to all of the software in the executable aside from these
   * third-party libraries.
   *
   * \par
   * This program is distributed in the hope that it will be useful,
   * but WITHOUT ANY WARRANTY; without even the implied warranty of
   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   * GNU General Public License for more details.
   *
   * \par
   * You should have received a copy of the GNU General Public
   * License along with this program; if not, write to the Free
   * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
   * Boston, MA 02110-1301, USA.
   *
   * \see  http://www.gnu.org/copyleft/gpl.html
   ***************************************************************/
  
  #ifdef _MSC_VER
  #pragma once
  #endif
  
  #ifndef OGDF_GEOMETRIC_H
  #define OGDF_GEOMETRIC_H
  
  #include <float.h> // for DBL_MAX
  #include <math.h>
  
  #include <ogdf/basic/List.h>
  #include <ogdf/basic/Hashing.h>
  
  #define GEOMETRIC_CMP_EPS  1e-06
  
  namespace ogdf {
  
  //! Determines the orientation in hierarchical layouts.
  enum Orientation {
  	topToBottom, //!< Edges are oriented from top to bottom.
  	bottomToTop, //!< Edges are oriented from bottom to top.
  	leftToRight, //!< Edges are oriented from left to right.
  	rightToLeft  //!< Edges are oriented from right to left.
  };
  
  
  
  // Important: be careful, if compared values are (+/-)DBL_MAX !!!
  inline
  bool DIsEqual(const double &a, const double &b, const double eps = GEOMETRIC_CMP_EPS)
  {
      return (a < (b + eps) && a > (b - eps));
  }
  
  inline
  bool DIsGreaterEqual(const double &a, const double &b, const double eps = GEOMETRIC_CMP_EPS)
  {
  	return (a > (b - eps));
  }
  
  inline
  bool DIsGreater(const double &a, const double &b, const double eps = GEOMETRIC_CMP_EPS)
  {
  	return (a > (b + eps));
  }
  
  inline
  bool DIsLessEqual(const double &a, const double &b, const double eps = GEOMETRIC_CMP_EPS)
  {
  	return (a < (b + eps));
  }
  
  inline
  bool DIsLess(const double &a, const double &b, const double eps = GEOMETRIC_CMP_EPS)
  {
  	return (a < (b - eps));
  }
  
  inline
  double DRound(const double &d, int prec = 0)
  {
      if (prec == 0)
          return floor(d + 0.5);
      double factor = pow(10.0, ((double) prec));
      return DRound(d * factor, 0) / factor;
  }
  
  /**
   * \brief Parameterized base class for points.
   *
   * This class serves as base class for two-dimensional points with specific
   * coordinate types like integer points (IPoint) and real points (DPoint).
   * The template parameter NUMBER is the type for the coordinates of the point
   * and has to support assignment and equality/inequality operators.
   */
  template <class NUMBER>
  class GenericPoint
  {
  public:
  	//! The type for coordinates of the point.
  	typedef NUMBER numberType;
  
  	NUMBER m_x; //!< The x-coordinate.
  	NUMBER m_y; //!< The y-coordinate.
  
  	//! Creates a generic point.
  	/**
  	 * \warning Does not assign something like zero to the coordinates,
  	 *          since we do not require that 0 can be casted to a NUMBER.
  	 */
  	GenericPoint() { }
  
  	//! Creates a generic point (\a x,\a y).
  	GenericPoint(NUMBER x, NUMBER y) : m_x(x), m_y(y) { }
  
  	//! Copy constructor.
  	GenericPoint(const GenericPoint &ip) : m_x(ip.m_x), m_y(ip.m_y) { }
  
  	//! Assignment operator.
  	GenericPoint operator=(const GenericPoint &ip) {
  		m_x = ip.m_x;
  		m_y = ip.m_y;
  		return *this;
  	}
  
  	//! Equality operator.
  	bool operator==(const GenericPoint &ip) const {
  		return m_x == ip.m_x && m_y == ip.m_y;
  	}
  
  	//! Inequality operator.
  	bool operator!=(const GenericPoint &ip) const {
  		return m_x != ip.m_x || m_y != ip.m_y;
  	}
  
  };//class GenericPoint
  
  
  /**
   * \brief Integer points.
   *
   * This class represent a two-dimensional point with integer coordinates.
   */
  class OGDF_EXPORT IPoint : public GenericPoint<int>
  {
  public:
  	//! Creates an integer point (0,0).
  	IPoint() : GenericPoint<int>(0,0) { }
  
  	//! Creates an integer point (\a x,\a y).
  	IPoint(int x, int y) : GenericPoint<int>(x,y) { }
  
  	//! Copy constructor.
  	IPoint(const IPoint &ip) : GenericPoint<int>(ip) { }
  
      //! Returns the euclidean distance between \a p and this point.
  	double distance(const IPoint &p) const;
  };//class IPoint
  
  
  //! Output operator for integer points.
  OGDF_EXPORT ostream &operator<<(ostream &os, const IPoint &ip);
  
  
  template<> class DefHashFunc<IPoint>
  {
  public:
  	int hash(const IPoint &ip) const {
  		return 7*ip.m_x + 23*ip.m_y;
  	}
  };
  
  
  /**
   * \brief Polylines with integer coordinates.
   *
   * This class represents integer polylines by a list of integer points.
   * Such polylines are, e.g., used in layouts for representing bend
   * point lists. Note that in this case, only the bend points are in the
   * list and neither the start nor the end point.
   */
  class OGDF_EXPORT IPolyline : public List<IPoint> {
  public:
  	//! Creates an empty integer polyline.
  	IPolyline() { }
  
  	//! Copy constructor.
  	IPolyline(const IPolyline &ipl) : List<IPoint>(ipl) { }
  
  	//! Assignment operator.
  	IPolyline &operator=(const IPolyline &ipl) {
  		List<IPoint>::operator =(ipl);
  		return *this;
  	}
  
      //! Returns the euclidean length of the polyline.
      double length() const;
  };
  
  
  
  /**
   * \brief Real points.
   *
   * This class represent a two-dimensional point with real coordinates.
   */
  class OGDF_EXPORT DPoint : public GenericPoint<double>
  {
  public:
  	//! Creates an real point (0,0).
  	DPoint() : GenericPoint<double>(0,0) { }
  
  	//! Creates an real point (\a x,\a y).
  	DPoint(double x, double y) : GenericPoint<double>(x,y) { }
  
  	//! Copy constructor.
  	DPoint(const DPoint &dp) : GenericPoint<double>(dp) { }
  
      //! Relaxed equality operator.
  	bool operator==(const DPoint &dp) const {
  		return DIsEqual(m_x, dp.m_x) && DIsEqual(m_y,dp.m_y);
  	}
  
      //! Addition of real points.
  	DPoint operator+(const DPoint &p) const;
  
  	//! Subtraction of real points.
  	DPoint operator-(const DPoint &p) const;
  
      //! Returns the euclidean distance between \a p and this point.
  	double distance(const DPoint &p) const;
  };
  
  //! Output operator for real points.
  OGDF_EXPORT ostream &operator<<(ostream &os, const DPoint &dp);
  
  
  /**
   * \brief Vectos with real coordinates.
   */
  class OGDF_EXPORT DVector : public DPoint {
  public:
  
  	//! Creates a vector (0,0).
  	DVector() : DPoint() { }
  
  	//! Creates a vector (\a x,\a y).
  	DVector(double x, double y) : DPoint(x, y) { }
  
  	//! Copy constructor.
  	DVector(const DVector &dv) : DPoint(dv) { }
  
  	//! Assignment operator.
      DVector operator=(const DPoint &ip) {
          if (this != &ip)
          {
              m_x = ip.m_x;
              m_y = ip.m_y;
          }
          return *this;
      }
  
      //! Multiplies all coordinates with \a val.
      DVector operator*(const double val) const;
  
      //! Divides all coordinates by \a val.
  	DVector operator/(const double val) const;
  
      //! Returns the length of the vector.
      double length() const;
  
      //! Returns the determinante of the vector.
      double operator^(const DVector &dv) const;
  
      //! Returns the scalar product of this vecor and \a dv.
      double operator*(const DVector &dv) const;
  
      /**
  	 * \brief Returns a vector that is orthogonal to this vector.
  	 *
  	 * Returns the vector \f$(y/x,1)\f$ if \f$x\neq 0\f$, or \f$(1,0)\f$
  	 * otherwise, where \f$(x,y)\f$ is this vector.
  	 */
      DVector operator++() const;
  
      /**
  	 * \brief Returns a vector that is orthogonal to this vector.
  	 *
  	 * Returns the vector \f$(-y/x,-1)\f$ if \f$x\neq 0\f$, or \f$(-1,0)\f$
  	 * otherwise, where \f$(x,y)\f$ is this vector.
  	 */
      DVector operator--() const;
  };
  
  
  
  /**
   * \brief Polylines with real coordinates.
   *
   * This class represents real polylines by a list of real points.
   * Such polylines are, e.g., used in layouts for representing bend
   * point lists.
   */
  class OGDF_EXPORT DPolyline : public List<DPoint> {
      static const double s_prec; //!< The conversion-precision.
  public:
  	//! Creates an empty integer polyline.
  	DPolyline() { }
  
  	//! Copy constructor.
  	DPolyline(const DPolyline &dpl) : List<DPoint>(dpl) { }
  
  	//! Assignment operator.
  	DPolyline &operator=(const DPolyline &dpl) {
  		List<DPoint>::operator =(dpl);
  		return *this;
  	}
  
      //! Returns the euclidean length of the polyline.
      double length() const;
  
      /**
  	 * \brief Returns a point on the polyline which is \a fraction * \a len
  	 *        away from the start point.
  	 *
  	 * @param fraction defines the fraction of \a lento be considered.
  	 * @param len is the given length, or the length of the polyline if \a len < 0.
  	 */
      DPoint position(const double fraction, double len = -1.0) const;
  
      //! Writes the polyline as graph in gml-format to file \a filename.
      void writeGML(const char* filename) const;
  
      //! Writes the polyline as graph in gml-format to output stream \a stream.
      void writeGML(ostream &stream) const;
  
      //! Deletes all successive points with equal coordinates.
      void unify();	
  
      //! Deletes all redundant points on the polyline that lie on a straight line given by their adajcent points.
  	void normalize();
  	
  	 //! Deletes all redundant points on the polyline that lie on a straight line given by their adajcent points.
  	void normalize(DPoint src, //start point of the edge
  					DPoint tgt); //end point of the edge
  
      //! Converts all coordinates rounded to \a s_prec decimal digits.
      void convertToInt();
  
      //void reConvertToDouble();
  };
  
  
  /**
   * \brief Lines with real coordinates.
   */
  class OGDF_EXPORT DLine {
  
  protected:
      DPoint m_start; //!< The start point of the line.
      DPoint m_end;   //!< The end point of the line.
  
  public:
  
      //! Creates an empty line.
      DLine() : m_start(), m_end() {}
  
  	//! Creates a line with start point \a p1 and end point \a p2.
      DLine(const DPoint &p1, const DPoint &p2) : m_start(p1), m_end(p2) {}
  
  	//! Copy constructor.
      DLine(const DLine &dl) : m_start(dl.m_start), m_end(dl.m_end) {}
  
  	//! Creates a line with start point (\a x1,\a y1) and end point (\a x2,\a y2).
      DLine(double x1, double y1, double x2, double y2) {
          m_start.m_x = x1; m_start.m_y = y1; m_end.m_x = x2; m_end.m_y = y2;
      }
  
      //! Equality operator.
      bool operator==(const DLine &dl) const {
          return m_start == dl.m_start && m_end == dl.m_end;
      }
  
  	//! Inequality operator.
      bool operator!=(const DLine &dl) const {
          return !(*this == dl);
      }
  
      //! Assignment operator.
      DLine &operator= (const DLine &dl) {
          if (this != &dl) { // don't assign myself
              m_start = dl.m_start;
              m_end   = dl.m_end;
          }
          return *this;
      }
  
      //! Returns the start point of the line.
      const DPoint &start() const { return m_start; }
  
  	//! Returns the end point of the line.
      const DPoint &end() const { return m_end; }
  
  	//! Returns the x-coordinate of the difference (end point - start point).
      double dx() const { return m_end.m_x - m_start.m_x; }
  
  	//! Returns the y-coordinate of the difference (end point - start point).
  	double dy() const { return m_end.m_y - m_start.m_y; }
  
  	//! Returns the slope of the line.
      double slope() const { return (dx() == 0) ? DBL_MAX : dy()/dx(); }
  
  	//! Returns the value y' such that (0,y') lies on the unlimited straight-line define dby this line.
      double yAbs() const { return (dx() == 0) ? DBL_MAX : m_start.m_y - (slope() * m_start.m_x); }
  
  	//! Returns true iff this line runs vertically.
      bool isVertical()   const { return (DIsEqual(dx(), 0.0)); }
  
  	//! Returns true iff this line runs horizontally.
      bool isHorizontal() const { return (DIsEqual(dy(), 0.0)); }
  
      /**
  	 * \brief Returns true iff \a line and this line intersect.
  	 *
  	 * @param line is the second line.
  	 * @param inter is assigned  the intersection point if true is returned.
  	 * @param endpoints determines if common endpoints are treated as intersection.
  	 */
      bool intersection(const DLine &line, DPoint &inter, bool endpoints = true) const;
  
      //! Returns true iff \a p lie on this line.
  	bool contains(const DPoint &p) const;
  
      //! Returns the length (euclidean distance between start and edn point) of this line.
      double length() const {
          return m_start.distance(m_end);
      }
  
  	/**
  	 * \brief Computes the intersection between this line and the horizontal line through y = \a horAxis.
  	 *
  	 * @param horAxis defines the horizontal line.
  	 * @param crossing is assigned the x-coordinate of the intersection point.
  	 *
  	 * \return the number of intersection points (0 = none, 1 = one, 2 = this
  	 *         line lies on the horizontal line through y = \a horAxis).
  	 */
      int horIntersection(const double horAxis, double &crossing) const;
  
  // gives the intersection with the vertical axis 'verAxis', returns the number of intersections
  // 0 = no, 1 = one, 2 = infinity or both end-points, e.g. parallel on this axis
  	/**
  	 * \brief Computes the intersection between this line and the vertical line through x = \a verAxis.
  	 *
  	 * @param verAxis defines the vertical line.
  	 * @param crossing is assigned the y-coordinate of the intersection point.
  	 *
  	 * \return the number of intersection points (0 = none, 1 = one, 2 = this
  	 *         line lies on the vertical line through x = \a verAxis).
  	 */
  	int verIntersection(const double verAxis, double &crossing) const;
  };
  
  //! Output operator for lines.
  ostream &operator<<(ostream &os, const DLine &dl);
  
  
  /**
   * \brief Rectangles with real coordinates.
   */
  class OGDF_EXPORT DRect {
  
  private:
      DPoint m_p1; //!< The lower left point of the rectangle.
      DPoint m_p2; //!< The upper right point of the rectangle.
  
  public:
      //! Creates a rectangle with lower left and upper right point (0,0).
      DRect() : m_p1(), m_p2() {}
  
  	//! Creates a rectangle with lower left point \a p1 and upper right point \a p2.
      DRect(const DPoint &p1, const DPoint &p2) : m_p1(p1), m_p2(p2)
          { normalize(); }
  
  	//! Creates a rectangle with lower left point (\a x1,\a y1) and upper right point (\a x1,\a y2).
      DRect(double x1, double y1, double x2, double y2) {
          m_p1.m_x = x1; m_p1.m_y = y1; m_p2.m_x = x2; m_p2.m_y = y2;
          normalize();
      }
  
  	//! Creates a rectangle defined by the end points of line \a dl.
      DRect(const DLine &dl) : m_p1(dl.start()), m_p2(dl.end())
          { normalize(); }
  
  	//! Copy constructor.
      DRect(const DRect &dr) : m_p1(dr.m_p1), m_p2(dr.m_p2)
          { normalize(); }
  
      //! Equality operator.
      bool operator==(const DRect &dr) const {
          return m_p1 == dr.m_p1 && m_p2 == dr.m_p2;
      }
  
  	//! Inequality operator.
      bool operator!=(const DRect &dr) const {
          return !(*this == dr);
      }
  
      //! Assignment operator.
      DRect &operator= (const DRect &dr) {
          if (this != &dr) { // don't assign myself
              m_p1 = dr.m_p1;
              m_p2 = dr.m_p2;
          }
          return *this;
      }
  
      //! Returns the width of the rectangle.
      double width() const {
          return m_p2.m_x - m_p1.m_x;
      }
  
  	//! Returns the height of the rectangle.
      double height() const {
          return m_p2.m_y - m_p1.m_y;
      }
  
      /**
  	 * \brief Normalizes the rectangle.
  	 *
  	 * Makes sure that the lower left point lies below and left of the upper
  	 * right point.
  	 */
      void normalize() {
          if (width() < 0)  std::swap(m_p2.m_x, m_p1.m_x);
          if (height() < 0) std::swap(m_p2.m_y, m_p1.m_y);
      }
  
      //! Returns the lower left point of the rectangle.
      const DPoint &p1() const { return m_p1; }
  
  	//! Returns the upper right point of the rectangle.
      const DPoint &p2() const { return m_p2; }
  
  	//! Returns the top side of the rectangle.
  	const DLine topLine() const {
  		return DLine( DPoint(m_p1.m_x, m_p2.m_y), DPoint(m_p2.m_x, m_p2.m_y));
  	}
  
  	//! Returns the right side of the rectangle.
      const DLine rightLine() const {
  		return DLine( DPoint(m_p2.m_x, m_p2.m_y), DPoint(m_p2.m_x, m_p1.m_y));
  	}
  
  	//! Returns the left side of the rectangle.
  	const DLine leftLine() const {
  		return DLine( DPoint(m_p1.m_x, m_p1.m_y), DPoint(m_p1.m_x, m_p2.m_y));
  	}
  
  	//! Returns the bottom side of the rectangle.
  	const DLine bottomLine() const {
  		return DLine( DPoint(m_p2.m_x, m_p1.m_y), DPoint(m_p1.m_x, m_p1.m_y));
  	}
  
      //! Swaps the y-coordinates of the two points.
      void yInvert() { std::swap(m_p1.m_y, m_p2.m_y); }
  
      //! Swaps the x-coordinates of the two points.
      void xInvert() { std::swap(m_p1.m_x, m_p2.m_x); }
  
      //! Returns true iff \a p lies within this rectangle.
      bool contains(const DPoint &p) const {
          if (DIsLess   (p.m_x, m_p1.m_x) ||
              DIsGreater(p.m_x, m_p2.m_x) ||
              DIsLess   (p.m_y, m_p1.m_y) ||
              DIsGreater(p.m_y, m_p2.m_y))
              return false;
          return true;
      }
  };
  
  //! Output operator for rectangles.
  OGDF_EXPORT ostream &operator<<(ostream &os, const DRect &dr);
  
  
  /**
   * \brief Scaling between coordinate systems.
   */
  class OGDF_EXPORT DScaler {
  
  private:
  
      const DRect *m_from; //!< Rectangluar area in source coordinate system.
      const DRect *m_to; //!< Rectangluar area in target coordinate system.
  
      double m_factorX; //!< The scaling factor for the x-coordinates.
      double m_factorY; //!< The scaling factor for the y-coordinates.
      double m_offsetX; //!< The offset for the x-coordinates.
      double m_offsetY; //!< The offset for the y-coordinates.
  
  public:
      //! Creates a scaler for scaling from area \a from to area \a to.
      DScaler(const DRect &from, const DRect &to) :
          m_from(&from),
          m_to(&to),
          m_factorX(to.width()/from.width()),
          m_factorY(to.height()/from.height()),
          m_offsetX(to.p1().m_x - from.p1().m_x * m_factorX),
          m_offsetY(to.p1().m_y - from.p1().m_y * m_factorY)
          {}
  
      ~DScaler() {}
  
      //! Returns the rectangle in the source coordinate system.
      const DRect &from() const { return *m_from; }
  
      //! Returns the rectangle in the target coordinate system.
  	const DRect &to()   const { return *m_to;   }
  
      //! Transforms x-coordinates from source to target coordinate system.
      double scaleToX(double x) { return x * m_factorX + m_offsetX; }
  
      //! Transforms y-coordinates from source to target coordinate system.
  	double scaleToY(double y) { return y * m_factorY + m_offsetY; }
  
      //! Scales a horizontal length from source to target coordinate system.
      double scaleWidth(double width)   { return width  * m_to->width() /m_from->width();  }
  
      //! Scales a vertical length from source to target coordinate system.
      double scaleHeight(double height) { return height * m_to->height()/m_from->height(); }
  };
  
  //! Output operator for scalers.
  OGDF_EXPORT ostream &operator<<(ostream &os, const DScaler &ds);
  
  
  /**
   * \brief Line segments with real coordinates.
   */
  class OGDF_EXPORT DSegment : public DLine {
  
  protected:
  
  public:
  
  	//! Creates an empty line segment.
      DSegment() : DLine() {}
  
  	//! Creates a line segment from \a p1 to \a p2.
      DSegment(const DPoint &p1, const DPoint &p2) : DLine(p1, p2) {}
  
  	//! Creates a line segment defined by the start and end point of line \a dl.
      DSegment(const DLine &dl) : DLine(dl) {}
  
  	//! Creates a line segment from (\a x1,\a y1) to (\a x2,\a y2).
  	DSegment(double x1, double y1, double x2, double y2) : DLine(x1, y1, x2, y2) {}
  
  	//! Copy constructor.
      DSegment(const DSegment &ds) : DLine(ds) {}
  
  
  	/**
  	 * \brief Determines if \a segment is left or right of this segment.
  	 *
  	 * \return a positve number if \a segment is left of this segment, and a
  	 *         a negative number if \a segment is right of this segment.
  	 */
  	double det(const DSegment &segment) const {
  		return (dx() * segment.dy() - dy() * segment.dx());
  	}
  };
  
  
  /**
   * \brief Polygons with real coordinates.
   */
  class OGDF_EXPORT DPolygon : public DPolyline {
  
  protected:
  
  	bool m_counterclock; //!< If true points are given in conter-clockwise order.
  
  public:
  	/**
  	 * \brief Creates an empty polygon.
  	 *
  	 * @param cc determines in which order the points will be given; true means
  	 *        counter-clockwise, false means clockwise.
  	 */
  	DPolygon(bool cc = true) : m_counterclock(cc) { }
  
  	//! Creates a polgon from a rectangle.
  	DPolygon(const DRect &rect, bool cc = true) : m_counterclock(cc) {
  		operator=(rect);
  	}
  
  	//! Copy constructor.
  	DPolygon(const DPolygon  &dop) : DPolyline(dop), m_counterclock(dop.m_counterclock) { }
  
  	//! Returns true iff points are given in counter-clockwise order.
      bool counterclock() { return m_counterclock; }
  
  	//! Assignment operator.
  	DPolygon &operator=(const DPolygon &dop) {
  		List<DPoint>::operator =(dop);
  		m_counterclock = dop.m_counterclock;
  		return *this;
  	}
  
  	//! Assignment operator (for assigning from a rectangle).
  	DPolygon &operator=(const DRect &rect);
  
  	//! Returns the line segment that starts at position \a it.
  	DSegment segment(ListConstIterator<DPoint> it) const;
  
  
      //! Inserts point \a p, that must lie on a polygon segment.
      ListIterator<DPoint> insertPoint(const DPoint &p) {
          return insertPoint(p, begin(), begin());
      }
  
      /**
  	 * \brief Inserts point \a p, but just searching from point \a p1 to \a p2.
  	 *
  	 * That is, from the segment starting at \a p1 to the segment ending at \a p2.
  	 */
      ListIterator<DPoint> insertPoint(const DPoint &p,
                                       ListIterator<DPoint> p1,
                                       ListIterator<DPoint> p2);
  
  	//! Inserts point p on every segment (a,b) with \a p in the open range ]a, b[.
      void insertCrossPoint(const DPoint &p);
  
  	//! Returns the list of intersection points of this polygon with \a p.
      int getCrossPoints(const DPolygon &p, List<DPoint> &crossPoints) const;
  
  	//! Deletes all consecutive points that are equal.
      void unify();
  
  	//! Deletes all points, which are not facets.
  	void normalize();
  
      //! Writes the polygon as graph in gml-format to file \a filename.
      void writeGML(const char* filename) const;
  
      //! Writes the polygon as graph in gml-format to output stream \a stream.
      void writeGML(ostream &stream)      const;
  
  	/**
  	 * \brief Checks wether a Point /a p is inside the Poylgon or not.
  	 * \note Polygons with crossings have inner areas that count as outside!
  	 * \par p the Point to check.
  	 * return true if Point is inside.
  	 */
  	bool containsPoint(DPoint &p) const;
  };
  
  //! Output operator for polygons.
  OGDF_EXPORT ostream &operator<<(ostream &os, const DPolygon &dop);
  
  
  
  } // end namespace ogdf
  
  #endif
  