codac  1.5.7
codac_GrahamScan.h
1 
11 #ifndef __CODAC_GRAHAMSCAN_H__
12 #define __CODAC_GRAHAMSCAN_H__
13 
14 #include <stack>
15 #include "codac_Interval.h"
16 #include "codac_ThickPoint.h"
17 #include "codac_ConvexPolygon.h"
18 
19 namespace codac
20 {
21  enum class OrientationInterval { CLOCKWISE, COUNTERCLOCKWISE, UNDEFINED } ;
22 
23  class GrahamScan
24  {
25  public:
26 
27  // Prints convex hull of a set of n points.
28  static const std::vector<Vector> convex_hull(const std::vector<Vector>& v_points);
29 
30  // A utility function to find next to top in a stack
31  static const Vector next_to_top(const std::stack<Vector>& s);
32 
33  // To find orientation of ordered triplet (p, q, r).
34  static OrientationInterval orientation(const IntervalVector& p0, const IntervalVector& p1, const IntervalVector& p2);
35 
36 
37  protected:
38 
39  // A utility function to swap two points
40  static void swap(Vector& p1, Vector& p2);
41 
42  // A utility function to return square of distance between p1 and p2
43  static const Interval dist(const IntervalVector& p1, const IntervalVector& p2);
44 
45  friend class ThickPointsSorter;
46  friend class ConvexPolygon;
47  };
48 
49  class ThickPointsSorter
50  {
51  public:
52 
53  ThickPointsSorter(const Vector& p0);
54  bool operator()(const Vector& p1, const Vector& p2);
55 
56  protected:
57 
58  Vector m_p0 = Vector(2);
59  };
60 }
61 
62 #endif
FixPoint of a separator The fixpoint of a separator is computed by calling the "::"separate function ...
Definition: codac_capd_helpers.h:9