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