Tulip 5.7.1
Large graphs analysis and drawing
Loading...
Searching...
No Matches
Circle.cxx
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#include <cstdlib>
20#include <tulip/TlpTools.h>
21
22template <typename Obj, typename OTYPE>
23tlp::Circle<Obj, OTYPE> &tlp::Circle<Obj, OTYPE>::merge(const tlp::Circle<Obj, OTYPE> &c) {
24 Vector<Obj, 2, OTYPE> p1(*this);
25 Vector<Obj, 2, OTYPE> p2(c);
26 Vector<Obj, 2, OTYPE> c12 = p2 - p1;
27 double norm = c12.norm();
28
29 if (norm < 0.0000001) {
30 if (radius < c.radius)
31 return (*this) = c;
32 else
33 return *this;
34 }
35
36 double dx = c12[0] / norm;
37 double dy = c12[1] / norm;
38 p1[0] -= dx * radius;
39 p1[1] -= dy * radius;
40 p2[0] += dx * c.radius;
41 p2[1] += dy * c.radius;
42 Obj tmpDist = p1.dist(p2) / 2.;
43
44 if ((tmpDist < radius) || (tmpDist < c.radius)) {
45 if (radius > c.radius)
46 return *this;
47 else
48 return (*this) = c;
49 } else {
50 p1 += p2;
51 p1 /= 2.;
52 (*this)[0] = p1[0];
53 (*this)[1] = p1[1];
54 radius = tmpDist;
55 return *this;
56 }
57}
58
59template <typename Obj, typename OTYPE>
60bool tlp::Circle<Obj, OTYPE>::isIncludeIn(const tlp::Circle<Obj, OTYPE> &c) const {
61 Vector<Obj, 2, OTYPE> dir = c - *this;
62 return (dir.norm() + radius) <= c.radius;
63}
64
65template <typename Obj, typename OTYPE>
66tlp::Circle<Obj, OTYPE> tlp::enclosingCircle(const tlp::Circle<Obj, OTYPE> &c1,
67 const tlp::Circle<Obj, OTYPE> &c2) {
68 Vector<Obj, 2, OTYPE> dir = c2 - c1;
69 Obj n = dir.norm();
70
71 if (n == 0)
72 return Circle<Obj, OTYPE>(c1, std::max(c1.radius, c2.radius));
73
74 dir /= n;
75 Vector<Obj, 2, OTYPE> ext1 = c1 - dir * c1.radius;
76 Vector<Obj, 2, OTYPE> ext2 = c2 + dir * c2.radius;
77 return Circle<Obj, OTYPE>((ext1 + ext2) / Obj(2), (ext2 - ext1).norm() / Obj(2));
78}
79
80template <typename Obj, typename OTYPE>
81tlp::Circle<Obj, OTYPE>
82tlp::lazyEnclosingCircle(const std::vector<tlp::Circle<Obj, OTYPE>> &circles) {
83 // compute bounding box of a
84 tlp::Vector<Obj, 4, OTYPE> boundingBox;
85 // for (int i=0;i<4;++i) boundingBox[i]=0;
86 typename std::vector<tlp::Circle<Obj, OTYPE>>::const_iterator it = circles.begin();
87 boundingBox[0] = (*it)[0] - (*it).radius;
88 boundingBox[1] = (*it)[1] - (*it).radius;
89 boundingBox[2] = (*it)[0] + (*it).radius;
90 boundingBox[3] = (*it)[1] + (*it).radius;
91 ++it;
92
93 for (; it != circles.end(); ++it) {
94 boundingBox[0] = std::min(boundingBox[0], ((*it)[0] - (*it).radius));
95 boundingBox[1] = std::min(boundingBox[1], ((*it)[1] - (*it).radius));
96 boundingBox[2] = std::max(boundingBox[2], ((*it)[0] + (*it).radius));
97 boundingBox[3] = std::max(boundingBox[3], ((*it)[1] + (*it).radius));
98 }
99
100 tlp::Vector<Obj, 2, OTYPE> center;
101 center[0] = (boundingBox[0] + boundingBox[2]) / 2.;
102 center[1] = (boundingBox[1] + boundingBox[3]) / 2.;
103 Obj radius =
104 std::max((boundingBox[2] - boundingBox[0]) / 2., (boundingBox[3] - boundingBox[1]) / 2.);
105 tlp::Circle<Obj, OTYPE> result(center, radius);
106
107 // compute circle hull
108 for (typename std::vector<tlp::Circle<Obj, OTYPE>>::const_iterator it = circles.begin();
109 it != circles.end(); ++it)
110 result.merge(*it);
111
112 return result;
113}
114
115template <typename Obj, typename OTYPE>
116tlp::Circle<Obj, OTYPE> tlp::enclosingCircle(const std::vector<tlp::Circle<Obj, OTYPE>> &circles) {
117 class OptimumCircleHull {
118 const std::vector<tlp::Circle<Obj, OTYPE>> *circles;
119 std::vector<unsigned> enclosedCircles;
120 unsigned first, last;
121 unsigned b1, b2;
122 tlp::Circle<Obj, OTYPE> result;
123
124 static tlp::Circle<Obj, OTYPE> enclosingCircle(const tlp::Circle<Obj, OTYPE> &c1,
125 const tlp::Circle<Obj, OTYPE> &c2,
126 const tlp::Circle<Obj, OTYPE> &c3) {
127 Obj a1 = c1[0];
128 Obj b1 = c1[1];
129 Obj r1 = c1.radius;
130 Obj a2 = c2[0];
131 Obj b2 = c2[1];
132 Obj r2 = c2.radius;
133 Obj a3 = c3[0];
134 Obj b3 = c3[1];
135 Obj r3 = c3.radius;
136 Obj b = -b1 * r2 * a1 * a1 * b3 + a3 * a3 * r2 * r2 * r2 + b2 * b2 * r3 * r3 * r3 +
137 b1 * b1 * r3 * r3 * r3 + b1 * b1 * r2 * r2 * r2 + r1 * r1 * r1 * b3 * b3 +
138 r1 * r1 * r1 * b2 * b2 + r2 * r2 * r2 * b3 * b3 + a1 * a1 * r3 * r3 * r3 +
139 a2 * a2 * r1 * r1 * r1 + a2 * a2 * r3 * r3 * r3 + a1 * a1 * r2 * r2 * r2 +
140 a3 * a3 * r1 * r1 * r1 - b2 * b2 * r3 * a3 * a3 - b2 * b2 * r3 * b3 * b3 -
141 2 * b2 * r3 * r3 * r3 * b1 - b1 * b1 * r3 * a3 * a3 - b1 * b1 * r3 * b3 * b3 -
142 b1 * b1 * r2 * a2 * a2 + 2 * b1 * b1 * r2 * b3 * b3 - b1 * b1 * r2 * r3 * r3 -
143 r1 * b3 * b3 * b3 * b2 + r1 * b3 * b3 * b3 * b1 + 2 * r1 * b2 * b2 * b3 * b3 -
144 r1 * b2 * b2 * r3 * r3 + r2 * b3 * b3 * b3 * b2 - r2 * b3 * b3 * b3 * b1 -
145 b2 * b2 * b2 * r3 * b1 + 2 * b2 * b2 * r3 * b1 * b1 + b2 * b2 * b2 * r3 * b3 -
146 b2 * b2 * r3 * r1 * r1 + b1 * b1 * b1 * r3 * b3 - b1 * b1 * b1 * r3 * b2 -
147 b1 * b1 * r3 * r2 * r2 - b1 * b1 * r2 * b2 * b2 - b1 * b1 * b1 * r2 * b3 +
148 b1 * b1 * b1 * r2 * b2 - 2 * b1 * r2 * r2 * r2 * b3 - r1 * b3 * b3 * b1 * b1 -
149 2 * r1 * r1 * r1 * b3 * b2 - r1 * b3 * b3 * r2 * r2 - r1 * b3 * b3 * a1 * a1 +
150 r1 * b2 * b2 * b2 * b1 - r1 * b2 * b2 * b1 * b1 - r1 * b2 * b2 * b2 * b3 -
151 r1 * b2 * b2 * a1 * a1 - r2 * b3 * b3 * a2 * a2 - r2 * b3 * b3 * b2 * b2 -
152 r2 * b3 * b3 * r1 * r1 - b2 * r3 * b1 * b1 * b3 + b2 * r3 * a2 * a2 * b3 +
153 b2 * r3 * r1 * r1 * b3 - b2 * r3 * r2 * r2 * b3 + b2 * r3 * a1 * a1 * b3 -
154 2 * b2 * r3 * a1 * a2 * b3 + a1 * a3 * b2 * b2 * r3 - 2 * a1 * a3 * b2 * b1 * r3 -
155 2 * a1 * a3 * b2 * b1 * r2 - 2 * a1 * a3 * b2 * r1 * b3 + a1 * a3 * b2 * b2 * r1 -
156 2 * a1 * a3 * b2 * r2 * b3 - b2 * r3 * b1 * a2 * a2 + 2 * b2 * r3 * b1 * a3 * a3 +
157 2 * b2 * r3 * b1 * b3 * b3 + b1 * r2 * b2 * a3 * a3 - b1 * r2 * b2 * b3 * b3 +
158 b1 * r2 * b2 * r3 * r3 + r1 * b3 * b1 * a2 * a2 - r1 * b3 * b2 * a3 * a3 +
159 r1 * b3 * b2 * r3 * r3 + r1 * b3 * b1 * a3 * a3 - r1 * b3 * b1 * r3 * r3 +
160 r1 * b2 * b1 * a2 * a2 + r1 * b2 * b1 * a3 * a3 - r1 * b2 * b1 * b3 * b3 +
161 r1 * b2 * b1 * r3 * r3 + 2 * r2 * b3 * b1 * a2 * a2 + r2 * b3 * b2 * a3 * a3 -
162 r2 * b3 * b2 * r3 * r3 - r2 * b3 * b1 * a3 * a3 + r2 * b3 * b1 * r3 * r3 +
163 b2 * r3 * b1 * r2 * r2 + 4 * b2 * r3 * a1 * a2 * b1 + b1 * r3 * a2 * a2 * b3 -
164 b1 * r3 * b2 * b2 * b3 - b1 * r3 * r1 * r1 * b3 + b1 * r3 * r1 * r1 * b2 +
165 b1 * r3 * r2 * r2 * b3 + b1 * r3 * a1 * a1 * b3 - b1 * r3 * a1 * a1 * b2 -
166 2 * b1 * r3 * a1 * a2 * b3 - b1 * b1 * r3 * a1 * a2 + b1 * b1 * r3 * a1 * a3 +
167 2 * b1 * r2 * b2 * b2 * b3 + b1 * r2 * r1 * r1 * b3 - b1 * r2 * r1 * r1 * b2 +
168 b1 * r2 * a1 * a1 * b2 - 2 * b1 * r2 * a1 * a2 * b3 + b1 * b1 * r2 * a1 * a2 -
169 b1 * b1 * r2 * a1 * a3 - r1 * b3 * b1 * b2 * b2 + 2 * r1 * b3 * b1 * b1 * b2 +
170 2 * r1 * b3 * a1 * a1 * b2 + r1 * b3 * b1 * r2 * r2 + r1 * b3 * b3 * a1 * a2 -
171 r1 * b2 * a2 * a2 * b3 + r1 * b2 * r2 * r2 * b3 - r1 * b2 * b1 * r2 * r2 -
172 2 * r1 * b2 * a1 * a2 * b3 - r2 * b3 * b1 * b1 * b2 + r2 * b3 * r1 * r1 * b2 +
173 r2 * b3 * a1 * a1 * b2 + r2 * b3 * b3 * a1 * a2 + 4 * r2 * b3 * a1 * a3 * b1 -
174 a1 * a1 * a3 * a3 * r3 + 2 * a1 * a1 * a3 * a3 * r2 + a1 * a3 * a3 * a3 * r1 -
175 a1 * a1 * b3 * b3 * r3 - a1 * b3 * b3 * a3 * r2 + a1 * r3 * r3 * a3 * r2 -
176 a2 * a1 * a1 * a3 * r2 + a2 * b1 * b1 * a3 * r2 + a2 * b3 * b3 * a3 * r2 -
177 a1 * a3 * a3 * a2 * r1 + 2 * a1 * a3 * a3 * a2 * r3 + 2 * a1 * b3 * b3 * a2 * r3 +
178 a1 * b3 * b3 * a3 * r1 - 2 * a1 * r3 * r3 * r3 * a2 - a1 * a1 * r3 * r3 * r2 -
179 a2 * a1 * a1 * a1 * r3 - a2 * a2 * a1 * a1 * r1 + 2 * a2 * a2 * a1 * a1 * r3 +
180 a2 * a1 * a1 * a1 * r2 - a2 * a2 * b1 * b1 * r1 + 2 * a2 * a2 * a3 * a3 * r1 -
181 a2 * a2 * a3 * a3 * r3 - a2 * a3 * a3 * a3 * r1 - a2 * a2 * b3 * b3 * r3 -
182 a2 * a2 * r1 * r1 * r3 - 2 * a2 * r1 * r1 * r1 * a3 + a1 * r3 * r3 * a2 * r1 -
183 a1 * r3 * r3 * a3 * r1 + 2 * a2 * a1 * a1 * a3 * r1 + 2 * a2 * b1 * b1 * a3 * r1 -
184 a2 * a3 * a3 * a1 * r2 - a2 * b3 * b3 * a3 * r1 + a2 * r1 * r1 * a1 * r3 -
185 a2 * r1 * r1 * a1 * r2 - a2 * a2 * r3 * r3 * r1 - a1 * a3 * a3 * a3 * r2 +
186 a2 * a3 * a3 * a3 * r2 - a1 * a1 * r3 * r2 * r2 + a1 * a1 * a1 * r3 * a3 +
187 a2 * a2 * a2 * r1 * a1 - a2 * a2 * a2 * r1 * a3 - a2 * a2 * a2 * r3 * a1 +
188 a2 * a2 * a2 * r3 * a3 - a1 * a1 * r2 * a2 * a2 - a1 * a1 * r2 * b2 * b2 -
189 a1 * a1 * a1 * r2 * a3 - 2 * a1 * r2 * r2 * r2 * a3 - a3 * a3 * r1 * a1 * a1 -
190 a3 * a3 * r1 * b1 * b1 - a3 * a3 * r1 * r2 * r2 - a3 * a3 * r2 * a2 * a2 -
191 a3 * a3 * r2 * b2 * b2 - a3 * a3 * r2 * r1 * r1 + a2 * r3 * r3 * a1 * r2 +
192 a2 * r3 * r3 * a3 * r1 - 2 * a3 * r2 * b1 * a2 * b3 + a2 * r1 * r1 * a3 * r2 -
193 a2 * r3 * r3 * a3 * r2 - a1 * r3 * a3 * a2 * a2 - a1 * r3 * a3 * r1 * r1 +
194 a1 * r3 * a3 * r2 * r2 + a2 * r1 * a1 * b2 * b2 - a2 * r1 * a1 * r2 * r2 -
195 a2 * r1 * a3 * b2 * b2 + a2 * r1 * a3 * r2 * r2 - 2 * a2 * r1 * b1 * a3 * b2 -
196 a2 * r3 * a1 * b2 * b2 + a2 * r3 * a1 * r2 * r2 - a2 * r3 * a3 * a1 * a1 +
197 a2 * r3 * a3 * b1 * b1 + a2 * r3 * a3 * b2 * b2 + a2 * r3 * a3 * r1 * r1 -
198 a2 * r3 * a3 * r2 * r2 - 2 * a2 * r3 * b1 * a3 * b2 + 2 * a1 * r2 * a3 * a2 * a2 +
199 2 * a1 * r2 * a3 * b2 * b2 + a1 * r2 * a3 * r1 * r1 - a3 * r1 * a1 * a2 * a2 +
200 a3 * r1 * a1 * r2 * r2 - 2 * a3 * r1 * b1 * a2 * b3 + 4 * r1 * a3 * b2 * a2 * b3;
201 Obj tmp = a2 * b3 - a3 * b2 - a2 * b1 - a1 * b3 + a1 * b2 + a3 * b1;
202 Obj d = sqrt((a2 * a2 + b2 * b2 - r2 * r2 - 2 * a2 * a3 + a3 * a3 - r3 * r3 - 2 * b3 * b2 +
203 b3 * b3 + 2 * r3 * r2) *
204 (b3 * b3 + b1 * b1 - r1 * r1 - r3 * r3 - 2 * b1 * b3 + 2 * r3 * r1 + a3 * a3 -
205 2 * a1 * a3 + a1 * a1) *
206 (a1 * a1 - 2 * a1 * a2 - r1 * r1 + b1 * b1 + b2 * b2 - r2 * r2 - 2 * b2 * b1 +
207 2 * r2 * r1 + a2 * a2) *
208 tmp * tmp);
209 Obj v = d - b;
210
211 if (v < 0)
212 return tlp::Circle<Obj, OTYPE>(0, 0, 0);
213
214 Obj aa = -2 * a3 * b2 * b2 * a1 - 2 * a2 * b3 * b3 * a1 - 2 * a1 * a1 * b3 * b2 +
215 a3 * a3 * b2 * b2 + a2 * a2 * b3 * b3 - r1 * r1 * b3 * b3 - r1 * r1 * b2 * b2 +
216 a2 * a2 * b1 * b1 + a3 * a3 * b1 * b1 - a2 * a2 * r1 * r1 - a2 * a2 * r3 * r3 -
217 a3 * a3 * r2 * r2 - 2 * a3 * b2 * a2 * b3 + 2 * a3 * b2 * a2 * b1 +
218 2 * a2 * b3 * a3 * b1 - 2 * b1 * a2 * a2 * b3 - a3 * a3 * r1 * r1 -
219 2 * a3 * a3 * b2 * b1 + 2 * b1 * r3 * r3 * b2 + 2 * r1 * r1 * b3 * b2 +
220 2 * b3 * b1 * r2 * r2 - 2 * a2 * b1 * b1 * a3 + 2 * a2 * a3 * r1 * r1 -
221 b2 * b2 * r3 * r3 - b1 * b1 * r3 * r3 - b1 * b1 * r2 * r2 - r2 * r2 * b3 * b3 -
222 a1 * a1 * r3 * r3 - a1 * a1 * r2 * r2 + a1 * a1 * b3 * b3 + a1 * a1 * b2 * b2 +
223 2 * b2 * b2 * r3 * r1 + 2 * b1 * b1 * r3 * r2 + 2 * r1 * b3 * b3 * r2 -
224 2 * b2 * r3 * b1 * r2 - 2 * b2 * r3 * r1 * b3 + 2 * b2 * r3 * r2 * b3 +
225 2 * b1 * r3 * r1 * b3 - 2 * b1 * r3 * r1 * b2 - 2 * b1 * r3 * r2 * b3 -
226 2 * b1 * r2 * r1 * b3 + 2 * b1 * r2 * r1 * b2 - 2 * r1 * b2 * r2 * b3 +
227 2 * a1 * r3 * r3 * a2 + 2 * a1 * a1 * r3 * r2 + 2 * a2 * a2 * r1 * r3 +
228 2 * a1 * r2 * r2 * a3 + 2 * a3 * a3 * r1 * r2 - 2 * a1 * r3 * a2 * r1 +
229 2 * a1 * r3 * a3 * r1 + 2 * a2 * r1 * a1 * r2 - 2 * a2 * r3 * a1 * r2 -
230 2 * a2 * r3 * a3 * r1 - 2 * a1 * r2 * a3 * r1 - 2 * a1 * r3 * a3 * r2 -
231 2 * a2 * r1 * a3 * r2 + 2 * a2 * r3 * a3 * r2 + 2 * a2 * b3 * a1 * b2 +
232 2 * a3 * b2 * a1 * b3 + 2 * a2 * b1 * a1 * b3 - 2 * a2 * b1 * a1 * b2 -
233 2 * a1 * b3 * a3 * b1 + 2 * a1 * b2 * a3 * b1;
234 Obj R = 0.5 * v / aa;
235 Obj y = -0.5 *
236 (-2 * a1 * R * r2 - 2 * a3 * R * r1 + 2 * a2 * R * r1 + 2 * a3 * R * r2 -
237 2 * a2 * R * r3 + a1 * a3 * a3 + a1 * b3 * b3 - a1 * r3 * r3 + a2 * a1 * a1 +
238 a2 * b1 * b1 + a1 * r2 * r2 + 2 * a1 * R * r3 - a3 * b1 * b1 + a3 * a2 * a2 +
239 a3 * b2 * b2 + a3 * r1 * r1 - a3 * r2 * r2 - a2 * a3 * a3 - a2 * b3 * b3 -
240 a2 * r1 * r1 + a2 * r3 * r3 - a1 * a2 * a2 - a1 * b2 * b2 - a3 * a1 * a1) /
241 (a2 * b3 + a3 * b1 - a2 * b1 - a1 * b3 + a1 * b2 - a3 * b2);
242 Obj x = 0.5 *
243 (-a1 * a1 * b3 + a1 * a1 * b2 + 2 * R * r2 * b3 + b1 * a3 * a3 + b1 * b3 * b3 +
244 2 * b1 * R * r3 - 2 * R * r1 * b3 + 2 * R * r1 * b2 + b1 * r2 * r2 - b2 * a3 * a3 -
245 b2 * b3 * b3 + b2 * r3 * r3 - 2 * b2 * R * r3 - b1 * r3 * r3 - r2 * r2 * b3 +
246 a2 * a2 * b3 - r1 * r1 * b2 - b1 * b2 * b2 + b1 * b1 * b2 - b1 * b1 * b3 -
247 b1 * a2 * a2 + b2 * b2 * b3 + r1 * r1 * b3 - 2 * b1 * R * r2) /
248 (a2 * b3 + a3 * b1 - a2 * b1 - a1 * b3 + a1 * b2 - a3 * b2);
249 return tlp::Circle<Obj, OTYPE>(x, y, R);
250 }
251
252 void process2() {
253 if (isEmpty()) {
254 result = tlp::enclosingCircle((*circles)[b1], (*circles)[b2]);
255 } else {
256 unsigned selectedCircle = popBack();
257 process2();
258
259 if (!(*circles)[selectedCircle].isIncludeIn(result)) {
260 result = enclosingCircle((*circles)[b1], (*circles)[b2], (*circles)[selectedCircle]);
261 pushFront(selectedCircle);
262 } else {
263 pushBack(selectedCircle);
264 }
265 }
266 }
267
268 void process1() {
269 if (isEmpty()) {
270 result = (*circles)[b1];
271 } else {
272 unsigned selectedCircle = popBack();
273 process1();
274
275 if (!(*circles)[selectedCircle].isIncludeIn(result)) {
276 b2 = selectedCircle;
277 process2();
278 pushFront(selectedCircle);
279 } else {
280 pushBack(selectedCircle);
281 }
282 }
283 }
284 void process0() {
285 if (isEmpty()) {
286 result = Circle<Obj, OTYPE>(0, 0, 0);
287 } else {
288 unsigned selectedCircle = popBack();
289 process0();
290
291 if (!(*circles)[selectedCircle].isIncludeIn(result)) {
292 b1 = selectedCircle;
293 process1();
294 pushFront(selectedCircle);
295 } else {
296 pushBack(selectedCircle);
297 }
298 }
299 }
300 bool isEmpty() const {
301 return first == (last + 1) % enclosedCircles.size();
302 }
303 void pushFront(unsigned c) {
304 first = (first + enclosedCircles.size() - 1) % enclosedCircles.size();
305 enclosedCircles[first] = c;
306 }
307 unsigned popBack() {
308 unsigned result = enclosedCircles[last];
309 last = (last + enclosedCircles.size() - 1) % enclosedCircles.size();
310 return result;
311 }
312 void pushBack(unsigned c) {
313 last = (last + 1) % enclosedCircles.size();
314 enclosedCircles[last] = c;
315 }
316
317 public:
318 OptimumCircleHull() : circles(nullptr), first(0), last(0), b1(0), b2(0) {}
319
320 tlp::Circle<Obj, OTYPE> operator()(const std::vector<tlp::Circle<Obj, OTYPE>> &circlesSet) {
321 circles = &circlesSet;
322 enclosedCircles.resize(circlesSet.size() + 1);
323 first = 0;
324 last = circlesSet.size() - 1;
325
326 for (unsigned i = 0; i < circlesSet.size(); ++i)
327 enclosedCircles[i] = i;
328
329 for (unsigned i = circlesSet.size(); i > 0;) {
330 unsigned idx = tlp::randomUnsignedInteger(i - 1);
331 --i;
332 std::swap(enclosedCircles[idx], enclosedCircles[i]);
333 }
334
335 process0();
336 return result;
337 }
338 };
339 return OptimumCircleHull()(circles);
340}
341
342template <typename Obj, typename OTYPE>
343std::ostream &tlp::operator<<(std::ostream &os, const tlp::Circle<Obj, OTYPE> &a) {
344 os << "((" << a[0] << "," << a[1] << ")," << a.radius << ")";
345 return os;
346}
unsigned int randomUnsignedInteger(unsigned int max)
Returns a random unsigned integer in the range [0, max].
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.