Tulip  6.0.0
Large graphs analysis and drawing
Circle.h
1 /*
2  *
3  * This file is part of Tulip (https://tulip.labri.fr)
4  *
5  * Authors: David Auber and the Tulip development Team
6  * from LaBRI, University of Bordeaux
7  *
8  * Tulip is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License
10  * as published by the Free Software Foundation, either version 3
11  * of the License, or (at your option) any later version.
12  *
13  * Tulip is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16  * See the GNU General Public License for more details.
17  *
18  */
19 ///@cond DOXYGEN_HIDDEN
20 
21 #ifndef TLP_GEO_CIRCLE_H
22 #define TLP_GEO_CIRCLE_H
23 
24 #include <vector>
25 #include <tulip/Vector.h>
26 namespace tlp {
27 /**
28  * @ingroup Structures
29  * \brief class for circle
30  *
31  * Enables to both create and manipulate a circle
32  *
33  * \author David Auber auber@labri.fr
34  * \version 0.0.1 24/01/2003
35  */
36 template <typename Obj, typename OTYPE>
37 struct Circle : public Vector<Obj, 2, OTYPE> {
38  Circle() {}
39  Circle(const Vector<Obj, 2, OTYPE> &pos, Obj radius)
40  : Vector<Obj, 2, OTYPE>(pos), radius(radius) {}
41  Circle(const Circle &c) : Vector<Obj, 2, OTYPE>(c), radius(c.radius) {}
42  Circle(Obj x, Obj y, Obj radius) : radius(radius) {
43  (*this)[0] = x;
44  (*this)[1] = y;
45  }
46  Circle &operator=(const Circle &) = default;
47  /**
48  * Translate "this" by vector v
49  */
50  void translate(const Vector<Obj, 2, OTYPE> &v) {
51  (*this) += v;
52  }
53  /**
54  * Merges this circle with another circle; merging operation
55  * consists in computing the smallest enclosing circle of the
56  * two circle and to store the result in "this".
57  */
58  Circle<Obj, OTYPE> &merge(const Circle<Obj, OTYPE> &c);
59  /**
60  * Radius of the circle
61  */
62  Obj radius;
63  /**
64  * Returns true if the circle is include in an other circle, false otherwise.
65  */
66  bool isIncludeIn(const Circle<Obj, OTYPE> &circle) const;
67 };
68 
69 /**
70  * Give the instersection of two circles, return false if no intersection exist else put the two
71  * points in p1 & p2,
72  * if there is only one solution p1 == p2;
73  */
74 template <typename Obj, typename OTYPE>
75 bool intersection(const tlp::Circle<Obj, OTYPE> &c1, const tlp::Circle<Obj, OTYPE> &c2,
76  tlp::Vector<Obj, 2, OTYPE> &sol1, tlp::Vector<Obj, 2, OTYPE> &sol2) {
77  double d = c1.dist(c2);
78  double r1 = c1.radius;
79  double r2 = c2.radius;
80 
81  if (c1 == c2)
82  return false;
83 
84  if (d > (r1 + r2))
85  return false; // outside
86 
87  if (d < fabs(r1 - r2))
88  return false; // inside
89 
90  double a = ((r1 * r1) - (r2 * r2) + (d * d)) / (2.0 * d);
91  Vec2d c1c2(c2 - c1);
92  Vec2d p2(c1 + c1c2 * a / d);
93 
94  double h = sqrt((r1 * r1) - (a * a));
95  double rx = -c1c2[1] * (h / d);
96  double ry = c1c2[0] * (h / d);
97 
98  sol1[0] = p2[0] + rx;
99  sol1[1] = p2[1] + ry;
100 
101  sol2[0] = p2[0] - rx;
102  sol2[1] = p2[1] - ry;
103 
104  return true;
105 }
106 
107 /**
108  * Compute the optimum enclosing circle of 2 circles.
109  */
110 template <typename Obj, typename OTYPE>
111 tlp::Circle<Obj, OTYPE> enclosingCircle(const tlp::Circle<Obj, OTYPE> &,
112  const tlp::Circle<Obj, OTYPE> &);
113 
114 /**
115  * Compute the optimum enclosing circle of a set of circles.
116  */
117 template <typename Obj, typename OTYPE>
118 tlp::Circle<Obj, OTYPE> enclosingCircle(const std::vector<tlp::Circle<Obj, OTYPE>> &circles);
119 /**
120  * Compute an enclosing circle of a set of circles,
121  * this algorithm is an approximation of the smallest
122  * enclosing circle.
123  */
124 template <typename Obj, typename OTYPE>
125 tlp::Circle<Obj, OTYPE> lazyEnclosingCircle(const std::vector<tlp::Circle<Obj, OTYPE>> &circles);
126 /**
127  * Write circle in a stream
128  */
129 template <typename Obj, typename OTYPE>
130 std::ostream &operator<<(std::ostream &os, const tlp::Circle<Obj, OTYPE> &);
131 
132 typedef Circle<double, long double> Circled;
133 typedef Circle<float, double> Circlef;
134 typedef Circle<int, double> Circlei;
135 } // namespace tlp
136 
137 #include "cxx/Circle.cxx"
138 #endif
139 ///@endcond
std::ostream & operator<<(std::ostream &os, const Array< T, N > &array)
operator << stream operator to easily print an array, or save it to a file.