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