1/*
2 * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
3 * http://code.google.com/p/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 <vector>
37#include <cstddef>
38#include <assert.h>
39#include <cmath>
40
41namespace p2t {
42
43struct Edge;
44
45struct Point {
46
47 double x, y;
48
49 /// Default constructor does nothing (for performance).
50 Point()
51 {
52 x = 0.0;
53 y = 0.0;
54 }
55
56 /// The edges this point constitutes an upper ending point
57 std::vector<Edge*> edge_list;
58
59 /// Construct using coordinates.
60 Point(double x, double y) : x(x), y(y) {}
61
62 /// Set this point to all zeros.
63 void set_zero()
64 {
65 x = 0.0;
66 y = 0.0;
67 }
68
69 /// Set this point to some specified coordinates.
70 void set(double x_, double y_)
71 {
72 x = x_;
73 y = y_;
74 }
75
76 /// Negate this point.
77 Point operator -() const
78 {
79 Point v;
80 v.set(x_: -x, y_: -y);
81 return v;
82 }
83
84 /// Add a point to this point.
85 void operator +=(const Point& v)
86 {
87 x += v.x;
88 y += v.y;
89 }
90
91 /// Subtract a point from this point.
92 void operator -=(const Point& v)
93 {
94 x -= v.x;
95 y -= v.y;
96 }
97
98 /// Multiply this point by a scalar.
99 void operator *=(double a)
100 {
101 x *= a;
102 y *= a;
103 }
104
105 /// Get the length of this point (the norm).
106 double Length() const
107 {
108 return std::sqrt(x: x * x + y * y);
109 }
110
111 /// Convert this point into a unit point. Returns the Length.
112 double Normalize()
113 {
114 double len = Length();
115 x /= len;
116 y /= len;
117 return len;
118 }
119
120};
121
122// Represents a simple polygon's edge
123struct Edge {
124
125 Point* p, *q;
126
127 /// Constructor
128 Edge(Point& p1, Point& p2) : p(&p1), q(&p2)
129 {
130 if (p1.y > p2.y) {
131 q = &p1;
132 p = &p2;
133 } else if (p1.y == p2.y) {
134 if (p1.x > p2.x) {
135 q = &p1;
136 p = &p2;
137 } else if (p1.x == p2.x) {
138 // Repeat points
139 assert(false);
140 }
141 }
142
143 q->edge_list.push_back(x: this);
144 }
145};
146
147// Triangle-based data structures are know to have better performance than quad-edge structures
148// See: J. Shewchuk, "Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator"
149// "Triangulations in CGAL"
150class Triangle {
151public:
152
153/// Constructor
154Triangle(Point& a, Point& b, Point& c);
155
156/// Flags to determine if an edge is a Constrained edge
157bool constrained_edge[3];
158/// Flags to determine if an edge is a Delauney edge
159bool delaunay_edge[3];
160
161Point* GetPoint(const int& index);
162Point* PointCW(Point& point);
163Point* PointCCW(Point& point);
164Point* OppositePoint(Triangle& t, Point& p);
165
166Triangle* GetNeighbor(const int& index);
167void MarkNeighbor(Point* p1, Point* p2, Triangle* t);
168void MarkNeighbor(Triangle& t);
169
170void MarkConstrainedEdge(const int index);
171void MarkConstrainedEdge(Edge& edge);
172void MarkConstrainedEdge(Point* p, Point* q);
173
174int Index(const Point* p);
175int EdgeIndex(const Point* p1, const Point* p2);
176
177Triangle* NeighborCW(Point& point);
178Triangle* NeighborCCW(Point& point);
179bool GetConstrainedEdgeCCW(Point& p);
180bool GetConstrainedEdgeCW(Point& p);
181void SetConstrainedEdgeCCW(Point& p, bool ce);
182void SetConstrainedEdgeCW(Point& p, bool ce);
183bool GetDelunayEdgeCCW(Point& p);
184bool GetDelunayEdgeCW(Point& p);
185void SetDelunayEdgeCCW(Point& p, bool e);
186void SetDelunayEdgeCW(Point& p, bool e);
187
188bool Contains(Point* p);
189bool Contains(const Edge& e);
190bool Contains(Point* p, Point* q);
191void Legalize(Point& point);
192void Legalize(Point& opoint, Point& npoint);
193/**
194 * Clears all references to all other triangles and points
195 */
196void Clear();
197void ClearNeighbor(Triangle *triangle );
198void ClearNeighbors();
199void ClearDelunayEdges();
200
201inline bool IsInterior();
202inline void IsInterior(bool b);
203
204Triangle& NeighborAcross(Point& opoint);
205
206void DebugPrint();
207
208private:
209
210/// Triangle points
211Point* points_[3];
212/// Neighbor list
213Triangle* neighbors_[3];
214
215/// Has this triangle been marked as an interior triangle?
216bool interior_;
217};
218
219inline bool cmp(const Point* a, const Point* b)
220{
221 if (a->y < b->y) {
222 return true;
223 } else if (a->y == b->y) {
224 // Make sure q is point with greater x value
225 if (a->x < b->x) {
226 return true;
227 }
228 }
229 return false;
230}
231
232/// Add two points_ component-wise.
233inline Point operator +(const Point& a, const Point& b)
234{
235 return Point(a.x + b.x, a.y + b.y);
236}
237
238/// Subtract two points_ component-wise.
239inline Point operator -(const Point& a, const Point& b)
240{
241 return Point(a.x - b.x, a.y - b.y);
242}
243
244/// Multiply point by scalar
245inline Point operator *(double s, const Point& a)
246{
247 return Point(s * a.x, s * a.y);
248}
249
250inline bool operator ==(const Point& a, const Point& b)
251{
252 return a.x == b.x && a.y == b.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
260/// Peform the dot product on two vectors.
261inline double Dot(const Point& a, const Point& b)
262{
263 return a.x * b.x + a.y * b.y;
264}
265
266/// Perform the cross product on two vectors. In 2D this produces a scalar.
267inline double Cross(const Point& a, const Point& b)
268{
269 return a.x * b.y - a.y * b.x;
270}
271
272/// Perform the cross product on a point and a scalar. In 2D this produces
273/// a point.
274inline Point Cross(const Point& a, double s)
275{
276 return Point(s * a.y, -s * a.x);
277}
278
279/// Perform the cross product on a scalar and a point. In 2D this produces
280/// a point.
281inline Point Cross(const double s, const Point& a)
282{
283 return Point(-s * a.y, s * a.x);
284}
285
286inline Point* Triangle::GetPoint(const int& index)
287{
288 return points_[index];
289}
290
291inline Triangle* Triangle::GetNeighbor(const int& index)
292{
293 return neighbors_[index];
294}
295
296inline bool Triangle::Contains(Point* p)
297{
298 return p == points_[0] || p == points_[1] || p == points_[2];
299}
300
301inline bool Triangle::Contains(const Edge& e)
302{
303 return Contains(p: e.p) && Contains(p: e.q);
304}
305
306inline bool Triangle::Contains(Point* p, Point* q)
307{
308 return Contains(p) && Contains(p: q);
309}
310
311inline bool Triangle::IsInterior()
312{
313 return interior_;
314}
315
316inline void Triangle::IsInterior(bool b)
317{
318 interior_ = b;
319}
320
321}
322
323#endif
324
325
326

source code of qtlocation/src/3rdparty/poly2tri/common/shapes.h