]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright 2009 The Trustees of Indiana University. |
2 | ||
3 | // Distributed under the Boost Software License, Version 1.0. | |
4 | // (See accompanying file LICENSE_1_0.txt or copy at | |
5 | // http://www.boost.org/LICENSE_1_0.txt) | |
6 | ||
7 | // Authors: Jeremiah Willcock | |
8 | // Douglas Gregor | |
9 | // Andrew Lumsdaine | |
10 | #ifndef BOOST_GRAPH_TOPOLOGY_HPP | |
11 | #define BOOST_GRAPH_TOPOLOGY_HPP | |
12 | ||
13 | #include <boost/config/no_tr1/cmath.hpp> | |
14 | #include <cmath> | |
15 | #include <boost/random/uniform_01.hpp> | |
16 | #include <boost/random/linear_congruential.hpp> | |
17 | #include <boost/math/constants/constants.hpp> // For root_two | |
18 | #include <boost/algorithm/minmax.hpp> | |
19 | #include <boost/config.hpp> // For BOOST_STATIC_CONSTANT | |
20 | #include <boost/math/special_functions/hypot.hpp> | |
21 | ||
22 | // Classes and concepts to represent points in a space, with distance and move | |
23 | // operations (used for Gurson-Atun layout), plus other things like bounding | |
24 | // boxes used for other layout algorithms. | |
25 | ||
26 | namespace boost { | |
27 | ||
28 | /*********************************************************** | |
29 | * Topologies * | |
30 | ***********************************************************/ | |
31 | template<std::size_t Dims> | |
32 | class convex_topology | |
33 | { | |
34 | public: // For VisualAge C++ | |
35 | struct point | |
36 | { | |
37 | BOOST_STATIC_CONSTANT(std::size_t, dimensions = Dims); | |
38 | point() { } | |
39 | double& operator[](std::size_t i) {return values[i];} | |
40 | const double& operator[](std::size_t i) const {return values[i];} | |
41 | ||
42 | private: | |
43 | double values[Dims]; | |
44 | }; | |
45 | ||
46 | public: // For VisualAge C++ | |
47 | struct point_difference | |
48 | { | |
49 | BOOST_STATIC_CONSTANT(std::size_t, dimensions = Dims); | |
50 | point_difference() { | |
51 | for (std::size_t i = 0; i < Dims; ++i) values[i] = 0.; | |
52 | } | |
53 | double& operator[](std::size_t i) {return values[i];} | |
54 | const double& operator[](std::size_t i) const {return values[i];} | |
55 | ||
56 | friend point_difference operator+(const point_difference& a, const point_difference& b) { | |
57 | point_difference result; | |
58 | for (std::size_t i = 0; i < Dims; ++i) | |
59 | result[i] = a[i] + b[i]; | |
60 | return result; | |
61 | } | |
62 | ||
63 | friend point_difference& operator+=(point_difference& a, const point_difference& b) { | |
64 | for (std::size_t i = 0; i < Dims; ++i) | |
65 | a[i] += b[i]; | |
66 | return a; | |
67 | } | |
68 | ||
69 | friend point_difference operator-(const point_difference& a) { | |
70 | point_difference result; | |
71 | for (std::size_t i = 0; i < Dims; ++i) | |
72 | result[i] = -a[i]; | |
73 | return result; | |
74 | } | |
75 | ||
76 | friend point_difference operator-(const point_difference& a, const point_difference& b) { | |
77 | point_difference result; | |
78 | for (std::size_t i = 0; i < Dims; ++i) | |
79 | result[i] = a[i] - b[i]; | |
80 | return result; | |
81 | } | |
82 | ||
83 | friend point_difference& operator-=(point_difference& a, const point_difference& b) { | |
84 | for (std::size_t i = 0; i < Dims; ++i) | |
85 | a[i] -= b[i]; | |
86 | return a; | |
87 | } | |
88 | ||
89 | friend point_difference operator*(const point_difference& a, const point_difference& b) { | |
90 | point_difference result; | |
91 | for (std::size_t i = 0; i < Dims; ++i) | |
92 | result[i] = a[i] * b[i]; | |
93 | return result; | |
94 | } | |
95 | ||
96 | friend point_difference operator*(const point_difference& a, double b) { | |
97 | point_difference result; | |
98 | for (std::size_t i = 0; i < Dims; ++i) | |
99 | result[i] = a[i] * b; | |
100 | return result; | |
101 | } | |
102 | ||
103 | friend point_difference operator*(double a, const point_difference& b) { | |
104 | point_difference result; | |
105 | for (std::size_t i = 0; i < Dims; ++i) | |
106 | result[i] = a * b[i]; | |
107 | return result; | |
108 | } | |
109 | ||
110 | friend point_difference operator/(const point_difference& a, const point_difference& b) { | |
111 | point_difference result; | |
112 | for (std::size_t i = 0; i < Dims; ++i) | |
113 | result[i] = (b[i] == 0.) ? 0. : a[i] / b[i]; | |
114 | return result; | |
115 | } | |
116 | ||
117 | friend double dot(const point_difference& a, const point_difference& b) { | |
118 | double result = 0; | |
119 | for (std::size_t i = 0; i < Dims; ++i) | |
120 | result += a[i] * b[i]; | |
121 | return result; | |
122 | } | |
123 | ||
124 | private: | |
125 | double values[Dims]; | |
126 | }; | |
127 | ||
128 | public: | |
129 | typedef point point_type; | |
130 | typedef point_difference point_difference_type; | |
131 | ||
132 | double distance(point a, point b) const | |
133 | { | |
134 | double dist = 0.; | |
135 | for (std::size_t i = 0; i < Dims; ++i) { | |
136 | double diff = b[i] - a[i]; | |
137 | dist = boost::math::hypot(dist, diff); | |
138 | } | |
139 | // Exact properties of the distance are not important, as long as | |
140 | // < on what this returns matches real distances; l_2 is used because | |
141 | // Fruchterman-Reingold also uses this code and it relies on l_2. | |
142 | return dist; | |
143 | } | |
144 | ||
145 | point move_position_toward(point a, double fraction, point b) const | |
146 | { | |
147 | point result; | |
148 | for (std::size_t i = 0; i < Dims; ++i) | |
149 | result[i] = a[i] + (b[i] - a[i]) * fraction; | |
150 | return result; | |
151 | } | |
152 | ||
153 | point_difference difference(point a, point b) const { | |
154 | point_difference result; | |
155 | for (std::size_t i = 0; i < Dims; ++i) | |
156 | result[i] = a[i] - b[i]; | |
157 | return result; | |
158 | } | |
159 | ||
160 | point adjust(point a, point_difference delta) const { | |
161 | point result; | |
162 | for (std::size_t i = 0; i < Dims; ++i) | |
163 | result[i] = a[i] + delta[i]; | |
164 | return result; | |
165 | } | |
166 | ||
167 | point pointwise_min(point a, point b) const { | |
168 | BOOST_USING_STD_MIN(); | |
169 | point result; | |
170 | for (std::size_t i = 0; i < Dims; ++i) | |
171 | result[i] = min BOOST_PREVENT_MACRO_SUBSTITUTION (a[i], b[i]); | |
172 | return result; | |
173 | } | |
174 | ||
175 | point pointwise_max(point a, point b) const { | |
176 | BOOST_USING_STD_MAX(); | |
177 | point result; | |
178 | for (std::size_t i = 0; i < Dims; ++i) | |
179 | result[i] = max BOOST_PREVENT_MACRO_SUBSTITUTION (a[i], b[i]); | |
180 | return result; | |
181 | } | |
182 | ||
183 | double norm(point_difference delta) const { | |
184 | double n = 0.; | |
185 | for (std::size_t i = 0; i < Dims; ++i) | |
186 | n = boost::math::hypot(n, delta[i]); | |
187 | return n; | |
188 | } | |
189 | ||
190 | double volume(point_difference delta) const { | |
191 | double n = 1.; | |
192 | for (std::size_t i = 0; i < Dims; ++i) | |
193 | n *= delta[i]; | |
194 | return n; | |
195 | } | |
196 | ||
197 | }; | |
198 | ||
199 | template<std::size_t Dims, | |
200 | typename RandomNumberGenerator = minstd_rand> | |
201 | class hypercube_topology : public convex_topology<Dims> | |
202 | { | |
203 | typedef uniform_01<RandomNumberGenerator, double> rand_t; | |
204 | ||
205 | public: | |
206 | typedef typename convex_topology<Dims>::point_type point_type; | |
207 | typedef typename convex_topology<Dims>::point_difference_type point_difference_type; | |
208 | ||
209 | explicit hypercube_topology(double scaling = 1.0) | |
210 | : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)), | |
211 | scaling(scaling) | |
212 | { } | |
213 | ||
214 | hypercube_topology(RandomNumberGenerator& gen, double scaling = 1.0) | |
215 | : gen_ptr(), rand(new rand_t(gen)), scaling(scaling) { } | |
216 | ||
217 | point_type random_point() const | |
218 | { | |
219 | point_type p; | |
220 | for (std::size_t i = 0; i < Dims; ++i) | |
221 | p[i] = (*rand)() * scaling; | |
222 | return p; | |
223 | } | |
224 | ||
225 | point_type bound(point_type a) const | |
226 | { | |
227 | BOOST_USING_STD_MIN(); | |
228 | BOOST_USING_STD_MAX(); | |
229 | point_type p; | |
230 | for (std::size_t i = 0; i < Dims; ++i) | |
231 | p[i] = min BOOST_PREVENT_MACRO_SUBSTITUTION (scaling, max BOOST_PREVENT_MACRO_SUBSTITUTION (-scaling, a[i])); | |
232 | return p; | |
233 | } | |
234 | ||
235 | double distance_from_boundary(point_type a) const | |
236 | { | |
237 | BOOST_USING_STD_MIN(); | |
238 | BOOST_USING_STD_MAX(); | |
239 | #ifndef BOOST_NO_STDC_NAMESPACE | |
240 | using std::abs; | |
241 | #endif | |
242 | BOOST_STATIC_ASSERT (Dims >= 1); | |
243 | double dist = abs(scaling - a[0]); | |
244 | for (std::size_t i = 1; i < Dims; ++i) | |
245 | dist = min BOOST_PREVENT_MACRO_SUBSTITUTION (dist, abs(scaling - a[i])); | |
246 | return dist; | |
247 | } | |
248 | ||
249 | point_type center() const { | |
250 | point_type result; | |
251 | for (std::size_t i = 0; i < Dims; ++i) | |
252 | result[i] = scaling * .5; | |
253 | return result; | |
254 | } | |
255 | ||
256 | point_type origin() const { | |
257 | point_type result; | |
258 | for (std::size_t i = 0; i < Dims; ++i) | |
259 | result[i] = 0; | |
260 | return result; | |
261 | } | |
262 | ||
263 | point_difference_type extent() const { | |
264 | point_difference_type result; | |
265 | for (std::size_t i = 0; i < Dims; ++i) | |
266 | result[i] = scaling; | |
267 | return result; | |
268 | } | |
269 | ||
270 | private: | |
271 | shared_ptr<RandomNumberGenerator> gen_ptr; | |
272 | shared_ptr<rand_t> rand; | |
273 | double scaling; | |
274 | }; | |
275 | ||
276 | template<typename RandomNumberGenerator = minstd_rand> | |
277 | class square_topology : public hypercube_topology<2, RandomNumberGenerator> | |
278 | { | |
279 | typedef hypercube_topology<2, RandomNumberGenerator> inherited; | |
280 | ||
281 | public: | |
282 | explicit square_topology(double scaling = 1.0) : inherited(scaling) { } | |
283 | ||
284 | square_topology(RandomNumberGenerator& gen, double scaling = 1.0) | |
285 | : inherited(gen, scaling) { } | |
286 | }; | |
287 | ||
288 | template<typename RandomNumberGenerator = minstd_rand> | |
289 | class rectangle_topology : public convex_topology<2> | |
290 | { | |
291 | typedef uniform_01<RandomNumberGenerator, double> rand_t; | |
292 | ||
293 | public: | |
294 | rectangle_topology(double left, double top, double right, double bottom) | |
295 | : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)), | |
296 | left(std::min BOOST_PREVENT_MACRO_SUBSTITUTION (left, right)), | |
297 | top(std::min BOOST_PREVENT_MACRO_SUBSTITUTION (top, bottom)), | |
298 | right(std::max BOOST_PREVENT_MACRO_SUBSTITUTION (left, right)), | |
299 | bottom(std::max BOOST_PREVENT_MACRO_SUBSTITUTION (top, bottom)) { } | |
300 | ||
301 | rectangle_topology(RandomNumberGenerator& gen, double left, double top, double right, double bottom) | |
302 | : gen_ptr(), rand(new rand_t(gen)), | |
303 | left(std::min BOOST_PREVENT_MACRO_SUBSTITUTION (left, right)), | |
304 | top(std::min BOOST_PREVENT_MACRO_SUBSTITUTION (top, bottom)), | |
305 | right(std::max BOOST_PREVENT_MACRO_SUBSTITUTION (left, right)), | |
306 | bottom(std::max BOOST_PREVENT_MACRO_SUBSTITUTION (top, bottom)) { } | |
307 | ||
308 | typedef typename convex_topology<2>::point_type point_type; | |
309 | typedef typename convex_topology<2>::point_difference_type point_difference_type; | |
310 | ||
311 | point_type random_point() const | |
312 | { | |
313 | point_type p; | |
314 | p[0] = (*rand)() * (right - left) + left; | |
315 | p[1] = (*rand)() * (bottom - top) + top; | |
316 | return p; | |
317 | } | |
318 | ||
319 | point_type bound(point_type a) const | |
320 | { | |
321 | BOOST_USING_STD_MIN(); | |
322 | BOOST_USING_STD_MAX(); | |
323 | point_type p; | |
324 | p[0] = min BOOST_PREVENT_MACRO_SUBSTITUTION (right, max BOOST_PREVENT_MACRO_SUBSTITUTION (left, a[0])); | |
325 | p[1] = min BOOST_PREVENT_MACRO_SUBSTITUTION (bottom, max BOOST_PREVENT_MACRO_SUBSTITUTION (top, a[1])); | |
326 | return p; | |
327 | } | |
328 | ||
329 | double distance_from_boundary(point_type a) const | |
330 | { | |
331 | BOOST_USING_STD_MIN(); | |
332 | BOOST_USING_STD_MAX(); | |
333 | #ifndef BOOST_NO_STDC_NAMESPACE | |
334 | using std::abs; | |
335 | #endif | |
336 | double dist = abs(left - a[0]); | |
337 | dist = min BOOST_PREVENT_MACRO_SUBSTITUTION (dist, abs(right - a[0])); | |
338 | dist = min BOOST_PREVENT_MACRO_SUBSTITUTION (dist, abs(top - a[1])); | |
339 | dist = min BOOST_PREVENT_MACRO_SUBSTITUTION (dist, abs(bottom - a[1])); | |
340 | return dist; | |
341 | } | |
342 | ||
343 | point_type center() const { | |
344 | point_type result; | |
345 | result[0] = (left + right) / 2.; | |
346 | result[1] = (top + bottom) / 2.; | |
347 | return result; | |
348 | } | |
349 | ||
350 | point_type origin() const { | |
351 | point_type result; | |
352 | result[0] = left; | |
353 | result[1] = top; | |
354 | return result; | |
355 | } | |
356 | ||
357 | point_difference_type extent() const { | |
358 | point_difference_type result; | |
359 | result[0] = right - left; | |
360 | result[1] = bottom - top; | |
361 | return result; | |
362 | } | |
363 | ||
364 | private: | |
365 | shared_ptr<RandomNumberGenerator> gen_ptr; | |
366 | shared_ptr<rand_t> rand; | |
367 | double left, top, right, bottom; | |
368 | }; | |
369 | ||
370 | template<typename RandomNumberGenerator = minstd_rand> | |
371 | class cube_topology : public hypercube_topology<3, RandomNumberGenerator> | |
372 | { | |
373 | typedef hypercube_topology<3, RandomNumberGenerator> inherited; | |
374 | ||
375 | public: | |
376 | explicit cube_topology(double scaling = 1.0) : inherited(scaling) { } | |
377 | ||
378 | cube_topology(RandomNumberGenerator& gen, double scaling = 1.0) | |
379 | : inherited(gen, scaling) { } | |
380 | }; | |
381 | ||
382 | template<std::size_t Dims, | |
383 | typename RandomNumberGenerator = minstd_rand> | |
384 | class ball_topology : public convex_topology<Dims> | |
385 | { | |
386 | typedef uniform_01<RandomNumberGenerator, double> rand_t; | |
387 | ||
388 | public: | |
389 | typedef typename convex_topology<Dims>::point_type point_type; | |
390 | typedef typename convex_topology<Dims>::point_difference_type point_difference_type; | |
391 | ||
392 | explicit ball_topology(double radius = 1.0) | |
393 | : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)), | |
394 | radius(radius) | |
395 | { } | |
396 | ||
397 | ball_topology(RandomNumberGenerator& gen, double radius = 1.0) | |
398 | : gen_ptr(), rand(new rand_t(gen)), radius(radius) { } | |
399 | ||
400 | point_type random_point() const | |
401 | { | |
402 | point_type p; | |
403 | double dist_sum; | |
404 | do { | |
405 | dist_sum = 0.0; | |
406 | for (std::size_t i = 0; i < Dims; ++i) { | |
407 | double x = (*rand)() * 2*radius - radius; | |
408 | p[i] = x; | |
409 | dist_sum += x * x; | |
410 | } | |
411 | } while (dist_sum > radius*radius); | |
412 | return p; | |
413 | } | |
414 | ||
415 | point_type bound(point_type a) const | |
416 | { | |
417 | BOOST_USING_STD_MIN(); | |
418 | BOOST_USING_STD_MAX(); | |
419 | double r = 0.; | |
420 | for (std::size_t i = 0; i < Dims; ++i) | |
421 | r = boost::math::hypot(r, a[i]); | |
422 | if (r <= radius) return a; | |
423 | double scaling_factor = radius / r; | |
424 | point_type p; | |
425 | for (std::size_t i = 0; i < Dims; ++i) | |
426 | p[i] = a[i] * scaling_factor; | |
427 | return p; | |
428 | } | |
429 | ||
430 | double distance_from_boundary(point_type a) const | |
431 | { | |
432 | double r = 0.; | |
433 | for (std::size_t i = 0; i < Dims; ++i) | |
434 | r = boost::math::hypot(r, a[i]); | |
435 | return radius - r; | |
436 | } | |
437 | ||
438 | point_type center() const { | |
439 | point_type result; | |
440 | for (std::size_t i = 0; i < Dims; ++i) | |
441 | result[i] = 0; | |
442 | return result; | |
443 | } | |
444 | ||
445 | point_type origin() const { | |
446 | point_type result; | |
447 | for (std::size_t i = 0; i < Dims; ++i) | |
448 | result[i] = -radius; | |
449 | return result; | |
450 | } | |
451 | ||
452 | point_difference_type extent() const { | |
453 | point_difference_type result; | |
454 | for (std::size_t i = 0; i < Dims; ++i) | |
455 | result[i] = 2. * radius; | |
456 | return result; | |
457 | } | |
458 | ||
459 | private: | |
460 | shared_ptr<RandomNumberGenerator> gen_ptr; | |
461 | shared_ptr<rand_t> rand; | |
462 | double radius; | |
463 | }; | |
464 | ||
465 | template<typename RandomNumberGenerator = minstd_rand> | |
466 | class circle_topology : public ball_topology<2, RandomNumberGenerator> | |
467 | { | |
468 | typedef ball_topology<2, RandomNumberGenerator> inherited; | |
469 | ||
470 | public: | |
471 | explicit circle_topology(double radius = 1.0) : inherited(radius) { } | |
472 | ||
473 | circle_topology(RandomNumberGenerator& gen, double radius = 1.0) | |
474 | : inherited(gen, radius) { } | |
475 | }; | |
476 | ||
477 | template<typename RandomNumberGenerator = minstd_rand> | |
478 | class sphere_topology : public ball_topology<3, RandomNumberGenerator> | |
479 | { | |
480 | typedef ball_topology<3, RandomNumberGenerator> inherited; | |
481 | ||
482 | public: | |
483 | explicit sphere_topology(double radius = 1.0) : inherited(radius) { } | |
484 | ||
485 | sphere_topology(RandomNumberGenerator& gen, double radius = 1.0) | |
486 | : inherited(gen, radius) { } | |
487 | }; | |
488 | ||
489 | template<typename RandomNumberGenerator = minstd_rand> | |
490 | class heart_topology | |
491 | { | |
492 | // Heart is defined as the union of three shapes: | |
493 | // Square w/ corners (+-1000, -1000), (0, 0), (0, -2000) | |
494 | // Circle centered at (-500, -500) radius 500*sqrt(2) | |
495 | // Circle centered at (500, -500) radius 500*sqrt(2) | |
496 | // Bounding box (-1000, -2000) - (1000, 500*(sqrt(2) - 1)) | |
497 | ||
498 | struct point | |
499 | { | |
500 | point() { values[0] = 0.0; values[1] = 0.0; } | |
501 | point(double x, double y) { values[0] = x; values[1] = y; } | |
502 | ||
503 | double& operator[](std::size_t i) { return values[i]; } | |
504 | double operator[](std::size_t i) const { return values[i]; } | |
505 | ||
506 | private: | |
507 | double values[2]; | |
508 | }; | |
509 | ||
510 | bool in_heart(point p) const | |
511 | { | |
512 | #ifndef BOOST_NO_STDC_NAMESPACE | |
513 | using std::abs; | |
514 | #endif | |
515 | ||
516 | if (p[1] < abs(p[0]) - 2000) return false; // Bottom | |
517 | if (p[1] <= -1000) return true; // Diagonal of square | |
518 | if (boost::math::hypot(p[0] - -500, p[1] - -500) <= 500. * boost::math::constants::root_two<double>()) | |
519 | return true; // Left circle | |
520 | if (boost::math::hypot(p[0] - 500, p[1] - -500) <= 500. * boost::math::constants::root_two<double>()) | |
521 | return true; // Right circle | |
522 | return false; | |
523 | } | |
524 | ||
525 | bool segment_within_heart(point p1, point p2) const | |
526 | { | |
527 | // Assumes that p1 and p2 are within the heart | |
528 | if ((p1[0] < 0) == (p2[0] < 0)) return true; // Same side of symmetry line | |
529 | if (p1[0] == p2[0]) return true; // Vertical | |
530 | double slope = (p2[1] - p1[1]) / (p2[0] - p1[0]); | |
531 | double intercept = p1[1] - p1[0] * slope; | |
532 | if (intercept > 0) return false; // Crosses between circles | |
533 | return true; | |
534 | } | |
535 | ||
536 | typedef uniform_01<RandomNumberGenerator, double> rand_t; | |
537 | ||
538 | public: | |
539 | typedef point point_type; | |
540 | ||
541 | heart_topology() | |
542 | : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)) { } | |
543 | ||
544 | heart_topology(RandomNumberGenerator& gen) | |
545 | : gen_ptr(), rand(new rand_t(gen)) { } | |
546 | ||
547 | point random_point() const | |
548 | { | |
549 | point result; | |
550 | do { | |
551 | result[0] = (*rand)() * (1000 + 1000 * boost::math::constants::root_two<double>()) - (500 + 500 * boost::math::constants::root_two<double>()); | |
552 | result[1] = (*rand)() * (2000 + 500 * (boost::math::constants::root_two<double>() - 1)) - 2000; | |
553 | } while (!in_heart(result)); | |
554 | return result; | |
555 | } | |
556 | ||
557 | // Not going to provide clipping to bounding region or distance from boundary | |
558 | ||
559 | double distance(point a, point b) const | |
560 | { | |
561 | if (segment_within_heart(a, b)) { | |
562 | // Straight line | |
563 | return boost::math::hypot(b[0] - a[0], b[1] - a[1]); | |
564 | } else { | |
565 | // Straight line bending around (0, 0) | |
566 | return boost::math::hypot(a[0], a[1]) + boost::math::hypot(b[0], b[1]); | |
567 | } | |
568 | } | |
569 | ||
570 | point move_position_toward(point a, double fraction, point b) const | |
571 | { | |
572 | if (segment_within_heart(a, b)) { | |
573 | // Straight line | |
574 | return point(a[0] + (b[0] - a[0]) * fraction, | |
575 | a[1] + (b[1] - a[1]) * fraction); | |
576 | } else { | |
577 | double distance_to_point_a = boost::math::hypot(a[0], a[1]); | |
578 | double distance_to_point_b = boost::math::hypot(b[0], b[1]); | |
579 | double location_of_point = distance_to_point_a / | |
580 | (distance_to_point_a + distance_to_point_b); | |
581 | if (fraction < location_of_point) | |
582 | return point(a[0] * (1 - fraction / location_of_point), | |
583 | a[1] * (1 - fraction / location_of_point)); | |
584 | else | |
585 | return point( | |
586 | b[0] * ((fraction - location_of_point) / (1 - location_of_point)), | |
587 | b[1] * ((fraction - location_of_point) / (1 - location_of_point))); | |
588 | } | |
589 | } | |
590 | ||
591 | private: | |
592 | shared_ptr<RandomNumberGenerator> gen_ptr; | |
593 | shared_ptr<rand_t> rand; | |
594 | }; | |
595 | ||
596 | } // namespace boost | |
597 | ||
598 | #endif // BOOST_GRAPH_TOPOLOGY_HPP |