DGtal 1.3.0
Loading...
Searching...
No Matches
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
63namespace 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