 # OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
geometry.h
Go to the documentation of this file.
1
33#pragma once
34
36#include <ogdf/basic/Hashing.h>
37#include <ogdf/basic/List.h>
38#include <ogdf/basic/Math.h>
39
40#include <cfloat>
41
42namespace ogdf {
43
44extern OGDF_EXPORT const EpsilonTest OGDF_GEOM_ET;
45
47enum class Orientation {
52};
53
55enum class IntersectionType {
56 None,
59};
60
72template<typename T>
74public:
76 using numberType = T;
77
78 T m_x;
79 T m_y;
80
82 explicit GenericPoint(T x = 0, T y = 0) : m_x(x), m_y(y) { }
83
85 GenericPoint(const GenericPoint<T>& p) : m_x(p.m_x), m_y(p.m_y) { }
86
89 if (this != &p) {
90 m_x = p.m_x;
91 m_y = p.m_y;
92 }
93 return *this;
94 }
95
97 bool operator==(const GenericPoint<T>& dp) const {
98 // OGDF_GEOM_ET uses different methods for integers and floats
99 return OGDF_GEOM_ET.equal(m_x, dp.m_x) && OGDF_GEOM_ET.equal(m_y, dp.m_y);
100 }
101
103 bool operator!=(const GenericPoint<T>& p) const { return !(*this == p); }
104
107 bool operator<(const GenericPoint<T>& p) const {
108 // OGDF_GEOM_ET uses different methods for integers and floats
109 return OGDF_GEOM_ET.less(m_x, p.m_x)
111 }
112
114 bool operator>(const GenericPoint<T>& p) const { return p < *this; }
115
118 return GenericPoint<T>(m_x + p.m_x, m_y + p.m_y);
119 }
120
123 return GenericPoint<T>(m_x - p.m_x, m_y - p.m_y);
124 }
125
128 const double dx1 = q.m_x - m_x, dy1 = q.m_y - m_y;
129 const double dx2 = r.m_x - m_x, dy2 = r.m_y - m_y;
130
131 // two vertices on the same place!
132 if ((dx1 == 0 && dy1 == 0) || (dx2 == 0 && dy2 == 0)) {
133 return 0.0;
134 }
135
136 double phi = std::atan2(dy2, dx2) - std::atan2(dy1, dx1);
137 if (phi < 0) {
138 phi += 2 * Math::pi;
139 }
140
141 return phi;
142 }
143
148
150 double distance(const GenericPoint<T>& p) const {
151 double dx = p.m_x - m_x;
152 double dy = p.m_y - m_y;
153 return sqrt(dx * dx + dy * dy);
154 }
155
157 double norm() const { return sqrt(m_x * m_x + m_y * m_y); }
158
161 m_x += p.m_x;
162 m_y += p.m_y;
163 return *this;
164 }
165
168 m_x -= p.m_x;
169 m_y -= p.m_y;
170 return *this;
171 }
172
175 m_x *= c;
176 m_y *= c;
177 return *this;
178 }
179
182 return GenericPoint<T>(c * p.m_x, c * p.m_y);
183 }
184
187 return GenericPoint<T>(c * p.m_x, c * p.m_y);
188 }
189
192 m_x /= c;
193 m_y /= c;
194 return *this;
195 }
196
198 friend GenericPoint<T> operator/(const GenericPoint<T>& p, double c) {
199 return GenericPoint<T>(p.m_x / c, p.m_y / c);
200 }
201
203 T determinant(const GenericPoint<T>& dv) const { return (m_x * dv.m_y) - (m_y * dv.m_x); }
204
206 T operator*(const GenericPoint<T>& dv) const { return (m_x * dv.m_x) + (m_y * dv.m_y); }
207
215 GenericPoint<T> ret(1, 1);
216 if (m_x != 0.0) {
217 ret.m_x = -m_y / m_x;
218 } else {
219 ret.m_y = 0.0;
220 }
221 return ret;
222 }
223};
224
226template<typename T>
227std::ostream& operator<<(std::ostream& os, const GenericPoint<T>& p) {
228 os << "(" << p.m_x << "," << p.m_y << ")";
229 return os;
230}
231
234
237
238template<>
240public:
241 int hash(const IPoint& ip) const { return 7 * ip.m_x + 23 * ip.m_y; }
242};
243
252template<class PointType>
253class GenericPolyline : public List<PointType> {
254public:
257
260
263
267 return *this;
268 }
269
271 double length() const {
272 OGDF_ASSERT(!this->empty());
273
274 double len = 0.0;
276
277 pred = iter = this->begin();
278 ++iter;
279
280 while (iter.valid()) {
281 len += (*iter).distance(*pred);
282 ++pred;
283 ++iter;
284 }
285
286 return len;
287 }
288
296 DPoint position(const double fraction, double len = -1.0) const {
297 OGDF_ASSERT(!this->empty());
298 OGDF_ASSERT(fraction >= 0.0);
299 OGDF_ASSERT(fraction <= 1.0);
300 if (len < 0.0) {
301 len = length();
302 }
303 OGDF_ASSERT(len >= 0.0);
304
305 DPoint p = *(this->begin());
306 double liter = 0.0;
307 double pos = len * fraction;
308 double seglen = 0.0;
310
311 pred = iter = this->begin();
312 ++iter;
313
314 // search the segment, which contains the desired point
315 double DX = 0, DY = 0; // for further use
316 while (iter.valid()) {
317 DX = (*iter).m_x - (*pred).m_x;
318 DY = (*iter).m_y - (*pred).m_y;
319 seglen = sqrt(DX * DX + DY * DY);
320 liter += seglen;
321 if (liter >= pos) {
322 break;
323 }
324 ++pred;
325 ++iter;
326 }
327
328 if (!iter.valid()) { // position not inside the polyline, return last point!
329 p = *(this->rbegin());
330 } else {
331 if (seglen == 0.0) { // *pred == *iter and pos is inbetween
332 return *pred;
333 }
334
335 double segpos = seglen + pos - liter;
336
337 double dx = DX * segpos / seglen;
338 double dy = DY * segpos / seglen;
339
340 p = *pred;
341 p.m_x += dx;
342 p.m_y += dy;
343 }
344
345 return p;
346 }
347
349 void unify() {
350 if (this->empty()) {
351 return;
352 }
354 for (iter = next = this->begin(), ++next; next.valid() && (this->size() > 2); ++next) {
355 if (*iter == *next) {
356 this->del(next);
357 next = iter;
358 } else {
359 iter = next;
360 }
361 }
362 }
363
364protected:
373
374 double maxAngle = 2 * Math::pi - minAngle;
377
378 while (iter.valid()) {
379 next = iter;
380 ++next;
381 if (!next.valid()) {
382 break;
383 }
384 onext = next;
385 ++onext;
386 if (!onext.valid()) {
387 break;
388 }
389 double phi = (*next).angle(*iter, *onext);
390
391 // Is *next on the way from *iter to *onext?
393 this->del(next);
394 if (iter != this->begin()) {
395 --iter;
396 }
397 } else {
398 ++iter;
399 }
400 }
401 }
402
403public:
406
420 void normalize(double minAngle = Math::pi) {
421 unify();
423 }
424
431 unify();
432 this->pushFront(src);
433 this->pushBack(tgt);
435 this->popFront();
436 this->popBack();
437 }
438};
439
442
445
447template<class PointType>
449public:
450 using numberType = typename PointType::numberType;
451
452protected:
455
457 numberType dx() const { return m_p2.m_x - m_p1.m_x; }
458
460 numberType dy() const { return m_p2.m_y - m_p1.m_y; }
461
462public:
464 GenericLine() : m_p1(), m_p2() { }
465
467 GenericLine(const PointType& p1, const PointType& p2) : m_p1(p1), m_p2(p2) { }
468
471
474 : GenericLine(PointType(x1, y1), PointType(x2, y2)) { }
475
478 return isVertical() ? dl.isVertical() && m_p1.m_x == dl.m_p1.m_x
479 : slope() == dl.slope() && yAbs() == dl.yAbs();
480 }
481
483 bool operator!=(const GenericLine<PointType>& dl) const { return !(*this == dl); }
484
487 if (this != &dl) { // don't assign myself
488 m_p1 = dl.m_p1;
489 m_p2 = dl.m_p2;
490 }
491 return *this;
492 }
493
495 bool isVertical() const { return OGDF_GEOM_ET.equal(dx(), 0.0); }
496
498 bool isHorizontal() const { return OGDF_GEOM_ET.equal(dy(), 0.0); }
499
501 double slope() const { return isVertical() ? std::numeric_limits<double>::max() : dy() / dx(); }
502
505 double yAbs() const {
506 return isVertical() ? std::numeric_limits<double>::max() : m_p1.m_y - (slope() * m_p1.m_x);
507 }
508
516 double det(const GenericLine<PointType>& line) const {
517 return dx() * line.dy() - dy() * line.dx();
518 }
519
529 if (isVertical() && line.isVertical()) {
530 inter = m_p1;
533 } else if (isVertical()) {
534 inter = DPoint(m_p1.m_x, line.slope() * m_p1.m_x + line.yAbs());
536 } else if (line.isVertical()) {
537 inter = DPoint(line.m_p1.m_x, slope() * line.m_p1.m_x + yAbs());
539 } else if (OGDF_GEOM_ET.equal(slope(), line.slope())) {
540 // For parallel lines only return true if the lines are equal.
541 inter = m_p1;
544 } else {
545 double ix = (line.yAbs() - yAbs()) / (slope() - line.slope());
546 inter = DPoint(ix, slope() * ix + yAbs());
548 }
549 }
550
552 virtual bool contains(const DPoint& p) const {
553 if (p == m_p1 || p == m_p2) {
554 return true;
555 }
556
557 if (isVertical()) {
558 return OGDF_GEOM_ET.equal(p.m_x, m_p1.m_x);
559 }
560
561 double dx2p = p.m_x - m_p1.m_x;
562 double dy2p = p.m_y - m_p1.m_y;
563
564 // dx() != 0.0 since this line is not vertical.
565 if (dx2p == 0.0) {
566 return false;
567 }
568
569 return OGDF_GEOM_ET.equal(slope(), (dy2p / dx2p));
570 }
571
580 virtual IntersectionType horIntersection(const double horAxis, double& crossing) const {
581 if (isHorizontal()) {
582 crossing = 0.0;
584 }
585 crossing = (m_p1.m_x * (m_p2.m_y - horAxis) - m_p2.m_x * (m_p1.m_y - horAxis)) / dy();
587 }
588
597 virtual IntersectionType verIntersection(const double verAxis, double& crossing) const {
598 if (isVertical()) {
599 crossing = 0.0;
601 }
602 crossing = (m_p1.m_y * (m_p2.m_x - verAxis) - m_p2.m_y * (m_p1.m_x - verAxis)) / dx();
604 }
605};
606
608template<class PointType>
609std::ostream& operator<<(std::ostream& os, const GenericLine<PointType>& line) {
610 if (line.isVertical()) {
611 os << "Line: vertical with x = " << line.m_p1.m_x;
612 } else {
613 os << "Line: f(x) = " << line.slope() << "x + " << line.yAbs();
614 }
615 return os;
616}
617
620
622template<class PointType>
623class GenericSegment : public GenericLine<PointType> {
624private:
627
632 bool inBoundingRect(const PointType& p, bool includeBorders = true) const {
633 double minx = min(this->m_p1.m_x, this->m_p2.m_x);
634 double miny = min(this->m_p1.m_y, this->m_p2.m_y);
635 double maxx = max(this->m_p1.m_x, this->m_p2.m_x);
636 double maxy = max(this->m_p1.m_y, this->m_p2.m_y);
637
638 if (includeBorders) {
639 return OGDF_GEOM_ET.geq(p.m_x, minx) && OGDF_GEOM_ET.leq(p.m_x, maxx)
640 && OGDF_GEOM_ET.geq(p.m_y, miny) && OGDF_GEOM_ET.leq(p.m_y, maxy);
641 } else {
642 return OGDF_GEOM_ET.greater(p.m_x, minx) && OGDF_GEOM_ET.less(p.m_x, maxx)
643 && OGDF_GEOM_ET.greater(p.m_y, miny) && OGDF_GEOM_ET.less(p.m_y, maxy);
644 }
645 }
646
647public:
650
652 GenericSegment(const PointType& p1, const PointType& p2) : GenericLine<PointType>(p1, p2) { }
653
656
658 GenericSegment(double x1, double y1, double x2, double y2)
659 : GenericLine<PointType>(x1, y1, x2, y2) { }
660
663
666
669 return this->m_p1 == dl.m_p1 && this->m_p2 == dl.m_p2;
670 }
671
673 bool operator!=(const GenericSegment<PointType>& dl) const { return !(*this == dl); }
674
676 const PointType& start() const { return this->m_p1; }
677
679 const PointType& end() const { return this->m_p2; }
680
683
686
698 bool endpoints = true) const {
700
707 } else {
708 // Let inter be the second smallest point of this/the given segment.
709 Array<DPoint> points({this->m_p1, this->m_p2, segment.m_p1, segment.m_p2});
710 std::sort(points.begin(), points.end(), [](DPoint p1, DPoint p2) { return p1 < p2; });
711 inter = points;
712
715 } else if (points == points && !(this->m_p1 == inter && this->m_p2 == inter)
716 && !(segment.m_p1 == inter && segment.m_p2 == inter)) {
717 // There is an intersection at a single point inter, which is
718 // both an endpoint of this and an endpoint of the other segment.
720 } else {
722 }
723 }
724 }
725
727 bool contains(const PointType& p) const override {
729 }
730
732 double length() const { return this->m_p1.distance(this->m_p2); }
733
743 IntersectionType horIntersection(const double horAxis, double& crossing) const override {
745 if (result != IntersectionType::SinglePoint) {
746 return result;
747 } else if (inBoundingRect(DPoint(crossing, horAxis))) {
749 } else {
750 crossing = 0.0;
752 }
753 }
754
764 IntersectionType verIntersection(const double verAxis, double& crossing) const override {
766 if (result != IntersectionType::SinglePoint) {
767 return result;
768 } else if (inBoundingRect(DPoint(verAxis, crossing))) {
770 } else {
771 crossing = 0.0;
773 }
774 }
775};
776
778template<class PointType>
779std::ostream& operator<<(std::ostream& os, const GenericSegment<PointType>& dl) {
780 os << "Segment-Start: " << dl.start() << ", Segment-End: " << dl.end();
781 return os;
782}
783
786
791 friend OGDF_EXPORT std::ostream& operator<<(std::ostream& os, const DRect& dr);
792
793protected:
796
797public:
799 DRect() = default;
800
802 DRect(const DPoint& p1, const DPoint& p2) : m_p1(p1), m_p2(p2) { normalize(); }
803
805 DRect(const DRect& dr) : m_p1(dr.m_p1), m_p2(dr.m_p2) { }
806
808 DRect(double x1, double y1, double x2, double y2) : DRect(DPoint(x1, y1), DPoint(x2, y2)) { }
809
811 explicit DRect(const DSegment& dl) : DRect(dl.start(), dl.end()) { }
812
813 virtual ~DRect() = default;
814
816 bool operator==(const DRect& dr) const { return m_p1 == dr.m_p1 && m_p2 == dr.m_p2; }
817
819 bool operator!=(const DRect& dr) const { return !(*this == dr); }
820
823 if (this != &dr) { // don't assign myself
824 m_p1 = dr.m_p1;
825 m_p2 = dr.m_p2;
826 }
827 return *this;
828 }
829
831 double width() const { return m_p2.m_x - m_p1.m_x; }
832
834 double height() const { return m_p2.m_y - m_p1.m_y; }
835
842 void normalize() {
843 if (width() < 0) {
844 std::swap(m_p2.m_x, m_p1.m_x);
845 }
846 if (height() < 0) {
847 std::swap(m_p2.m_y, m_p1.m_y);
848 }
849 }
850
852 const DPoint& p1() const { return m_p1; }
853
855 const DPoint& p2() const { return m_p2; }
856
858 const DSegment top() const {
859 return DSegment(DPoint(m_p1.m_x, m_p2.m_y), DPoint(m_p2.m_x, m_p2.m_y));
860 }
861
863 const DSegment right() const {
864 return DSegment(DPoint(m_p2.m_x, m_p2.m_y), DPoint(m_p2.m_x, m_p1.m_y));
865 }
866
868 const DSegment left() const {
869 return DSegment(DPoint(m_p1.m_x, m_p1.m_y), DPoint(m_p1.m_x, m_p2.m_y));
870 }
871
873 const DSegment bottom() const {
874 return DSegment(DPoint(m_p2.m_x, m_p1.m_y), DPoint(m_p1.m_x, m_p1.m_y));
875 }
876
878 void yInvert() { std::swap(m_p1.m_y, m_p2.m_y); }
879
881 void xInvert() { std::swap(m_p1.m_x, m_p2.m_x); }
882
884 bool contains(const DPoint& p) const {
885 return OGDF_GEOM_ET.geq(p.m_x, m_p1.m_x) && OGDF_GEOM_ET.leq(p.m_x, m_p2.m_x)
886 && OGDF_GEOM_ET.geq(p.m_y, m_p1.m_y) && OGDF_GEOM_ET.leq(p.m_y, m_p2.m_y);
887 }
888
890 bool intersection(const DSegment& segment) const {
892 return segment.intersection(top(), inter) != IntersectionType::None
893 || segment.intersection(bottom(), inter) != IntersectionType::None
894 || segment.intersection(right(), inter) != IntersectionType::None
895 || segment.intersection(left(), inter) != IntersectionType::None;
896 }
897
898protected:
900 double parallelDist(const DSegment& d1, const DSegment& d2) const;
901
903 double pointDist(const DPoint& p1, const DPoint& p2) const {
904 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));
905 }
906};
907
915 friend OGDF_EXPORT std::ostream& operator<<(std::ostream& os, const DIntersectableRect& dr);
916
917 double m_area = 0.0;
919
925
926public:
929
931 DIntersectableRect(const DPoint& p1, const DPoint& p2) : DRect(p1, p2) { initAreaAndCenter(); }
932
934 DIntersectableRect(double x1, double y1, double x2, double y2)
935 : DIntersectableRect(DPoint(x1, y1), DPoint(x2, y2)) { }
936
939 : DRect(static_cast<DRect>(dr)), m_area(dr.m_area), m_center(dr.m_center) { }
940
942 DIntersectableRect(const DPoint& center, double width, double height)
943 : DIntersectableRect(DPoint(center.m_x - width / 2, center.m_y - height / 2),
944 DPoint(center.m_x + width / 2, center.m_y + height / 2)) {};
945
948 if (this != &dr) { // don't assign myself
949 m_p1 = dr.m_p1;
950 m_p2 = dr.m_p2;
951 m_center = dr.m_center;
952 m_area = dr.m_area;
953 }
954 return *this;
955 }
956
958 DPoint center() const { return m_center; }
959
961 double area() const { return m_area; }
962
965
970
972 double distance(const DIntersectableRect& other) const;
973
975 void move(const DPoint& point);
976};
977
982protected:
984
985public:
992 DPolygon(bool cc = true) : m_counterclock(cc) { }
993
995 explicit DPolygon(const DRect& rect, bool cc = true) : m_counterclock(cc) { operator=(rect); }
996
998 DPolygon(const DPolygon& dop) : DPolyline(dop), m_counterclock(dop.m_counterclock) { }
999
1001 bool counterclock() { return m_counterclock; }
1002
1006 m_counterclock = dop.m_counterclock;
1007 return *this;
1008 }
1009
1012
1015
1017 ListIterator<DPoint> insertPoint(const DPoint& p) { return insertPoint(p, begin(), begin()); }
1018
1026
1028 void insertCrossPoint(const DPoint& p);
1029
1032
1034 void unify();
1035
1038
1045 bool containsPoint(DPoint& p) const;
1046};
1047
1049OGDF_EXPORT std::ostream& operator<<(std::ostream& os, const DPolygon& dop);
1050
1051int orientation(const DPoint& p, const DPoint& q, const DPoint& r);
1052
1053inline int orientation(const DSegment& s, const DPoint& p) {
1054 return orientation(s.start(), s.end(), p);
1055}
1056
1057}
Compare floating point numbers with epsilons and integral numbers with normal compare operators.
Declaration of classes used for hashing.
Declaration of doubly linked lists and iterators.
Mathematical Helpers.
The parameterized class Array implements dynamic arrays of type E.
Definition Array.h:214
Rectangles with real coordinates.
Definition geometry.h:914
DIntersectableRect()=default
Creates a rectangle with lower left and upper right point (0,0).
DPoint center() const
Center of the rectangle.
Definition geometry.h:958
double area() const
Area of the rectangle.
Definition geometry.h:961
DIntersectableRect(double x1, double y1, double x2, double y2)
Creates a rectangle with lower left point (x1,y1) and upper right point (x1,y2).
Definition geometry.h:934
DIntersectableRect(const DPoint &p1, const DPoint &p2)
Creates a rectangle with lower left point p1 and upper right point p2.
Definition geometry.h:931
void move(const DPoint &point)
Moves the rectangle such that its center is at the given point.
friend std::ostream & operator<<(std::ostream &os, const DIntersectableRect &dr)
double distance(const DIntersectableRect &other) const
Computes distance between two rectangles.
DIntersectableRect(const DIntersectableRect &dr)
Copy constructor.
Definition geometry.h:938
bool intersects(const DIntersectableRect &rectangle) const
Tests if this and the argument rectangle intersect.
DIntersectableRect & operator=(const DIntersectableRect &dr)
Assignment operator.
Definition geometry.h:947
DIntersectableRect intersection(const DIntersectableRect &other) const
Returns the rectangle resulting from intersection of this and other. Returns a rectangle with zero wi...
void initAreaAndCenter()
Normalizes the rectangle.
DIntersectableRect(const DPoint &center, double width, double height)
Constructs a rectangle from the center point, width and height.
Definition geometry.h:942
Polygons with real coordinates.
Definition geometry.h:981
DPolygon(const DRect &rect, bool cc=true)
Creates a polgon from a rectangle.
Definition geometry.h:995
ListIterator< DPoint > insertPoint(const DPoint &p, ListIterator< DPoint > p1, ListIterator< DPoint > p2)
Inserts point p, but just searching from point p1 to p2.
DSegment segment(ListConstIterator< DPoint > it) const
Returns the line segment that starts at position it.
bool counterclock()
Returns true iff points are given in counter-clockwise order.
Definition geometry.h:1001
int getCrossPoints(const DPolygon &p, List< DPoint > &crossPoints) const
Returns the list of intersection points of this polygon with p.
void insertCrossPoint(const DPoint &p)
Inserts point p on every segment (a,b) with p in the open range ]a, b[.
DPolygon & operator=(const DPolygon &dop)
Assignment operator.
Definition geometry.h:1004
DPolygon(bool cc=true)
Creates an empty polygon.
Definition geometry.h:992
bool containsPoint(DPoint &p) const
Checks wether a Point /a p is inside the Poylgon or not.
bool m_counterclock
If true points are given in conter-clockwise order.
Definition geometry.h:983
DPolygon & operator=(const DRect &rect)
Assignment operator (for assigning from a rectangle).
DPolygon(const DPolygon &dop)
Copy constructor.
Definition geometry.h:998
void normalize()
Deletes all points, which are not facets.
ListIterator< DPoint > insertPoint(const DPoint &p)
Inserts point p, that must lie on a polygon segment.
Definition geometry.h:1017
void unify()
Deletes all consecutive points that are equal.
Rectangles with real coordinates.
Definition geometry.h:790
double parallelDist(const DSegment &d1, const DSegment &d2) const
Computes distance between parallel line segments.
bool operator==(const DRect &dr) const
Equality operator: both rectangles have the same coordinates.
Definition geometry.h:816
virtual ~DRect()=default
const DSegment bottom() const
Returns the bottom side of the rectangle.
Definition geometry.h:873
double pointDist(const DPoint &p1, const DPoint &p2) const
Computes distance between two points.
Definition geometry.h:903
DRect()=default
Creates a rectangle with lower left and upper right point (0,0).
bool intersection(const DSegment &segment) const
Returns true iff segment intersects this DRect.
Definition geometry.h:890
void normalize()
Normalizes the rectangle.
Definition geometry.h:842
void xInvert()
Swaps the x-coordinates of the two points.
Definition geometry.h:881
double height() const
Returns the height of the rectangle.
Definition geometry.h:834
bool contains(const DPoint &p) const
Returns true iff p lies within this rectangle, modulo the comparison epsilon OGDF_GEOM_ET.
Definition geometry.h:884
void yInvert()
Swaps the y-coordinates of the two points.
Definition geometry.h:878
const DSegment right() const
Returns the right side of the rectangle.
Definition geometry.h:863
const DPoint & p1() const
Returns the lower left point of the rectangle.
Definition geometry.h:852
const DSegment top() const
Returns the top side of the rectangle.
Definition geometry.h:858
DRect(const DSegment &dl)
Creates a rectangle defined by the end points of line segment dl.
Definition geometry.h:811
DPoint m_p2
The upper right point of the rectangle.
Definition geometry.h:795
friend std::ostream & operator<<(std::ostream &os, const DRect &dr)
bool operator!=(const DRect &dr) const
Inequality operator.
Definition geometry.h:819
DPoint m_p1
The lower left point of the rectangle.
Definition geometry.h:794
const DPoint & p2() const
Returns the upper right point of the rectangle.
Definition geometry.h:855
DRect(double x1, double y1, double x2, double y2)
Creates a rectangle with lower left point (x1,y1) and upper right point (x2,y2).
Definition geometry.h:808
DRect(const DRect &dr)
Copy constructor.
Definition geometry.h:805
DRect(const DPoint &p1, const DPoint &p2)
Creates a rectangle with lower left point p1 and upper right point p2.
Definition geometry.h:802
DRect & operator=(const DRect &dr)
Assignment operator.
Definition geometry.h:822
const DSegment left() const
Returns the left side of the rectangle.
Definition geometry.h:868
double width() const
Returns the width of the rectangle.
Definition geometry.h:831
int hash(const IPoint &ip) const
Definition geometry.h:241
Default hash functions.
Definition Hashing.h:213
std::enable_if< std::is_integral< T >::value, bool >::type leq(const T &x, const T &y) const
Compare if x is LEQ than y for integral types.
Definition EpsilonTest.h:83
std::enable_if< std::is_integral< T >::value, bool >::type geq(const T &x, const T &y) const
Compare if x is GEQ to y for integral types.
std::enable_if< std::is_integral< T >::value, bool >::type less(const T &x, const T &y) const
Compare if x is LESS than y for integral types.
Definition EpsilonTest.h:57
std::enable_if< std::is_integral< T >::value, bool >::type equal(const T &x, const T &y) const
Compare if x is EQUAL to y for integral types.
std::enable_if< std::is_integral< T >::value, bool >::type greater(const T &x, const T &y) const
Compare if x is GREATER than y for integral types.
Infinite lines.
Definition geometry.h:448
bool operator!=(const GenericLine< PointType > &dl) const
Inequality operator.
Definition geometry.h:483
GenericLine< PointType > & operator=(const GenericLine< PointType > &dl)
Assignment operator.
Definition geometry.h:486
PointType m_p1
The first point of the line.
Definition geometry.h:453
PointType m_p2
The second point of the line.
Definition geometry.h:454
numberType dx() const
Returns the x-coordinate of the difference (second point - first point).
Definition geometry.h:457
virtual IntersectionType verIntersection(const double verAxis, double &crossing) const
Computes the intersection between this line and the vertical line through x = verAxis.
Definition geometry.h:597
virtual IntersectionType horIntersection(const double horAxis, double &crossing) const
Computes the intersection of this line and the horizontal line through y = horAxis.
Definition geometry.h:580
numberType dy() const
Returns the y-coordinate of the difference (second point - first point).
Definition geometry.h:460
double slope() const
Returns the slope of the line.
Definition geometry.h:501
GenericLine(const GenericLine< PointType > &dl)
Copy constructor.
Definition geometry.h:470
GenericLine(const PointType &p1, const PointType &p2)
Creates a line through the points p1 and p2.
Definition geometry.h:467
GenericLine(numberType x1, numberType y1, numberType x2, numberType y2)
Creates a line through the points (x1,y1) and (x2,y2).
Definition geometry.h:473
virtual bool contains(const DPoint &p) const
Returns true iff p lies on this line.
Definition geometry.h:552
GenericLine()
Creates an empty line.
Definition geometry.h:464
bool isVertical() const
Returns true iff this line runs vertically.
Definition geometry.h:495
bool isHorizontal() const
Returns true iff this line runs horizontally.
Definition geometry.h:498
IntersectionType intersection(const GenericLine< PointType > &line, DPoint &inter) const
Returns an IntersectionType specifying whether line and this line intersect.
Definition geometry.h:528
bool operator==(const GenericLine< PointType > &dl) const
Equality operator.
Definition geometry.h:477
typename PointType::numberType numberType
Definition geometry.h:450
double det(const GenericLine< PointType > &line) const
Determines if line is left or right of this line.
Definition geometry.h:516
double yAbs() const
Returns the value y' such that (0,y') lies on the unlimited straight-line defined by this line.
Definition geometry.h:505
Parameterized base class for points.
Definition geometry.h:73
double norm() const
Returns the norm of the point.
Definition geometry.h:157
T operator*(const GenericPoint< T > &dv) const
Returns the scalar product of this and dv.
Definition geometry.h:206
GenericPoint< T > & operator*=(T c)
Point-wise multiplies this with c.
Definition geometry.h:174
GenericPoint< T > & operator/=(T c)
Point-wise divide this by c.
Definition geometry.h:191
bool operator<(const GenericPoint< T > &p) const
Operator 'less'. Returns true iff the x coordinate of this is less than the x coordinate of p or,...
Definition geometry.h:107
GenericPoint< T > & operator-=(const GenericPoint< T > &p)
Subtracts p from this.
Definition geometry.h:167
GenericPoint(T x=0, T y=0)
Creates a generic point (x,y).
Definition geometry.h:82
double angle(GenericPoint< T > q, GenericPoint< T > r) const
Compute angle (in radians) between vectors.
Definition geometry.h:127
friend GenericPoint< T > operator*(T c, const GenericPoint< T > &p)
Point-wise multiplies p with c.
Definition geometry.h:181
GenericPoint< T > & operator+=(const GenericPoint< T > &p)
Definition geometry.h:160
friend GenericPoint< T > operator*(const GenericPoint< T > &p, T c)
Point-wise multiplies p with c.
Definition geometry.h:186
bool operator==(const GenericPoint< T > &dp) const
Equality operator.
Definition geometry.h:97
T m_y
The y-coordinate.
Definition geometry.h:79
double angleDegrees(GenericPoint< T > q, GenericPoint< T > r) const
Compute angle (in degrees) between vectors.
Definition geometry.h:145
GenericPoint< T > orthogonal() const
Returns a vector that is orthogonal to this vector.
Definition geometry.h:214
T determinant(const GenericPoint< T > &dv) const
Returns the determinant of the matrix (this, dv).
Definition geometry.h:203
double distance(const GenericPoint< T > &p) const
Returns the Euclidean distance between p and this point.
Definition geometry.h:150
T m_x
The x-coordinate.
Definition geometry.h:78
GenericPoint< T > & operator=(const GenericPoint< T > &p)
Assignment operator.
Definition geometry.h:88
bool operator>(const GenericPoint< T > &p) const
Operator 'greater'. Returns true iff p is less than this.
Definition geometry.h:114
GenericPoint(const GenericPoint< T > &p)
Copy constructor.
Definition geometry.h:85
bool operator!=(const GenericPoint< T > &p) const
Inequality operator.
Definition geometry.h:103
T numberType
The type for coordinates of the point.
Definition geometry.h:76
friend GenericPoint< T > operator/(const GenericPoint< T > &p, double c)
Point-wise divide p by c.
Definition geometry.h:198
GenericPoint< T > operator+(const GenericPoint< T > &p) const
Definition geometry.h:117
GenericPoint< T > operator-(const GenericPoint< T > &p) const
Subtraction of points.
Definition geometry.h:122
Polylines with PointType points.
Definition geometry.h:253
DPoint position(const double fraction, double len=-1.0) const
Returns a point on the polyline which is fraction * len away from the start point.
Definition geometry.h:296
GenericPolyline< PointType > & operator=(const GenericPolyline &pl)
Assignment operator.
Definition geometry.h:265
GenericPolyline()
Creates an empty polyline.
Definition geometry.h:256
void normalize(PointType src, PointType tgt, double minAngle=Math::pi)
Deletes all redundant points on the polyline that lie on a (nearly) straight line given by their adja...
Definition geometry.h:430
GenericPolyline(const GenericPolyline< PointType > &pl)
Copy constructor.
Definition geometry.h:262
void unify()
Deletes all successive points with equal coordinates.
Definition geometry.h:349
void normalizeUnified(double minAngle)
Deletes all redundant points on the polyline that lie on a (nearly) straight line given by their adja...
Definition geometry.h:370
GenericPolyline(const List< PointType > &pl)
Creates a polyline using the list of points pl.
Definition geometry.h:259
double length() const
Returns the Euclidean length of the polyline.
Definition geometry.h:271
void normalize(double minAngle=Math::pi)
Deletes all redundant points on the polyline that lie on a (nearly) straight line given by their adja...
Definition geometry.h:420
Finite line segments.
Definition geometry.h:623
bool operator==(const GenericSegment< PointType > &dl) const
Equality operator.
Definition geometry.h:668
IntersectionType horIntersection(const double horAxis, double &crossing) const override
Computes the intersection of this line segment and the horizontal line through y = horAxis.
Definition geometry.h:743
GenericSegment()
Creates an empty line segment.
Definition geometry.h:649
bool operator!=(const GenericSegment< PointType > &dl) const
Inequality operator.
Definition geometry.h:673
GenericLine< PointType >::numberType dx() const
Returns the x-coordinate of the difference (end point - start point).
Definition geometry.h:682
double length() const
Returns the length (Euclidean distance between start and end point) of this line segment.
Definition geometry.h:732
GenericSegment(const GenericSegment< PointType > &ds)=default
Copy constructor.
GenericLine< PointType >::numberType dy() const
Returns the y-coordinate of the difference (end point - start point).
Definition geometry.h:685
GenericSegment(const PointType &p1, const PointType &p2)
Creates a line segment from p1 to p2.
Definition geometry.h:652
IntersectionType verIntersection(const double verAxis, double &crossing) const override
Computes the intersection between this line segment and the vertical line through x = verAxis.
Definition geometry.h:764
const PointType & start() const
Returns the start point of the line segment.
Definition geometry.h:676
GenericSegment(double x1, double y1, double x2, double y2)
Creates a line segment from (x1,y1) to (x2,y2).
Definition geometry.h:658
bool contains(const PointType &p) const override
Returns true iff p lies on this line segment.
Definition geometry.h:727
IntersectionType intersection(const GenericSegment< PointType > &segment, PointType &inter, bool endpoints=true) const
Returns an IntersectionType specifying whether segment and this line segment intersect.
Definition geometry.h:697
GenericSegment & operator=(const GenericSegment< PointType > &ds)=default
Copy assignment operator.
GenericSegment(const GenericLine< PointType > &dl)
Creates a line segment defined by the start and end point of line dl.
Definition geometry.h:655
const PointType & end() const
Returns the end point of the line segment.
Definition geometry.h:679
bool inBoundingRect(const PointType &p, bool includeBorders=true) const
Returns whether p lies in the rectangle which has m_p1 and m_p2 as opposing corners.
Definition geometry.h:632
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
void popFront()
Removes the first element from the list.
Definition List.h:1569
int size() const
Returns the number of elements in the list.
Definition List.h:1472
iterator pushBack(const PointType &x)
Adds element x at the end of the list.
Definition List.h:1531
void del(iterator it)
Removes it from the list.
Definition List.h:1595
List< E > & operator=(const List< E > &L)
Assignment operator.
Definition List.h:1485
iterator pushFront(const PointType &x)
Adds element x at the beginning of the list.
Definition List.h:1518
void popBack()
Removes the last element from the list.
Definition List.h:1582
Encapsulates a pointer to a list element.
Definition List.h:103
bool valid() const
Returns true iff the iterator points to an element.
Definition List.h:137
iterator begin()
Returns an iterator to the first element of the list.
Definition List.h:375
int pos(const_iterator it) const
Returns the position (starting with 0) of iterator it in the list.
Definition List.h:353
reverse_iterator rbegin()
Returns an iterator to the last element of the list.
Definition List.h:411
bool empty() const
Returns true iff the list is empty.
Definition List.h:270
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
#define OGDF_ASSERT(expr)
Definition basic.h:41
int r[]
constexpr double pi
The constant .
Definition Math.h:59
Converts an angle from radians to degrees.
Definition Math.h:130
The namespace for all OGDF objects.
IntersectionType
Determines the type of intersection of two geometric objects.
Definition geometry.h:55
@ SinglePoint
Two geometric objects intersect in a single point.
@ None
Two geometric objects do not intersect.
@ Overlapping
Two geometric objects intersect in infinitely many points.
int orientation(const DPoint &p, const DPoint &q, const DPoint &r)
GenericPoint< double > DPoint
Representing two-dimensional point with real coordinates.
Definition geometry.h:236
std::ostream & operator<<(std::ostream &os, const ogdf::Array< E, INDEX > &a)
Prints array a to output stream os.
Definition Array.h:978
Orientation
Determines the orientation in hierarchical layouts.
Definition geometry.h:47
@ rightToLeft
Edges are oriented from right to left.
@ bottomToTop
Edges are oriented from bottom to top.
@ leftToRight
Edges are oriented from left to right.
@ topToBottom
Edges are oriented from top to bottom.
const EpsilonTest OGDF_GEOM_ET