# OpenGraph DrawingFramework

v.2012.07

geometry.h
Go to the documentation of this file.
1 /*
2  * $Revision: 2564$
3  *
4  * last checkin:
5  * $Author: gutwenger$
6  * $Date: 2012-07-07 00:03:48 +0200 (Sa, 07. Jul 2012)$
7  ***************************************************************/
8
43 #ifdef _MSC_VER
44 #pragma once
45 #endif
46
47 #ifndef OGDF_GEOMETRY_H
48 #define OGDF_GEOMETRY_H
49
50 #include <ogdf/basic/List.h>
51 #include <ogdf/basic/Hashing.h>
52 #include <float.h>
53 #include <math.h>
54
55 #define OGDF_GEOM_EPS 1e-06
56
57
58 namespace ogdf {
59
66 };
67
68
69 // Important: be careful, if compared values are (+/-)DBL_MAX !!!
70 inline
71  bool DIsEqual(const double &a, const double &b, const double eps = OGDF_GEOM_EPS)
72 {
73  return (a < (b + eps) && a > (b - eps));
74 }
75
76 inline
77  bool DIsGreaterEqual(const double &a, const double &b, const double eps = OGDF_GEOM_EPS)
78 {
79  return (a > (b - eps));
80 }
81
82 inline
83  bool DIsGreater(const double &a, const double &b, const double eps = OGDF_GEOM_EPS)
84 {
85  return (a > (b + eps));
86 }
87
88 inline
89  bool DIsLessEqual(const double &a, const double &b, const double eps = OGDF_GEOM_EPS)
90 {
91  return (a < (b + eps));
92 }
93
94 inline
95  bool DIsLess(const double &a, const double &b, const double eps = OGDF_GEOM_EPS)
96 {
97  return (a < (b - eps));
98 }
99
100 inline
101  double DRound(const double &d, int prec = 0)
102 {
103  if (prec == 0)
104  return floor(d + 0.5);
105  double factor = pow(10.0, ((double) prec));
106  return DRound(d * factor, 0) / factor;
107 }
108
117 template <class NUMBER>
119 {
120 public:
122  typedef NUMBER numberType;
123
124  NUMBER m_x;
125  NUMBER m_y;
126
128
133
135  GenericPoint(NUMBER x, NUMBER y) : m_x(x), m_y(y) { }
136
138  GenericPoint(const GenericPoint &ip) : m_x(ip.m_x), m_y(ip.m_y) { }
139
142  m_x = ip.m_x;
143  m_y = ip.m_y;
144  return *this;
145  }
146
148  bool operator==(const GenericPoint &ip) const {
149  return m_x == ip.m_x && m_y == ip.m_y;
150  }
151
153  bool operator!=(const GenericPoint &ip) const {
154  return m_x != ip.m_x || m_y != ip.m_y;
155  }
156
157 };//class GenericPoint
158
159
165 class OGDF_EXPORT IPoint : public GenericPoint<int>
166 {
167 public:
169  IPoint() : GenericPoint<int>(0,0) { }
170
172  IPoint(int x, int y) : GenericPoint<int>(x,y) { }
173
175  IPoint(const IPoint &ip) : GenericPoint<int>(ip) { }
176
178  double distance(const IPoint &p) const;
179 };//class IPoint
180
181
183 OGDF_EXPORT ostream &operator<<(ostream &os, const IPoint &ip);
184
185
186 template<> class DefHashFunc<IPoint>
187 {
188 public:
189  int hash(const IPoint &ip) const {
190  return 7*ip.m_x + 23*ip.m_y;
191  }
192 };
193
194
203 class OGDF_EXPORT IPolyline : public List<IPoint> {
204 public:
206  IPolyline() { }
207
209  IPolyline(const IPolyline &ipl) : List<IPoint>(ipl) { }
210
214  return *this;
215  }
216
218  double length() const;
219 };
220
221
222
228 class OGDF_EXPORT DPoint : public GenericPoint<double>
229 {
230 public:
232  DPoint() : GenericPoint<double>(0,0) { }
233
235  DPoint(double x, double y) : GenericPoint<double>(x,y) { }
236
238  DPoint(const DPoint &dp) : GenericPoint<double>(dp) { }
239
241  bool operator==(const DPoint &dp) const {
242  return DIsEqual(m_x, dp.m_x) && DIsEqual(m_y,dp.m_y);
243  }
244
246  double norm() const {
247  return sqrt(m_x*m_x + m_y*m_y);
248  }
249
251  DPoint operator+(const DPoint &p) const;
252
254  DPoint operator-(const DPoint &p) const;
255
257  double distance(const DPoint &p) const;
258 };
259
261 OGDF_EXPORT ostream &operator<<(ostream &os, const DPoint &dp);
262
263
267 class OGDF_EXPORT DVector : public DPoint {
268 public:
269
271  DVector() : DPoint() { }
272
274  DVector(double x, double y) : DPoint(x, y) { }
275
277  DVector(const DVector &dv) : DPoint(dv) { }
278
280  DVector operator=(const DPoint &ip) {
281  if (this != &ip)
282  {
283  m_x = ip.m_x;
284  m_y = ip.m_y;
285  }
286  return *this;
287  }
288
290  DVector operator*(const double val) const;
291
293  DVector operator/(const double val) const;
294
296  double length() const;
297
299  double operator^(const DVector &dv) const;
300
302  double operator*(const DVector &dv) const;
303
310  DVector operator++() const;
311
318  DVector operator--() const;
319 };
320
321
322
330 class OGDF_EXPORT DPolyline : public List<DPoint> {
331  static const double s_prec;
332 public:
334  DPolyline() { }
335
337  DPolyline(const DPolyline &dpl) : List<DPoint>(dpl) { }
338
342  return *this;
343  }
344
346  double length() const;
347
355  DPoint position(const double fraction, double len = -1.0) const;
356
358  void writeGML(const char* filename) const;
359
361  void writeGML(ostream &stream) const;
362
364  void unify();
365
367  void normalize();
368
370  void normalize(DPoint src, //start point of the edge
371  DPoint tgt); //end point of the edge
372
374  void convertToInt();
375
376  //void reConvertToDouble();
377 };
378
379
384
385 protected:
388
389 public:
390
392  DLine() : m_start(), m_end() {}
393
395  DLine(const DPoint &p1, const DPoint &p2) : m_start(p1), m_end(p2) {}
396
398  DLine(const DLine &dl) : m_start(dl.m_start), m_end(dl.m_end) {}
399
401  DLine(double x1, double y1, double x2, double y2) {
402  m_start.m_x = x1; m_start.m_y = y1; m_end.m_x = x2; m_end.m_y = y2;
403  }
404
406  bool operator==(const DLine &dl) const {
407  return m_start == dl.m_start && m_end == dl.m_end;
408  }
409
411  bool operator!=(const DLine &dl) const {
412  return !(*this == dl);
413  }
414
416  DLine &operator= (const DLine &dl) {
417  if (this != &dl) { // don't assign myself
418  m_start = dl.m_start;
419  m_end = dl.m_end;
420  }
421  return *this;
422  }
423
425  const DPoint &start() const { return m_start; }
426
428  const DPoint &end() const { return m_end; }
429
431  double dx() const { return m_end.m_x - m_start.m_x; }
432
434  double dy() const { return m_end.m_y - m_start.m_y; }
435
437  double slope() const { return (dx() == 0) ? DBL_MAX : dy()/dx(); }
438
440  double yAbs() const { return (dx() == 0) ? DBL_MAX : m_start.m_y - (slope() * m_start.m_x); }
441
443  bool isVertical() const { return (DIsEqual(dx(), 0.0)); }
444
446  bool isHorizontal() const { return (DIsEqual(dy(), 0.0)); }
447
455  bool intersection(const DLine &line, DPoint &inter, bool endpoints = true) const;
456
458  bool contains(const DPoint &p) const;
459
461  double length() const {
462  return m_start.distance(m_end);
463  }
464
474  int horIntersection(const double horAxis, double &crossing) const;
475
476  // gives the intersection with the vertical axis 'verAxis', returns the number of intersections
477  // 0 = no, 1 = one, 2 = infinity or both end-points, e.g. parallel on this axis
487  int verIntersection(const double verAxis, double &crossing) const;
488 };
489
491 ostream &operator<<(ostream &os, const DLine &dl);
492
493
498
499 private:
502
503 public:
505  DRect() : m_p1(), m_p2() {}
506
508  DRect(const DPoint &p1, const DPoint &p2) : m_p1(p1), m_p2(p2)
509  { normalize(); }
510
512  DRect(double x1, double y1, double x2, double y2) {
513  m_p1.m_x = x1; m_p1.m_y = y1; m_p2.m_x = x2; m_p2.m_y = y2;
514  normalize();
515  }
516
518  DRect(const DLine &dl) : m_p1(dl.start()), m_p2(dl.end())
519  { normalize(); }
520
522  DRect(const DRect &dr) : m_p1(dr.m_p1), m_p2(dr.m_p2)
523  { normalize(); }
524
526  bool operator==(const DRect &dr) const {
527  return m_p1 == dr.m_p1 && m_p2 == dr.m_p2;
528  }
529
531  bool operator!=(const DRect &dr) const {
532  return !(*this == dr);
533  }
534
536  DRect &operator= (const DRect &dr) {
537  if (this != &dr) { // don't assign myself
538  m_p1 = dr.m_p1;
539  m_p2 = dr.m_p2;
540  }
541  return *this;
542  }
543
545  double width() const {
546  return m_p2.m_x - m_p1.m_x;
547  }
548
550  double height() const {
551  return m_p2.m_y - m_p1.m_y;
552  }
553
560  void normalize() {
561  if (width() < 0) swap(m_p2.m_x, m_p1.m_x);
562  if (height() < 0) swap(m_p2.m_y, m_p1.m_y);
563  }
564
566  const DPoint &p1() const { return m_p1; }
567
569  const DPoint &p2() const { return m_p2; }
570
572  const DLine topLine() const {
573  return DLine( DPoint(m_p1.m_x, m_p2.m_y), DPoint(m_p2.m_x, m_p2.m_y));
574  }
575
577  const DLine rightLine() const {
578  return DLine( DPoint(m_p2.m_x, m_p2.m_y), DPoint(m_p2.m_x, m_p1.m_y));
579  }
580
582  const DLine leftLine() const {
583  return DLine( DPoint(m_p1.m_x, m_p1.m_y), DPoint(m_p1.m_x, m_p2.m_y));
584  }
585
587  const DLine bottomLine() const {
588  return DLine( DPoint(m_p2.m_x, m_p1.m_y), DPoint(m_p1.m_x, m_p1.m_y));
589  }
590
592  void yInvert() { swap(m_p1.m_y, m_p2.m_y); }
593
595  void xInvert() { swap(m_p1.m_x, m_p2.m_x); }
596
598  bool contains(const DPoint &p) const {
599  if (DIsLess (p.m_x, m_p1.m_x) ||
600  DIsGreater(p.m_x, m_p2.m_x) ||
601  DIsLess (p.m_y, m_p1.m_y) ||
602  DIsGreater(p.m_y, m_p2.m_y))
603  return false;
604  return true;
605  }
606 };
607
609 OGDF_EXPORT ostream &operator<<(ostream &os, const DRect &dr);
610
611
616
617 private:
618
619  const DRect *m_from;
620  const DRect *m_to;
621
622  double m_factorX;
623  double m_factorY;
624  double m_offsetX;
625  double m_offsetY;
626
627 public:
629  DScaler(const DRect &from, const DRect &to) :
630  m_from(&from),
631  m_to(&to),
632  m_factorX(to.width()/from.width()),
633  m_factorY(to.height()/from.height()),
634  m_offsetX(to.p1().m_x - from.p1().m_x * m_factorX),
635  m_offsetY(to.p1().m_y - from.p1().m_y * m_factorY) { }
636
637  ~DScaler() {}
638
640  const DRect &from() const { return *m_from; }
641
643  const DRect &to() const { return *m_to; }
644
646  double scaleToX(double x) { return x * m_factorX + m_offsetX; }
647
649  double scaleToY(double y) { return y * m_factorY + m_offsetY; }
650
652  double scaleWidth(double width) { return width * m_to->width() /m_from->width(); }
653
655  double scaleHeight(double height) { return height * m_to->height()/m_from->height(); }
656 };
657
658
660 OGDF_EXPORT ostream &operator<<(ostream &os, const DScaler &ds);
661
662
666 class OGDF_EXPORT DSegment : public DLine {
667
668 protected:
669
670 public:
671
673  DSegment() : DLine() {}
674
676  DSegment(const DPoint &p1, const DPoint &p2) : DLine(p1, p2) {}
677
679  DSegment(const DLine &dl) : DLine(dl) {}
680
682  DSegment(double x1, double y1, double x2, double y2) : DLine(x1, y1, x2, y2) {}
683
685  DSegment(const DSegment &ds) : DLine(ds) {}
686
687
694  double det(const DSegment &segment) const {
695  return (dx() * segment.dy() - dy() * segment.dx());
696  }
697 };
698
699
704
705 protected:
706
708
709 public:
716  DPolygon(bool cc = true) : m_counterclock(cc) { }
717
719  DPolygon(const DRect &rect, bool cc = true) : m_counterclock(cc) {
720  operator=(rect);
721  }
722
724  DPolygon(const DPolygon &dop) : DPolyline(dop), m_counterclock(dop.m_counterclock) { }
725
727  bool counterclock() { return m_counterclock; }
728
730  DPolygon &operator=(const DPolygon &dop) {
732  m_counterclock = dop.m_counterclock;
733  return *this;
734  }
735
737  DPolygon &operator=(const DRect &rect);
738
740  DSegment segment(ListConstIterator<DPoint> it) const;
741
742
745  return insertPoint(p, begin(), begin());
746  }
747
753  ListIterator<DPoint> insertPoint(const DPoint &p,
756
758  void insertCrossPoint(const DPoint &p);
759
761  int getCrossPoints(const DPolygon &p, List<DPoint> &crossPoints) const;
762
764  void unify();
765
767  void normalize();
768
770  void writeGML(const char* filename) const;
771
773  void writeGML(ostream &stream) const;
774
781  bool containsPoint(DPoint &p) const;
782 };
783
785 OGDF_EXPORT ostream &operator<<(ostream &os, const DPolygon &dop);
786
787
788
789 } // end namespace ogdf
790
791 #endif