Tulip  5.3.0
Large graphs analysis and drawing
Circle.h
1 /*
2  *
3  * This file is part of Tulip (http://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  /**
47  * Translate "this" by vector v
48  */
49  void translate(const Vector<Obj, 2, OTYPE> &v) {
50  (*this) += v;
51  }
52  /**
53  * Merges this circle with another circle; merging operation
54  * consists in computing the smallest enclosing circle of the
55  * two circle and to store the result in "this".
56  */
57  Circle<Obj, OTYPE> &merge(const Circle<Obj, OTYPE> &c);
58  /**
59  * Radius of the circle
60  */
61  Obj radius;
62  /**
63  * Returns true if the circle is include in an other circle, false otherwise.
64  */
65  bool isIncludeIn(const Circle<Obj, OTYPE> &circle) const;
66 };
67 
68 /**
69  * Give the instersction of two circles, return false if no intersection exist else put the two
70  * points in p1 & p2,
71  * if there is only one solution p1 == p2;
72  */
73 template <typename Obj, typename OTYPE>
74 bool intersection(const tlp::Circle<Obj, OTYPE> &c1, const tlp::Circle<Obj, OTYPE> &c2,
75  tlp::Vector<Obj, 2, OTYPE> &sol1, tlp::Vector<Obj, 2, OTYPE> &sol2) {
76  double d = c1.dist(c2);
77  double r1 = c1.radius;
78  double r2 = c2.radius;
79 
80  if (c1 == c2)
81  return false;
82 
83  if (d > (r1 + r2))
84  return false; // outside
85 
86  if (d < fabs(r1 - r2))
87  return false; // inside
88 
89  double a = ((r1 * r1) - (r2 * r2) + (d * d)) / (2.0 * d);
90  Vec2d c1c2(c2 - c1);
91  Vec2d p2(c1 + c1c2 * a / d);
92 
93  double h = sqrt((r1 * r1) - (a * a));
94  double rx = -c1c2[1] * (h / d);
95  double ry = c1c2[0] * (h / d);
96 
97  sol1[0] = p2[0] + rx;
98  sol1[1] = p2[1] + ry;
99 
100  sol2[0] = p2[0] - rx;
101  sol2[1] = p2[1] - ry;
102 
103  return true;
104 }
105 
106 /**
107  * Compute the optimum enclosing circle of 2 circles.
108  */
109 template <typename Obj, typename OTYPE>
110 tlp::Circle<Obj, OTYPE> enclosingCircle(const tlp::Circle<Obj, OTYPE> &,
111  const tlp::Circle<Obj, OTYPE> &);
112 
113 /**
114  * Compute the optimum enclosing circle of a set of circles.
115  */
116 template <typename Obj, typename OTYPE>
117 tlp::Circle<Obj, OTYPE> enclosingCircle(const std::vector<tlp::Circle<Obj, OTYPE>> &circles);
118 /**
119  * Compute an enclosing circle of a set of circles,
120  * this algorithm is an aproximation of the smallest
121  * enclosing circle.
122  */
123 template <typename Obj, typename OTYPE>
124 tlp::Circle<Obj, OTYPE> lazyEnclosingCircle(const std::vector<tlp::Circle<Obj, OTYPE>> &circles);
125 /**
126  * Write circle in a stream
127  */
128 template <typename Obj, typename OTYPE>
129 std::ostream &operator<<(std::ostream &os, const tlp::Circle<Obj, OTYPE> &);
130 
131 typedef Circle<double, long double> Circled;
132 typedef Circle<float, double> Circlef;
133 typedef Circle<int, double> Circlei;
134 } // namespace tlp
135 
136 #include "cxx/Circle.cxx"
137 #endif
138 ///@endcond