Horizon
shapes.h
1 /*
2  * Poly2Tri Copyright (c) 2009-2018, Poly2Tri Contributors
3  * https://github.com/jhasse/poly2tri
4  *
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without modification,
8  * are permitted provided that the following conditions are met:
9  *
10  * * Redistributions of source code must retain the above copyright notice,
11  * this list of conditions and the following disclaimer.
12  * * Redistributions in binary form must reproduce the above copyright notice,
13  * this list of conditions and the following disclaimer in the documentation
14  * and/or other materials provided with the distribution.
15  * * Neither the name of Poly2Tri nor the names of its contributors may be
16  * used to endorse or promote products derived from this software without specific
17  * prior written permission.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
23  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
24  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
26  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
27  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
28  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
29  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30  */
31 
32 // Include guard
33 #ifndef SHAPES_H
34 #define SHAPES_H
35 
36 #include <cmath>
37 #include <cstddef>
38 #include <stdexcept>
39 #include <vector>
40 
41 namespace p2t {
42 
43 struct Edge;
44 
45 struct Point {
46 
47  double x, y;
48 
51  {
52  x = 0.0;
53  y = 0.0;
54  }
55 
57  std::vector<Edge*> edge_list;
58 
60  Point(double x, double y) : x(x), y(y) {}
61 
63  void set_zero()
64  {
65  x = 0.0;
66  y = 0.0;
67  }
68 
70  void set(double x_, double y_)
71  {
72  x = x_;
73  y = y_;
74  }
75 
77  Point operator -() const
78  {
79  Point v;
80  v.set(-x, -y);
81  return v;
82  }
83 
85  void operator +=(const Point& v)
86  {
87  x += v.x;
88  y += v.y;
89  }
90 
92  void operator -=(const Point& v)
93  {
94  x -= v.x;
95  y -= v.y;
96  }
97 
99  void operator *=(double a)
100  {
101  x *= a;
102  y *= a;
103  }
104 
106  double Length() const
107  {
108  return sqrt(x * x + y * y);
109  }
110 
112  double Normalize()
113  {
114  const double len = Length();
115  x /= len;
116  y /= len;
117  return len;
118  }
119 
120 };
121 
122 std::ostream& operator<<(std::ostream&, const Point&);
123 
124 // Represents a simple polygon's edge
125 struct Edge {
126 
127  Point* p, *q;
128 
130  Edge(Point& p1, Point& p2) : p(&p1), q(&p2)
131  {
132  if (p1.y > p2.y) {
133  q = &p1;
134  p = &p2;
135  } else if (p1.y == p2.y) {
136  if (p1.x > p2.x) {
137  q = &p1;
138  p = &p2;
139  } else if (p1.x == p2.x) {
140  // Repeat points
141  throw std::runtime_error("Edge::Edge: p1 == p2");
142  }
143  }
144 
145  q->edge_list.push_back(this);
146  }
147 };
148 
149 // Triangle-based data structures are know to have better performance than quad-edge structures
150 // See: J. Shewchuk, "Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator"
151 // "Triangulations in CGAL"
152 class Triangle {
153 public:
154 
156 Triangle(Point& a, Point& b, Point& c);
157 
162 
163 Point* GetPoint(int index);
164 Point* PointCW(const Point& point);
165 Point* PointCCW(const Point& point);
166 Point* OppositePoint(Triangle& t, const Point& p);
167 
168 Triangle* GetNeighbor(int index);
169 void MarkNeighbor(Point* p1, Point* p2, Triangle* t);
170 void MarkNeighbor(Triangle& t);
171 
172 void MarkConstrainedEdge(int index);
173 void MarkConstrainedEdge(Edge& edge);
174 void MarkConstrainedEdge(Point* p, Point* q);
175 
176 int Index(const Point* p);
177 int EdgeIndex(const Point* p1, const Point* p2);
178 
179 Triangle* NeighborAcross(const Point& point);
180 Triangle* NeighborCW(const Point& point);
181 Triangle* NeighborCCW(const Point& point);
182 bool GetConstrainedEdgeCCW(const Point& p);
183 bool GetConstrainedEdgeCW(const Point& p);
184 void SetConstrainedEdgeCCW(const Point& p, bool ce);
185 void SetConstrainedEdgeCW(const Point& p, bool ce);
186 bool GetDelunayEdgeCCW(const Point& p);
187 bool GetDelunayEdgeCW(const Point& p);
188 void SetDelunayEdgeCCW(const Point& p, bool e);
189 void SetDelunayEdgeCW(const Point& p, bool e);
190 
191 bool Contains(const Point* p);
192 bool Contains(const Edge& e);
193 bool Contains(const Point* p, const Point* q);
194 void Legalize(Point& point);
195 void Legalize(Point& opoint, Point& npoint);
199 void Clear();
200 void ClearNeighbor(const Triangle *triangle);
201 void ClearNeighbors();
202 void ClearDelunayEdges();
203 
204 inline bool IsInterior();
205 inline void IsInterior(bool b);
206 
207 void DebugPrint();
208 
209 bool CircumcicleContains(const Point&) const;
210 
211 private:
212 
213 bool IsCounterClockwise() const;
214 
216 Point* points_[3];
218 Triangle* neighbors_[3];
219 
221 bool interior_;
222 };
223 
224 inline bool cmp(const Point* a, const Point* b)
225 {
226  if (a->y < b->y) {
227  return true;
228  } else if (a->y == b->y) {
229  // Make sure q is point with greater x value
230  if (a->x < b->x) {
231  return true;
232  }
233  }
234  return false;
235 }
236 
238 inline Point operator +(const Point& a, const Point& b)
239 {
240  return Point(a.x + b.x, a.y + b.y);
241 }
242 
244 inline Point operator -(const Point& a, const Point& b)
245 {
246  return Point(a.x - b.x, a.y - b.y);
247 }
248 
250 inline Point operator *(double s, const Point& a)
251 {
252  return Point(s * a.x, s * a.y);
253 }
254 
255 inline bool operator ==(const Point& a, const Point& b)
256 {
257  return a.x == b.x && a.y == b.y;
258 }
259 
260 inline bool operator !=(const Point& a, const Point& b)
261 {
262  return !(a.x == b.x) && !(a.y == b.y);
263 }
264 
266 inline double Dot(const Point& a, const Point& b)
267 {
268  return a.x * b.x + a.y * b.y;
269 }
270 
272 inline double Cross(const Point& a, const Point& b)
273 {
274  return a.x * b.y - a.y * b.x;
275 }
276 
279 inline Point Cross(const Point& a, double s)
280 {
281  return Point(s * a.y, -s * a.x);
282 }
283 
286 inline Point Cross(double s, const Point& a)
287 {
288  return Point(-s * a.y, s * a.x);
289 }
290 
291 inline Point* Triangle::GetPoint(int index)
292 {
293  return points_[index];
294 }
295 
296 inline Triangle* Triangle::GetNeighbor(int index)
297 {
298  return neighbors_[index];
299 }
300 
301 inline bool Triangle::Contains(const Point* p)
302 {
303  return p == points_[0] || p == points_[1] || p == points_[2];
304 }
305 
306 inline bool Triangle::Contains(const Edge& e)
307 {
308  return Contains(e.p) && Contains(e.q);
309 }
310 
311 inline bool Triangle::Contains(const Point* p, const Point* q)
312 {
313  return Contains(p) && Contains(q);
314 }
315 
316 inline bool Triangle::IsInterior()
317 {
318  return interior_;
319 }
320 
321 inline void Triangle::IsInterior(bool b)
322 {
323  interior_ = b;
324 }
325 
327 bool IsDelaunay(const std::vector<p2t::Triangle*>&);
328 
329 }
330 
331 #endif
Definition: shapes.h:152
bool constrained_edge[3]
Flags to determine if an edge is a Constrained edge.
Definition: shapes.h:159
Triangle(Point &a, Point &b, Point &c)
Constructor.
Definition: shapes.cpp:42
bool delaunay_edge[3]
Flags to determine if an edge is a Delauney edge.
Definition: shapes.h:161
void Clear()
Clears all references to all other triangles and points.
Definition: shapes.cpp:82
Sweep-line, Constrained Delauney Triangulation (CDT) See: Domiter, V.
Definition: shapes.cpp:36
Point operator*(double s, const Point &a)
Multiply point by scalar.
Definition: shapes.h:250
double Dot(const Point &a, const Point &b)
Peform the dot product on two vectors.
Definition: shapes.h:266
Point operator+(const Point &a, const Point &b)
Add two points_ component-wise.
Definition: shapes.h:238
bool IsDelaunay(const std::vector< p2t::Triangle * > &triangles)
Is this set a valid delaunay triangulation?
Definition: shapes.cpp:392
Point operator-(const Point &a, const Point &b)
Subtract two points_ component-wise.
Definition: shapes.h:244
double Cross(const Point &a, const Point &b)
Perform the cross product on two vectors. In 2D this produces a scalar.
Definition: shapes.h:272
Definition: shapes.h:125
Edge(Point &p1, Point &p2)
Constructor.
Definition: shapes.h:130
Definition: shapes.h:45
double Length() const
Get the length of this point (the norm).
Definition: shapes.h:106
Point operator-() const
Negate this point.
Definition: shapes.h:77
void operator+=(const Point &v)
Add a point to this point.
Definition: shapes.h:85
std::vector< Edge * > edge_list
The edges this point constitutes an upper ending point.
Definition: shapes.h:57
Point(double x, double y)
Construct using coordinates.
Definition: shapes.h:60
void operator-=(const Point &v)
Subtract a point from this point.
Definition: shapes.h:92
Point()
Default constructor does nothing (for performance).
Definition: shapes.h:50
void operator*=(double a)
Multiply this point by a scalar.
Definition: shapes.h:99
void set(double x_, double y_)
Set this point to some specified coordinates.
Definition: shapes.h:70
void set_zero()
Set this point to all zeros.
Definition: shapes.h:63
double Normalize()
Convert this point into a unit point. Returns the Length.
Definition: shapes.h:112