00001
00002
00003
00004
00005
00006
00007
00008
00042 #ifdef _MSC_VER
00043 #pragma once
00044 #endif
00045
00046 #ifndef OGDF_GEOMETRIC_H
00047 #define OGDF_GEOMETRIC_H
00048
00049 #include <float.h>
00050 #include <math.h>
00051
00052 #include <ogdf/basic/List.h>
00053 #include <ogdf/basic/Hashing.h>
00054
00055 #define GEOMETRIC_CMP_EPS 1e-06
00056
00057 namespace ogdf {
00058
00060 enum Orientation {
00061 topToBottom,
00062 bottomToTop,
00063 leftToRight,
00064 rightToLeft
00065 };
00066
00067
00068
00069
00070 inline
00071 bool DIsEqual(const double &a, const double &b, const double eps = GEOMETRIC_CMP_EPS)
00072 {
00073 return (a < (b + eps) && a > (b - eps));
00074 }
00075
00076 inline
00077 bool DIsGreaterEqual(const double &a, const double &b, const double eps = GEOMETRIC_CMP_EPS)
00078 {
00079 return (a > (b - eps));
00080 }
00081
00082 inline
00083 bool DIsGreater(const double &a, const double &b, const double eps = GEOMETRIC_CMP_EPS)
00084 {
00085 return (a > (b + eps));
00086 }
00087
00088 inline
00089 bool DIsLessEqual(const double &a, const double &b, const double eps = GEOMETRIC_CMP_EPS)
00090 {
00091 return (a < (b + eps));
00092 }
00093
00094 inline
00095 bool DIsLess(const double &a, const double &b, const double eps = GEOMETRIC_CMP_EPS)
00096 {
00097 return (a < (b - eps));
00098 }
00099
00100 inline
00101 double DRound(const double &d, int prec = 0)
00102 {
00103 if (prec == 0)
00104 return floor(d + 0.5);
00105 double factor = pow(10.0, ((double) prec));
00106 return DRound(d * factor, 0) / factor;
00107 }
00108
00117 template <class NUMBER>
00118 class GenericPoint
00119 {
00120 public:
00122 typedef NUMBER numberType;
00123
00124 NUMBER m_x;
00125 NUMBER m_y;
00126
00128
00132 GenericPoint() { }
00133
00135 GenericPoint(NUMBER x, NUMBER y) : m_x(x), m_y(y) { }
00136
00138 GenericPoint(const GenericPoint &ip) : m_x(ip.m_x), m_y(ip.m_y) { }
00139
00141 GenericPoint operator=(const GenericPoint &ip) {
00142 m_x = ip.m_x;
00143 m_y = ip.m_y;
00144 return *this;
00145 }
00146
00148 bool operator==(const GenericPoint &ip) const {
00149 return m_x == ip.m_x && m_y == ip.m_y;
00150 }
00151
00153 bool operator!=(const GenericPoint &ip) const {
00154 return m_x != ip.m_x || m_y != ip.m_y;
00155 }
00156
00157 };
00158
00159
00165 class OGDF_EXPORT IPoint : public GenericPoint<int>
00166 {
00167 public:
00169 IPoint() : GenericPoint<int>(0,0) { }
00170
00172 IPoint(int x, int y) : GenericPoint<int>(x,y) { }
00173
00175 IPoint(const IPoint &ip) : GenericPoint<int>(ip) { }
00176
00178 double distance(const IPoint &p) const;
00179 };
00180
00181
00183 OGDF_EXPORT ostream &operator<<(ostream &os, const IPoint &ip);
00184
00185
00186 template<> class DefHashFunc<IPoint>
00187 {
00188 public:
00189 int hash(const IPoint &ip) const {
00190 return 7*ip.m_x + 23*ip.m_y;
00191 }
00192 };
00193
00194
00203 class OGDF_EXPORT IPolyline : public List<IPoint> {
00204 public:
00206 IPolyline() { }
00207
00209 IPolyline(const IPolyline &ipl) : List<IPoint>(ipl) { }
00210
00212 IPolyline &operator=(const IPolyline &ipl) {
00213 List<IPoint>::operator =(ipl);
00214 return *this;
00215 }
00216
00218 double length() const;
00219 };
00220
00221
00222
00228 class OGDF_EXPORT DPoint : public GenericPoint<double>
00229 {
00230 public:
00232 DPoint() : GenericPoint<double>(0,0) { }
00233
00235 DPoint(double x, double y) : GenericPoint<double>(x,y) { }
00236
00238 DPoint(const DPoint &dp) : GenericPoint<double>(dp) { }
00239
00241 bool operator==(const DPoint &dp) const {
00242 return DIsEqual(m_x, dp.m_x) && DIsEqual(m_y,dp.m_y);
00243 }
00244
00246 DPoint operator+(const DPoint &p) const;
00247
00249 DPoint operator-(const DPoint &p) const;
00250
00252 double distance(const DPoint &p) const;
00253 };
00254
00256 OGDF_EXPORT ostream &operator<<(ostream &os, const DPoint &dp);
00257
00258
00262 class OGDF_EXPORT DVector : public DPoint {
00263 public:
00264
00266 DVector() : DPoint() { }
00267
00269 DVector(double x, double y) : DPoint(x, y) { }
00270
00272 DVector(const DVector &dv) : DPoint(dv) { }
00273
00275 DVector operator=(const DPoint &ip) {
00276 if (this != &ip)
00277 {
00278 m_x = ip.m_x;
00279 m_y = ip.m_y;
00280 }
00281 return *this;
00282 }
00283
00285 DVector operator*(const double val) const;
00286
00288 DVector operator/(const double val) const;
00289
00291 double length() const;
00292
00294 double operator^(const DVector &dv) const;
00295
00297 double operator*(const DVector &dv) const;
00298
00305 DVector operator++() const;
00306
00313 DVector operator--() const;
00314 };
00315
00316
00317
00325 class OGDF_EXPORT DPolyline : public List<DPoint> {
00326 static const double s_prec;
00327 public:
00329 DPolyline() { }
00330
00332 DPolyline(const DPolyline &dpl) : List<DPoint>(dpl) { }
00333
00335 DPolyline &operator=(const DPolyline &dpl) {
00336 List<DPoint>::operator =(dpl);
00337 return *this;
00338 }
00339
00341 double length() const;
00342
00350 DPoint position(const double fraction, double len = -1.0) const;
00351
00353 void writeGML(const char* filename) const;
00354
00356 void writeGML(ostream &stream) const;
00357
00359 void unify();
00360
00362 void normalize();
00363
00365 void normalize(DPoint src,
00366 DPoint tgt);
00367
00369 void convertToInt();
00370
00371
00372 };
00373
00374
00378 class OGDF_EXPORT DLine {
00379
00380 protected:
00381 DPoint m_start;
00382 DPoint m_end;
00383
00384 public:
00385
00387 DLine() : m_start(), m_end() {}
00388
00390 DLine(const DPoint &p1, const DPoint &p2) : m_start(p1), m_end(p2) {}
00391
00393 DLine(const DLine &dl) : m_start(dl.m_start), m_end(dl.m_end) {}
00394
00396 DLine(double x1, double y1, double x2, double y2) {
00397 m_start.m_x = x1; m_start.m_y = y1; m_end.m_x = x2; m_end.m_y = y2;
00398 }
00399
00401 bool operator==(const DLine &dl) const {
00402 return m_start == dl.m_start && m_end == dl.m_end;
00403 }
00404
00406 bool operator!=(const DLine &dl) const {
00407 return !(*this == dl);
00408 }
00409
00411 DLine &operator= (const DLine &dl) {
00412 if (this != &dl) {
00413 m_start = dl.m_start;
00414 m_end = dl.m_end;
00415 }
00416 return *this;
00417 }
00418
00420 const DPoint &start() const { return m_start; }
00421
00423 const DPoint &end() const { return m_end; }
00424
00426 double dx() const { return m_end.m_x - m_start.m_x; }
00427
00429 double dy() const { return m_end.m_y - m_start.m_y; }
00430
00432 double slope() const { return (dx() == 0) ? DBL_MAX : dy()/dx(); }
00433
00435 double yAbs() const { return (dx() == 0) ? DBL_MAX : m_start.m_y - (slope() * m_start.m_x); }
00436
00438 bool isVertical() const { return (DIsEqual(dx(), 0.0)); }
00439
00441 bool isHorizontal() const { return (DIsEqual(dy(), 0.0)); }
00442
00450 bool intersection(const DLine &line, DPoint &inter, bool endpoints = true) const;
00451
00453 bool contains(const DPoint &p) const;
00454
00456 double length() const {
00457 return m_start.distance(m_end);
00458 }
00459
00469 int horIntersection(const double horAxis, double &crossing) const;
00470
00471
00472
00482 int verIntersection(const double verAxis, double &crossing) const;
00483 };
00484
00486 ostream &operator<<(ostream &os, const DLine &dl);
00487
00488
00492 class OGDF_EXPORT DRect {
00493
00494 private:
00495 DPoint m_p1;
00496 DPoint m_p2;
00497
00498 public:
00500 DRect() : m_p1(), m_p2() {}
00501
00503 DRect(const DPoint &p1, const DPoint &p2) : m_p1(p1), m_p2(p2)
00504 { normalize(); }
00505
00507 DRect(double x1, double y1, double x2, double y2) {
00508 m_p1.m_x = x1; m_p1.m_y = y1; m_p2.m_x = x2; m_p2.m_y = y2;
00509 normalize();
00510 }
00511
00513 DRect(const DLine &dl) : m_p1(dl.start()), m_p2(dl.end())
00514 { normalize(); }
00515
00517 DRect(const DRect &dr) : m_p1(dr.m_p1), m_p2(dr.m_p2)
00518 { normalize(); }
00519
00521 bool operator==(const DRect &dr) const {
00522 return m_p1 == dr.m_p1 && m_p2 == dr.m_p2;
00523 }
00524
00526 bool operator!=(const DRect &dr) const {
00527 return !(*this == dr);
00528 }
00529
00531 DRect &operator= (const DRect &dr) {
00532 if (this != &dr) {
00533 m_p1 = dr.m_p1;
00534 m_p2 = dr.m_p2;
00535 }
00536 return *this;
00537 }
00538
00540 double width() const {
00541 return m_p2.m_x - m_p1.m_x;
00542 }
00543
00545 double height() const {
00546 return m_p2.m_y - m_p1.m_y;
00547 }
00548
00555 void normalize() {
00556 if (width() < 0) swap(m_p2.m_x, m_p1.m_x);
00557 if (height() < 0) swap(m_p2.m_y, m_p1.m_y);
00558 }
00559
00561 const DPoint &p1() const { return m_p1; }
00562
00564 const DPoint &p2() const { return m_p2; }
00565
00567 const DLine topLine() const {
00568 return DLine( DPoint(m_p1.m_x, m_p2.m_y), DPoint(m_p2.m_x, m_p2.m_y));
00569 }
00570
00572 const DLine rightLine() const {
00573 return DLine( DPoint(m_p2.m_x, m_p2.m_y), DPoint(m_p2.m_x, m_p1.m_y));
00574 }
00575
00577 const DLine leftLine() const {
00578 return DLine( DPoint(m_p1.m_x, m_p1.m_y), DPoint(m_p1.m_x, m_p2.m_y));
00579 }
00580
00582 const DLine bottomLine() const {
00583 return DLine( DPoint(m_p2.m_x, m_p1.m_y), DPoint(m_p1.m_x, m_p1.m_y));
00584 }
00585
00587 void yInvert() { swap(m_p1.m_y, m_p2.m_y); }
00588
00590 void xInvert() { swap(m_p1.m_x, m_p2.m_x); }
00591
00593 bool contains(const DPoint &p) const {
00594 if (DIsLess (p.m_x, m_p1.m_x) ||
00595 DIsGreater(p.m_x, m_p2.m_x) ||
00596 DIsLess (p.m_y, m_p1.m_y) ||
00597 DIsGreater(p.m_y, m_p2.m_y))
00598 return false;
00599 return true;
00600 }
00601 };
00602
00604 OGDF_EXPORT ostream &operator<<(ostream &os, const DRect &dr);
00605
00606
00610 class OGDF_EXPORT DScaler {
00611
00612 private:
00613
00614 const DRect *m_from;
00615 const DRect *m_to;
00616
00617 double m_factorX;
00618 double m_factorY;
00619 double m_offsetX;
00620 double m_offsetY;
00621
00622 public:
00624 DScaler(const DRect &from, const DRect &to) :
00625 m_from(&from),
00626 m_to(&to),
00627 m_factorX(to.width()/from.width()),
00628 m_factorY(to.height()/from.height()),
00629 m_offsetX(to.p1().m_x - from.p1().m_x * m_factorX),
00630 m_offsetY(to.p1().m_y - from.p1().m_y * m_factorY)
00631 {}
00632
00633 ~DScaler() {}
00634
00636 const DRect &from() const { return *m_from; }
00637
00639 const DRect &to() const { return *m_to; }
00640
00642 double scaleToX(double x) { return x * m_factorX + m_offsetX; }
00643
00645 double scaleToY(double y) { return y * m_factorY + m_offsetY; }
00646
00648 double scaleWidth(double width) { return width * m_to->width() /m_from->width(); }
00649
00651 double scaleHeight(double height) { return height * m_to->height()/m_from->height(); }
00652 };
00653
00655 OGDF_EXPORT ostream &operator<<(ostream &os, const DScaler &ds);
00656
00657
00661 class OGDF_EXPORT DSegment : public DLine {
00662
00663 protected:
00664
00665 public:
00666
00668 DSegment() : DLine() {}
00669
00671 DSegment(const DPoint &p1, const DPoint &p2) : DLine(p1, p2) {}
00672
00674 DSegment(const DLine &dl) : DLine(dl) {}
00675
00677 DSegment(double x1, double y1, double x2, double y2) : DLine(x1, y1, x2, y2) {}
00678
00680 DSegment(const DSegment &ds) : DLine(ds) {}
00681
00682
00689 double det(const DSegment &segment) const {
00690 return (dx() * segment.dy() - dy() * segment.dx());
00691 }
00692 };
00693
00694
00698 class OGDF_EXPORT DPolygon : public DPolyline {
00699
00700 protected:
00701
00702 bool m_counterclock;
00703
00704 public:
00711 DPolygon(bool cc = true) : m_counterclock(cc) { }
00712
00714 DPolygon(const DRect &rect, bool cc = true) : m_counterclock(cc) {
00715 operator=(rect);
00716 }
00717
00719 DPolygon(const DPolygon &dop) : DPolyline(dop), m_counterclock(dop.m_counterclock) { }
00720
00722 bool counterclock() { return m_counterclock; }
00723
00725 DPolygon &operator=(const DPolygon &dop) {
00726 List<DPoint>::operator =(dop);
00727 m_counterclock = dop.m_counterclock;
00728 return *this;
00729 }
00730
00732 DPolygon &operator=(const DRect &rect);
00733
00735 DSegment segment(ListConstIterator<DPoint> it) const;
00736
00737
00739 ListIterator<DPoint> insertPoint(const DPoint &p) {
00740 return insertPoint(p, begin(), begin());
00741 }
00742
00748 ListIterator<DPoint> insertPoint(const DPoint &p,
00749 ListIterator<DPoint> p1,
00750 ListIterator<DPoint> p2);
00751
00753 void insertCrossPoint(const DPoint &p);
00754
00756 int getCrossPoints(const DPolygon &p, List<DPoint> &crossPoints) const;
00757
00759 void unify();
00760
00762 void normalize();
00763
00765 void writeGML(const char* filename) const;
00766
00768 void writeGML(ostream &stream) const;
00769
00776 bool containsPoint(DPoint &p) const;
00777 };
00778
00780 OGDF_EXPORT ostream &operator<<(ostream &os, const DPolygon &dop);
00781
00782
00783
00784 }
00785
00786 #endif