Branch data Line data Source code
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 : :
41 : : namespace p2t {
42 : :
43 : : struct Edge;
44 : :
45 : 117 : 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 : 117 : 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, -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 sqrt(x * x + y * y);
109 : : }
110 : :
111 : : /// Convert this point into a unit point. Returns the Length.
112 : : double Normalize()
113 : : {
114 : : const double len = Length();
115 : : x /= len;
116 : : y /= len;
117 : : return len;
118 : : }
119 : :
120 : : };
121 : :
122 : : std::ostream& operator<<(std::ostream&, const Point&);
123 : :
124 : : // Represents a simple polygon's edge
125 : : struct Edge {
126 : :
127 : : Point* p, *q;
128 : :
129 : : /// Constructor
130 : 91 : Edge(Point& p1, Point& p2) : p(&p1), q(&p2)
131 : : {
132 : 91 : if (p1.y > p2.y) {
133 : 26 : q = &p1;
134 : 26 : p = &p2;
135 : 91 : } else if (p1.y == p2.y) {
136 : 39 : if (p1.x > p2.x) {
137 : 13 : q = &p1;
138 : 13 : p = &p2;
139 : 39 : } else if (p1.x == p2.x) {
140 : : // Repeat points
141 : 0 : throw std::runtime_error("Edge::Edge: p1 == p2");
142 : : }
143 : 39 : }
144 : :
145 : 91 : q->edge_list.push_back(this);
146 : 91 : }
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"
152 : : class Triangle {
153 : : public:
154 : :
155 : : /// Constructor
156 : : Triangle(Point& a, Point& b, Point& c);
157 : :
158 : : /// Flags to determine if an edge is a Constrained edge
159 : : bool constrained_edge[3];
160 : : /// Flags to determine if an edge is a Delauney edge
161 : : bool delaunay_edge[3];
162 : :
163 : : Point* GetPoint(int index);
164 : : Point* PointCW(const Point& point);
165 : : Point* PointCCW(const Point& point);
166 : : Point* OppositePoint(Triangle& t, const Point& p);
167 : :
168 : : Triangle* GetNeighbor(int index);
169 : : void MarkNeighbor(Point* p1, Point* p2, Triangle* t);
170 : : void MarkNeighbor(Triangle& t);
171 : :
172 : : void MarkConstrainedEdge(int index);
173 : : void MarkConstrainedEdge(Edge& edge);
174 : : void MarkConstrainedEdge(Point* p, Point* q);
175 : :
176 : : int Index(const Point* p);
177 : : int EdgeIndex(const Point* p1, const Point* p2);
178 : :
179 : : Triangle* NeighborCW(const Point& point);
180 : : Triangle* NeighborCCW(const Point& point);
181 : : bool GetConstrainedEdgeCCW(const Point& p);
182 : : bool GetConstrainedEdgeCW(const Point& p);
183 : : void SetConstrainedEdgeCCW(const Point& p, bool ce);
184 : : void SetConstrainedEdgeCW(const Point& p, bool ce);
185 : : bool GetDelunayEdgeCCW(const Point& p);
186 : : bool GetDelunayEdgeCW(const Point& p);
187 : : void SetDelunayEdgeCCW(const Point& p, bool e);
188 : : void SetDelunayEdgeCW(const Point& p, bool e);
189 : :
190 : : bool Contains(const Point* p);
191 : : bool Contains(const Edge& e);
192 : : bool Contains(const Point* p, const Point* q);
193 : : void Legalize(Point& point);
194 : : void Legalize(Point& opoint, Point& npoint);
195 : : /**
196 : : * Clears all references to all other triangles and points
197 : : */
198 : : void Clear();
199 : : void ClearNeighbor(const Triangle *triangle);
200 : : void ClearNeighbors();
201 : : void ClearDelunayEdges();
202 : :
203 : : inline bool IsInterior();
204 : : inline void IsInterior(bool b);
205 : :
206 : : Triangle& NeighborAcross(const Point& opoint);
207 : :
208 : : void DebugPrint();
209 : :
210 : : bool CircumcicleContains(const Point&) const;
211 : :
212 : : private:
213 : :
214 : : bool IsCounterClockwise() const;
215 : :
216 : : /// Triangle points
217 : : Point* points_[3];
218 : : /// Neighbor list
219 : : Triangle* neighbors_[3];
220 : :
221 : : /// Has this triangle been marked as an interior triangle?
222 : : bool interior_;
223 : : };
224 : :
225 : 169 : inline bool cmp(const Point* a, const Point* b)
226 : : {
227 : 169 : if (a->y < b->y) {
228 : 78 : return true;
229 : 91 : } else if (a->y == b->y) {
230 : : // Make sure q is point with greater x value
231 : 39 : if (a->x < b->x) {
232 : 13 : return true;
233 : : }
234 : 26 : }
235 : 78 : return false;
236 : 169 : }
237 : :
238 : : /// Add 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 : : /// Subtract two points_ component-wise.
245 : : inline Point operator -(const Point& a, const Point& b)
246 : : {
247 : : return Point(a.x - b.x, a.y - b.y);
248 : : }
249 : :
250 : : /// Multiply point by scalar
251 : : inline Point operator *(double s, const Point& a)
252 : : {
253 : : return Point(s * a.x, s * a.y);
254 : : }
255 : :
256 : 0 : inline bool operator ==(const Point& a, const Point& b)
257 : : {
258 : 0 : return a.x == b.x && a.y == b.y;
259 : : }
260 : :
261 : : inline bool operator !=(const Point& a, const Point& b)
262 : : {
263 : : return !(a.x == b.x) && !(a.y == b.y);
264 : : }
265 : :
266 : : /// Peform the dot product on two vectors.
267 : : inline double Dot(const Point& a, const Point& b)
268 : : {
269 : : return a.x * b.x + a.y * b.y;
270 : : }
271 : :
272 : : /// Perform the cross product on two vectors. In 2D this produces a scalar.
273 : : inline double Cross(const Point& a, const Point& b)
274 : : {
275 : : return a.x * b.y - a.y * b.x;
276 : : }
277 : :
278 : : /// Perform the cross product on a point and a scalar. In 2D this produces
279 : : /// a point.
280 : : inline Point Cross(const Point& a, double s)
281 : : {
282 : : return Point(s * a.y, -s * a.x);
283 : : }
284 : :
285 : : /// Perform the cross product on a scalar and a point. In 2D this produces
286 : : /// a point.
287 : : inline Point Cross(double s, const Point& a)
288 : : {
289 : : return Point(-s * a.y, s * a.x);
290 : : }
291 : :
292 : 767 : inline Point* Triangle::GetPoint(int index)
293 : : {
294 : 767 : return points_[index];
295 : : }
296 : :
297 : 1196 : inline Triangle* Triangle::GetNeighbor(int index)
298 : : {
299 : 1196 : return neighbors_[index];
300 : : }
301 : :
302 : 741 : inline bool Triangle::Contains(const Point* p)
303 : : {
304 : 741 : return p == points_[0] || p == points_[1] || p == points_[2];
305 : : }
306 : :
307 : : inline bool Triangle::Contains(const Edge& e)
308 : : {
309 : : return Contains(e.p) && Contains(e.q);
310 : : }
311 : :
312 : 377 : inline bool Triangle::Contains(const Point* p, const Point* q)
313 : : {
314 : 377 : return Contains(p) && Contains(q);
315 : : }
316 : :
317 : 195 : inline bool Triangle::IsInterior()
318 : : {
319 : 195 : return interior_;
320 : : }
321 : :
322 : 91 : inline void Triangle::IsInterior(bool b)
323 : : {
324 : 91 : interior_ = b;
325 : 91 : }
326 : :
327 : : /// Is this set a valid delaunay triangulation?
328 : : bool IsDelaunay(const std::vector<p2t::Triangle*>&);
329 : :
330 : : }
331 : :
332 : : #endif
|
