DGtal  1.5.beta
Hull2DHelpers.h
1 
17 #pragma once
18 
33 #if defined(Hull2DHelpers_RECURSES)
34 #error Recursive header files inclusion detected in Hull2DHelpers.h
35 #else // defined(Hull2DHelpers_RECURSES)
37 #define Hull2DHelpers_RECURSES
38 
39 #if !defined Hull2DHelpers_h
41 #define Hull2DHelpers_h
42 
44 // Inclusions
45 #include <iostream>
46 #include <list>
47 #include <vector>
48 #include "boost/utility.hpp"
49 
50 #include "DGtal/base/Common.h"
51 #include "DGtal/base/IteratorCirculatorTraits.h"
52 #include "DGtal/base/FrontInsertionSequenceToStackAdapter.h"
53 #include "DGtal/base/BackInsertionSequenceToStackAdapter.h"
54 #include "DGtal/base/CStack.h"
55 #include "DGtal/geometry/tools/CPolarPointComparator2D.h"
56 #include "DGtal/geometry/tools/PolarPointComparatorBy2x2DetComputer.h"
57 #include "DGtal/geometry/tools/determinant/COrientationFunctor2.h"
58 #include "DGtal/geometry/tools/determinant/PredicateFromOrientationFunctor2.h"
59 #include "DGtal/geometry/tools/determinant/AvnaimEtAl2x2DetSignComputer.h"
60 #include "DGtal/geometry/tools/determinant/Simple2x2DetComputer.h"
62 
63 namespace DGtal
64 {
65 
66  namespace functions
67  {
73  namespace Hull2D
74  {
75  // used to compare point alignement in computeHullThickness.
76  constexpr double angleTolerance = 1e-6;
79 
80 
98  template <typename Stack,
99  typename Point,
100  typename Predicate>
101  void updateHullWithStack(Stack& aStack,
102  const Point& aNewPoint,
103  const Predicate& aPredicate);
104 
120  template <typename Stack,
121  typename Point,
122  typename Predicate>
123  void updateHullWithAdaptedStack(Stack aStack,
124  const Point& aNewPoint,
125  const Predicate& aPredicate);
126 
144  template <typename Stack,
145  typename ForwardIterator,
146  typename Predicate>
147  void buildHullWithStack(Stack& aStack,
148  const ForwardIterator& itb,
149  const ForwardIterator& ite,
150  const Predicate& aPredicate);
151 
170  template <typename Stack,
171  typename ForwardIterator,
172  typename Predicate>
173  void buildHullWithAdaptedStack(Stack aStack,
174  const ForwardIterator& itb,
175  const ForwardIterator& ite,
176  const Predicate& aPredicate);
177 
192  template <typename ForwardIterator,
193  typename OutputIterator,
194  typename Predicate>
195  void openGrahamScan(const ForwardIterator& itb,
196  const ForwardIterator& ite,
197  OutputIterator res,
198  const Predicate& aPredicate);
199 
217  template <typename ForwardIterator,
218  typename OutputIterator,
219  typename Predicate>
220  void closedGrahamScanFromVertex(const ForwardIterator& itb,
221  const ForwardIterator& ite,
222  OutputIterator res,
223  const Predicate& aPredicate);
224 
242  template <typename ForwardIterator,
243  typename OutputIterator,
244  typename Predicate>
245  void closedGrahamScanFromAnyPoint(const ForwardIterator& itb,
246  const ForwardIterator& ite,
247  OutputIterator res,
248  const Predicate& aPredicate);
249 
281  template <typename ForwardIterator,
282  typename OutputIterator,
283  typename Predicate,
284  typename PolarComparator >
285  void grahamConvexHullAlgorithm(const ForwardIterator& itb,
286  const ForwardIterator& ite,
287  OutputIterator res,
288  const Predicate& aPredicate,
289  PolarComparator& aPolarComparator);
290 
319  template <typename ForwardIterator,
320  typename OutputIterator,
321  typename Predicate,
322  typename PolarComparator >
323  void grahamConvexHullAlgorithm(const ForwardIterator& itb,
324  const ForwardIterator& ite,
325  OutputIterator res,
326  const Predicate& aPredicate);
327 
352  template <typename ForwardIterator,
353  typename OutputIterator,
354  typename Predicate >
355  void andrewConvexHullAlgorithm(const ForwardIterator& itb,
356  const ForwardIterator& ite,
357  OutputIterator res,
358  const Predicate& aPredicate );
359 
360 
390  template <typename ForwardIterator >
391  double computeHullThickness(const ForwardIterator& itb,
392  const ForwardIterator& ite,
393  const ThicknessDefinition& def);
394 
395 
428  template <typename ForwardIterator,
429  typename TInputPoint >
430  double computeHullThickness(const ForwardIterator& itb,
431  const ForwardIterator& ite,
432  const ThicknessDefinition& def,
433  TInputPoint& antipodalEdgeP,
434  TInputPoint& antipodalEdgeQ,
435  TInputPoint& antipodalVertexR);
436 
437 
446  template<typename TInputPoint>
447  inline
448  double getAngle(const TInputPoint& a, const TInputPoint& b,const TInputPoint& c,const TInputPoint& d);
449 
450 
459  template<typename TInputPoint>
460  inline
461  bool isCoLinearOpp(const TInputPoint& a, const TInputPoint& b,
462  const TInputPoint& c, const TInputPoint& d );
463 
464 
465 
466 
485  template<typename TInputPoint>
486  double getThicknessAntipodalPair(const TInputPoint& p, const TInputPoint& q,
487  const TInputPoint& r, const ThicknessDefinition& def);
488 
499  template< typename TInputPoint>
500  double
501  computeHProjDistance(const TInputPoint& a, const TInputPoint& b, const TInputPoint& c, bool& isInside );
502 
503 
514  template< typename TInputPoint>
515  double
516  computeVProjDistance(const TInputPoint& a, const TInputPoint& b, const TInputPoint& c, bool& isInside );
517 
518 
528  template< typename TInputPoint>
529  double
530  computeEuclideanDistance(const TInputPoint& a, const TInputPoint& b, const TInputPoint& c, bool& isInside );
531 
532 
533 
534  } // namespace convexHull2D
535 
536  } // namespace functions
537 
538 } // namespace DGtal
539 
541 // Includes friend functions.
542 #include "DGtal/geometry/tools/MelkmanConvexHull.h"
543 
545 // Includes inline functions.
546 #include "DGtal/geometry/tools/Hull2DHelpers.ih"
547 
548 // //
550 
551 #endif // !defined Hull2DHelpers_h
552 
553 #undef Hull2DHelpers_RECURSES
554 #endif // else defined(Hull2DHelpers_RECURSES)
double computeHProjDistance(const TInputPoint &a, const TInputPoint &b, const TInputPoint &c, bool &isInside)
void buildHullWithStack(Stack &aStack, const ForwardIterator &itb, const ForwardIterator &ite, const Predicate &aPredicate)
Procedure that retrieves the vertices of the convex hull of a weakly externally visible polygon (WEVP...
void andrewConvexHullAlgorithm(const ForwardIterator &itb, const ForwardIterator &ite, OutputIterator res, const Predicate &aPredicate)
Procedure that retrieves the vertices of the hull of a set of 2D points given by the range [ itb ,...
double computeEuclideanDistance(const TInputPoint &a, const TInputPoint &b, const TInputPoint &c, bool &isInside)
void closedGrahamScanFromAnyPoint(const ForwardIterator &itb, const ForwardIterator &ite, OutputIterator res, const Predicate &aPredicate)
Procedure that retrieves the vertices of the convex hull of a weakly externally visible polygon (WEVP...
double computeVProjDistance(const TInputPoint &a, const TInputPoint &b, const TInputPoint &c, bool &isInside)
double getAngle(const TInputPoint &a, const TInputPoint &b, const TInputPoint &c, const TInputPoint &d)
void buildHullWithAdaptedStack(Stack aStack, const ForwardIterator &itb, const ForwardIterator &ite, const Predicate &aPredicate)
Procedure that calls Hull2D::buildHullWithStack on a copy of the stack object used to retrieved the h...
void openGrahamScan(const ForwardIterator &itb, const ForwardIterator &ite, OutputIterator res, const Predicate &aPredicate)
Procedure that retrieves the vertices of the convex hull of a weakly externally visible polygon (WEVP...
double getThicknessAntipodalPair(const TInputPoint &p, const TInputPoint &q, const TInputPoint &r, const ThicknessDefinition &def)
double computeHullThickness(const ForwardIterator &itb, const ForwardIterator &ite, const ThicknessDefinition &def)
Procedure to compute the convex hull thickness given from different definitions (Horizontal/vertical ...
void updateHullWithAdaptedStack(Stack aStack, const Point &aNewPoint, const Predicate &aPredicate)
Procedure that calls Hull2D::updateHullWithStack on a copy of the stack object used to retrieved the ...
void updateHullWithStack(Stack &aStack, const Point &aNewPoint, const Predicate &aPredicate)
Procedure that updates the hull when an extra point aNewPoint is considered: while the last three con...
ThicknessDefinition
The 2 thickness definitions.
Definition: Hull2DHelpers.h:78
constexpr double angleTolerance
Definition: Hull2DHelpers.h:76
void grahamConvexHullAlgorithm(const ForwardIterator &itb, const ForwardIterator &ite, OutputIterator res, const Predicate &aPredicate, PolarComparator &aPolarComparator)
Procedure that retrieves the vertices of the convex hull of a set of 2D points given by the range [ i...
bool isCoLinearOpp(const TInputPoint &a, const TInputPoint &b, const TInputPoint &c, const TInputPoint &d)
void closedGrahamScanFromVertex(const ForwardIterator &itb, const ForwardIterator &ite, OutputIterator res, const Predicate &aPredicate)
Procedure that retrieves the vertices of the convex hull of a weakly externally visible polygon (WEVP...
DGtal is the top-level namespace which contains all DGtal functions and types.
MyPointD Point
Definition: testClone2.cpp:383