Horizon
delaunator.hpp
1 #pragma once
2 
3 #ifdef DELAUNATOR_HEADER_ONLY
4 #define INLINE inline
5 #else
6 #define INLINE
7 #endif
8 
9 #include <limits>
10 #include <vector>
11 #include <ostream>
12 
13 namespace delaunator {
14 
15 constexpr std::size_t INVALID_INDEX =
16  (std::numeric_limits<std::size_t>::max)();
17 
18 class Point
19 {
20 public:
21  Point(double x, double y) : m_x(x), m_y(y)
22  {}
23  Point() : m_x(0), m_y(0)
24  {}
25 
26  double x() const
27  { return m_x; }
28 
29  double y() const
30  { return m_y; }
31 
32  double magnitude2() const
33  { return m_x * m_x + m_y * m_y; }
34 
35  static double determinant(const Point& p1, const Point& p2)
36  {
37  return p1.m_x * p2.m_y - p1.m_y * p2.m_x;
38  }
39 
40  static Point vector(const Point& p1, const Point& p2)
41  {
42  return Point(p2.m_x - p1.m_x, p2.m_y - p1.m_y);
43  }
44 
45  static double dist2(const Point& p1, const Point& p2)
46  {
47  Point vec = vector(p1, p2);
48  return vec.m_x * vec.m_x + vec.m_y * vec.m_y;
49  }
50 
51  static bool equal(const Point& p1, const Point& p2, double span)
52  {
53  double dist = dist2(p1, p2) / span;
54 
55  // ABELL - This number should be examined to figure how how
56  // it correlates with the breakdown of calculating determinants.
57  return dist < 1e-20;
58  }
59 
60 private:
61  double m_x;
62  double m_y;
63 };
64 
65 inline std::ostream& operator<<(std::ostream& out, const Point& p)
66 {
67  out << p.x() << "/" << p.y();
68  return out;
69 }
70 
71 
72 class Points
73 {
74 public:
75  using const_iterator = Point const *;
76 
77  Points(const std::vector<double>& coords) : m_coords(coords)
78  {}
79 
80  const Point& operator[](size_t offset)
81  {
82  return reinterpret_cast<const Point&>(
83  *(m_coords.data() + (offset * 2)));
84  };
85 
86  Points::const_iterator begin() const
87  { return reinterpret_cast<const Point *>(m_coords.data()); }
88  Points::const_iterator end() const
89  { return reinterpret_cast<const Point *>(
90  m_coords.data() + m_coords.size()); }
91  size_t size() const
92  { return m_coords.size() / 2; }
93 
94 private:
95  const std::vector<double>& m_coords;
96 };
97 
98 class Delaunator {
99 
100 public:
101  std::vector<double> const& coords;
102  Points m_points;
103 
104  // 'triangles' stores the indices to the 'X's of the input
105  // 'coords'.
106  std::vector<std::size_t> triangles;
107 
108  // 'halfedges' store indices into 'triangles'. If halfedges[X] = Y,
109  // It says that there's an edge from X to Y where a) X and Y are
110  // both indices into triangles and b) X and Y are indices into different
111  // triangles in the array. This allows you to get from a triangle to
112  // its adjacent triangle. If the a triangle edge has no adjacent triangle,
113  // its half edge will be INVALID_INDEX.
114  std::vector<std::size_t> halfedges;
115 
116  std::vector<std::size_t> hull_prev;
117  std::vector<std::size_t> hull_next;
118 
119  // This contains indexes into the triangles array.
120  std::vector<std::size_t> hull_tri;
121  std::size_t hull_start;
122 
123  INLINE Delaunator(std::vector<double> const& in_coords);
124  INLINE double get_hull_area();
125  INLINE double get_triangle_area();
126 
127 private:
128  std::vector<std::size_t> m_hash;
129  Point m_center;
130  std::size_t m_hash_size;
131  std::vector<std::size_t> m_edge_stack;
132 
133  INLINE std::size_t legalize(std::size_t a);
134  INLINE std::size_t hash_key(double x, double y) const;
135  INLINE std::size_t add_triangle(
136  std::size_t i0,
137  std::size_t i1,
138  std::size_t i2,
139  std::size_t a,
140  std::size_t b,
141  std::size_t c);
142  INLINE void link(std::size_t a, std::size_t b);
143 };
144 
145 } //namespace delaunator
146 
147 #undef INLINE
Definition: delaunator.hpp:98
Definition: delaunator.hpp:19
Definition: delaunator.hpp:73