Horizon
Loading...
Searching...
No Matches
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
13namespace delaunator {
14
15constexpr std::size_t INVALID_INDEX =
16 (std::numeric_limits<std::size_t>::max)();
17
18class Point
19{
20public:
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
60private:
61 double m_x;
62 double m_y;
63};
64
65inline std::ostream& operator<<(std::ostream& out, const Point& p)
66{
67 out << p.x() << "/" << p.y();
68 return out;
69}
70
71
72class Points
73{
74public:
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
94private:
95 const std::vector<double>& m_coords;
96};
97
99
100public:
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
127private:
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