Horizon
Loading...
Searching...
No Matches
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
41namespace p2t {
42
43struct Edge;
44
45struct 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
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
122std::ostream& operator<<(std::ostream&, const Point&);
123
124// Represents a simple polygon's edge
125struct 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"
152class Triangle {
153public:
154
156Triangle(Point& a, Point& b, Point& c);
157
162
163Point* GetPoint(int index);
164Point* PointCW(const Point& point);
165Point* PointCCW(const Point& point);
166Point* OppositePoint(Triangle& t, const Point& p);
167
168Triangle* GetNeighbor(int index);
169void MarkNeighbor(Point* p1, Point* p2, Triangle* t);
170void MarkNeighbor(Triangle& t);
171
172void MarkConstrainedEdge(int index);
173void MarkConstrainedEdge(Edge& edge);
174void MarkConstrainedEdge(Point* p, Point* q);
175
176int Index(const Point* p);
177int EdgeIndex(const Point* p1, const Point* p2);
178
179Triangle* NeighborAcross(const Point& point);
180Triangle* NeighborCW(const Point& point);
181Triangle* NeighborCCW(const Point& point);
182bool GetConstrainedEdgeCCW(const Point& p);
183bool GetConstrainedEdgeCW(const Point& p);
184void SetConstrainedEdgeCCW(const Point& p, bool ce);
185void SetConstrainedEdgeCW(const Point& p, bool ce);
186bool GetDelunayEdgeCCW(const Point& p);
187bool GetDelunayEdgeCW(const Point& p);
188void SetDelunayEdgeCCW(const Point& p, bool e);
189void SetDelunayEdgeCW(const Point& p, bool e);
190
191bool Contains(const Point* p);
192bool Contains(const Edge& e);
193bool Contains(const Point* p, const Point* q);
194void Legalize(Point& point);
195void Legalize(Point& opoint, Point& npoint);
199void Clear();
200void ClearNeighbor(const Triangle *triangle);
201void ClearNeighbors();
202void ClearDelunayEdges();
203
204inline bool IsInterior();
205inline void IsInterior(bool b);
206
207void DebugPrint();
208
209bool CircumcicleContains(const Point&) const;
210
211private:
212
213bool IsCounterClockwise() const;
214
216Point* points_[3];
218Triangle* neighbors_[3];
219
221bool interior_;
222};
223
224inline 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
238inline Point operator +(const Point& a, const Point& b)
239{
240 return Point(a.x + b.x, a.y + b.y);
241}
242
244inline Point operator -(const Point& a, const Point& b)
245{
246 return Point(a.x - b.x, a.y - b.y);
247}
248
250inline Point operator *(double s, const Point& a)
251{
252 return Point(s * a.x, s * a.y);
253}
254
255inline bool operator ==(const Point& a, const Point& b)
256{
257 return a.x == b.x && a.y == b.y;
258}
259
260inline bool operator !=(const Point& a, const Point& b)
261{
262 return !(a.x == b.x) && !(a.y == b.y);
263}
264
266inline double Dot(const Point& a, const Point& b)
267{
268 return a.x * b.x + a.y * b.y;
269}
270
272inline double Cross(const Point& a, const Point& b)
273{
274 return a.x * b.y - a.y * b.x;
275}
276
279inline Point Cross(const Point& a, double s)
280{
281 return Point(s * a.y, -s * a.x);
282}
283
286inline Point Cross(double s, const Point& a)
287{
288 return Point(-s * a.y, s * a.x);
289}
290
291inline Point* Triangle::GetPoint(int index)
292{
293 return points_[index];
294}
295
296inline Triangle* Triangle::GetNeighbor(int index)
297{
298 return neighbors_[index];
299}
300
301inline bool Triangle::Contains(const Point* p)
302{
303 return p == points_[0] || p == points_[1] || p == points_[2];
304}
305
306inline bool Triangle::Contains(const Edge& e)
307{
308 return Contains(e.p) && Contains(e.q);
309}
310
311inline bool Triangle::Contains(const Point* p, const Point* q)
312{
313 return Contains(p) && Contains(q);
314}
315
316inline bool Triangle::IsInterior()
317{
318 return interior_;
319}
320
321inline void Triangle::IsInterior(bool b)
322{
323 interior_ = b;
324}
325
327bool 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
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