DGtal  0.9.2
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)
36 
37 #define Hull2DHelpers_RECURSES
38 
39 #if !defined Hull2DHelpers_h
40 
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 
76 
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 
468  template<typename TInputPoint>
469  double getThicknessAntipodalPair(const TInputPoint& p, const TInputPoint& q,
470  const TInputPoint& r, const ThicknessDefinition& def);
471 
482  template< typename TInputPoint>
483  double
484  computeHProjDistance(const TInputPoint& a, const TInputPoint& b, const TInputPoint& c, bool& isInside );
485 
486 
497  template< typename TInputPoint>
498  double
499  computeVProjDistance(const TInputPoint& a, const TInputPoint& b, const TInputPoint& c, bool& isInside );
500 
501 
511  template< typename TInputPoint>
512  double
513  computeEuclideanDistance(const TInputPoint& a, const TInputPoint& b, const TInputPoint& c, bool& isInside );
514 
515 
516 
517  } // namespace convexHull2D
518 
519  } // namespace functions
520 
521 } // namespace DGtal
522 
524 // Includes friend functions.
525 #include "DGtal/geometry/tools/MelkmanConvexHull.h"
526 
528 // Includes inline functions.
529 #include "DGtal/geometry/tools/Hull2DHelpers.ih"
530 
531 // //
533 
534 #endif // !defined Hull2DHelpers_h
535 
536 #undef Hull2DHelpers_RECURSES
537 #endif // else defined(Hull2DHelpers_RECURSES)
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...
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 ...
ThicknessDefinition
The 2 thickness definitions.
Definition: Hull2DHelpers.h:78
double getThicknessAntipodalPair(const TInputPoint &p, const TInputPoint &q, const TInputPoint &r, const ThicknessDefinition &def)
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 getAngle(const TInputPoint &a, const TInputPoint &b, const TInputPoint &c, const TInputPoint &d)
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 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 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...
DGtal is the top-level namespace which contains all DGtal functions and types.
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 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...
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...
double computeVProjDistance(const TInputPoint &a, const TInputPoint &b, const TInputPoint &c, bool &isInside)
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...
double computeHProjDistance(const TInputPoint &a, const TInputPoint &b, const TInputPoint &c, bool &isInside)