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

source code of qt3d/src/3rdparty/assimp/src/contrib/poly2tri/poly2tri/common/shapes.h