Jpp test-rotations-old
the software that should make you happy
Loading...
Searching...
No Matches
JGeometry2DToolkit.hh
Go to the documentation of this file.
1#ifndef __JGEOMETRY2DTOOLKIT__
2#define __JGEOMETRY2DTOOLKIT__
3
4#include <utility>
5#include <algorithm>
6#include <limits>
7
10
11
12/**
13 * \author mdejong
14 */
15
16/**
17 * Auxiliary classes and methods for 2D geometrical objects and operations.
18 */
19namespace JGEOMETRY2D {}
20namespace JPP { using namespace JGEOMETRY2D; }
21
22namespace JGEOMETRY2D {
23
25
26
27 /**
28 * Check sequence of three points in X-Y plane.
29 *
30 * \param a 1st point
31 * \param b 2nd point
32 * \param c 3rd point
33 * \return true if points a, b, c are counter clockwise; else false
34 */
35 template<class T>
36 inline bool getCCW(const T& a,
37 const T& b,
38 const T& c)
39 {
40 const double A = a.getX() - b.getX();
41 const double B = a.getY() - b.getY();
42 const double C = c.getX() - b.getX();
43 const double D = c.getY() - b.getY();
44
45 return A*D <= B*C;
46 }
47
48
49 /**
50 * Center.
51 */
52 class JCenter2D :
53 public JVector2D
54 {
55 public:
56 /**
57 * Constructor.
58 *
59 * \param p0 first point
60 * \param p1 second point
61 */
63 const JVector2D& p1) :
64 JVector2D()
65 {
66 add(p0);
67 add(p1);
68
69 div(2);
70 }
71
72
73 /**
74 * Constructor.
75 *
76 * \param p0 first point
77 * \param p1 second point
78 * \param p2 third point
79 */
81 const JVector2D& p1,
82 const JVector2D& p2) :
83 JVector2D()
84 {
85 add(p0);
86 add(p1);
87 add(p2);
88
89 div(3);
90 }
91
92
93 /**
94 * Constructor.
95 *
96 * \param __begin begin of data
97 * \param __end end of data
98 */
99 template<class T>
100 JCenter2D(T __begin,
101 T __end) :
102 JVector2D()
103 {
104 if (__begin != __end) {
105
106 for (T i = __begin; i != __end; ++i) {
107 add(*i);
108 }
109
110 div(std::distance(__begin, __end));
111 }
112 }
113 };
114
115
116 /**
117 * Auxiliary class for convex hull determination in X-Y plane.
118 */
120 protected:
121 /**
122 * Partition half Hull.
123 *
124 * \param __begin begin of data
125 * \param __end end of data
126 * \param compare comparator
127 * \return end of data
128 */
129 template<class T, class JCompare_t>
130 static inline T getConvexHull2D(T __begin,
131 T __end,
132 JCompare_t compare)
133 {
134 using namespace std;
135
136 if (__begin != __end) {
137
138 sort(__begin, __end, compare);
139
140 T l = __begin;
141
142 if (++l != __end) {
143
144 T i = __begin;
145
146 ++(++i);
147
148 for (T j, k; i != __end; ++i) {
149
150 for (j = k = l; j != __begin && getCCW(*i, *j, *--k); --j) {}
151
152 l = j;
153 ++l;
154
155 iter_swap(l,i);
156 }
157 }
158
159 return l;
160
161 } else {
162
163 return __begin;
164 }
165 }
166
167
168 /**
169 * Auxiliary class for sorting elements.
170 */
171 struct JLowerHull {
172 /**
173 * Sort criterion for lower hull.
174 *
175 * \param first first point
176 * \param second second point
177 * \return true if first before second; else false
178 */
179 template<class T>
180 inline bool operator()(const T& first, const T& second) const
181 {
182 if (first.getX() == second.getX())
183 return second.getY() > first.getY();
184 else
185 return first.getX() > second.getX();
186 }
187 };
188
189
190 /**
191 * Auxiliary class for sorting elements.
192 */
193 struct JUpperHull {
194 /**
195 * Sort criterion for upper hull.
196 *
197 * \param first first point
198 * \param second second point
199 * \return true if first before second; else false
200 */
201 template<class T>
202 inline bool operator()(const T& first, const T& second) const
203 {
204 if (first.getX() == second.getX())
205 return second.getY() < first.getY();
206 else
207 return first.getX() < second.getX();
208 }
209 };
210
211
212 public:
213 /**
214 * Default constructor.
215 */
218
219
220 static const JLowerHull sortLowerHull; //!< Function object for sorting elements.
221 static const JUpperHull sortUpperHull; //!< Function object for sorting elements.
222
223
224 /**
225 * Get convex Hull.
226 *
227 * \param __begin begin of data
228 * \param __end end of data
229 * \return end of lower and upper Hull data
230 */
231 template<class T>
232 inline std::pair<T,T> operator()(T __begin, T __end) const
233 {
234 using namespace std;
235
236 T __p = getConvexHull2D(__begin, __end, sortLowerHull); // make lower hull
237
238 if (__p == __begin || __p == __end) {
239 return make_pair(__p, __p);
240 }
241
242 // add first point of lower hull to upper hull
243
244 reverse(__begin, __p);
245
246 T __q = getConvexHull2D(--__p, __end, sortUpperHull); // make upper hull
247
248 ++__q;
249
250 // re-store order and keep the extra point
251
252 reverse(__p, __q);
253 reverse(__begin, __q);
254
255 const int n = distance(__p, __q);
256
257 __p = __begin;
258
259 advance(__p, n);
260
261 return make_pair(__p, __q);
262 }
263 };
264
265
266 /**
267 * Function object for convex hull determination.
268 */
270
271
272 /**
273 * Get area of a convex polygon.
274 *
275 * \param __begin begin of data
276 * \param __end end of data
277 * \return area
278 */
279 template<class T>
280 inline double getArea2D(T __begin, T __end)
281 {
282 using namespace std;
283
284 if (distance(__begin,__end) >= 3) {
285
286 double A = 0.0;
287
288 T i, j, k;
289
290 i = j = k = __begin;
291
292 for (++j, ++(++k); k != __end; ++i, ++j, ++k) {
293 A += j->getX() * (k->getY() - i->getY());
294 }
295
296 k = __begin;
297
298 A += j->getX() * (k->getY() - i->getY());
299
300 ++i;
301 j = k;
302 ++k;
303
304 A += j->getX() * (k->getY() - i->getY());
305
306 return 0.5 * fabs(A);
307
308 } else {
309
310 return 0.0;
311 }
312 }
313
314
315 /**
316 * Check if given point is inside a convex polygon.
317 *
318 * \param __begin begin of data
319 * \param __end end of data
320 * \param pos position
321 * \return true if inside; else false
322 */
323 template<class T>
324 inline bool inside2D(T __begin, T __end, const JVector2D& pos)
325 {
326 using namespace std;
327
328 if (distance(__begin,__end) >= 2) {
329
330 T i = __begin, j = __begin;
331
332 for (++j; j != __end; ++i, ++j) {
333
334 if (!getCCW(*i, *j, pos)) {
335 return false;
336 }
337 }
338
339 j = __begin;
340
341 return getCCW(*i, *j, pos);
342
343 } else {
344
345 return false;
346 }
347 }
348
349
350 /**
351 * Check if given point is inside a convex polygon.
352 *
353 * \param __begin begin of data
354 * \param __end1 end of lower hull
355 * \param __end2 end of upper hull
356 * \param pos position
357 * \return true if inside; else false
358 */
359 template<class T>
360 inline bool inside2D(T __begin, T __end1, T __end2, const JVector2D& pos)
361 {
362 using namespace std;
363
364 if (distance(__begin,__end2) >= 3) {
365
366 if (pos.getX() < __begin->getX()) {
367 return false;
368 }
369
370 T i = lower_bound(__begin, __end1, pos, JConvexHull2D::sortUpperHull);
371
372 if (i == __end1) {
373 return false;
374 }
375
376 T j = i--;
377
378 if (!getCCW(*i, *j, pos)) {
379 return false;
380 }
381
382 i = lower_bound(__end1, __end2, pos, JConvexHull2D::sortLowerHull);
383 j = i--;
384
385 if (j == __end2) {
386 j = __begin;
387 }
388
389 return getCCW(*i, *j, pos);
390
391 } else {
392
393 return false;
394 }
395 }
396
397
398 /**
399 * Auxiliary class for determination of smallest distance between pair of 2D points.
400 *
401 * Reference:
402 * Computational Geometry
403 * Algorithms and Applications
404 * Authors: de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.
405 */
407 protected:
408 /**
409 * Get distance beween the closest points within a strip around the median in x.\n
410 * Note that this method runs not at O(n^2) but at O(6)!
411 *
412 * \param __begin begin of data
413 * \param __end end of data
414 * \param delta width of strip
415 * \return minimal distance
416 */
417 template<class T>
418 static double getDmin(T __begin, T __end, const double delta)
419 {
420 using namespace std;
421
422 double Dmin = delta;
423
424 sort(__begin, __end, compareY);
425
426 for (T i = __begin; i != __end; ++i) {
427 for (T j = i; ++j != __end && (j->getY() - i->getY()) < Dmin; ) {
428
429 const double d = getDistance(*i, *j);
430
431 if (d < Dmin) {
432 Dmin = d;
433 }
434 }
435 }
436
437 sort(__begin, __end, compareX);
438
439 return Dmin;
440 }
441
442
443 /**
444 * Recursive method to find the smallest distance.
445 *
446 * \param __begin begin of data
447 * \param __end end of data
448 * \return minimal distance
449 */
450 template<class T>
451 static double getDmin(T __begin, T __end)
452 {
453 using namespace std;
454
455 const int N = distance(__begin, __end);
456
457 if (N <= 3) {
458
459 double Dmin = numeric_limits<double>::max();
460
461 for (T i = __begin; i != __end; ++i) {
462 for (T j = i; ++j != __end; ) {
463
464 const double d = getDistance(*i, *j);
465
466 if (d < Dmin) {
467 Dmin = d;
468 }
469 }
470 }
471
472 return Dmin;
473
474 } else {
475
476 T i = __begin;
477
478 advance(i, N/2);
479
480 const double dl = getDmin(__begin, i);
481 const double dr = getDmin(i, __end);
482
483 const double Dmin = min(dl, dr);
484
485 T il = i;
486 T ir = i;
487
488 while (--il != __begin && i ->getX() - il->getX() < Dmin) {}
489 while (++ir != __end && ir->getX() - i ->getX() < Dmin) {}
490
491 return min(Dmin, getDmin(++il, ir, Dmin));
492 }
493 }
494
495
496 /**
497 * Auxiliary class for sorting elements.
498 */
499 struct JCompareX {
500 /**
501 * Compare x-positions of given points.
502 *
503 * \param first first point
504 * \param second second point
505 * \return true if x of first point less than that of second; else false
506 */
507 template<class T>
508 inline bool operator()(const T& first, const T& second) const
509 {
510 return first.getX() < second.getX();
511 }
512 };
513
514
515 /**
516 * Auxiliary class for sorting elements.
517 */
518 struct JCompareY {
519 /**
520 * Compare y-positions of given points.
521 *
522 * \param first first point
523 * \param second second point
524 * \return true if y of first point less than that of second; else false
525 */
526 template<class T>
527 inline bool operator()(const T& first, const T& second) const
528 {
529 return first.getY() < second.getY();
530 }
531 };
532
533
534 public:
535 /**
536 * Default constructor.
537 */
540
541
542 static const JCompareX compareX; //!< Function object for sorting elements.
543 static const JCompareY compareY; //!< Function object for sorting elements.
544
545
546 /**
547 * Get smallest distance between two points.\n
548 * Note that this method changes the order of the elements.
549 *
550 * \param __begin begin of data
551 * \param __end end of data
552 * \return minimal distance
553 */
554 template<class T>
555 double operator()(T __begin, T __end) const
556 {
557 using namespace std;
558
559 sort(__begin, __end, compareX);
560
561 return getDmin(__begin, __end);
562 }
563
564
565 /**
566 * Get distance beween the closest points within a strip around the median in z.\n
567 * Note that this method changes the order of the elements.
568 *
569 * \param __begin begin of data
570 * \param __end end of data
571 * \param delta width of strip
572 * \return minimal distance
573 */
574 template<class T>
575 double operator()(T __begin, T __end, const double delta) const
576 {
577 using namespace std;
578
579 double Dmin = delta;
580
581 sort(__begin, __end, compareX);
582
583 for (T i = __begin; i != __end; ) {
584
585 T j = i;
586
587 for ( ; ++j != __end && (j->getX() - i->getX()) < Dmin; ) {}
588
589 const double d = getDmin(i, j);
590
591 if (d < Dmin) {
592 Dmin = d;
593 }
594
595 i = j;
596 }
597
598 return Dmin;
599 }
600
601
602 /**
603 * Get pairs with smaller or equal given maximal distance.\n
604 * Note that this method changes the order of the elements.
605 *
606 * \param __begin begin of data
607 * \param __end end of data
608 * \param Dmax maximal distance
609 * \return pair of elements
610 */
611 template<class T>
612 static inline std::pair<T,T> getPair(T __begin, T __end, const double Dmax)
613 {
614 using namespace std;
615
616 sort(__begin, __end, compareX);
617
618 for (T i = __begin; i != __end; ++i) {
619
620 T j = i;
621
622 while (++j != __end && (j->getX() - i->getX()) <= Dmax) {}
623
624 if (distance(i,j) != 1) {
625
626 if (distance(i,j) == 2) {
627
628 if (getDistance(*i, *--j) <= Dmax) {
629 return make_pair(i,j);
630 }
631
632 } else {
633
634 sort(i, j, compareY);
635
636 for (T __i = i; __i != j; ++__i) {
637 for (T __j = __i; ++__j != j && (__j->getY() - __i->getY()) <= Dmax; ) {
638
639 const double d = getDistance(*__i, *__j);
640
641 if (d <= Dmax) {
642 return make_pair(__i,__j);
643 }
644 }
645 }
646
647 sort(i, j, compareX);
648 }
649 }
650 }
651
652 return make_pair(__end,__end);
653 }
654 };
655
656
657 /**
658 * Function object for smallest distance determination.
659 */
661}
662
663#endif
TPaveText * p1
Auxiliary methods for geometrical methods.
std::vector< T >::difference_type distance(typename std::vector< T >::const_iterator first, typename PhysicsEvent::const_iterator< T > second)
Specialisation of STL distance.
JCenter2D(const JVector2D &p0, const JVector2D &p1, const JVector2D &p2)
Constructor.
JCenter2D(const JVector2D &p0, const JVector2D &p1)
Constructor.
JCenter2D(T __begin, T __end)
Constructor.
Auxiliary class for convex hull determination in X-Y plane.
JConvexHull2D()
Default constructor.
static T getConvexHull2D(T __begin, T __end, JCompare_t compare)
Partition half Hull.
static const JUpperHull sortUpperHull
Function object for sorting elements.
static const JLowerHull sortLowerHull
Function object for sorting elements.
std::pair< T, T > operator()(T __begin, T __end) const
Get convex Hull.
Auxiliary class for determination of smallest distance between pair of 2D points.
static double getDmin(T __begin, T __end, const double delta)
Get distance beween the closest points within a strip around the median in x.
static const JCompareY compareY
Function object for sorting elements.
static double getDmin(T __begin, T __end)
Recursive method to find the smallest distance.
static const JCompareX compareX
Function object for sorting elements.
JSmallestDistance2D()
Default constructor.
double operator()(T __begin, T __end, const double delta) const
Get distance beween the closest points within a strip around the median in z.
static std::pair< T, T > getPair(T __begin, T __end, const double Dmax)
Get pairs with smaller or equal given maximal distance.
double operator()(T __begin, T __end) const
Get smallest distance between two points.
Data structure for vector in two dimensions.
Definition JVector2D.hh:34
double getX() const
Get x position.
Definition JVector2D.hh:63
JVector2D & div(const double factor)
Scale vector.
Definition JVector2D.hh:145
JVector2D & add(const JVector2D &vector)
Add vector.
Definition JVector2D.hh:100
Auxiliary classes and methods for 2D geometrical objects and operations.
Definition JAngle2D.hh:19
static const JConvexHull2D getConvexHull2D
Function object for convex hull determination.
bool getCCW(const T &a, const T &b, const T &c)
Check sequence of three points in X-Y plane.
static const JSmallestDistance2D getSmallestDistance2D
Function object for smallest distance determination.
double getArea2D(T __begin, T __end)
Get area of a convex polygon.
bool inside2D(T __begin, T __end, const JVector2D &pos)
Check if given point is inside a convex polygon.
double getDistance(const JFirst_t &first, const JSecond_t &second)
Get distance between objects.
This name space includes all other name spaces (except KM3NETDAQ, KM3NET and ANTARES).
Auxiliary class for sorting elements.
bool operator()(const T &first, const T &second) const
Sort criterion for lower hull.
Auxiliary class for sorting elements.
bool operator()(const T &first, const T &second) const
Sort criterion for upper hull.
Auxiliary class for sorting elements.
bool operator()(const T &first, const T &second) const
Compare x-positions of given points.
Auxiliary class for sorting elements.
bool operator()(const T &first, const T &second) const
Compare y-positions of given points.