geometry.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/EpsilonTest.h>
#include <ogdf/basic/Hashing.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/Math.h>
 
#include <cfloat>
 
namespace ogdf {
 
extern OGDF_EXPORT const EpsilonTest OGDF_GEOM_ET;
 
enum class Orientation {
    topToBottom, 
    bottomToTop, 
    leftToRight, 
    rightToLeft 
};
 
enum class IntersectionType {
    None, 
    SinglePoint, 
    Overlapping 
};
 
template<typename T>
class GenericPoint {
public:
    using numberType = T;
 
    T m_x; 
    T m_y; 
 
    explicit GenericPoint(T x = 0, T y = 0) : m_x(x), m_y(y) { }
 
    GenericPoint(const GenericPoint<T>& p) : m_x(p.m_x), m_y(p.m_y) { }
 
    GenericPoint<T>& operator=(const GenericPoint<T>& p) {
        if (this != &p) {
            m_x = p.m_x;
            m_y = p.m_y;
        }
        return *this;
    }
 
    bool operator==(const GenericPoint<T>& dp) const {
        // OGDF_GEOM_ET uses different methods for integers and floats
        return OGDF_GEOM_ET.equal(m_x, dp.m_x) && OGDF_GEOM_ET.equal(m_y, dp.m_y);
    }
 
    bool operator!=(const GenericPoint<T>& p) const { return !(*this == p); }
 
    bool operator<(const GenericPoint<T>& p) const {
        // OGDF_GEOM_ET uses different methods for integers and floats
        return OGDF_GEOM_ET.less(m_x, p.m_x)
                || (OGDF_GEOM_ET.equal(m_x, p.m_x) && OGDF_GEOM_ET.less(m_y, p.m_y));
    }
 
    bool operator>(const GenericPoint<T>& p) const { return p < *this; }
 
    GenericPoint<T> operator+(const GenericPoint<T>& p) const {
        return GenericPoint<T>(m_x + p.m_x, m_y + p.m_y);
    }
 
    GenericPoint<T> operator-(const GenericPoint<T>& p) const {
        return GenericPoint<T>(m_x - p.m_x, m_y - p.m_y);
    }
 
    double angle(GenericPoint<T> q, GenericPoint<T> r) const {
        const double dx1 = q.m_x - m_x, dy1 = q.m_y - m_y;
        const double dx2 = r.m_x - m_x, dy2 = r.m_y - m_y;
 
        // two vertices on the same place!
        if ((dx1 == 0 && dy1 == 0) || (dx2 == 0 && dy2 == 0)) {
            return 0.0;
        }
 
        double phi = std::atan2(dy2, dx2) - std::atan2(dy1, dx1);
        if (phi < 0) {
            phi += 2 * Math::pi;
        }
 
        return phi;
    }
 
    double angleDegrees(GenericPoint<T> q, GenericPoint<T> r) const {
        return Math::radiansToDegrees(angle(q, r));
    }
 
    double distance(const GenericPoint<T>& p) const {
        double dx = p.m_x - m_x;
        double dy = p.m_y - m_y;
        return sqrt(dx * dx + dy * dy);
    }
 
    double norm() const { return sqrt(m_x * m_x + m_y * m_y); }
 
    GenericPoint<T>& operator+=(const GenericPoint<T>& p) {
        m_x += p.m_x;
        m_y += p.m_y;
        return *this;
    }
 
    GenericPoint<T>& operator-=(const GenericPoint<T>& p) {
        m_x -= p.m_x;
        m_y -= p.m_y;
        return *this;
    }
 
    GenericPoint<T>& operator*=(T c) {
        m_x *= c;
        m_y *= c;
        return *this;
    }
 
    friend GenericPoint<T> operator*(T c, const GenericPoint<T>& p) {
        return GenericPoint<T>(c * p.m_x, c * p.m_y);
    }
 
    friend GenericPoint<T> operator*(const GenericPoint<T>& p, T c) {
        return GenericPoint<T>(c * p.m_x, c * p.m_y);
    }
 
    GenericPoint<T>& operator/=(T c) {
        m_x /= c;
        m_y /= c;
        return *this;
    }
 
    friend GenericPoint<T> operator/(const GenericPoint<T>& p, double c) {
        return GenericPoint<T>(p.m_x / c, p.m_y / c);
    }
 
    T determinant(const GenericPoint<T>& dv) const { return (m_x * dv.m_y) - (m_y * dv.m_x); }
 
    T operator*(const GenericPoint<T>& dv) const { return (m_x * dv.m_x) + (m_y * dv.m_y); }
 
    GenericPoint<T> orthogonal() const {
        GenericPoint<T> ret(1, 1);
        if (m_x != 0.0) {
            ret.m_x = -m_y / m_x;
        } else {
            ret.m_y = 0.0;
        }
        return ret;
    }
};
 
template<typename T>
std::ostream& operator<<(std::ostream& os, const GenericPoint<T>& p) {
    os << "(" << p.m_x << "," << p.m_y << ")";
    return os;
}
 
using IPoint = GenericPoint<int>;
 
using DPoint = GenericPoint<double>;
 
template<>
class DefHashFunc<IPoint> {
public:
    int hash(const IPoint& ip) const { return 7 * ip.m_x + 23 * ip.m_y; }
};
 
template<class PointType>
class GenericPolyline : public List<PointType> {
public:
    GenericPolyline() { }
 
    GenericPolyline(const List<PointType>& pl) : List<PointType>(pl) { }
 
    GenericPolyline(const GenericPolyline<PointType>& pl) : List<PointType>(pl) { }
 
    GenericPolyline<PointType>& operator=(const GenericPolyline& pl) {
        List<PointType>::operator=(pl);
        return *this;
    }
 
    double length() const {
        OGDF_ASSERT(!this->empty());
 
        double len = 0.0;
        ListConstIterator<PointType> pred, iter;
 
        pred = iter = this->begin();
        ++iter;
 
        while (iter.valid()) {
            len += (*iter).distance(*pred);
            ++pred;
            ++iter;
        }
 
        return len;
    }
 
    DPoint position(const double fraction, double len = -1.0) const {
        OGDF_ASSERT(!this->empty());
        OGDF_ASSERT(fraction >= 0.0);
        OGDF_ASSERT(fraction <= 1.0);
        if (len < 0.0) {
            len = length();
        }
        OGDF_ASSERT(len >= 0.0);
 
        DPoint p = *(this->begin());
        double liter = 0.0;
        double pos = len * fraction;
        double seglen = 0.0;
        ListConstIterator<PointType> pred, iter;
 
        pred = iter = this->begin();
        ++iter;
 
        // search the segment, which contains the desired point
        double DX = 0, DY = 0; // for further use
        while (iter.valid()) {
            DX = (*iter).m_x - (*pred).m_x;
            DY = (*iter).m_y - (*pred).m_y;
            seglen = sqrt(DX * DX + DY * DY);
            liter += seglen;
            if (liter >= pos) {
                break;
            }
            ++pred;
            ++iter;
        }
 
        if (!iter.valid()) { // position not inside the polyline, return last point!
            p = *(this->rbegin());
        } else {
            if (seglen == 0.0) { // *pred == *iter and pos is inbetween
                return *pred;
            }
 
            double segpos = seglen + pos - liter;
 
            double dx = DX * segpos / seglen;
            double dy = DY * segpos / seglen;
 
            p = *pred;
            p.m_x += dx;
            p.m_y += dy;
        }
 
        return p;
    }
 
    void unify() {
        if (this->empty()) {
            return;
        }
        ListIterator<PointType> iter, next;
        for (iter = next = this->begin(), ++next; next.valid() && (this->size() > 2); ++next) {
            if (*iter == *next) {
                this->del(next);
                next = iter;
            } else {
                iter = next;
            }
        }
    }
 
protected:
    void normalizeUnified(double minAngle) {
        OGDF_ASSERT(OGDF_GEOM_ET.geq(minAngle, 0.0));
        OGDF_ASSERT(OGDF_GEOM_ET.leq(minAngle, Math::pi));
 
        double maxAngle = 2 * Math::pi - minAngle;
        ListIterator<PointType> iter = this->begin();
        ListIterator<PointType> next, onext;
 
        while (iter.valid()) {
            next = iter;
            ++next;
            if (!next.valid()) {
                break;
            }
            onext = next;
            ++onext;
            if (!onext.valid()) {
                break;
            }
            double phi = (*next).angle(*iter, *onext);
 
            // Is *next on the way from *iter to *onext?
            if (OGDF_GEOM_ET.geq(phi, minAngle) && OGDF_GEOM_ET.leq(phi, maxAngle)) {
                this->del(next);
                if (iter != this->begin()) {
                    --iter;
                }
            } else {
                ++iter;
            }
        }
    }
 
public:
 
    void normalize(double minAngle = Math::pi) {
        unify();
        normalizeUnified(minAngle);
    }
 
    void normalize(PointType src, PointType tgt, double minAngle = Math::pi) {
        unify();
        this->pushFront(src);
        this->pushBack(tgt);
        normalize(minAngle);
        this->popFront();
        this->popBack();
    }
};
 
using IPolyline = GenericPolyline<IPoint>;
 
using DPolyline = GenericPolyline<DPoint>;
 
template<class PointType>
class GenericLine {
public:
    using numberType = typename PointType::numberType;
 
protected:
    PointType m_p1; 
    PointType m_p2; 
 
    numberType dx() const { return m_p2.m_x - m_p1.m_x; }
 
    numberType dy() const { return m_p2.m_y - m_p1.m_y; }
 
public:
    GenericLine() : m_p1(), m_p2() { }
 
    GenericLine(const PointType& p1, const PointType& p2) : m_p1(p1), m_p2(p2) { }
 
    GenericLine(const GenericLine<PointType>& dl) : m_p1(dl.m_p1), m_p2(dl.m_p2) { }
 
    GenericLine(numberType x1, numberType y1, numberType x2, numberType y2)
        : GenericLine(PointType(x1, y1), PointType(x2, y2)) { }
 
    bool operator==(const GenericLine<PointType>& dl) const {
        return isVertical() ? dl.isVertical() && m_p1.m_x == dl.m_p1.m_x
                            : slope() == dl.slope() && yAbs() == dl.yAbs();
    }
 
    bool operator!=(const GenericLine<PointType>& dl) const { return !(*this == dl); }
 
    GenericLine<PointType>& operator=(const GenericLine<PointType>& dl) {
        if (this != &dl) { // don't assign myself
            m_p1 = dl.m_p1;
            m_p2 = dl.m_p2;
        }
        return *this;
    }
 
    bool isVertical() const { return OGDF_GEOM_ET.equal(dx(), 0.0); }
 
    bool isHorizontal() const { return OGDF_GEOM_ET.equal(dy(), 0.0); }
 
    double slope() const { return isVertical() ? std::numeric_limits<double>::max() : dy() / dx(); }
 
    double yAbs() const {
        return isVertical() ? std::numeric_limits<double>::max() : m_p1.m_y - (slope() * m_p1.m_x);
    }
 
    double det(const GenericLine<PointType>& line) const {
        return dx() * line.dy() - dy() * line.dx();
    }
 
    IntersectionType intersection(const GenericLine<PointType>& line, DPoint& inter) const {
        if (isVertical() && line.isVertical()) {
            inter = m_p1;
            return OGDF_GEOM_ET.equal(m_p1.m_x, line.m_p1.m_x) ? IntersectionType::Overlapping
                                                               : IntersectionType::None;
        } else if (isVertical()) {
            inter = DPoint(m_p1.m_x, line.slope() * m_p1.m_x + line.yAbs());
            return IntersectionType::SinglePoint;
        } else if (line.isVertical()) {
            inter = DPoint(line.m_p1.m_x, slope() * line.m_p1.m_x + yAbs());
            return IntersectionType::SinglePoint;
        } else if (OGDF_GEOM_ET.equal(slope(), line.slope())) {
            // For parallel lines only return true if the lines are equal.
            inter = m_p1;
            return OGDF_GEOM_ET.equal(yAbs(), line.yAbs()) ? IntersectionType::Overlapping
                                                           : IntersectionType::None;
        } else {
            double ix = (line.yAbs() - yAbs()) / (slope() - line.slope());
            inter = DPoint(ix, slope() * ix + yAbs());
            return IntersectionType::SinglePoint;
        }
    }
 
    virtual bool contains(const DPoint& p) const {
        if (p == m_p1 || p == m_p2) {
            return true;
        }
 
        if (isVertical()) {
            return OGDF_GEOM_ET.equal(p.m_x, m_p1.m_x);
        }
 
        double dx2p = p.m_x - m_p1.m_x;
        double dy2p = p.m_y - m_p1.m_y;
 
        // dx() != 0.0 since this line is not vertical.
        if (dx2p == 0.0) {
            return false;
        }
 
        return OGDF_GEOM_ET.equal(slope(), (dy2p / dx2p));
    }
 
    virtual IntersectionType horIntersection(const double horAxis, double& crossing) const {
        if (isHorizontal()) {
            crossing = 0.0;
            return m_p1.m_y == horAxis ? IntersectionType::Overlapping : IntersectionType::None;
        }
        crossing = (m_p1.m_x * (m_p2.m_y - horAxis) - m_p2.m_x * (m_p1.m_y - horAxis)) / dy();
        return IntersectionType::SinglePoint;
    }
 
    virtual IntersectionType verIntersection(const double verAxis, double& crossing) const {
        if (isVertical()) {
            crossing = 0.0;
            return m_p1.m_x == verAxis ? IntersectionType::Overlapping : IntersectionType::None;
        }
        crossing = (m_p1.m_y * (m_p2.m_x - verAxis) - m_p2.m_y * (m_p1.m_x - verAxis)) / dx();
        return IntersectionType::SinglePoint;
    }
};
 
template<class PointType>
std::ostream& operator<<(std::ostream& os, const GenericLine<PointType>& line) {
    if (line.isVertical()) {
        os << "Line: vertical with x = " << line.m_p1.m_x;
    } else {
        os << "Line: f(x) = " << line.slope() << "x + " << line.yAbs();
    }
    return os;
}
 
using DLine = GenericLine<DPoint>;
 
template<class PointType>
class GenericSegment : public GenericLine<PointType> {
private:
 
    bool inBoundingRect(const PointType& p, bool includeBorders = true) const {
        double minx = min(this->m_p1.m_x, this->m_p2.m_x);
        double miny = min(this->m_p1.m_y, this->m_p2.m_y);
        double maxx = max(this->m_p1.m_x, this->m_p2.m_x);
        double maxy = max(this->m_p1.m_y, this->m_p2.m_y);
 
        if (includeBorders) {
            return OGDF_GEOM_ET.geq(p.m_x, minx) && OGDF_GEOM_ET.leq(p.m_x, maxx)
                    && OGDF_GEOM_ET.geq(p.m_y, miny) && OGDF_GEOM_ET.leq(p.m_y, maxy);
        } else {
            return OGDF_GEOM_ET.greater(p.m_x, minx) && OGDF_GEOM_ET.less(p.m_x, maxx)
                    && OGDF_GEOM_ET.greater(p.m_y, miny) && OGDF_GEOM_ET.less(p.m_y, maxy);
        }
    }
 
public:
    GenericSegment() : GenericLine<PointType>() { }
 
    GenericSegment(const PointType& p1, const PointType& p2) : GenericLine<PointType>(p1, p2) { }
 
    explicit GenericSegment(const GenericLine<PointType>& dl) : GenericLine<PointType>(dl) { }
 
    GenericSegment(double x1, double y1, double x2, double y2)
        : GenericLine<PointType>(x1, y1, x2, y2) { }
 
    GenericSegment(const GenericSegment<PointType>& ds) = default;
 
    GenericSegment& operator=(const GenericSegment<PointType>& ds) = default;
 
    bool operator==(const GenericSegment<PointType>& dl) const {
        return this->m_p1 == dl.m_p1 && this->m_p2 == dl.m_p2;
    }
 
    bool operator!=(const GenericSegment<PointType>& dl) const { return !(*this == dl); }
 
    const PointType& start() const { return this->m_p1; }
 
    const PointType& end() const { return this->m_p2; }
 
    typename GenericLine<PointType>::numberType dx() const { return GenericLine<PointType>::dx(); }
 
    typename GenericLine<PointType>::numberType dy() const { return GenericLine<PointType>::dy(); }
 
    IntersectionType intersection(const GenericSegment<PointType>& segment, PointType& inter,
            bool endpoints = true) const {
        IntersectionType lineIntersection = GenericLine<PointType>::intersection(segment, inter);
 
        if (lineIntersection == IntersectionType::None) {
            return IntersectionType::None;
        } else if (lineIntersection == IntersectionType::SinglePoint) {
            return inBoundingRect(inter, endpoints) && segment.inBoundingRect(inter, endpoints)
                    ? IntersectionType::SinglePoint
                    : IntersectionType::None;
        } else {
            // Let inter be the second smallest point of this/the given segment.
            Array<DPoint> points({this->m_p1, this->m_p2, segment.m_p1, segment.m_p2});
            std::sort(points.begin(), points.end(), [](DPoint p1, DPoint p2) { return p1 < p2; });
            inter = points[1];
 
            if (!inBoundingRect(inter, endpoints) || !segment.inBoundingRect(inter, endpoints)) {
                return IntersectionType::None;
            } else if (points[1] == points[2] && !(this->m_p1 == inter && this->m_p2 == inter)
                    && !(segment.m_p1 == inter && segment.m_p2 == inter)) {
                // There is an intersection at a single point inter, which is
                // both an endpoint of this and an endpoint of the other segment.
                return IntersectionType::SinglePoint;
            } else {
                return IntersectionType::Overlapping;
            }
        }
    }
 
    bool contains(const PointType& p) const override {
        return GenericLine<PointType>::contains(p) && inBoundingRect(p);
    }
 
    double length() const { return this->m_p1.distance(this->m_p2); }
 
    IntersectionType horIntersection(const double horAxis, double& crossing) const override {
        IntersectionType result = GenericLine<PointType>::horIntersection(horAxis, crossing);
        if (result != IntersectionType::SinglePoint) {
            return result;
        } else if (inBoundingRect(DPoint(crossing, horAxis))) {
            return IntersectionType::SinglePoint;
        } else {
            crossing = 0.0;
            return IntersectionType::None;
        }
    }
 
    IntersectionType verIntersection(const double verAxis, double& crossing) const override {
        IntersectionType result = GenericLine<PointType>::verIntersection(verAxis, crossing);
        if (result != IntersectionType::SinglePoint) {
            return result;
        } else if (inBoundingRect(DPoint(verAxis, crossing))) {
            return IntersectionType::SinglePoint;
        } else {
            crossing = 0.0;
            return IntersectionType::None;
        }
    }
};
 
template<class PointType>
std::ostream& operator<<(std::ostream& os, const GenericSegment<PointType>& dl) {
    os << "Segment-Start: " << dl.start() << ", Segment-End: " << dl.end();
    return os;
}
 
using DSegment = GenericSegment<DPoint>;
 
class OGDF_EXPORT DRect {
    friend OGDF_EXPORT std::ostream& operator<<(std::ostream& os, const DRect& dr);
 
protected:
    DPoint m_p1; 
    DPoint m_p2; 
 
public:
    DRect() = default;
 
    DRect(const DPoint& p1, const DPoint& p2) : m_p1(p1), m_p2(p2) { normalize(); }
 
    DRect(const DRect& dr) : m_p1(dr.m_p1), m_p2(dr.m_p2) { }
 
    DRect(double x1, double y1, double x2, double y2) : DRect(DPoint(x1, y1), DPoint(x2, y2)) { }
 
    explicit DRect(const DSegment& dl) : DRect(dl.start(), dl.end()) { }
 
    virtual ~DRect() = default;
 
    bool operator==(const DRect& dr) const { return m_p1 == dr.m_p1 && m_p2 == dr.m_p2; }
 
    bool operator!=(const DRect& dr) const { return !(*this == dr); }
 
    DRect& operator=(const DRect& dr) {
        if (this != &dr) { // don't assign myself
            m_p1 = dr.m_p1;
            m_p2 = dr.m_p2;
        }
        return *this;
    }
 
    double width() const { return m_p2.m_x - m_p1.m_x; }
 
    double height() const { return m_p2.m_y - m_p1.m_y; }
 
    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);
        }
    }
 
    const DPoint& p1() const { return m_p1; }
 
    const DPoint& p2() const { return m_p2; }
 
    const DSegment top() const {
        return DSegment(DPoint(m_p1.m_x, m_p2.m_y), DPoint(m_p2.m_x, m_p2.m_y));
    }
 
    const DSegment right() const {
        return DSegment(DPoint(m_p2.m_x, m_p2.m_y), DPoint(m_p2.m_x, m_p1.m_y));
    }
 
    const DSegment left() const {
        return DSegment(DPoint(m_p1.m_x, m_p1.m_y), DPoint(m_p1.m_x, m_p2.m_y));
    }
 
    const DSegment bottom() const {
        return DSegment(DPoint(m_p2.m_x, m_p1.m_y), DPoint(m_p1.m_x, m_p1.m_y));
    }
 
    void yInvert() { std::swap(m_p1.m_y, m_p2.m_y); }
 
    void xInvert() { std::swap(m_p1.m_x, m_p2.m_x); }
 
    bool contains(const DPoint& p) const {
        return OGDF_GEOM_ET.geq(p.m_x, m_p1.m_x) && OGDF_GEOM_ET.leq(p.m_x, m_p2.m_x)
                && OGDF_GEOM_ET.geq(p.m_y, m_p1.m_y) && OGDF_GEOM_ET.leq(p.m_y, m_p2.m_y);
    }
 
    bool intersection(const DSegment& segment) const {
        DPoint inter;
        return segment.intersection(top(), inter) != IntersectionType::None
                || segment.intersection(bottom(), inter) != IntersectionType::None
                || segment.intersection(right(), inter) != IntersectionType::None
                || segment.intersection(left(), inter) != IntersectionType::None;
    }
 
protected:
    double parallelDist(const DSegment& d1, const DSegment& d2) const;
 
    double pointDist(const DPoint& p1, const DPoint& p2) const {
        return sqrt((p1.m_y - p2.m_y) * (p1.m_y - p2.m_y) + (p1.m_x - p2.m_x) * (p1.m_x - p2.m_x));
    }
};
 
class OGDF_EXPORT DIntersectableRect : public DRect {
    friend OGDF_EXPORT std::ostream& operator<<(std::ostream& os, const DIntersectableRect& dr);
 
    double m_area = 0.0;
    DPoint m_center;
 
    void initAreaAndCenter();
 
public:
    DIntersectableRect() = default;
 
    DIntersectableRect(const DPoint& p1, const DPoint& p2) : DRect(p1, p2) { initAreaAndCenter(); }
 
    DIntersectableRect(double x1, double y1, double x2, double y2)
        : DIntersectableRect(DPoint(x1, y1), DPoint(x2, y2)) { }
 
    DIntersectableRect(const DIntersectableRect& dr)
        : DRect(static_cast<DRect>(dr)), m_area(dr.m_area), m_center(dr.m_center) { }
 
    DIntersectableRect(const DPoint& center, double width, double height)
        : DIntersectableRect(DPoint(center.m_x - width / 2, center.m_y - height / 2),
                DPoint(center.m_x + width / 2, center.m_y + height / 2)) {};
 
    DIntersectableRect& operator=(const DIntersectableRect& dr) {
        if (this != &dr) { // don't assign myself
            m_p1 = dr.m_p1;
            m_p2 = dr.m_p2;
            m_center = dr.m_center;
            m_area = dr.m_area;
        }
        return *this;
    }
 
    DPoint center() const { return m_center; }
 
    double area() const { return m_area; }
 
    bool intersects(const DIntersectableRect& rectangle) const;
 
    DIntersectableRect intersection(const DIntersectableRect& other) const;
 
    double distance(const DIntersectableRect& other) const;
 
    void move(const DPoint& point);
};
 
class OGDF_EXPORT DPolygon : public DPolyline {
protected:
    bool m_counterclock; 
 
public:
    DPolygon(bool cc = true) : m_counterclock(cc) { }
 
    explicit DPolygon(const DRect& rect, bool cc = true) : m_counterclock(cc) { operator=(rect); }
 
    DPolygon(const DPolygon& dop) : DPolyline(dop), m_counterclock(dop.m_counterclock) { }
 
    bool counterclock() { return m_counterclock; }
 
    DPolygon& operator=(const DPolygon& dop) {
        List<DPoint>::operator=(dop);
        m_counterclock = dop.m_counterclock;
        return *this;
    }
 
    DPolygon& operator=(const DRect& rect);
 
    DSegment segment(ListConstIterator<DPoint> it) const;
 
    ListIterator<DPoint> insertPoint(const DPoint& p) { return insertPoint(p, begin(), begin()); }
 
    ListIterator<DPoint> insertPoint(const DPoint& p, ListIterator<DPoint> p1,
            ListIterator<DPoint> p2);
 
    void insertCrossPoint(const DPoint& p);
 
    int getCrossPoints(const DPolygon& p, List<DPoint>& crossPoints) const;
 
    void unify();
 
    void normalize();
 
    bool containsPoint(DPoint& p) const;
};
 
OGDF_EXPORT std::ostream& operator<<(std::ostream& os, const DPolygon& dop);
 
int orientation(const DPoint& p, const DPoint& q, const DPoint& r);
 
inline int orientation(const DSegment& s, const DPoint& p) {
    return orientation(s.start(), s.end(), p);
}
 
}