geometry.h

Go to the documentation of this file.

/*
 * $Revision: 2027 $
 *
 * last checkin:
 *   $Author: gutwenger $
 *   $Date: 2010-09-01 11:55:17 +0200 (Wed, 01 Sep 2010) $
 ***************************************************************/

#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 {

enum Orientation {
    topToBottom, 
    bottomToTop, 
    leftToRight, 
    rightToLeft  
};



// 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;
}

template <class NUMBER>
class GenericPoint
{
public:
    typedef NUMBER numberType;

    NUMBER m_x; 
    NUMBER m_y; 


    GenericPoint() { }

    GenericPoint(NUMBER x, NUMBER y) : m_x(x), m_y(y) { }

    GenericPoint(const GenericPoint &ip) : m_x(ip.m_x), m_y(ip.m_y) { }

    GenericPoint operator=(const GenericPoint &ip) {
        m_x = ip.m_x;
        m_y = ip.m_y;
        return *this;
    }

    bool operator==(const GenericPoint &ip) const {
        return m_x == ip.m_x && m_y == ip.m_y;
    }

    bool operator!=(const GenericPoint &ip) const {
        return m_x != ip.m_x || m_y != ip.m_y;
    }

};//class GenericPoint


class OGDF_EXPORT IPoint : public GenericPoint<int>
{
public:
    IPoint() : GenericPoint<int>(0,0) { }

    IPoint(int x, int y) : GenericPoint<int>(x,y) { }

    IPoint(const IPoint &ip) : GenericPoint<int>(ip) { }

    double distance(const IPoint &p) const;
};//class IPoint


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;
    }
};


class OGDF_EXPORT IPolyline : public List<IPoint> {
public:
    IPolyline() { }

    IPolyline(const IPolyline &ipl) : List<IPoint>(ipl) { }

    IPolyline &operator=(const IPolyline &ipl) {
        List<IPoint>::operator =(ipl);
        return *this;
    }

    double length() const;
};



class OGDF_EXPORT DPoint : public GenericPoint<double>
{
public:
    DPoint() : GenericPoint<double>(0,0) { }

    DPoint(double x, double y) : GenericPoint<double>(x,y) { }

    DPoint(const DPoint &dp) : GenericPoint<double>(dp) { }

    bool operator==(const DPoint &dp) const {
        return DIsEqual(m_x, dp.m_x) && DIsEqual(m_y,dp.m_y);
    }

    DPoint operator+(const DPoint &p) const;

    DPoint operator-(const DPoint &p) const;

    double distance(const DPoint &p) const;
};

OGDF_EXPORT ostream &operator<<(ostream &os, const DPoint &dp);


class OGDF_EXPORT DVector : public DPoint {
public:

    DVector() : DPoint() { }

    DVector(double x, double y) : DPoint(x, y) { }

    DVector(const DVector &dv) : DPoint(dv) { }

    DVector operator=(const DPoint &ip) {
        if (this != &ip)
        {
            m_x = ip.m_x;
            m_y = ip.m_y;
        }
        return *this;
    }

    DVector operator*(const double val) const;

    DVector operator/(const double val) const;

    double length() const;

    double operator^(const DVector &dv) const;

    double operator*(const DVector &dv) const;

    DVector operator++() const;

    DVector operator--() const;
};



class OGDF_EXPORT DPolyline : public List<DPoint> {
    static const double s_prec; 
public:
    DPolyline() { }

    DPolyline(const DPolyline &dpl) : List<DPoint>(dpl) { }

    DPolyline &operator=(const DPolyline &dpl) {
        List<DPoint>::operator =(dpl);
        return *this;
    }

    double length() const;

    DPoint position(const double fraction, double len = -1.0) const;

    void writeGML(const char* filename) const;

    void writeGML(ostream &stream) const;

    void unify();   

    void normalize();
    
    void normalize(DPoint src, //start point of the edge
                    DPoint tgt); //end point of the edge

    void convertToInt();

    //void reConvertToDouble();
};


class OGDF_EXPORT DLine {

protected:
    DPoint m_start; 
    DPoint m_end;   

public:

    DLine() : m_start(), m_end() {}

    DLine(const DPoint &p1, const DPoint &p2) : m_start(p1), m_end(p2) {}

    DLine(const DLine &dl) : m_start(dl.m_start), m_end(dl.m_end) {}

    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;
    }

    bool operator==(const DLine &dl) const {
        return m_start == dl.m_start && m_end == dl.m_end;
    }

    bool operator!=(const DLine &dl) const {
        return !(*this == dl);
    }

    DLine &operator= (const DLine &dl) {
        if (this != &dl) { // don't assign myself
            m_start = dl.m_start;
            m_end   = dl.m_end;
        }
        return *this;
    }

    const DPoint &start() const { return m_start; }

    const DPoint &end() const { return m_end; }

    double dx() const { return m_end.m_x - m_start.m_x; }

    double dy() const { return m_end.m_y - m_start.m_y; }

    double slope() const { return (dx() == 0) ? DBL_MAX : dy()/dx(); }

    double yAbs() const { return (dx() == 0) ? DBL_MAX : m_start.m_y - (slope() * m_start.m_x); }

    bool isVertical()   const { return (DIsEqual(dx(), 0.0)); }

    bool isHorizontal() const { return (DIsEqual(dy(), 0.0)); }

    bool intersection(const DLine &line, DPoint &inter, bool endpoints = true) const;

    bool contains(const DPoint &p) const;

    double length() const {
        return m_start.distance(m_end);
    }

    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
    int verIntersection(const double verAxis, double &crossing) const;
};

ostream &operator<<(ostream &os, const DLine &dl);


class OGDF_EXPORT DRect {

private:
    DPoint m_p1; 
    DPoint m_p2; 

public:
    DRect() : m_p1(), m_p2() {}

    DRect(const DPoint &p1, const DPoint &p2) : m_p1(p1), m_p2(p2)
        { normalize(); }

    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();
    }

    DRect(const DLine &dl) : m_p1(dl.start()), m_p2(dl.end())
        { normalize(); }

    DRect(const DRect &dr) : m_p1(dr.m_p1), m_p2(dr.m_p2)
        { normalize(); }

    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)  swap(m_p2.m_x, m_p1.m_x);
        if (height() < 0) swap(m_p2.m_y, m_p1.m_y);
    }

    const DPoint &p1() const { return m_p1; }

    const DPoint &p2() const { return m_p2; }

    const DLine topLine() const {
        return DLine( DPoint(m_p1.m_x, m_p2.m_y), DPoint(m_p2.m_x, m_p2.m_y));
    }

    const DLine rightLine() const {
        return DLine( DPoint(m_p2.m_x, m_p2.m_y), DPoint(m_p2.m_x, m_p1.m_y));
    }

    const DLine leftLine() const {
        return DLine( DPoint(m_p1.m_x, m_p1.m_y), DPoint(m_p1.m_x, m_p2.m_y));
    }

    const DLine bottomLine() const {
        return DLine( DPoint(m_p2.m_x, m_p1.m_y), DPoint(m_p1.m_x, m_p1.m_y));
    }

    void yInvert() { swap(m_p1.m_y, m_p2.m_y); }

    void xInvert() { swap(m_p1.m_x, m_p2.m_x); }

    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;
    }
};

OGDF_EXPORT ostream &operator<<(ostream &os, const DRect &dr);


class OGDF_EXPORT DScaler {

private:

    const DRect *m_from; 
    const DRect *m_to; 

    double m_factorX; 
    double m_factorY; 
    double m_offsetX; 
    double m_offsetY; 

public:
    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() {}

    const DRect &from() const { return *m_from; }

    const DRect &to()   const { return *m_to;   }

    double scaleToX(double x) { return x * m_factorX + m_offsetX; }

    double scaleToY(double y) { return y * m_factorY + m_offsetY; }

    double scaleWidth(double width)   { return width  * m_to->width() /m_from->width();  }

    double scaleHeight(double height) { return height * m_to->height()/m_from->height(); }
};

OGDF_EXPORT ostream &operator<<(ostream &os, const DScaler &ds);


class OGDF_EXPORT DSegment : public DLine {

protected:

public:

    DSegment() : DLine() {}

    DSegment(const DPoint &p1, const DPoint &p2) : DLine(p1, p2) {}

    DSegment(const DLine &dl) : DLine(dl) {}

    DSegment(double x1, double y1, double x2, double y2) : DLine(x1, y1, x2, y2) {}

    DSegment(const DSegment &ds) : DLine(ds) {}


    double det(const DSegment &segment) const {
        return (dx() * segment.dy() - dy() * segment.dx());
    }
};


class OGDF_EXPORT DPolygon : public DPolyline {

protected:

    bool m_counterclock; 

public:
    DPolygon(bool cc = true) : m_counterclock(cc) { }

    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();

    void writeGML(const char* filename) const;

    void writeGML(ostream &stream)      const;

    bool containsPoint(DPoint &p) const;
};

OGDF_EXPORT ostream &operator<<(ostream &os, const DPolygon &dop);



} // end namespace ogdf

#endif