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 | |
43 | namespace p2t { |
44 | |
45 | struct Edge; |
46 | |
47 | struct 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 |
125 | struct 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" |
154 | class Triangle { |
155 | public: |
156 | |
157 | /// Constructor |
158 | Triangle(Point& a, Point& b, Point& c); |
159 | |
160 | /// Flags to determine if an edge is a Constrained edge |
161 | bool constrained_edge[3]; |
162 | /// Flags to determine if an edge is a Delauney edge |
163 | bool delaunay_edge[3]; |
164 | |
165 | Point* GetPoint(int index); |
166 | Point* PointCW(const Point& point); |
167 | Point* PointCCW(const Point& point); |
168 | Point* OppositePoint(Triangle& t, const Point& p); |
169 | |
170 | Triangle* GetNeighbor(int index); |
171 | void MarkNeighbor(Point* p1, Point* p2, Triangle* t); |
172 | void MarkNeighbor(Triangle& t); |
173 | |
174 | void MarkConstrainedEdge(int index); |
175 | void MarkConstrainedEdge(Edge& edge); |
176 | void MarkConstrainedEdge(Point* p, Point* q); |
177 | |
178 | int Index(const Point* p); |
179 | int EdgeIndex(const Point* p1, const Point* p2); |
180 | |
181 | Triangle* NeighborCW(const Point& point); |
182 | Triangle* NeighborCCW(const Point& point); |
183 | bool GetConstrainedEdgeCCW(const Point& p); |
184 | bool GetConstrainedEdgeCW(const Point& p); |
185 | void SetConstrainedEdgeCCW(const Point& p, bool ce); |
186 | void SetConstrainedEdgeCW(const Point& p, bool ce); |
187 | bool GetDelunayEdgeCCW(const Point& p); |
188 | bool GetDelunayEdgeCW(const Point& p); |
189 | void SetDelunayEdgeCCW(const Point& p, bool e); |
190 | void SetDelunayEdgeCW(const Point& p, bool e); |
191 | |
192 | bool Contains(const Point* p); |
193 | bool Contains(const Edge& e); |
194 | bool Contains(const Point* p, const Point* q); |
195 | void Legalize(Point& point); |
196 | void Legalize(Point& opoint, Point& npoint); |
197 | /** |
198 | * Clears all references to all other triangles and points |
199 | */ |
200 | void Clear(); |
201 | void ClearNeighbor(const Triangle *triangle); |
202 | void ClearNeighbors(); |
203 | void ClearDelunayEdges(); |
204 | |
205 | inline bool IsInterior(); |
206 | inline void IsInterior(bool b); |
207 | |
208 | Triangle& NeighborAcross(const Point& opoint); |
209 | |
210 | void DebugPrint(); |
211 | |
212 | private: |
213 | |
214 | /// Triangle points |
215 | Point* points_[3]; |
216 | /// Neighbor list |
217 | Triangle* neighbors_[3]; |
218 | |
219 | /// Has this triangle been marked as an interior triangle? |
220 | bool interior_; |
221 | }; |
222 | |
223 | inline 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. |
237 | inline 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. |
243 | inline 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 |
249 | inline Point operator *(double s, const Point& a) |
250 | { |
251 | return Point(s * a.x, s * a.y); |
252 | } |
253 | |
254 | inline bool operator ==(const Point& a, const Point& b) |
255 | { |
256 | return a.x == b.x && a.y == b.y; |
257 | } |
258 | |
259 | inline 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. |
265 | inline 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. |
271 | inline 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. |
278 | inline 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. |
285 | inline Point Cross(double s, const Point& a) |
286 | { |
287 | return Point(-s * a.y, s * a.x); |
288 | } |
289 | |
290 | inline Point* Triangle::GetPoint(int index) |
291 | { |
292 | return points_[index]; |
293 | } |
294 | |
295 | inline Triangle* Triangle::GetNeighbor(int index) |
296 | { |
297 | return neighbors_[index]; |
298 | } |
299 | |
300 | inline bool Triangle::Contains(const Point* p) |
301 | { |
302 | return p == points_[0] || p == points_[1] || p == points_[2]; |
303 | } |
304 | |
305 | inline bool Triangle::Contains(const Edge& e) |
306 | { |
307 | return Contains(p: e.p) && Contains(p: e.q); |
308 | } |
309 | |
310 | inline bool Triangle::Contains(const Point* p, const Point* q) |
311 | { |
312 | return Contains(p) && Contains(p: q); |
313 | } |
314 | |
315 | inline bool Triangle::IsInterior() |
316 | { |
317 | return interior_; |
318 | } |
319 | |
320 | inline void Triangle::IsInterior(bool b) |
321 | { |
322 | interior_ = b; |
323 | } |
324 | |
325 | } |
326 | |
327 | #endif |